définition
En informatique, un arbre B est un arbre d'auto-équilibre qui conserve les données en ordre. Cette structure de données permet à la recherche de données, à l'accès séquentiel, à l'insertion de données et à la suppression des opérations de terminer en temps logarithmique.
Pourquoi introduire B-Tree?
Tout d'abord, y compris l'arbre rouge et noir que nous avons introduit plus tôt, est un arbre de recherche interne qui stocke la entrée dans la mémoire .
B-Tree est une extension de l'algorithme d'arbre d'équilibre précédent. Il prend en charge les recherches externes pour les tables de symboles enregistrées sur le disque ou le réseau . Ces fichiers peuvent être beaucoup plus importants que l'entrée que nous avons considérée auparavant (difficile à stocker en mémoire).
Étant donné que le contenu est stocké sur le disque, les E / S disque lisent et écrivent trop fréquemment en raison de la grande profondeur de l'arbre (le taux de lecture et d'écriture du disque est limité), ce qui conduit à une efficacité de requête inefficace.
Ensuite, il est naturellement important de réduire la profondeur de l'arbre. Par conséquent, nous introduisons l'arbre de recherche B-Tree, multiple.
Caractéristiques
Chaque nœud de l'arbre contient au plus m enfants (m> = 2);
À l'exception du nœud racine et du nœud feuille, chaque nœud a au moins des enfants [CEIL (m / 2)] (où le cail (x) est une fonction qui prend la limite supérieure);
Si le nœud racine n'est pas un nœud foliaire, il y aura au moins 2 enfants (cas spécial: il n'y a pas de nœud racine pour les enfants, c'est-à-dire que le nœud racine est un nœud de feuille et l'arbre entier n'a qu'un seul nœud racine);
Tous les nœuds de feuilles apparaissent dans la même couche (couche inférieure), et les nœuds de feuilles sont des nœuds externes, qui sauvent le contenu, à savoir la clé et la valeur .
Les autres nœuds sont des nœuds internes, qui sauvent l'index, à savoir la clé et ensuite .
Mots-clés des nœuds internes: k [1], k [2],…, k [M-1]; et k [i] <k [i + 1];
Pointeurs à côté du nœud de contenu: p [1], p [2],…, p [m]; où p [1] pointe vers un sous-arbre avec le mot clé inférieur à K [1], P [M] pointe vers un sous-arbre avec le mot clé supérieur à K [M-1], et d'autres p [i] pointent vers un sous-arbre avec le mot-clé (k [i-1], k [i]);
Par exemple: (m = 3)
Trouver et insérer
Pour plus de commodité, une touche sentinelle spéciale est utilisée ici, qui est plus petite que toutes les autres clés et est représentée par *.
Au début, le B-Tree ne contient qu'un seul nœud racine et le nœud racine ne contient la touche Sentinel uniquement lorsqu'il est initialisé.
Chaque clé d'un nœud interne est associée à un nœud. Toutes les clés sont supérieures ou égales à la clé associée à ce nœud, mais plus petites que toutes les autres clés.
Ces conventions peuvent considérablement simplifier le code.
Code
Cliquez pour télécharger.
Cette implémentation de code présente la touche Sentinel et la sortie de code l'élimine.
Le B-Tree avec la touche Sentinel dans le code (enregistrez l'image localement pour afficher, et les mots seront plus clairs):
La sortie de B-Tree par le code (enregistrez l'image localement pour afficher, et les mots seront plus clairs):
La classe publique BTree <Key étend comparable <yey>, valeur> {// max enfants par b-tree node = m-1 // (doit être uniforme et supérieur à 2) final statique privé int m = 4; racine de nœud privé; // Racine de la hauteur privée de B-Tree; // Hauteur du B-Tree privé int n; // Nombre de paires de valeurs clés dans le nœud de classe finale statique finale statique privée {private int m; // Nombre d'enfants Entrée privée [] enfants = nouvelle entrée [M]; // Le tableau d'enfants // Créer un nœud avec k enfants nœud privé (int k) {m = k; }} // nœuds internes: utilisez uniquement la touche et les nœuds externes suivants: utilisez uniquement la clé et la valeur de la classe statique privée entrée {clé comparable privée; objet privé Val; Node privé Suivant; // Champ d'assistance pour itérer les entrées du tableau Entrée publique (clé comparable, objet Val, nœud suivant) {this.key = key; this.val = val; this.next = suivant; }} / ** * Initialise un arbre B vide. * / public btree () {root = nouveau nœud (0); } / ** * Renvoie True si cette table de symbole est vide. * @return {@code true} Si cette table de symbole est vide; {@code false} Sinon * / public boolean isEmpty () {return size () == 0; } / ** * Renvoie le nombre de paires de valeurs clés dans cette table de symbole. * @return le nombre de paires de valeurs clés dans cette table de symbole * / public int size () {return n; } / ** * Renvoie la hauteur de ce b-are (pour le débogage). * * @return la hauteur de ce b-are * / public int height () {return height; } / ** * Renvoie la valeur associée à la clé donnée. * * @param clé La clé * @return la valeur associée à la clé donnée si la clé se trouve dans la table des symboles * et {@code null} si la touche n'est pas dans la table de symbole * @Throws nullpointerException if {@code key nul"); } return search (root, key, hauteur); } @SuppressWarnings ("Unchecked") Recherche de valeur privée (Node X, clé clé, int ht) {entrée [] enfants = x.children; // nœud externe au nœud de feuille le plus bas, Traverse if (ht == 0) {for (int j = 0; j <xm; j ++) {if (eq (key, enfants [j] .key)) {return (value) enfants [j] .val; }}} // Node interne recherche récursivement l'adresse suivante else {for (int j = 0; j <xm; j ++) {if (j + 1 == xm || moins (key, enfants [j + 1] .key)) {return search (enfants [j] .next, key, ht-1); }}} return null; } / ** * Insère la paire de valeurs de clé dans la table de symboles, écrasant l'ancienne valeur * avec la nouvelle valeur si la clé est déjà dans la table des symboles. * Si la valeur est {@code null}, cela supprime efficacement la clé de la table de symbole. * * @Param Key La clé * @param val la valeur * @throws nullpointerException if {@code key} est {@code null} * / public void put (key key, value val) {if (key == null) {throw nullpointerException ("key ne doit pas être null"); } Nœud u = insert (root, key, val, height); // le nœud droit généré après la division n ++; if (u == null) {return; } // doit diviser la réorganisation racine nœud racine t = nouveau nœud (2); t.children [0] = nouvelle entrée (root.children [0] .key, null, root); t.children [1] = nouvelle entrée (u.children [0] .key, null, u); root = t; hauteur ++; } insert de nœud privé (nœud h, clé de clé, valeur val, int ht) {int j; Entrée t = nouvelle entrée (clé, val, null); // Node externe externe, qui est également un nœud feuille. Au bas de l'arbre, la valeur de contenu est stockée if (ht == 0) {for (j = 0; j <hm; j ++) {if (moins (key, h.children [j] .key)) {break; }}} // Le nœud interne à l'intérieur du nœud est l'adresse suivante else {for (j = 0; j <hm; j ++) {if ((j + 1 == hm) || moins (key, h.children [j + 1] .key)) {node u = insert (h.children [j ++]. if (u == null) {return null; } t.key = u.children [0] .key; t.next = u; casser; }}} pour (int i = hm; i> j; i--) {h.children [i] = h.children [i-1]; } h.children [j] = t; H.M ++; if (hm <m) {return null; } else {// nœud divisé return Split (h); }} // Node de division dans la moitié du nœud privé Split (nœud h) {nœud t = nouveau nœud (m / 2); hm = m / 2; pour (int j = 0; j <m / 2; j ++) {t.children [j] = h.children [m / 2 + j]; } return t; } / ** * Renvoie une représentation de chaîne de ce B-Tree (pour le débogage). * * @return une représentation de chaîne de ce b-are. * / public String toString () {return toString (root, height, "") + "/ n"; } private String toString (node h, int ht, string indent) {stringBuilder s = new StringBuilder (); Entrée [] enfants = H.Children; if (ht == 0) {for (int j = 0; j <hm; j ++) {s.append (indent + enfants [j] .key + "" + enfants [j] .val + "/ n"); }} else {for (int j = 0; j <hm; j ++) {if (j> 0) {s.append (indent + "(" + enfants [j] .key + ") / n"); } S.APPEND (toString (enfants [J] .Next, ht-1, indent + "")); }} return s.toString (); } // Fonctions de comparaison - Rendez comparable au lieu de la clé pour éviter les casts booléens privés moins (K1 comparable, comparable k2) {return k1.compareto (k2) <0; } EQ Boolean privé (K1 comparable, comparable K2) {return k1.compareto (k2) == 0; } / ** * L'unité teste le type de données {@code btree}. * * @param args les arguments de ligne de commande * / public static void main (String [] args) {btree <string, string> st = new btree <string, string> (); St.put ("www.cs.princeton.edu", "128.112.136.12"); St.put ("www.cs.princeton.edu", "128.112.136.11"); St.put ("www.princeton.edu", "128.112.128.15"); St.put ("www.yale.edu", "130.132.143.21"); St.put ("www.simpons.com", "209.052.165.60"); St.put ("www.apple.com", "17.112.152.32"); St.put ("www.amazon.com", "207.171.182.16"); St.put ("www.ebay.com", "66.135.192.87"); St.put ("www.cnn.com", "64.236.16.20"); St.put ("www.google.com", "216.239.41.99"); St.put ("www.nytimes.com", "199.239.136.200"); St.put ("www.microsoft.com", "207.126.99.140"); St.put ("www.dell.com", "143.166.224.230"); St.put ("www.slashdot.org", "66.35.250.151"); St.put ("www.espn.com", "199.181.135.201"); St.put ("www.weather.com", "63.111.66.11"); St.put ("www.yahoo.com", "216.109.118.65"); System.out.println ("cs.princeton.edu:" + St.Get ("www.cs.princeton.edu")); System.out.println ("hardvardsucks.com:" + St.Get ("www.harvardsucks.com")); System.out.println ("Simpsons.com:" + St.Get ("www.simpons.com")); System.out.println ("Apple.com:" + St.Get ("www.apple.com")); System.out.println ("eBay.com:" + St.Get ("www.ebay.com")); System.out.println ("Dell.com:" + St.Get ("www.dell.com")); System.out.println ("Taille:" + St.Size ()); System.out.println ("Height:" + St.Height ()); System.out.println (ST); System.out.println (); }} Sortir:
cs.princeton.edu: 128.112.136.12
hardvardsucks.com: null
Simpsons.com: 209.052.165.60
Apple.com: 17.112.152.32
ebay.com: 66.135.192.87
Dell.com: 143.166.224.230
Taille: 17
hauteur: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.