Definition
In der Informatik ist ein B-Tree ein selbstausgleichender Baum, der Daten in Ordnung hält. Diese Datenstruktur ermöglicht die Suche nach Daten, den sequentiellen Zugriff, das Einfügen von Daten und das Löschen von Vorgängen in logarithmischer Zeit.
Warum B-Tree vorstellen?
Zuallererst befindet sich ein interner Suchbaum, der die Eingabe in den Speicher speichert.
B-Tree ist eine Erweiterung des vorherigen Balance-Baumalgorithmus. Es unterstützt externe Suche nach Symboltabellen, die auf Festplatte oder Netzwerk gespeichert sind. Diese Dateien sind möglicherweise viel größer als die Eingabe, die wir zuvor in Betracht gezogen haben (schwer zu speichern zu speichern).
Da der Inhalt auf der Festplatte gespeichert ist, ist die Scheiben -E/A -Lesung und Schreiben aufgrund der großen Tiefe des Baumes zu häufig (die Scheibe -Lese- und Schreibrate begrenzt), was zu einer ineffizienten Abfrage -Effizienz führt.
Dann ist es natürlich wichtig, die Tiefe des Baumes zu verringern. Daher führen wir B-Tree, Mehrwegs-Suchbaum ein.
Merkmale
Jeder Knoten im Baum enthält höchstens m Kinder (M> = 2);
Mit Ausnahme des Wurzelknotens und des Blattknotens hat jeder Knoten mindestens [Ceil (m/2)] Kinder (wobei CEL (x) eine Funktion ist, die die obere Grenze übernimmt);
Wenn der Wurzelknoten kein Blattknoten ist, gibt es mindestens 2 Kinder (Sonderfall: Es gibt keinen Wurzelknoten für Kinder, dh der Wurzelknoten ist ein Blattknoten, und der gesamte Baum hat nur einen Wurzelknoten);
Alle Blattknoten erscheinen in derselben Schicht (untere Schicht), und die Blattknoten sind externe Knoten, die den Inhalt speichern, nämlich Schlüssel und Wert .
Andere Knoten sind interne Knoten, die den Index speichern, nämlich Schlüssel und nächstes .
Schlüsselwörter von internen Knoten: K [1], K [2],…, K [M-1]; und k [i] <k [i+1];
Zeiger neben dem Inhaltsknoten: P [1], P [2],…, P [m]; Wenn P [1] auf ein Subtree mit dem Schlüsselwort weniger als K [1] zeigt, zeigt P [m] auf ein Subtree mit dem Schlüsselwort größer als K [M-1] und andere P [i] auf einen Subtreiber mit dem Schlüsselwort (k [i-1], k [i]);
Zum Beispiel: (M = 3)
Finden und einfügen
Aus Gründen der Bequemlichkeit wird hier ein spezieller Sentinel -Schlüssel verwendet, der kleiner als alle anderen Schlüssel ist und von *dargestellt wird.
Am Anfang enthält der B-Tree nur einen Rootknoten, und der Stammknoten enthält nur die Sentinel-Taste, wenn sie initialisiert wird.
Jeder Schlüssel in einem internen Knoten ist einem Knoten zugeordnet. Alle Schlüssel sind größer oder gleich dem Taste, der diesem Knoten zugeordnet ist, aber kleiner als alle anderen Schlüssel.
Diese Konventionen können den Code stark vereinfachen.
Code
Klicken Sie hier, um herunterzuladen.
Diese Code -Implementierung führt den Sentinel -Schlüssel ein und die Codeausgabe beseitigt ihn.
Der B-Tree mit dem Sentinel-Schlüssel im Code (das Bild lokal speichern, um anzeigen, und die Wörter sind klarer):
Die B-Tree-Ausgabe durch den Code (das Bild lokal speichern, um anzeigen, und die Wörter sind klarer):
public class btree <Key erweitert vergleichbar <schlüssel>, Wert> {// max Kinder pro B-Tree Node = M-1 // (muss gleich und größer als 2) private statische endgültige int m = 4; private Knotenwurzel; // Wurzel des B-Tree Private int Height; // Höhe des B-Tree Private int n; // Anzahl der Schlüsselwertepaare im B-Tree // Helfer B-Tree-Knoten-Datentyp privater statischer endgültiger Klassenknoten {private int m; // Anzahl der Kinder privater Eintrag [] Kinder = neuer Eintrag [m]; // Das Array der Kinder // einen Knoten mit K Children Private Knoten (int k) {m = k; }} // Interne Knoten: Verwenden Sie nur Taste und Weiter // externe Knoten: Verwenden Sie nur Schlüssel und Wert private statische Klasseneintrag {private vergleichbare Schlüssel; privates Objekt val; Privatknoten als nächstes; // Helfer -Feld über Array -Einträge öffentlicher Eintrag (vergleichbarer Schlüssel, Objekt, Knoten als nächstes) {this.key = key; this.val = val; this.Next = Weiter; }} /*** initialisiert einen leeren B-Tree. */ public btree () {root = neuer Knoten (0); } /*** Gibt true zurück, wenn diese Symboltabelle leer ist. * @return {@code true} Wenn diese Symboltabelle leer ist; {@code false} sonst */ public boolean isEmpty () {return size () == 0; } /*** Gibt die Anzahl der Schlüsselwertpaare in dieser Symboltabelle zurück. * @return die Anzahl der Schlüsselwertpaare in dieser Symboltabelle */ public int size () {return n; } /*** Gibt die Höhe dieses B-Tree zurück (zum Debuggen). * * @return die Höhe dieses B-Tree */ public int height () {return Height; } /*** Gibt den mit dem angegebenen Schlüssel zugeordneten Wert zurück. * * @paramschlüssel Der Schlüssel * @return Der mit der angegebene Schlüssel zugeordnete Wert, wenn der Schlüssel in der Symboltabelle * und {@Code null} ist, wenn der Schlüssel nicht in der Symboltabelle ist } Rückgabesuche (Root, Schlüssel, Höhe); } @SuppressWarnings ("deaktiviert") private Wertsuche (Knoten X, Schlüsselschlüssel, int ht) {Eintrag [] childhes = x.Children; // externer Knoten an den niedrigsten Blattknoten, Traverse if (ht == 0) {für (int j = 0; j <xm; j ++) {if (EQ (Schlüssel, Kinder [j] .Key)) {return (value) childhus [j] .Val; }}} // interner Knoten sucht die nächste Adresse else {for (int j = 0; j <xm; j ++) {if (j+1 == xm || weniger (Schlüssel, Kinder [j+1] .Key)) {Return Search (Kinder [j] .Next, key, ht-1); }}} return null; } /** * fügt das Schlüsselwertpaar in die Symboltabelle ein und überschreiben Sie den alten Wert * mit dem neuen Wert, wenn sich der Schlüssel bereits in der Symboltabelle befindet. * Wenn der Wert {@code null} ist, löscht dies den Schlüssel effektiv aus der Symboltabelle. * * @paramschlüssel Der Schlüssel * @param val Der Wert * @throws nullPointerexception Wenn {@Code Key} {@Code null} */ public void put (Schlüssel, Wert val) {if (key == null) {nulpoInterexception ("Taste muss nicht null sein"); } Node u = insert (root, key, val, Höhe); // der rechte Knoten, der nach Split N ++ erzeugt wurde; if (u == null) {return; } // müssen die Root -Reorganisation des Root -Knotens t = neuer Knoten (2) teilen; t.children [0] = neuer Eintrag (root.Children [0] .Key, Null, root); t.children [1] = neuer Eintrag (U.Children [0] .Key, Null, U); root = t; Höhe ++; } privater Knoteneinfüge (Knoten H, Schlüsselschlüssel, Wert Val, int ht) {int j; Eintrag t = neuer Eintrag (Schlüssel, Val, NULL); // externer Knoten externer Knoten, der auch ein Blattknoten ist. Am Ende des Baumes wird der Inhaltswert gespeichert, wenn (ht == 0) {für (j = 0; j <hm; j ++) {if (weniger (Schlüssel, H.Children [j] .Key)) {break; }}} // Der interne Knoten im Knoten ist die nächste Adresse {für (j = 0; j <hm; j ++) {if (j+1 == hm) || weniger (Schlüssel, 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; brechen; }}} für (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 {// Splitknoten return split (h); }} // Knoten im halben privaten Knoten spalten (Knoten H) {Knoten t = neuer Knoten (m/2); hm = m/2; für (int j = 0; j <m/2; j ++) {t.children [j] = h.children [m/2+j]; } return t; } /*** Gibt eine String-Darstellung dieses B-Tree zurück (zum Debuggen). * * @return eine String-Darstellung dieses B-Tree. */ public String toString () {return toString (root, Höhe, "") + "/ n"; } private String toString (Knoten H, int ht, String -Eindrücke) {StringBuilder s = new StringBuilder (); Eintrag [] Kinder = H.Children; if (ht == 0) {für (int j = 0; j <hm; j ++) {S.And (Einklebung + Kinder [j] .Key + "" + Kinder [j] .val + "/n"); }} else {for (int j = 0; j <hm; j ++) {if (j> 0) {S.And (Einklebung + "(" + children [j] .Key + ")/n"); } S.Append (toString (Kinder [j] .Next, ht-1, Einzug + ""); }} return s.ToString (); } // Vergleichsfunktionen - vergleichbar anstelle von Schlüssel, um den privaten booleschen Abguss zu vermeiden (vergleichbarer K1, vergleichbarer K2) {return K1.comPareto (K2) <0; } private boolean EQ (vergleichbarer K1, Vergleichbar K2) {return K1.comPareto (K2) == 0; } /*** Unit testet den Datentyp {@code btree}. * * @param args die Befehlszeilenargumente */ 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.simpsons.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.simpsons.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 ("Größe:" + St.Size ()); System.out.println ("Höhe:" + St.Height ()); System.out.println (ST); System.out.println (); }} Ausgabe:
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
Größe: 17
Höhe: 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.simpsons.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
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.