Arbre B

Dans ce didacticiel, vous apprendrez ce qu'est un arbre B. Vous trouverez également des exemples pratiques d'opérations de recherche sur un arbre B en C, C ++, Java et Python.

B-tree est un type spécial d'arbre de recherche auto-équilibré dans lequel chaque nœud peut contenir plus d'une clé et peut avoir plus de deux enfants. C'est une forme généralisée de l'arbre de recherche binaire.

Il est également connu comme un arbre m-way à hauteur équilibrée.

Arbre B

Pourquoi B-tree?

Le besoin de B-tree est apparu avec l'augmentation du besoin de moins de temps pour accéder au support de stockage physique comme un disque dur. Les périphériques de stockage secondaires sont plus lents avec une plus grande capacité. Il y avait un besoin pour de tels types de structures de données qui réduisent au minimum les accès au disque.

D'autres structures de données telles qu'un arbre de recherche binaire, un arbre avl, un arbre rouge-noir, etc. ne peuvent stocker qu'une seule clé dans un nœud. Si vous devez stocker un grand nombre de clés, la hauteur de ces arbres devient très grande et le temps d'accès augmente.

Cependant, B-tree peut stocker de nombreuses clés dans un seul nœud et peut avoir plusieurs nœuds enfants. Cela diminue considérablement la hauteur, ce qui permet d'accéder plus rapidement au disque.

