logo

TechCodeview

Introduzione del B-Tree

Le limitazioni dei tradizionali alberi di ricerca binari possono essere frustranti. Scopri B-Tree, la struttura dati multitalento in grado di gestire enormi quantità di dati con facilità. Quando si tratta di archiviare e cercare grandi quantità di dati, i tradizionali alberi di ricerca binari possono diventare poco pratici a causa delle loro scarse prestazioni e dell'elevato utilizzo della memoria. I B-Tree, noti anche come B-Tree o Balanced Tree, sono un tipo di albero autobilanciante appositamente progettato per superare queste limitazioni.

A differenza dei tradizionali alberi di ricerca binari, i B-Tree sono caratterizzati dall’elevato numero di chiavi che possono memorizzare in un singolo nodo, motivo per cui sono conosciuti anche come grandi alberi di chiavi. Ogni nodo in un B-Tree può contenere più chiavi, il che consente all'albero di avere un fattore di ramificazione maggiore e quindi un'altezza inferiore. Questa altezza ridotta comporta un minor numero di I/O del disco, il che si traduce in operazioni di ricerca e inserimento più veloci. I B-Tree sono particolarmente adatti per i sistemi di archiviazione con accesso lento e voluminoso ai dati come dischi rigidi, memoria flash e CD-ROM.



B-Trees mantiene l'equilibrio garantendo che ciascun nodo abbia un numero minimo di chiavi, quindi l'albero è sempre bilanciato. Questo equilibrio garantisce che la complessità temporale per operazioni quali inserimento, cancellazione e ricerca sia sempre O(log n), indipendentemente dalla forma iniziale dell'albero.

Complessità temporale del B-Tree:

Signor No.AlgoritmoComplessità temporale
1.RicercaO(log n)
2.InserireO(log n)
3.EliminareO(log n)


Nota: n è il numero totale di elementi nell'albero B

versione java linux

Proprietà del B-Tree:

  • Tutte le foglie sono allo stesso livello.
  • B-Tree è definito dal termine grado minimo’ T ‘. Il valore di ' T ‘ dipende dalla dimensione del blocco del disco.
  • Ogni nodo tranne la radice deve contenere almeno chiavi t-1. La radice può contenere un minimo di 1 chiave.
  • Tutti i nodi (incluso root) possono contenere al massimo ( 2*t-1 ) chiavi.
  • Il numero di figli di un nodo è uguale al numero di chiavi in ​​esso contenute più 1 .
  • Tutte le chiavi di un nodo sono ordinate in ordine crescente. Il bambino tra due chiavi k1 E k2 contiene tutte le chiavi nell'intervallo da k1 E k2 .
  • B-Tree cresce e si restringe dalla radice, a differenza dell'albero di ricerca binaria. Gli alberi di ricerca binaria crescono verso il basso e si restringono anche dal basso.
  • Come altri alberi di ricerca binari bilanciati, la complessità temporale per la ricerca, l'inserimento e l'eliminazione è O(log n).
  • L'inserimento di un Nodo nel B-Tree avviene solo in corrispondenza del Nodo Foglia.


Di seguito è riportato un esempio di B-Tree di ordine minimo 5
Nota: che nei B-Tree pratici il valore dell'ordine minimo è molto più di 5.




Possiamo vedere nel diagramma sopra che tutti i nodi foglia sono allo stesso livello e tutti i nodi non foglie non hanno un sottoalbero vuoto e hanno una chiave in meno rispetto al numero dei loro figli.

Fatti interessanti sui B-Tree:

  • L'altezza minima del B-Tree che può esistere con n numero di nodi e m è il numero massimo di figli che un nodo può avere è: h_{min} =lceillog_m (n + 1) ceil - 1
  • L'altezza massima del B-Tree che può esistere con n numero di nodi e t è il numero minimo di figli che un nodo non radice può avere è: h_{max} =lpianolog_tfrac {n + 1}{2} pianoE t = lceilfrac {m}{2} ceil

Attraversamento nel B-Tree:

L'attraversamento è anche simile all'attraversamento inordine dell'albero binario. Iniziamo dal figlio più a sinistra, stampiamo ricorsivamente il figlio più a sinistra, quindi ripetiamo lo stesso processo per i figli e le chiavi rimanenti. Alla fine, stampa ricorsivamente il figlio più a destra.



