Scopritori o inventori | Rudolf Bayer , Edward M. McCreight |
---|---|
Data di scoperta | 1972 |
Problema correlato | Struttura dati |
Struttura dati | Albero radicato |
Nel peggiore dei casi | , , |
---|---|
Media | , , |
Nel peggiore dei casi | |
---|---|
Media |
In informatica , un albero B (chiamato anche B-tree per analogia al termine inglese " B-tree ") è una struttura di dati in un albero bilanciato . Gli alberi B sono implementati principalmente nei meccanismi di gestione del database e del file system . Memorizzano i dati in una forma ordinata e consentono l'esecuzione di operazioni di inserimento ed eliminazione in tempo sempre logaritmico.
Il principio è di consentire ai nodi padre di avere più di due nodi figli: è una generalizzazione dell'albero di ricerca binario . Questo principio minimizza le dimensioni dell'albero e riduce il numero di operazioni di equilibratura. Inoltre, un albero B cresce dalla radice, a differenza di un albero binario di ricerca che cresce dalle foglie.
Il creatore degli alberi B, Rudolf Bayer , non ha spiegato il significato della "B". La spiegazione più frequente è che la B corrisponde al termine inglese " Balance " (in francese: "Balance"). Tuttavia, potrebbe anche derivare da "Bayer", dal nome del creatore, oppure da "Boeing", dal nome dell'azienda per la quale il creatore ha lavorato ( Boeing Scientific Research Labs ).
Gli alberi B furono inventati nel 1970 da Rudolf Bayer e Edward M. McCreight nei laboratori di ricerca della Boeing . L'obiettivo era quello di poter gestire le pagine indice dei file di dati, tenendo conto che il volume degli indici poteva essere così grande che solo una frazione delle pagine poteva essere caricata nella RAM. Il primo articolo che descrive il meccanismo degli alberi B è stato scritto a luglio e pubblicato inNovembre 1970.
Un albero etichettato è un albero (nel senso informatico del termine) tale che ogni nodo è associato a un'etichetta o una chiave (oppure più etichette o chiavi nel caso degli alberi B) presi da un dato insieme. Quindi formalmente un albero etichettato è una coppia formata da un grafo diretto, aciclico e connesso e da una funzione di etichettatura dell'albero che attribuisce a ciascun nodo un'etichetta o una chiave. Tra gli alberi etichettati, un albero B ha alcune proprietà specifiche aggiuntive.
Siano L e U due interi naturali diversi da zero tali che L ≤ U. In generale, definiamo un albero LU B come segue: ogni nodo, eccetto la radice, ha un minimo di L - 1 chiavi (chiamate anche elementi), un massimo di U - 1 chiavi e al massimo U bambini. Per ogni nodo interno - nodo che non è una foglia - il numero di figli è sempre uguale al numero di chiavi aumentate di uno. Se n è il numero di figli, allora parliamo di n- nodo. Un albero LU contiene solo n nodi con L ≤ n ≤ U. Spesso scegliamo la configurazione L = te U = 2 × t: t è chiamato il grado minimo dell'albero B.
Inoltre, la costruzione degli alberi B assicura che un albero B sia sempre bilanciato . Ogni chiave di un nodo interno è infatti un limite che distingue i sottoalberi di questo nodo. Ad esempio, se un nodo ha 3 figli - che costituiscono le rispettive radici di tre sottostrutture: sottoalbero sinistro, sottostruttura centrale e sottoalbero destro - allora ha 2 tasti indicati c 1 e c 2 che delimitano le chiavi di ciascun sottostruttura: la le chiavi del sottoalbero di sinistra saranno inferiori a c 1 ; le chiavi della sottostruttura centrale saranno comprese tra c 1 e c 2 ; le chiavi della sottostruttura destra saranno maggiori di c 2 .
Un albero B è implementato da un albero radicato. Un nodo è etichettato da:
Inoltre, un albero B soddisfa queste proprietà:
Il più delle volte, la configurazione è tale che U = 2 L. Parliamo quindi di un albero B di ordine L.
Un albero B di ordine t è quindi definito più semplicemente da un albero che soddisfa le seguenti proprietà:
Come vedremo più avanti, l'altezza di un albero B è logaritmica nel numero di elementi. Pertanto, le operazioni di ricerca, inserimento e cancellazione possono essere implementate in O (log n) nel caso peggiore, dove n è il numero di elementi.
La ricerca viene eseguita come in un albero di ricerca binario . Partendo dalla radice, si attraversa l'albero in modo ricorsivo; ad ogni nodo scegliamo il sottoalbero figlio le cui chiavi sono comprese tra gli stessi limiti di quelle della chiave ricercata mediante una ricerca dicotomica.
Pseudo-codice fonction Rechercher(noeud, x): i = 0 tant que i < noeud.taille et x > noeud.cles[i]: i += 1 si noeud.feuille: retourner x == noeud.cles[i] sinon: si x == noeud.cles[i]: retourner Vrai sinon si i == noeud.taille et x > noeud.cles[noeud.taille - 1]: retourner Rechercher(noeud.branches[noeud.taille], x) sinon: retourner Rechercher(noeud.branches[i], x)In molte implementazioni, l'uguaglianza ( ) tra gli elementi è sostituita da equivalence ( ). Occorre quindi prestare attenzione a utilizzare tipi di dati in cui due elementi equivalenti sono considerati uguali.
L'inserimento richiede innanzitutto di trovare il nodo in cui inserire la nuova chiave e di inserirlo. Il resto avviene in modo ricorsivo, a seconda che un nodo abbia o meno troppe chiavi: se ha un numero accettabile di chiavi, non si fa nulla; altrimenti lo trasformiamo in due nodi, ognuno avente un numero minimo di chiavi, quindi facciamo “salire” il tasto centrale che viene poi inserito nel nodo genitore. Quest'ultimo può improvvisamente finire con un numero eccessivo di thread; il processo continua in questo modo fino a quando non viene raggiunta la radice. Se questa deve essere divisa, si fa “salire” la chiave di mezzo in una nuova radice, che genererà come nodi figli i due nodi creati a partire dalla vecchia radice, come nel passaggio precedente. Affinché l'operazione sia possibile, notiamo che U ≥ 2 L; altrimenti i nuovi nodi non avranno abbastanza chiavi.
Una variante consiste nell'esplodere preventivamente ogni nodo “pieno” (avente il numero massimo di chiavi) incontrato durante la ricerca del nodo dove avverrà l'inserimento. In questo modo evitiamo di risalire l'albero, poiché ci assicuriamo che il padre di un nodo da dividere in due possa ospitare una chiave aggiuntiva. La controparte è un leggero aumento dell'altezza media dell'albero.
Pseudo-codice fonction Inserer(x,c) n = nombre de clefs du noeud x Soit i tel que x.clef[i] > c ou i >= n Si x est une feuille : Inserer c dans x.clef a la i-ieme place Sinon: Si x.fils[i] est complet: Scinder x.fils[i] Si c > x.clef[i]: i := i+1 FinSi FinSi Inserer(x.fils[i],c) FinSi FinFonctionDobbiamo prima trovare la chiave per eliminarla ed eliminarla dal nodo che la contiene.
In particolare dopo la rimozione, l'albero può essere riequilibrato. Questa operazione consiste nel distribuire equamente i valori nei vari nodi dell'albero e nel ripristinare le proprietà minime di riempimento dei nodi.
Il riequilibrio inizia a livello delle foglie e procede verso la radice, fino a quest'ultima. La ridistribuzione implica il trasferimento di un elemento da un nodo adiacente che ha valori sufficienti al nodo che ne è privo. Questa ridistribuzione è chiamata rotazione . Se nessun vicino può fornire un valore senza essere esso stesso al di sotto del limite, il nodo difettoso deve essere unito a un vicino. Questa operazione provoca la perdita di un separatore nel nodo genitore, questo potrebbe quindi essere in deficit e necessita di essere bilanciato. La fusione e la ridistribuzione si diffonde alla radice, unico elemento dove viene tollerata la carenza di valori.
Un semplice algoritmo di bilanciamento è costituito da:
La rotazione sinistra di una tacca tra due nodi vicini viene eseguita in
Questo tipo di operazione può essere utilizzato anche per comprimere l'albero: un albero destinato alla sola lettura può essere svuotato di un massimo di slot di memoria inutilizzati riempiendo il più possibile un minimo di nodi.
Sia il numero di chiavi contenute nell'albero B. L'altezza dell'albero soddisfa la disuguaglianza:
DimostrazioneLa radice dell'albero contiene almeno 1 nodo, quindi ha almeno 2 figli. I nodi di profondità almeno 1 contengono almeno chiavi L-1 e figli L. Per induzione, infatti , mostriamo che il livello dell'albero, cioè l'insieme dei nodi di profondità , contiene almeno nodi e quindi almeno chiavi. Pertanto, il numero totale di chiavi nell'albero controlla:
Quindi e .
L'albero B + Albero (en) differisce leggermente dall'albero B, in quanto tutti i dati sono memorizzati solo in foglia, e questi sono collegati tra loro.
Esistono anche altre varianti, come l' albero B * (en) .