Corsi -> Basi di Dati e Sistemi Informativi I (Canale1) -> Esercizi sulla organizzazione fisica
 
 

Esercizi sulla organizzazione fisica dei dati  (Modifiche in grassetto)

1.
Supponiamo di avere un file di 250.000 record. Ogni record occupa 300 byte, di cui 75 per il campo chiave. Ogni blocco contiene 1024 byte. Un puntatore a blocco occupa 4 byte.
a) Se usiamo una organizzazione hash con 1200 bucket, quanti blocchi occorrono per la bucket directory ?
b) Quanti blocchi occorrono per i bucket, assumendo una distribuzione uniforme dei record nei bucket?
c) Assumendo ancora che tutti i bucket contengano il numero medio di record, qual è il numero medio di accessi a blocco per ricercare un record che sia presente nel file?
d) Quanti bucket dovremmo creare per avere invece un numero medio di accessi a blocco inferiore o al massimo uguale a 10, assumendo comunque una distribuzione uniforme dei record nei bucket?

2.
Supponiamo di avere un file di 150.000 records. Ogni record occupa 250 byte, di cui 50 per il campo chiave. Ogni blocco contiene 1024 byte. Un puntatore a blocco occupa 4 byte.
a) Se usiamo un indice ISAM sparso, e assumiamo che i record non siano puntati e che il fattore di utilizzo dei blocchi del file sia 0,7 (cioè i blocchi non sono completamente pieni, ma pieni al 70%), quanti blocchi dobbiamo utilizzare per líindice ?
b) Se usiamo un indice ISAM sparso, e assumiamo che i record siano puntati e che i blocchi del file siano pieni, quanti blocchi dobbiamo utilizzare per líindice ?
c) Se utilizziamo la ricerca binaria, quale è il numero massimo di accessi a blocco per ricercare un record presente nel file nei casi a) e b), supponendo nel caso b) di non avere liste di overflow ?

3.
Supponiamo di avere un file di 170.000 record. Ogni record occupa 200 byte, di cui 20 per il campo chiave. Ogni blocco contiene 1024 byte. Un puntatore a blocco occupa 4 byte.
a) Se usiamo un B-tree e assumiamo che sia i blocchi indice che i blocchi del file sono pieni al minimo, quanti blocchi vengono usati per il livello foglia (main file) e quanti per líindice, considerando tutti i livelli non foglia ?
b) Se il B-tree è usato invece come indice secondario, con i blocchi indice dei livelli intermedi pieni al massimo e i blocchi del livello foglia (indice denso) pieni al 60%, quanti blocchi vengono usati per i blocchi indice, compreso il livello foglia (indice denso), sapendo che per líindice secondario il numero di chiavi NK è 2500, che occupano ognuna LK = 10 byte e che un puntatore a record PR occupa 3 byte?