BTree: Esercizi

Di seguito sono riportati diversi esercizi svolti sui btree. Sono semplici applicazioni delle formule trattate nella parte di teoria . Prima di affrontarli il consiglio è quello di studiare bene la parte teorica.

Fattore di caricamento

Determinare il numero di pagine, sapendo che il fattore di caricamento è al $ 75 $% e il numero di tuple indicizzate è $ 21000 $ e l'ordine $ m = 230 $.

$$ f = \frac{m_{eff}}{m} \hspace{1cm} t_{eff} = m_{eff} - 1 $$ $$ N_{pag_{eff}} = \frac{T_{eff}}{t_{eff}}$$ $$ m_{eff} = \lfloor fm \rfloor = \lfloor 0.75 \cdot 230 \rfloor = 172 \rightarrow t_{eff} = m_{eff} - 1 = 171 $$ $$ N_{pag_{eff}} \cdot t_{eff} = T_{eff} \rightarrow 21000 \cdot 171 = 359100 $$

Determinare il numero di pagine, sapendo che il fattore di caricamento è all' $ 80 $% e il numero di tuple indicizzate è $ 20000 $, sapendo inoltre che: $$ \begin{cases} D_{PAG} = 4KB \\ D_{H} = 300byte \\ D_{P} = 5byte \\ D_{K} = 15byte \end{cases} $$

Per ricavarci l'ordine del btree (m) bisogna usare la disuguaglianza fondamentale: $$ D_{PAG} \geq D_{H} + mD_{P} + (m-1)(D_{P}+D_{K}) $$ svolgendo i dovuti calcoli, possiamo riscrivere la formula come: $$ m = \left\lfloor \frac{D_{PAG}-D_{H}+(D_{P}+D_{K})}{2D_{P}+D_{K}} \right\rfloor $$ dove $ m $ rapprsenta l'ordine del btree (il numero effettivo di puntatori su ogni nodo). Sostituendo i valori (e supponendo che essi siano tutti espressi in byte) avremo che: $$ m = \left\lfloor \frac{4096-300+20}{25} \right\rfloor = 152 $$ Ora conoscendo le relazioni che legano il numero di pagine al numero di tuple al fattore di caricamento:

$$ f = \frac{m_{eff}}{m} \hspace{1cm} t_{eff} = m_{eff} - 1 $$ $$ N_{pag_{eff}} = \frac{T_{eff}}{t_{eff}}$$ possiamo concludere che: $$ m_{eff} = \lfloor fm \rfloor = \lfloor 0.8 \cdot 152 \rfloor = 121 \rightarrow t_{eff} = m_{eff} - 1 = 120 $$ $$ N_{pag_{eff}} = \frac{20000}{120} = 166 $$

References

[1] - Jeffrey D. Ullman, Basi di dati e basi di conoscenza, Gruppo Editoriale Jackson S.p.a, Milano 1991, pagg. 430-481
[2] - R. Ramakrishnan - J. Gehrke, Sistemi di basi di dati, McGraw Hill, Milano 2004, pagg. 157-165, 175.