Propriétés de l'arbre B

  1. Pour chaque nœud x, les clés sont stockées par ordre croissant.
  2. Dans chaque nœud, il y a une valeur booléenne x.leaf qui est vraie si x est une feuille.
  3. Si n est l'ordre de l'arborescence, chaque nœud interne peut contenir au plus n - 1 clés avec un pointeur vers chaque enfant.
  4. Chaque nœud sauf root peut avoir au plus n enfants et au moins n / 2 enfants.
  5. Toutes les feuilles ont la même profondeur (c.-à-d. Hauteur-h de l'arbre).
  6. La racine a au moins 2 enfants et contient au moins 1 clé.
  7. Si n ≧ 1, alors pour tout n-clé B-arbre de hauteur h et le degré minimum t ≧ 2, .h ≧ logt (n+1)/2

Opérations

Recherche

La recherche d'un élément dans un arbre B est la forme généralisée de recherche d'un élément dans un arbre de recherche binaire. Les étapes suivantes sont suivies.

  1. À partir du nœud racine, comparez k avec la première clé du nœud.
    Si k = the first key of the node, retournez le nœud et l'index.
  2. Si k.leaf = true, renvoie NULL (c'est-à-dire non trouvé).
  3. Si k < the first key of the root node, recherchez l'enfant gauche de cette clé de manière récursive.
  4. S'il y a plus d'une clé dans le nœud actuel et k> the first key, comparez k avec la clé suivante dans le nœud.
    Si k < next key, recherchez l'enfant gauche de cette clé (c.-à-d. K se situe entre la première et la deuxième clés).
    Sinon, recherchez le bon enfant de la clé.
  5. Répétez les étapes 1 à 4 jusqu'à ce que la feuille soit atteinte.

Exemple de recherche

  1. Cherchons la clé k = 17dans l'arbre en dessous du degré 3. B-tree
  2. k n'est pas trouvé dans la racine, comparez-le avec la clé racine. k n'est pas trouvé sur le nœud racine
  3. Depuis k> 11, accédez au bon enfant du nœud racine. Aller au bon sous-arbre
  4. Comparez k avec 16. Depuis k> 16, comparez k avec la clé suivante 18. Comparez avec les touches de gauche à droite
  5. Depuis k < 18, k se situe entre 16 et 18. Recherche chez l'enfant droit de 16 ans ou l'enfant gauche de 18 ans. K se situe entre 16 et 18 ans
  6. k est trouvé. k est trouvé

Algorithme de recherche d'un élément

 BtreeSearch(x, k) i = 1 while i ≦ n(x) and k ≧ keyi(x) // n(x) means number of keys in x node 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)

Pour en savoir plus sur les différentes opérations de B-tree, veuillez visiter

  • Insertion sur B-tree
  • Suppression sur B-tree

Exemples Python, Java et C / C ++

Python Java C C ++ 
# Searching a key on a B-tree in Python # Create node class BTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = () self.child = () class BTree: def __init__(self, t): self.root = BTreeNode(True) self.t = t # Print the tree 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) # Search key def search_key(self, k, x=None): if x is not None: i = 0 while i x.keys(i)(0): i += 1 if i  = 0 and k(0)  = 0 and k(0)  x.keys(i)(0): i += 1 self.insert_non_full(x.child(i), k) # Split def split(self, x, i): t = self.t y = x.child(i) z = BTreeNode(y.leaf) x.child.insert_key(i + 1, z) x.keys.insert_key(i, y.keys(t - 1)) z.keys = y.keys(t: (2 * t) - 1) y.keys = y.keys(0: t - 1) if not y.leaf: z.child = y.child(t: 2 * t) y.child = y.child(0: t - 1) def main(): B = BTree(3) for i in range(10): B.insert_key((i, 2 * i)) B.print_tree(B.root) if B.search_key(8) is not None: print("Found") else: print("Not found") if __name__ == '__main__': main()   
 // Searching a key on a B-tree in Java public class BTree ( private int T; // Node creation public class Node ( int n; int key() = new int(2 * T - 1); Node child() = new Node(2 * T); boolean leaf = true; public int Find(int k) ( for (int i = 0; i < this.n; i++) ( if (this.key(i) == k) ( return i; ) ) return -1; ); ) public BTree(int t) ( T = t; root = new Node(); root.n = 0; root.leaf = true; ) private Node root; // Search key private Node Search(Node x, int key) ( int i = 0; if (x == null) return x; for (i = 0; i < x.n; i++) ( if (key < x.key(i)) ( break; ) if (key == x.key(i)) ( return x; ) ) if (x.leaf) ( return null; ) else ( return Search(x.child(i), key); ) ) // Splitting the node private void Split(Node x, int pos, Node y) ( Node z = new Node(); z.leaf = y.leaf; z.n = T - 1; for (int j = 0; j < T - 1; j++) ( z.key(j) = y.key(j + T); ) if (!y.leaf) ( for (int j = 0; j = pos + 1; j--) ( x.child(j + 1) = x.child(j); ) x.child(pos + 1) = z; for (int j = x.n - 1; j>= pos; j--) ( x.key(j + 1) = x.key(j); ) x.key(pos) = y.key(T - 1); x.n = x.n + 1; ) // Inserting a value public void Insert(final int key) ( Node r = root; if (r.n == 2 * T - 1) ( Node s = new Node(); root = s; s.leaf = false; s.n = 0; s.child(0) = r; Split(s, 0, r); insertValue(s, key); ) else ( insertValue(r, key); ) ) // Insert the node final private void insertValue(Node x, int k) ( if (x.leaf) ( int i = 0; for (i = x.n - 1; i>= 0 && k  = 0 && k x.key(i)) ( i++; ) ) insertValue(x.child(i), k); ) ) public void Show() ( Show(root); ) // Display private void Show(Node x) ( assert (x == null); for (int i = 0; i < x.n; i++) ( System.out.print(x.key(i) + " "); ) if (!x.leaf) ( for (int i = 0; i < x.n + 1; i++) ( Show(x.child(i)); ) ) ) // Check if present public boolean Contain(int k) ( if (this.Search(root, k) != null) ( return true; ) else ( return false; ) ) public static void main(String() args) ( BTree b = new BTree(3); b.Insert(8); b.Insert(9); b.Insert(10); b.Insert(11); b.Insert(15); b.Insert(20); b.Insert(17); b.Show(); if (b.Contain(12)) ( System.out.println("found"); ) else ( System.out.println("not found"); ) ; ) ) 
// Searching a key on a B-tree in C #include #include #define MAX 3 #define MIN 2 struct BTreeNode ( int val(MAX + 1), count; struct BTreeNode *link(MAX + 1); ); struct BTreeNode *root; // Create a node struct BTreeNode *createNode(int val, struct BTreeNode *child) ( struct BTreeNode *newNode; newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); newNode->val(1) = val; newNode->count = 1; newNode->link(0) = root; newNode->link(1) = child; return newNode; ) // Insert node void insertNode(int val, int pos, struct BTreeNode *node, struct BTreeNode *child) ( int j = node->count; while (j> pos) ( node->val(j + 1) = node->val(j); node->link(j + 1) = node->link(j); j--; ) node->val(j + 1) = val; node->link(j + 1) = child; node->count++; ) // Split node void splitNode(int val, int *pval, int pos, struct BTreeNode *node, struct BTreeNode *child, struct BTreeNode **newNode) ( int median, j; if (pos> MIN) median = MIN + 1; else median = MIN; *newNode = (struct BTreeNode *)malloc(sizeof(struct BTreeNode)); j = median + 1; while (j val(j - median) = node->val(j); (*newNode)->link(j - median) = node->link(j); j++; ) node->count = median; (*newNode)->count = MAX - median; if (pos val(node->count); (*newNode)->link(0) = node->link(node->count); node->count--; ) // Set the value int setValue(int val, int *pval, struct BTreeNode *node, struct BTreeNode **child) ( int pos; if (!node) ( *pval = val; *child = NULL; return 1; ) if (val val(1)) ( pos = 0; ) else ( for (pos = node->count; (val val(pos) && pos> 1); pos--) ; if (val == node->val(pos)) ( printf("Duplicates are not permitted"); return 0; ) ) if (setValue(val, pval, node->link(pos), child)) ( if (node->count < MAX) ( insertNode(*pval, pos, node, *child); ) else ( splitNode(*pval, pval, pos, node, *child, child); return 1; ) ) return 0; ) // Insert the value void insert(int val) ( int flag, i; struct BTreeNode *child; flag = setValue(val, &i, root, &child); if (flag) root = createNode(i, child); ) // Search node void search(int val, int *pos, struct BTreeNode *myNode) ( if (!myNode) ( return; ) if (val val(1)) ( *pos = 0; ) else ( for (*pos = myNode->count; (val val(*pos) && *pos> 1); (*pos)--) ; if (val == myNode->val(*pos)) ( printf("%d is found", val); return; ) ) search(val, pos, myNode->link(*pos)); return; ) // Traverse then nodes void traversal(struct BTreeNode *myNode) ( int i; if (myNode) ( for (i = 0; i count; i++) ( traversal(myNode->link(i)); printf("%d ", myNode->val(i + 1)); ) traversal(myNode->link(i)); ) ) int main() ( int val, ch; insert(8); insert(9); insert(10); insert(11); insert(15); insert(16); insert(17); insert(18); insert(20); insert(23); traversal(root); printf(""); search(11, &ch, root); )
// Searching a key on a B-tree in C++ #include using namespace std; class TreeNode ( int *keys; int t; TreeNode **C; int n; bool leaf; public: TreeNode(int temp, bool bool_leaf); void insertNonFull(int k); void splitChild(int i, TreeNode *y); void traverse(); TreeNode *search(int k); friend class BTree; ); class BTree ( TreeNode *root; int t; public: BTree(int temp) ( root = NULL; t = temp; ) void traverse() ( if (root != NULL) root->traverse(); ) TreeNode *search(int k) ( return (root == NULL) ? NULL : root->search(k); ) void insert(int k); ); TreeNode::TreeNode(int t1, bool leaf1) ( t = t1; leaf = leaf1; keys = new int(2 * t - 1); C = new TreeNode *(2 * t); n = 0; ) void TreeNode::traverse() ( int i; for (i = 0; i traverse(); cout << " " 
 search(k); ) void BTree::insert(int k) ( if (root == NULL) ( root = new TreeNode(t, true); root->keys(0) = k; root->n = 1; ) else ( if (root->n == 2 * t - 1) ( TreeNode *s = new TreeNode(t, false); s->C(0) = root; s->splitChild(0, root); int i = 0; if (s->keys(0) C(i)->insertNonFull(k); root = s; ) else root->insertNonFull(k); ) ) void TreeNode::insertNonFull(int k) ( int i = n - 1; if (leaf == true) ( while (i>= 0 && keys(i)> k) ( keys(i + 1) = keys(i); i--; ) keys(i + 1) = k; n = n + 1; ) else ( while (i>= 0 && keys(i)> k) i--; if (C(i + 1)->n == 2 * t - 1) ( splitChild(i + 1, C(i + 1)); if (keys(i + 1) insertNonFull(k); ) ) void TreeNode::splitChild(int i, TreeNode *y) ( TreeNode *z = new TreeNode(y->t, y->leaf); z->n = t - 1; for (int j = 0; j keys(j) = y->keys(j + t); if (y->leaf == false) ( for (int j = 0; j C(j) = y->C(j + t); ) y->n = t - 1; for (int j = n; j>= i + 1; j--) C(j + 1) = C(j); C(i + 1) = z; for (int j = n - 1; j>= i; j--) keys(j + 1) = keys(j); keys(i) = y->keys(t - 1); n = n + 1; ) int main() ( BTree t(3); t.insert(8); t.insert(9); t.insert(10); t.insert(11); t.insert(15); t.insert(16); t.insert(17); t.insert(18); t.insert(20); t.insert(23); cout << "The B-tree is: "; t.traverse(); int k = 10; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; k = 2; (t.search(k) != NULL) ? cout << endl << k << " is found" : cout << endl << k << " is not Found"; )

Recherche de complexité sur l'arbre B

Pire cas Complexité temporelle: Θ(log n)

Cas moyen Complexité temporelle: Θ(log n)

Meilleur cas Complexité temporelle: Θ(log n)

Complexité moyenne de l'espace de cas: Θ(n)

Pire cas Complexité spatiale: Θ(n)

Applications de l'arborescence B

  • bases de données et systèmes de fichiers
  • pour stocker des blocs de données (support de stockage secondaire)
  • indexation à plusieurs niveaux

Articles intéressants...