Operazione di ricerca in B-Tree:

La ricerca è simile alla ricerca nell'albero di ricerca binaria. Supponiamo che la chiave da cercare sia k.

  • Inizia dalla radice e attraversa ricorsivamente verso il basso.
  • Per ogni nodo non foglia visitato,
    • Se il nodo ha la chiave, restituiamo semplicemente il nodo.
    • Altrimenti, si ricorre al figlio appropriato (il figlio che si trova appena prima della prima chiave maggiore) del nodo.
  • Se raggiungiamo un nodo foglia e non troviamo k nel nodo foglia, restituiamo NULL.

La ricerca in un B-Tree è simile alla ricerca in un albero binario. L'algoritmo è simile e funziona con la ricorsione. Ad ogni livello, la ricerca è ottimizzata come se il valore della chiave non fosse presente nell'intervallo del genitore, allora la chiave fosse presente in un altro ramo. Poiché questi valori limitano la ricerca, sono noti anche come valori limite o valori di separazione. Se raggiungiamo un nodo foglia e non troviamo la chiave desiderata, verrà visualizzato NULL.

Algoritmo per la ricerca di un elemento in un B-Tree: -

C++

struct> Node {> >int> n;> >int> key[MAX_KEYS];> >Node* child[MAX_CHILDREN];> >bool> leaf;> };> Node* BtreeSearch(Node* x,>int> k) {> >int> i = 0;> >while> (i n && k>x->tasto[i]) {> >i++;> >}> >if> (i n && k == x->chiave[i]) {> >return> x;> >}> >if> (x->foglia) {> >return> nullptr;> >}> >return> BtreeSearch(x->bambino[i], k);> }> 
>
>

C

BtreeSearch(x, k)> >i = 1> > >// n[x] means number of keys in x node> >while> i ? n[x] and k ? keyi[x]> >do> i = i + 1> >if> i n[x] and k = keyi[x]> >then>return> (x, i)> >if> leaf [x]> >then>return> NIL> >else> >return> BtreeSearch(ci[x], k)> 
>
>

Giava

class> Node {> >int> n;> >int>[] key =>new> int>[MAX_KEYS];> >Node[] child =>new> Node[MAX_CHILDREN];> >boolean> leaf;> }> Node BtreeSearch(Node x,>int> k) {> >int> i =>0>;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }>
>
>

Python3

class> Node:> >def> __init__(>self>):> >self>.n>=> 0> >self>.key>=> [>0>]>*> MAX_KEYS> >self>.child>=> [>None>]>*> MAX_CHILDREN> >self>.leaf>=> True> def> BtreeSearch(x, k):> >i>=> 0> >while> i and k>= x.key[i]: i += 1 se i e k == x.key[i]: return x if x.leaf: return None return BtreeSearch(x.child[i], k)>
>
>

C#

class> Node {> >public> int> n;> >public> int>[] key =>new> int>[MAX_KEYS];> >public> Node[] child =>new> Node[MAX_CHILDREN];> >public> bool> leaf;> }> Node BtreeSearch(Node x,>int> k) {> >int> i = 0;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }>
>
>

Javascript

// Define a Node class with properties n, key, child, and leaf> class Node {> >constructor() {> >this>.n = 0;> >this>.key =>new> Array(MAX_KEYS);> >this>.child =>new> Array(MAX_CHILDREN);> >this>.leaf =>false>;> >}> }> // Define a function BtreeSearch that takes in a Node object x and an integer k> function> BtreeSearch(x, k) {> >let i = 0;> >while> (i = x.key[i]) {> >i++;> >}> >if> (i return x; } if (x.leaf) { return null; } return BtreeSearch(x.child[i], k); }>
>
>

Esempi:

la data viene convertita in stringa

Ingresso: Cerca 120 nel B-Tree indicato.



Soluzione:

aws redshift



