Datenstruktur - Baum (III): Mehrweg-Suchbaum B-Baum, B+ Baum

Mehrweg-Suchbaum

1. Höhe eines vollständigen Binärbaums: O(log2N), wobei 2 der Logarithmus ist
2. Höhe eines vollständigen M-Wege-Suchbaums: O(logmN), wobei M der Logarithmus ist, also die Anzahl der Knoten auf jeder Ebene des Baums
3. Der M-Way-Suchbaum wird hauptsächlich verwendet, um das Problem von Datenspeichern zu lösen, die zu groß sind, um in den Speicher geladen zu werden. Durch Erhöhen der Anzahl der Knoten in jeder Schicht und Speichern von mehr Daten in jedem Knoten können mehr Daten in einer Schicht gespeichert werden, wodurch die Höhe des Baums verringert und die Anzahl der Festplattenzugriffe bei der Suche nach Daten reduziert wird.
4. Daher gilt: Je mehr Knoten jede Ebene enthält und je mehr Schlüsselwörter jeder Knoten enthält, desto geringer ist die Baumhöhe. Allerdings ist die Datenbestimmung an jedem Knoten langsamer, aber B-Tree konzentriert sich auf Leistungsengpässe bei der Festplatte, sodass der Mehraufwand bei der Datensuche an einem einzelnen Knoten ignoriert werden kann.

B-Baum

B-Tree ist ein M-Wege-Suchbaum. B-Tree wird hauptsächlich verwendet, um das Ungleichgewicht von M-Wege-Suchbäumen zu lösen, das dazu führt, dass die Baumhöhe zunimmt, genau wie das Leistungsproblem, das durch die Degeneration eines Binärbaums in eine verknüpfte Liste verursacht wird. Der B-Baum gewährleistet das Gleichgewicht des M-Wege-Suchbaums, indem er die Knoten in jeder Ebene steuert und anpasst, z. B. durch Knotentrennung, Knotenzusammenführung und Aufteilung des übergeordneten Knotens nach oben, um eine neue Ebene hinzuzufügen, wenn eine Ebene voll ist. Die spezifischen Regeln lauten wie folgt:

1. Die Anzahl der Kindbäume des Wurzelknotens liegt zwischen 2 und M, und die Anzahl der Kindbäume anderer Nicht-Blattknoten liegt zwischen M/2 und M. Wenn die Anzahl der untergeordneten Bäume aufgrund der Aufteilung M überschreitet, muss der übergeordnete Knoten rekursiv nach oben aufgeteilt werden. Wenn ein übergeordneter Knoten gefunden wird, der nicht aufgeteilt werden muss, wird die Aufteilung beendet. Der Teilungsprozess wird bis zum Stammknoten fortgesetzt. Wenn der Stammknoten geteilt werden muss, werden zwei Wurzeln generiert. Daher muss eine neue Wurzel erstellt werden, um diese beiden Wurzeln als untergeordnete Knoten zu verwenden. Zu diesem Zeitpunkt erhöht sich die Höhe des Baums um 1.
2. Der Wert des Schlüsselworts jedes Nicht-Blattknotens nimmt von links nach rechts zu. Das i-te Schlüsselwort stellt das kleinste Schlüsselwort im Teilbaum i+1 dar; (wobei i für den Wurzelknoten zwischen 1 und (2 bis M) und für andere Nicht-Blattknoten zwischen 1 und (M/2 bis M) liegt);
3. Alle Datenelemente des B-Baums werden in Blattknoten gespeichert. Nicht-Blattknoten speichern keine Daten. Nicht-Blattknoten speichern nur Schlüsselwörter, die zur Angabe der Suchrichtung verwendet werden, nämlich Indizes. Dadurch werden mehr Nicht-Blattknoten in den Speicher geladen, was die Datensuche erleichtert.
4. Alle Blattknoten liegen in der gleichen Tiefe und jeder Blattknoten enthält L/2 bis L Datenelemente.
   

Größenoptionen: M und L

1. M ist die Reihenfolge oder Anzahl der Pfade des B-Baums
2. L ist die maximale Anzahl von Datenelementen, die in jedem Blattknoten gespeichert werden können
3. In einem B-Baum ist jeder Knoten ein Festplattenblock, daher müssen M und L basierend auf der Größe des Festplattenblocks bestimmt werden.

Festplattenblockgröße und M-Berechnung

1. Jeder Nicht-Blattknoten speichert Schlüsselwörter und Zeiger auf untergeordnete Bäume. Die genaue Zahl lautet: Für einen B-Baum der Ordnung M speichert jeder Nicht-Blattknoten M-1 Schlüsselwörter und M Zeiger auf untergeordnete Bäume. Wenn also die Größe jedes Schlüsselworts 8 Byte beträgt (wie z. B. der Java-Langtyp 8 Byte) und jeder Zeiger 4 Byte, dann benötigt jeder Nicht-Blattknoten des B-Baums der Ordnung M: 8 * (M-1) + 4 * M = 12M - 8 Byte.
2. Wenn festgelegt ist, dass jeder Nicht-Blattknoten (Festplattenblock) nicht mehr als 8 KB Speicher belegt, also 8192, dann beträgt der Maximalwert von M 683, also 683 * 12-8 = 8192.
   

Anzahl der Blattknotendatenelemente L

1. Wenn die Größe jedes Datenelements ebenfalls 256 Byte beträgt, kann jeder Blattknoten höchstens 8192/256 = 32 Datenelemente speichern, da die Festplattenblockgröße 8 KB oder 8192 Byte beträgt und jeder Blattknoten L/2 bis L Datenelemente speichern kann. Das bedeutet, dass die Größe von L 32 beträgt.
2. Die Struktur eines B-Baums 5. Ordnung ist wie folgt, d. h. M und L sind gleich 5: Jeder Nicht-Blattknoten enthält höchstens M-1=5-1=4 Schlüsselwörter, einschließlich M, d. h. 5 Zeiger auf Teilbäume. Wenn L gleich 5 ist, kann jeder Blattknoten bis zu 5 Datenelemente speichern.
   

B+ Baum

Die Struktur des B+-Baums ist grundsätzlich dieselbe wie die des B-Baums. Der einzige Unterschied besteht darin, dass die Blattknoten des B+-Baums durch Zeiger verbunden sind, um eine verknüpfte Liste zu bilden, sodass es einfach ist, alle Blattknoten zu durchlaufen, d. h. alle oder alle Datenelemente in einem bestimmten Bereich des Suchbegriffs abzurufen. Die InnoDB-Speicher-Engine von MySQL verwendet einen B+-Baum als Indeximplementierung.

Oben ist die vom Herausgeber eingeführte detaillierte Integration der Mehrwege-Suchbäume B-Baum und B+-Baum. Ich hoffe, es wird allen helfen. Wenn Sie Fragen haben, hinterlassen Sie mir bitte eine Nachricht und der Herausgeber wird Ihnen rechtzeitig antworten. Ich möchte auch allen für ihre Unterstützung der Website 123WORDPRESS.COM danken!