10 Febbraio 2025 A - Esercizio 3

[AglaiaNorza]

Supponiamo di avere un file di 22.500.000 record. Ogni record occupa 360 byte, di cui 20 per il campo chiave.

Ogni blocco contiene 2048 byte. Un puntatore a blocco occupa 4 byte.

Usiamo una organizzazione B+-Tree (a differenza del B-Tree classico, ogni blocco del file principale ha un puntatore al prossimo blocco).

I blocchi del file principale sono pieni al massimo, mentre i blocchi indice sono pieni al minimo.

Calcolare:

• il numero di blocchi del file principale

• il numero di blocchi complessivo del file indice

• il numero di accessi necessari per ricercare un record

[FeddyLix17]

• numero di blocchi del file principale

Togliendo i 4 byte del puntatore al prossimo blocco, un singolo blocco del file principale potrà contenere

$$\Large Numero\ di\ record\ per\ blocco = \left\lfloor\frac{2044}{360}\right\rfloor = \left\lfloor5,67\right\rfloor = 5\ record$$

dunque per il file principale saranno necessari

$$\Large Blocchi\ file\ principale = \left\lceil\frac{22.500.000}{5}\right\rceil = \left\lceil4.500.000\right\rceil = 4.500.000\ blocchi$$

---

• numero di blocchi complessivo del file indice

In un $\Large B^+-Tree$, il file indice è organizzato a livelli (come un albero), dove

• il livello 0 conterrà i blocchi "foglie", le quali punteranno ai blocchi del file principale

anche ogni blocco foglia (cosi come i blocchi del file indice), conterrano un puntatore al blocco successivo

• mentre i blocchi degli altri livelli 1, 2, 3 ecc. punteranno a quelli dei livelli sottostanti

ogni entry di un blocco, nel formato chiave - puntatore, occuperà 24 byte

I blocchi (a possibile eccezione della radice) saranno riempiti al minimo, ovvero $\Large \left\lceil\frac{n}{2}\right\rceil$, con $\Large n$ numero massimo di entry per blocco, da cui

$$\Large Entry\ massime\ per\ blocco = \left\lfloor\frac{2044}{24}\right\rfloor = \left\lfloor85,16\right\rfloor = 85\ entry$$

$$\Large Entry\ minime\ per\ blocco = \left\lceil\frac{85}{2}\right\rceil = \left\lceil42,5\right\rceil = 43\ entry$$

al quale bisognerà aggiungerci un puntatore finale.

$$\Large Blocchi\ livello\ 0 = \left\lceil\frac{4.500.000}{44}\right\rceil = 102.273\ blocchi$$

$$\Large \left\lfloor\frac{2044}{24}\right\rfloor = \left\lfloor\frac{2048}{24}\right\rfloor = 85$$

$$\Large Blocchi\ livello\ 1 = \left\lceil\frac{Blocchi\ livello\ 0}{44}\right\rceil = \left\lceil\frac{102..273}{44}\right\rceil = 2.325\ blocchi$$

$$\Large Blocchi\ livello\ 2 = \left\lceil\frac{Blocchi\ livello\ 1}{43}\right\rceil = \left\lceil\frac{2.325}{44}\right\rceil = 53\ blocchi$$

Il livello 3 conterrà 2 blocchi ed infine ci sarà l'ultimo blocco contenuto al livello 4 (radice)

$$\Large Numero\ Blocchi\ File\ Indice = 102.273 + 2.325 + 53 + 2 + 1 = 104.654\ blocchi$$

---

• numero di accessi necessari per ricercare un record

Scorrendo (dalla radice) ogni livello del file indice, ed infine con l'ultimo accesso al file principale, avremo un totale di 6 accessi necessari

[M1SC0]

Nel punto b, quando fai 57/43 viene per il livello 3, il risultato è 1,32 che si approssima a 2, quindi dovrebbe esserci un livello aggiuntivo.

[Alessandro700]

concordo pure io

[M1SC0]

[Alessandro700]

il numero di record per blocco del file indice = 42,5 va approssimato a 43, perche si sta usando un btree minimo
con btree minimo vanno presi parte superiore , record del file principale, indice e ovviamente i blocchi del principale e indice.
per il resto mi torna tutto.

[Alexangels05]

si hai ragione pero, poi devi aggiungere 1 per trovare m e fare 43+1 = 44 e poi quindi dividere tutto per 44 invece che 43, giusto?

[Alessandro700]

oddio si, scusa ero veramente stanco quella sera

[Alessandro700]

RBI=44 , 43+1 mi sono dimenticato di aggiungere 1.

[Alexangels05]

[cek753]