In questo esempio, possiamo vedere che la nostra ricerca è stata ridotta limitando semplicemente le possibilità in cui potesse essere presente la chiave contenente il valore. Allo stesso modo se nell’esempio sopra dobbiamo cercare 180, allora il controllo si fermerà al passo 2 perché il programma troverà che la chiave 180 è presente all’interno del nodo corrente. E allo stesso modo, se deve cercare 90, allora come 90 <100 andrà automaticamente al sottoalbero sinistro, e quindi il flusso di controllo andrà in modo simile come mostrato nell'esempio sopra.

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++

// C++ implementation of search() and traverse() methods> #include> using> namespace> std;> // A BTree node> class> BTreeNode {> >int>* keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode** C;>// An array of child pointers> >int> n;>// Current number of keys> >bool> leaf;>// Is true when node is leaf. Otherwise false> public>:> >BTreeNode(>int> _t,>bool> _leaf);>// Constructor> >// A function to traverse all nodes in a subtree rooted> >// with this node> >void> traverse();> >// A function to search a key in the subtree rooted with> >// this node.> >BTreeNode*> >search(>int> k);>// returns NULL if k is not present.> >// Make the BTree friend of this so that we can access> >// private members of this class in BTree functions> >friend> class> BTree;> };> // A BTree> class> BTree {> >BTreeNode* root;>// Pointer to root node> >int> t;>// Minimum degree> public>:> >// Constructor (Initializes tree as empty)> >BTree(>int> _t)> >{> >root = NULL;> >t = _t;> >}> >// function to traverse the tree> >void> traverse()> >{> >if> (root != NULL)> >root->traversa();> >}> >// function to search a key in this tree> >BTreeNode* search(>int> k)> >{> >return> (root == NULL) ? NULL : root->ricerca(k);> >}> };> // Constructor for BTreeNode class> BTreeNode::BTreeNode(>int> _t,>bool> _leaf)> {> >// Copy the given minimum degree and leaf property> >t = _t;> >leaf = _leaf;> >// Allocate memory for maximum number of possible keys> >// and child pointers> >keys =>new> int>[2 * t - 1];> >C =>new> BTreeNode*[2 * t];> >// Initialize the number of keys as 0> >n = 0;> }> // Function to traverse all nodes in a subtree rooted with> // this node> void> BTreeNode::traverse()> {> >// There are n keys and n+1 children, traverse through n> >// keys and first n children> >int> i;> >for> (i = 0; i // If this is not leaf, then before printing key[i], // traverse the subtree rooted with child C[i]. if (leaf == false) C[i]->attraversare(); cout<< ' ' << keys[i]; } // Print the subtree rooted with last child if (leaf == false) C[i]->attraversare(); } // Funzione per cercare la chiave k nel sottoalbero radicato con questo nodo BTreeNode* BTreeNode::search(int k) { // Trova la prima chiave maggiore o uguale a k int i = 0; while (i tasti[i]) i++; // Se la chiave trovata è uguale a k, restituisce questo nodo if (keys[i] == k) return this; // Se la chiave non viene trovata qui e questo è un nodo foglia if (leaf == true) restituisce NULL; // Vai al figlio appropriato return C[i]->search(k); }>
>
>

Giava

// Java program to illustrate the sum of two numbers> // A BTree> class> Btree {> >public> BTreeNode root;>// Pointer to root node> >public> int> t;>// Minimum degree> >// Constructor (Initializes tree as empty)> >Btree(>int> t)> >{> >this>.root =>null>;> >this>.t = t;> >}> >// function to traverse the tree> >public> void> traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >System.out.println();> >}> >// function to search a key in this tree> >public> BTreeNode search(>int> k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> }> // A BTree node> class> BTreeNode {> >int>[] keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode[] C;>// An array of child pointers> >int> n;>// Current number of keys> >boolean> >leaf;>// Is true when node is leaf. Otherwise false> >// Constructor> >BTreeNode(>int> t,>boolean> leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> int>[>2> * t ->1>];> >this>.C =>new> BTreeNode[>2> * t];> >this>.n =>0>;> >}> >// A function to traverse all nodes in a subtree rooted> >// with this node> >public> void> traverse()> >{> >// There are n keys and n+1 children, traverse> >// through n keys and first n children> >int> i =>0>;> >for> (i =>0>; i <>this>.n; i++) {> >// If this is not leaf, then before printing> >// key[i], traverse the subtree rooted with> >// child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >System.out.print(keys[i] +>' '>);> >}> >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> >// A function to search a key in the subtree rooted with> >// this node.> >BTreeNode search(>int> k)> >{>// returns NULL if k is not present.> >// Find the first key greater than or equal to k> >int> i =>0>;> >while> (i keys[i])> >i++;> >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> >// If the key is not found here and this is a leaf> >// node> >if> (leaf ==>true>)> >return> null>;> >// Go to the appropriate child> >return> C[i].search(k);> >}> }> 
>
>

