Kapitel 4. B-Bäume implementieren
Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: translation-feedback@oreilly.com
Im vorigen Kapitel haben wir über die allgemeinen Prinzipien der Zusammensetzung von Binärformaten gesprochen und gelernt, wie man Zellen erstellt, Hierarchien aufbaut und sie mit Hilfe von Zeigern mit Seiten verbindet. Diese Konzepte gelten sowohl für die In-Place-Update- als auch für die Append-Only-Speicherstrukturen. In diesem Kapitel besprechen wir einige Konzepte, die speziell für B-Trees gelten.
Die Abschnitte in diesem Kapitel sind in drei logische Gruppen unterteilt. Zunächst geht es um die Organisation: wie man Beziehungen zwischen Schlüsseln und Zeigern herstellt und wie man Kopfzeilen und Links zwischen Seiten implementiert.
Als Nächstes besprechen wir die Prozesse, die während des Abstiegs von der Wurzel zum Blatt ablaufen, nämlich wie man eine binäre Suche durchführt und wie man Breadcrumbs sammelt und den Überblick über die Elternknoten behält, falls wir später Knoten aufteilen oder zusammenführen müssen.
Schließlich werden Optimierungstechniken (Rebalancing, Right-Only Appends und Bulk Loading), Wartungsprozesse und Speicherbereinigung besprochen.
Seitenüberschrift
Der Seitenkopf enthält Informationen über die Seite, die für die Navigation, Wartung und Optimierung verwendet werden können. Er enthält in der Regel Flags, die den Inhalt und das Layout der Seite beschreiben, die Anzahl der Zellen auf ...