Nel seguente tutorial impareremo a conoscere la struttura dati del B Tree e prenderemo in considerazione la possibilità di visualizzarla.
mappa hash Java
Quindi iniziamo.
Cos'è un albero B?
IL B Albero è un tipo speciale di albero di ricerca a più vie , comunemente noto come M-way albero, che si equilibra. A causa della loro struttura equilibrata, questi alberi sono comunemente utilizzati per gestire e gestire immensi database e semplificare le ricerche. In un B Tree ogni nodo può avere al massimo n nodi figli. B Tree è un esempio di indicizzazione multilivello in un sistema di gestione di database (DBMS). I nodi foglia e interni avranno entrambi riferimenti a record. Il B Tree è noto come Balanced Stored Tree perché tutti i nodi foglia sono allo stesso livello.
Il seguente diagramma è un esempio di B Tree:
Figura 1. A B Albero con ordine 3
Comprendere le regole del B Tree
Le seguenti sono le proprietà importanti di un B Tree:
- Tutti i nodi foglia sono allo stesso livello.
- La struttura dati del B Tree è definita dal termine grado minimo 'd'. Il valore di 'd' dipende dalla dimensione del blocco del disco.
- Ogni nodo, esclusa la radice, deve essere costituito da almeno chiavi d-1. Il nodo radice può essere costituito da almeno 1 chiave.
- Tutti i nodi (incluso il nodo radice) possono essere costituiti al massimo da (2d-1) chiavi.
- Il numero di figli di un nodo è uguale a somma del numero di chiavi presenti in esso e .
- Tutte le chiavi di un nodo sono ordinate in ordine crescente. Il figlio tra due chiavi, k1 e k2, è costituito da tutte le chiavi comprese rispettivamente tra k1 e k2.
- A differenza dell'albero di ricerca binario, la struttura dei dati B Tree cresce e si restringe dalla radice. Mentre l'albero di ricerca binaria cresce verso il basso e si restringe verso il basso.
- Similmente ad altri alberi di ricerca binari autobilanciati, la complessità temporale della struttura dati dell'albero B per operazioni come ricerca, inserimento ed eliminazione è O(log?n) .
- L'Inserimento di un Nodo nell'Albero B avviene solo in corrispondenza del Nodo Foglia.
Consideriamo il seguente esempio di un B Tree di ordine minimo 5.
Figura 2. A B Albero di ordine 5
Nota: Il valore dell'ordine minimo è molto più di 5 in un pratico B Trees.
Nel diagramma sopra, possiamo osservare che tutti i nodi foglia sono allo stesso livello e tutti i nodi non foglia non hanno un sottoalbero vuoto e sono costituiti da chiavi una in meno rispetto al numero dei loro figli.
La formulazione dell'insieme delle regole del B Tree:
Ogni albero B dipende da un numero intero costante positivo noto come MINIMO , che viene utilizzato per determinare il numero di elementi di dati che possono essere contenuti in un singolo nodo.
Regola 1: La radice può avere solo un solo elemento dati (o anche nessun elemento dati se non ci sono figli); ogni altro nodo ha almeno MINIMO elementi di dati.
Regola 2: Il numero massimo di elementi di dati archiviati in un nodo è il doppio del valore di MINIMO .
Regola 3: Gli elementi dati di ciascun nodo del B Tree sono memorizzati in un array parzialmente riempito, ordinato dall'elemento dati più piccolo (all'indice 0 ) all'elemento dati più grande (nella posizione finale utilizzata dell'array).
Regola 4: Il numero totale di sottoalberi sotto un nodo non foglia è sempre uno in più rispetto al numero di elementi dati in quel nodo.
- sottoalbero 0,sottoalbero 1,...
Regola 5: Rispetto a qualsiasi nodo non foglia:
- Un elemento di dati nell'indice è maggiore di tutti gli elementi di dati nel numero della sottostruttura io del nodo, e
- Un elemento di dati nell'indice è inferiore a tutti gli elementi di dati nel numero della sottostruttura io+1 del nodo.
Regola 6: Ogni foglia in un B Tree ha la stessa profondità. Pertanto, garantisce che un B Tree prevenga il problema di un albero sbilanciato.
Operazioni su una struttura dati B Tree
Per garantire che nessuna delle proprietà di una struttura dati di B Tree venga violata durante le operazioni, il B Tree può essere suddiviso o unito. Di seguito sono riportate alcune operazioni che possiamo eseguire su un B Tree:
- Ricerca di un elemento di dati in B Tree
- Inserimento di un dato nel B Tree
- Cancellazione di un elemento di dati in B Tree
Operazione di ricerca su un B Tree
La ricerca di un elemento in un albero B è simile a quella in un albero di ricerca binario. Ma invece di prendere una decisione a doppio senso (Sinistra o Destra) come un albero di ricerca binario, un albero B prende una decisione a più vie in ciascun nodo dove m è il numero di figli del nodo.
Passaggi per cercare un elemento di dati in un B Tree:
Passo 1: La ricerca inizia dal nodo radice. Confronta l'elemento di ricerca, k, con la radice.
Passaggio 1.1: Se il nodo radice è costituito dall'elemento k, la ricerca sarà completa.
Passaggio 1.2: Se l'elemento k è inferiore al primo valore nella radice, ci sposteremo sul figlio più a sinistra e lo cercheremo ricorsivamente.
Passaggio 1.3.1: Se la radice ha solo due figli, ci sposteremo sul figlio più a destra e cercheremo ricorsivamente i nodi figli.
Passaggio 1.3.2: Se la radice ha più di due chiavi, cercheremo il resto.
Passo 2: Se l'elemento k non viene trovato dopo aver attraversato l'intero albero, allora l'elemento di ricerca non è presente nel B Tree.
Visualizziamo i passaggi precedenti con l'aiuto di un esempio. Supponiamo di voler cercare una chiave k=34 nel seguente B Tree:
Figura 3.1. Un dato albero B
clausole sql
- Innanzitutto, controlleremo se la chiave k = 34 è nel nodo radice. Poiché la chiave non è alla radice, passeremo ai suoi nodi figli. Possiamo anche osservare che il nodo radice ha due figli; pertanto, confronteremo il valore richiesto tra le due chiavi.
Figura 3.2. La chiave k non è presente alla radice - Ora che possiamo notare che la chiave k è maggiore del nodo radice, cioè 30, procederemo con il figlio destro della radice.
Figura 3.3. La chiave k> 30, spostati sul bambino destro - Confronteremo ora la chiave k con i valori presenti sul nodo, ovvero rispettivamente 40 e 50. Poiché la chiave k è inferiore alla chiave sinistra, ovvero 40, ci sposteremo sul figlio sinistro del nodo.
Figura 3.4. La chiave k<40, move to left child< li> - Poiché il valore nel figlio sinistro di 40 è 34, che è il valore richiesto, possiamo concludere che la chiave è stata trovata e l'operazione di ricerca è completata.
Figura 3.4. La chiave k = 34, il figlio sinistro di 40
Abbiamo confrontato la chiave con quattro valori diversi nell'esempio precedente finché non l'abbiamo trovata. Pertanto, la complessità temporale richiesta per l'operazione di ricerca in un B Tree è O(log?n) .
Operazione di inserimento su un B Tree
Durante l'inserimento di un dato in un B Tree dobbiamo prima verificare se quell'elemento è già presente nell'albero oppure no. Se l'elemento dati si trova all'interno del B Tree, l'operazione di inserimento non avviene. In caso contrario, invece, procederemo oltre con l'inserimento. Ci sono due scenari da considerare durante l'inserimento di un elemento nel nodo foglia:
Passaggi per inserire un elemento dati in un B Tree:
Passo 1: Inizieremo calcolando il numero massimo di chiavi nel nodo in base all'ordine del B Tree.
Passo 2: Se l'albero è vuoto, viene allocato un nodo radice e inseriremo la chiave che funge da nodo radice.
Passaggio 3: Cercheremo ora il nodo applicabile per l'inserimento.
Passaggio 4: Se il nodo è pieno:
Passaggio 4.1: Inseriremo gli elementi dati in ordine crescente.
Passaggio 4.2: Se gli elementi di dati sono maggiori del numero massimo di chiavi, divideremo l'intero nodo in corrispondenza della mediana.
Passaggio 4.3: Spingeremo il tasto mediano verso l'alto e divideremo i tasti sinistro e destro come figlio sinistro e destro.
Passaggio 5: Se il nodo non è pieno, lo inseriremo in ordine crescente.
Visualizziamo i passaggi precedenti con l'aiuto di un esempio. Supponiamo di dover creare un B Tree di ordine 4. I dati da inserire nel B Tree sono 5,3,21,11,1,16,8,13,4 e 9 .
- Poiché m è uguale a 3, il numero massimo di chiavi per un nodo = m-1 = 3-1 = 2 .
- Inizieremo inserendo 5 nell'albero vuoto.
Figura 4.1. Inserimento 5 - Ora ne inseriremo 3 nell'albero. Poiché 3 è inferiore a 5, inseriremo 3 a sinistra di 5 nello stesso nodo.
Figura 4.2. Inserimento 3 - Ora inseriremo 21 nell'albero e poiché 21 è maggiore di 5, verrà inserito a destra di 5 nello stesso nodo. Tuttavia, poiché sappiamo che il numero massimo di chiavi nel nodo è 2, una di queste chiavi verrà spostata su un nodo superiore per poterla dividere. Pertanto, 5, l'elemento dati centrale, si sposterà verso l'alto e 3 e 21 diventeranno rispettivamente i nodi sinistro e destro.
Figura 4.3. Inserimento 21 - Adesso è il momento di inserire il dato successivo, cioè 11, che è maggiore di 5 ma minore di 21. Pertanto, 11 verrà inserito come chiave a sinistra del nodo composto da 21 come chiave.
Figura 4.4. Inserimento 11 - Allo stesso modo, inseriremo il successivo elemento di dati 1 nell'albero e, come possiamo osservare, 1 è inferiore a 3; quindi verrà inserito come chiave a sinistra del nodo composto da 3 come chiave.
Figura 4.5. Inserimento 1 - Ora inseriremo l'elemento dati 16 nell'albero, che è maggiore di 11 ma minore di 21. Tuttavia, il numero di chiavi in quel nodo supera il numero massimo di chiavi. Pertanto, il nodo si dividerà, spostando la chiave centrale sulla fondamentale. Quindi, 16 verrà inserito a destra del 5, dividendo 11 e 21 in due nodi separati.
Figura 4.6. Inserimento 16 - L'elemento dati 8 verrà inserito come chiave a sinistra di 11.
Figura 4.7. Inserimento 8 - Inseriremo 13 nell'albero, che è inferiore a 16 e maggiore di 11. Pertanto, l'elemento di dati 13 dovrebbe essere inserito a destra del nodo composto da 8 e 11. Tuttavia, poiché il numero massimo di chiavi nell'albero può essere solo 2, si verificherà una divisione, spostando l'elemento dati centrale 11 nel nodo sopra e 8 e 13 in due nodi separati. Ora, il nodo precedente sarà composto da 5, 11 e 16, che superano nuovamente il numero massimo di chiavi. Pertanto, ci sarà un'altra divisione, rendendo l'elemento dati 11 il nodo radice con 5 e 16 come figli.
Figura 4.8. Inserimento 13 - Poiché l'elemento dati 4 è inferiore a 5 ma maggiore di 3, verrà inserito a destra del nodo composto da 1 e 3, che supererà nuovamente il conteggio massimo di chiavi in un nodo. Pertanto, si verificherà nuovamente uno spill, spostando il 3 sul nodo superiore accanto al 5.
Figura 4.9. Inserimento 4 - Infine il dato 9, che è maggiore di 8 ma minore di 11, verrà inserito a destra del nodo composto da 8 come chiave.
Figura 4.10. Inserimento 9
Nell'esempio sopra, abbiamo eseguito diversi confronti. Il primo valore è stato inserito direttamente nell'albero; dopodiché ogni valore doveva essere confrontato con i nodi disponibili in quell'albero. La complessità temporale dell'operazione di inserimento in un B Tree dipende dal numero di nodi e .
Operazione di eliminazione su un B Tree
L'eliminazione di un elemento dati su un B Tree contiene tre eventi principali:
strutture dati Java
- Cercando il nodo dove esiste la chiave da eliminare,
- Eliminazione della chiave e
- Bilanciare l'albero, se necessario.
Durante l'eliminazione di un elemento dall'albero, potrebbe verificarsi una condizione nota come Underflow. L'underflow si verifica quando un nodo è costituito da un numero di chiavi inferiore al minimo; dovrebbe reggere.
Di seguito sono riportati alcuni termini che è necessario comprendere prima di visualizzare l'operazione di cancellazione/rimozione:
Di seguito sono riportati tre casi importanti dell'operazione di eliminazione in un B Tree:
Caso 1: la cancellazione/rimozione della chiave risiede nel nodo Foglia - La fattispecie si suddivide ulteriormente in due casi diversi:
1. La cancellazione/rimozione della chiave non viola la proprietà del numero minimo di chiavi che un nodo dovrebbe contenere.
Visualizziamo questo caso utilizzando un esempio in cui elimineremo la chiave 32 dal seguente B Tree.
Figura 4.1: Eliminazione di una chiave del nodo foglia (32) dal B Tree
Come possiamo osservare, l'eliminazione di 32 da questo albero non viola la proprietà di cui sopra.
2. La cancellazione/rimozione della chiave viola la proprietà del numero minimo di chiavi che un nodo dovrebbe contenere. In questo caso, dobbiamo prendere in prestito una chiave dal suo nodo fratello più vicino nell'ordine da sinistra a destra.
Per prima cosa visiteremo il prossimo fratello di sinistra. Se il nodo fratello sinistro ha più di un numero minimo di chiavi, prenderà in prestito una chiave da questo nodo.
Altrimenti, controlleremo se prendere in prestito dal nodo fratello destro più vicino.
Visualizziamo ora questo caso con l'aiuto di un esempio in cui elimineremo 31 dal B Tree sopra. In questo caso prenderemo in prestito una chiave dal nodo fratello sinistro.
matrici nella programmazione c
Figura 4.2: Eliminazione di una chiave del nodo foglia (31) dal B Tree
Se entrambi i nodi fratelli prossimi consistono già di un numero minimo di chiavi, uniremo il nodo con il nodo fratello sinistro o con quello destro. Questo processo di fusione viene eseguito tramite il nodo genitore.
Visualizziamolo nuovamente eliminando la chiave 30 dal B Tree sopra.
Figura 4.3: Eliminazione di una chiave del nodo foglia (30) dal B Tree
Caso 2: l'eliminazione/rimozione della chiave si trova nel nodo non foglia - Questo caso è ulteriormente suddiviso in diversi casi:
1. Il nodo non foglia/interno, che viene rimosso, viene sostituito da un predecessore in ordine se il nodo figlio sinistro ha un numero di chiavi superiore al numero minimo.
Visualizziamo questo caso utilizzando un esempio in cui elimineremo la chiave 33 dal B Tree.
Figura 4.4: Eliminazione di una chiave del nodo foglia (33) dal B Tree
2. Il nodo non foglia/interno, che viene rimosso, viene sostituito da un successore in ordine se il nodo figlio destro ha un numero di chiavi superiore a quello minimo.
Se uno dei due figli ha un numero minimo di chiavi, uniremo i nodi figli Sinistro e Destro.
Visualizziamo questo caso eliminando la chiave 30 dal B Tree.
Figura 4.5: Eliminazione di una chiave del nodo foglia (30) dal B Tree
Dopo la fusione, se il nodo genitore ha meno del numero minimo di chiavi, è possibile cercare i fratelli, come in Caso 1 .
identificatori validi in Java
Caso 3: Nel caso seguente l'altezza dell'albero diminuisce. Se la chiave di destinazione si trova in un nodo Interno e la rimozione della chiave porta a un minor numero di chiavi nel nodo (che è inferiore al minimo richiesto), cercare il predecessore e il successore in ordine. Se entrambi i bambini hanno un numero minimo di chiavi, non è possibile il prestito. Questo porta a Caso 2(3) , ovvero unendo i nodi figli.
Cercheremo nuovamente il fratello per prendere in prestito una chiave. Tuttavia, se anche il fratello è costituito da un numero minimo di chiavi, uniremo il nodo con il fratello insieme al nodo genitore e disporremo i nodi figli secondo i requisiti (ordine crescente).
Visualizziamo questo caso con l'aiuto di un esempio in cui elimineremo l'elemento dati 10 dal B Tree fornito.
Figura 4.6: Eliminazione di una chiave del nodo foglia (10) dal B Tree
La complessità temporale negli esempi precedenti varia in base alla posizione da cui è necessario eliminare la chiave. Pertanto, la complessità temporale per l'operazione di eliminazione in un albero B è O(log?n) .
La conclusione
In questo tutorial, abbiamo imparato a conoscere il B Tree e visualizzato le sue diverse operazioni con diversi esempi. Abbiamo inoltre compreso alcune proprietà e regole fondamentali del B Tree.