Questi esempi, sono svolti, in casi disomogenei. Non basta saper applicare le formule, bisogna analizzare livello per livello il numero di tuple, di pagine ecc... Il metodo più semplice consiste nel costruirsi una tabella dove riportare per ogni livello i dati ricavati.

---

Stimare il numero di nodi e di tuple indicizzate sapendo che: $$ \begin{cases} D_{PAG} = 4KB \\ D_{H} = 32byte \\ D_{P} = 2byte \\ D_{K} = 6byte \end{cases} $$ e che:

• \( \diamond \) Il btree è composto da 3 livelli.
• \( \clubsuit \) Il numero di chiavi indicizzate nella radice è pari a 10 volte il numero minimo di chiavi presenti in una radice non vuota.
• \( \heartsuit\) I nodi al secondo livello sono pieni all'80%.
• \( \bullet \)I nodi foglia hanno tutti riempimento minimo.

Per risolvere questa tipologia di esercizio, bisogna dapprima saper adoperare tutte le formule sui btree(che puoi trovare nel formulario in cui viene spiegato il significato dettagliatamente), solo dopo aver chiare le formule e l'uso nei casi omogenei, si può passare al caso disomogeneo.

Iniziamo a costruirci la tabella che poi andremo a riempire:

La prima colonna \(t_{liv_i}\), rappresenta il numero di tuple(o chiavi dal momento che la corrispondenza è biunivoca), su ogni livello (ad esempio nel caso di una radice riempita al minimo, avremo 1 sola tupla al primo livello). La seconda colonna \( m_{liv_i}\) riporta il numero di puntatori su ogni livello; infine nell'ultima colonna riportiamo il numero di pagine su ogni livello \(Npag_{liv_i}\). Osservate che i valori sulle righe corrispondono al livello \( i\) e perciò non vengono cumulate. Questo calcolo verra riportato a fondo tabella, nella riga indicata con \( \Sigma \).

Iniziamo dal primo livello (il più semplice). Per la condizione (\( \clubsuit \)) sappiamo che in un btree il numero minimo di chiavi in una radice non vuota è 1 , di conseguenza avremo, sempre per la \( \clubsuit \) che \(t_{liv_1} = 10\), quindi il numero di puntatori sara \(11\) e naturalmente avremo solo una pagina cioè la radice stessa. Riportiamo i valori nella prima riga:

Per calcolare i valori sul 2 livello, la condizione (\( \heartsuit\)) ci impone di far uso dei dati empirici indicati sopra. Dobbiamo calcolarci il numero di tuple generico e da questo i valori effettivi con fattore all'80%. Ricordando la relazione fondamentale avremo che: $$ m = \left\lfloor \frac{4096-32+8}{10} \right\rfloor = 407 $$ $$ t = 406 $$ $$ m_{eff} = fm = 0.8\cdot407 = 325 $$ $$ t_{eff} = m_{eff}-1 = 325-1 = 324 $$ Ora possiamo calcolare il secondo livello: infatti se abbiamo \(11\) puntatori al primo livello, avremo \(11\) pagine al secondo livello ed \( 11\cdot t_{eff} \) tuple al secondo livello. Riportiamo i valori in tabella

Per il terzo livello il discorso è simile, solo che ora vale la condizione (\( \bullet \)). In questo caso bisogna ricorrere alle formule nel caso di riempimento minimo oppure procedere come prima ma con un fattore di caricamento al 50%. Procediamo secondo le formule: il numero di tuple minimo è dato da: \( \left\lfloor \frac{m}{2} \right\rfloor - 1 = 204-1 = 203 \) Per calcolare il numero di tuple al terzo livello bisogna moltiplicare il valore ottenuto per il numero di puntatori al livello precedente (visto che essi danno la numerosita delle pagine). Possiamo perciò concludere popolando l'ultima riga e sommando: