11 : Archivi e file Vers . 2.0 – Dicembre 2020
Ricerca applicata ad archivi sequenziali memorizzati su supporti ad accesso diretto In questo caso possono verificarsi le seguenti situazioni : a ) si conosce l ’ indirizzo del record da ricercare : allora il problema non sussiste perché mediante un accesso ci si posiziona direttamente sul record cercato ; b ) NON si conosce l ’ indirizzo del record da ricercare e l ’ archivio è DISORDINATO : allora il problema viene affrontato come nel caso dell ’ accesso sequenziale ; c ) NON si conosce l ’ indirizzo del record da ricercare e l ’ archivio è ORDINATO : allora il problema viene risolto con tecniche di ricerca molto efficienti quali ad esempio la ricerca binaria . In questo caso il numero medio ( ma anche riferito al caso pessimo ) di accessi diveniva : � log ( N ) in caso di successo
� log ( N ) in caso di insuccesso dove N è il numero di record presenti nell ’ archivio .
Struttura
L ’ ORGANIZZAZIONE SEQUENZIALE CON INDICE
Gli archivi sequenziali registrati su supporti fisici che permettono l ’ accesso diretto ( come i dischi ), possono essere gestiti anche con una variante dell ’ organizzazione sequenziale , caratterizzata dalla possibilità di velocizzare la ricerca di un record utilizzando uno o più indici .
Nell ’ organizzazione sequenziale ad indici ( o indexed sequential ) si possono distinguere due elementi fondamentali : - un archivio primario caratterizzato da record consecutivi che possono anche essere ordinati ; - un archivio secondario o indice ordinato ( o dizionario ) o una gerarchia di indici i cui elementi sono composti generalmente da due campi : � un campo chiave contenente la chiave del record ; � un campo puntatore contenente la posizione del record all ’ interno dell ’ archivio primario .
L ’ indice consente quindi di stabilire una corrispondenza tra ogni chiave e la posizione del relativo record memorizzato nell ’ archivio . L ’ indice ovviamente deve contenere tutte le chiavi presenti nell ’ archivio primario .
Chiave Puntatore Chiave Parte informativa A 5 B 6 D 2 F 1 E 3 C 4
Archivio secondario o Indice ordinato ( o dizionario )
1 2 3 4 5 6
F D E C A B
Informazioni su F Informazioni su D Informazioni su E Informazioni su C Informazioni su A Informazioni su E Archivio primario
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 20