Un Btree o B-albero è la generalizzazione di un albero binario di ricerca, in cui il numero di figli (puntatori) di ogni nodo è \( >2 \), di conseguenza la cardinalità dei nodi non è necessariamente una potenza di \( 2 \), ma dipende in linea di principio dal numero di puntatori che ogni nodo contiene.

In questo articolo mi occuperò essenzialmente dell'analisi delle caratteristiche dei btree, ovvero delle relazioni matematiche che legano i parametri caratterizzanti di un btree (cardinalità, ordine, altezza, puntatori ecc..); la trattazione sarà da background per i prossimi articoli in cui verranno risolti diversi esercizi di calcolo di indici sui database.

Iniziamo dal caso più semplice. Conosciamo il numero di puntatori in ogni nodo \( m \) (nella figura sono le parti in nero dei nodi) e l'altezza del btree \( h \) ovvero il numero di livelli(in basso ne sono raffigurati 4, ma in generale sono \( h \) ). Quanti nodi possiede l'albero? Facciamo un'analisi euristica, e cerchiamo di ricavarne una qualche relazione matematica.

Nel primo livello abbiamo 1 solo nodo (la radice); siccome essa ha \( m \) puntatori essa può puntare ad \( m \) nodi figli quindi al secondo livello abbiamo \( m \) nodi. Al terzo livello bisogna iterare il processo. Ogni nodo ha sempre \( m \) puntatori (abbiamo supposto che l'albero sia omogeneo, il numero di puntatori in ogni nodo è sempre lo stesso), bisogna quindi moltiplicare il numero di nodi al secondo livello \(m \) per il numero di puntatori in ogni nodo \( m \) otteniamo \( m^2 \) nodi al terzo livello:

All'i-esimo livello vale la relazione ricorsiva:

$${\large |nodi(liv_i)| = |nodi(liv_{i-1})| \cdot m }$$

Riportando in sequenza i nodi calcolati nei vari livelli possiamo cumulare i valori ottenendo la relazione:

$${\large (\heartsuit) \hspace{1cm} |nodi| = 1 + m + m^2 + m^3 + \ldots + m^{h-1}}$$

La somma si arresta alla potenza \( h-1 \) in quanto la relazione deve essere valida nel caso \( h = 1 \) ovvero al livello 1 dove si ottiene \( m^{1-1} = 1 \).

Diamo ora uno sguardo alla relazione \( (\heartsuit) \). Si tratta di una serie geometrica di ragione \( m \) arrestata alla potenza \( h-1 \)

Dalla teoria si dimostra facilmente per induzione che una serie geometrica si può esprimere mediante la seguente formula chiusa (puoi approfondire la dimostrazione in un mio articolo al seguente link) $$ {\large 1 + x + x^2 + x^3 + \ldots + x^{n} = \sum_{i=0}^{n}x^i = \frac{x^{n+1}-1}{x-1} } $$

Sostituendo nella formula, \( m \) al posto di \( x \) ed \( h-1 \) al posto di \( n\) si ottiene la relazione importante sul numero di nodi in funzione dell'altezza del btree: $$ {\large 1 + m + m^2 + m^3 + \ldots + m^{h-1} = \sum_{i=0}^{h-1}m^i = \frac{m^{h}-1}{m-1} = \frac{T}{t} } $$

Vediamo ora la formula, anzi le formule, in azione su di un paio di esempi: albero-binario ed albero-ternario

---

Nel caso di un albero binario \( m = 2 \) (ogni nodo possiede due puntatori a due figli per ogno livello) di conseguenza conoscendo l'altezza \( h \), possiamo subito calcolarci il numero di nodi usando la formula $$ { |nodi|_{max} = \frac{m^{h}-1}{m-1} = \large 2^{h}-1 } $$ nella figura ad esempio abbiamo \( h = 4 \) livelli; di conseguenza (prova a contare) ci sono \({\large 2^{4}-1 = 15 }\) nodi in totale.

Usando la formula inversa possiamo provare l'altezza: \({\large h = \log_2(15 + 1) = 4 }\)