Python3

# Create a node> class> BTreeNode:> >def> __init__(>self>, leaf>=>False>):> >self>.leaf>=> leaf> >self>.keys>=> []> >self>.child>=> []> # Tree> class> BTree:> >def> __init__(>self>, t):> >self>.root>=> BTreeNode(>True>)> >self>.t>=> t> ># Insert node> >def> insert(>self>, k):> >root>=> self>.root> >if> len>(root.keys)>=>=> (>2> *> self>.t)>-> 1>:> >temp>=> BTreeNode()> >self>.root>=> temp> >temp.child.insert(>0>, root)> >self>.split_child(temp,>0>)> >self>.insert_non_full(temp, k)> >else>:> >self>.insert_non_full(root, k)> ># Insert nonfull> >def> insert_non_full(>self>, x, k):> >i>=> len>(x.keys)>-> 1> >if> x.leaf:> >x.keys.append((>None>,>None>))> >while> i>>=> 0> and> k[>0>] 0]: x.keys[i + 1] = x.keys[i] i -= 1 x.keys[i + 1] = k else: while i>= 0 e k[0] 0]: i -= 1 i += 1 if len(x.child[i].keys) == (2 * self.t) - 1: self.split_child(x, i) if k[0]> x.keys[i][0]: i += 1 self.insert_non_full(x.child[i], k) # Divide il figlio def split_child(self, x, i): t = self .t y = x.child[i] z = BTreeNode(y.leaf) x.child.insert(i + 1, z) x.keys.insert(i, y.keys[t - 1]) z.keys = y.keys[t: (2 * t) - 1] y.keys = y.keys[0: t - 1] se non y.leaf: z.child = y.child[t: 2 * t] y. child = y.child[0: t - 1] # Stampa l'albero def print_tree(self, x, l=0): print('Level ', l, ' ', len(x.keys), end=':') for i in x.keys: print(i, end=' ') print() l += 1 if len(x.child)> 0: for i in x.child: self.print_tree(i, l) # Chiave di ricerca nell'albero def search_key(self, k, x=None): se x non è None: i = 0 while ix.keys[i][0]: i += 1 se i
>
>

C#

// C# program to illustrate the sum of two numbers> using> System;> // A BTree> class> Btree {> >public> BTreeNode root;>// Pointer to root node> >public> int> t;>// Minimum degree> >// Constructor (Initializes tree as empty)> >Btree(>int> t)> >{> >this>.root =>null>;> >this>.t = t;> >}> >// function to traverse the tree> >public> void> traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >Console.WriteLine();> >}> >// function to search a key in this tree> >public> BTreeNode search(>int> k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> }> // A BTree node> class> BTreeNode {> >int>[] keys;>// An array of keys> >int> t;>// Minimum degree (defines the range for number> >// of keys)> >BTreeNode[] C;>// An array of child pointers> >int> n;>// Current number of keys> >bool> leaf;>// Is true when node is leaf. Otherwise false> >// Constructor> >BTreeNode(>int> t,>bool> leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> int>[2 * t - 1];> >this>.C =>new> BTreeNode[2 * t];> >this>.n = 0;> >}> >// A function to traverse all nodes in a subtree rooted> >// with this node> >public> void> traverse()> >{> >// There are n keys and n+1 children, traverse> >// through n keys and first n children> >int> i = 0;> >for> (i = 0; i <>this>.n; i++) {> >// If this is not leaf, then before printing> >// key[i], traverse the subtree rooted with> >// child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >Console.Write(keys[i] +>' '>);> >}> >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> >// A function to search a key in the subtree rooted with> >// this node.> >public> BTreeNode search(>int> k)> >{>// returns NULL if k is not present.> >// Find the first key greater than or equal to k> >int> i = 0;> >while> (i keys[i])> >i++;> >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> >// If the key is not found here and this is a leaf> >// node> >if> (leaf ==>true>)> >return> null>;> >// Go to the appropriate child> >return> C[i].search(k);> >}> }> // This code is contributed by Rajput-Ji> 
>
>

Javascript

// Javascript program to illustrate the sum of two numbers> // A BTree> class Btree> {> >// Constructor (Initializes tree as empty)> >constructor(t)> >{> >this>.root =>null>;> >this>.t = t;> >}> > >// function to traverse the tree> >traverse()> >{> >if> (>this>.root !=>null>)> >this>.root.traverse();> >document.write(>' '>);> >}> > >// function to search a key in this tree> >search(k)> >{> >if> (>this>.root ==>null>)> >return> null>;> >else> >return> this>.root.search(k);> >}> > }> // A BTree node> class BTreeNode> {> >// Constructor> >constructor(t,leaf)> >{> >this>.t = t;> >this>.leaf = leaf;> >this>.keys =>new> Array(2 * t - 1);> >this>.C =>new> Array(2 * t);> >this>.n = 0;> >}> >// A function to traverse all nodes in a subtree rooted with this node> >traverse()> >{> >// There are n keys and n+1 children, traverse through n keys> >// and first n children> >let i = 0;> >for> (i = 0; i <>this>.n; i++) {> > >// If this is not leaf, then before printing key[i],> >// traverse the subtree rooted with child C[i].> >if> (>this>.leaf ==>false>) {> >C[i].traverse();> >}> >document.write(keys[i] +>' '>);> >}> > >// Print the subtree rooted with last child> >if> (leaf ==>false>)> >C[i].traverse();> >}> > >// A function to search a key in the subtree rooted with this node.> >search(k)>// returns NULL if k is not present.> >{> > >// Find the first key greater than or equal to k> >let i = 0;> >while> (i keys[i])> >i++;> > >// If the found key is equal to k, return this node> >if> (keys[i] == k)> >return> this>;> > >// If the key is not found here and this is a leaf node> >if> (leaf ==>true>)> >return> null>;> > >// Go to the appropriate child> >return> C[i].search(k);> >}> }> // This code is contributed by patel2127> 
>
>


Nota: Il codice sopra non contiene il programma del driver. Tratteremo il programma completo nel nostro prossimo post su Inserimento del B-Tree .

Esistono due convenzioni per definire un B-Tree, la prima è definire per grado minimo, la seconda è definire per ordine. Abbiamo seguito la convenzione sul titolo minimo e seguiremo lo stesso nei prossimi post su B-Tree. Anche i nomi delle variabili utilizzati nel programma precedente vengono mantenuti gli stessi

sommatore pieno

Applicazioni dei B-Tree:

  • Viene utilizzato in database di grandi dimensioni per accedere ai dati archiviati sul disco
  • La ricerca dei dati in un set di dati può essere ottenuta in un tempo notevolmente inferiore utilizzando il B-Tree
  • Con la funzione di indicizzazione è possibile ottenere l'indicizzazione multilivello.
  • La maggior parte dei server utilizza anche l'approccio B-tree.
  • I B-Tree vengono utilizzati nei sistemi CAD per organizzare e ricercare dati geometrici.
  • I B-Tree vengono utilizzati anche in altri settori come l'elaborazione del linguaggio naturale, le reti di computer e la crittografia.

Vantaggi dei B-Tree:

  • I B-Tree hanno una complessità temporale garantita pari a O(log n) per operazioni di base come inserimento, cancellazione e ricerca, che li rende adatti a grandi set di dati e applicazioni in tempo reale.
  • I B-Tree sono autobilancianti.
  • Elevata concorrenza e throughput elevato.
  • Utilizzo efficiente dello spazio di archiviazione.

Svantaggi dei B-Tree:

  • I B-Tree si basano su strutture dati basate su disco e possono avere un utilizzo elevato del disco.
  • Non è il massimo per tutti i casi.
  • Lento rispetto ad altre strutture dati.

Inserimento e cancellazione:
Inserimento del B-Tree
Eliminazione dell'albero B