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 der Seite, untere und obere Offsets, die den leeren Raum markieren (zum Anhängen von Zelloffsets und Daten), und andere nützliche Metadaten.

Für speichert PostgreSQL beispielsweise die Seitengröße und die Layout-Version im Header. In MySQL InnoDB enthält der Seitenkopf die Anzahl der Heap-Records, die Ebene und einige andere implementierungsspezifische Werte. In SQLite speichert der Seitenkopf die Anzahl der Zellen und einen Zeiger nach rechts.

Magische Zahlen

Eine der Werte, die oft im Datei- oder Seitenkopf stehen, ist eine magische Zahl. Dabei handelt es sich in der Regel um einen Multibyte-Block, der einen konstanten Wert enthält, mit dem signalisiert werden kann, dass der Block eine Seite repräsentiert, die Art der Seite spezifiziert oder ihre Version identifiziert.

Magische Zahlen werden oft für die Validierung von und zur Überprüfung der Richtigkeit verwendet [GIAMPAOLO98]. Es ist sehr unwahrscheinlich, dass die Bytefolge bei einem zufälligen Offset genau mit der magischen Zahl übereinstimmt. Wenn sie übereinstimmt, ist die Wahrscheinlichkeit groß, dass der Offset korrekt ist. Um zum Beispiel zu überprüfen, ob die Seite richtig geladen und ausgerichtet ist, können wir beim Schreiben die magische Zahl 50 41 47 45 (hexadezimal für PAGE) in den Header eingeben. Beim Lesen überprüfen wir die Seite, indem wir die vier Bytes aus dem Lesekopf mit der erwarteten Bytefolge vergleichen.

Zeiger ganz rechts

B-Tree-Trennschlüssel haben strenge Invarianten: Sie werden verwendet, um den Baum in Unterbäume aufzuteilen und in diesen zu navigieren, so dass es immer einen Zeiger mehr auf Unterseiten gibt als Schlüssel vorhanden sind. Daher kommt die +1, die in "Schlüssel zählen" erwähnt wird.

In "Separator Keys" haben wir die Invarianten von Separator Keys beschrieben. In vielen Implementierungen sehen die Knoten eher so aus wie in Abbildung 4-2: Jeder Trennschlüssel hat einen untergeordneten Zeiger, während der letzte Zeiger separat gespeichert wird, da er nicht mit einem Schlüssel gepaart ist. Du kannst dies mit Abbildung 2-10 vergleichen.

dbin 0402
Abbildung 4-2. Zeiger ganz rechts

Dieser zusätzliche Zeiger kann im Header gespeichert werden, wie er zum Beispiel in SQLite implementiert ist.

Wenn das rechte untergeordnete Element geteilt und die neue Zelle an das übergeordnete Element angehängt wird, muss der Zeiger auf das rechte untergeordnete Element neu zugewiesen werden. Wie in Abbildung 4-3 zu sehen ist, hat die Zelle, die an das übergeordnete Element angehängt wurde (grau dargestellt), nach der Aufteilung den beförderten Schlüssel und zeigt auf den aufgeteilten Knoten. Der Zeiger auf den neuen Knoten wird anstelle des vorherigen Zeigers ganz rechts zugewiesen. Ein ähnlicher Ansatz ist in SQLite beschrieben und implementiert.1

dbin 0403
Abbildung 4-3. Aktualisierung des Zeigers ganz rechts während des Node Splits. Der beförderte Schlüssel wird in grau dargestellt.

Knoten-Highkeys

Wir können einen etwas anderen Ansatz wählen und den Zeiger ganz rechts in der Zelle zusammen mit dem High Key des Knotens speichern. Der hohe Schlüssel stellt den höchstmöglichen Schlüssel dar, der in dem Teilbaum unter dem aktuellen Knoten vorhanden sein kann. Dieser Ansatz wird von PostgreSQL verwendet und wird Blink-Trees genannt (zu den Auswirkungen dieses Ansatzes auf die Gleichzeitigkeit siehe "Blink-Trees").

B-Bäume haben N Schlüssel (bezeichnet mit Ki) und N + 1 Zeiger (bezeichnet mit Pi). In jedem Teilbaum sind die Schlüssel begrenzt durch Ki-1 ≤ Ks < Ki. Der K0 = -∞ ist implizit und nicht in dem Knoten vorhanden.

Blink-Trees fügen jedem Knoten einen KN+1 Schlüssel zu jedem Knoten hinzu. Er gibt eine Obergrenze der Schlüssel an, die in dem Teilbaum gespeichert werden können, auf den der Zeiger PN verweist, und ist somit eine Obergrenze für die Werte, die im aktuellen Teilbaum gespeichert werden können. Beide Ansätze sind in Abbildung 4-4 dargestellt: (a) zeigt einen Knoten ohne hohen Schlüssel und (b) zeigt einen Knoten mit einem hohen Schlüssel.

dbin 0404
Abbildung 4-4. B-Bäume ohne (a) und mit (b) einem hohen Schlüssel

In diesem Fall können Zeiger paarweise gespeichert werden, und jede Zelle kann einen entsprechenden Zeiger haben, was den Umgang mit dem rechten Zeiger vereinfachen könnte, da nicht so viele Kanten zu berücksichtigen sind.

In Abbildung 4-5 siehst du die schematische Seitenstruktur für beide Ansätze und wie der Suchraum für diese Fälle unterschiedlich aufgeteilt wird: im ersten Fall bis zu +∞ und im zweiten Fall bis zur oberen Grenze von K3 im zweiten Fall.

dbin 0405
Abbildung 4-5. Verwendung von +∞ als virtueller Schlüssel (a) versus Speicherung des hohen Schlüssels (b)

Überlaufseiten

Die Werte für die Knotengröße und die Baumaufteilung sind fest und ändern sich nicht dynamisch. Es wäre auch schwierig, einen Wert zu finden, der universell optimal wäre: Wenn Werte mit variabler Größe im Baum vorhanden und groß genug sind, passen nur wenige von ihnen auf die Seite. Wenn die Werte winzig sind, verschwenden wir am Ende den reservierten Platz.

Der B-Tree-Algorithmus legt fest, dass jeder Knoten eine bestimmte Anzahl von Elementen speichert. Da einige Werte unterschiedlich groß sind, kann es vorkommen, dass der Knoten laut B-Tree-Algorithmus noch nicht voll ist, aber auf der Seite mit der festen Größe, die diesen Knoten enthält, kein freier Platz mehr vorhanden ist. Um die Größe der Seite zu ändern, müssen bereits geschriebene Daten in die neue Region kopiert werden, was oft unpraktisch ist. Trotzdem müssen wir einen Weg finden, die Seitengröße zu erhöhen oder zu erweitern.

Um Knoten mit variabler Größe zu implementieren, ohne Daten in die neue zusammenhängende Region zu kopieren, können wir Knoten aus mehreren verknüpften Seiten aufbauen. Ein Beispiel: Die Standard-Seitengröße beträgt 4 K, und nachdem wir einige Werte eingefügt haben, ist die Datengröße auf über 4 K angewachsen. Anstatt beliebige Größen zuzulassen, dürfen die Knoten in 4-K-Schritten wachsen. Diese verlinkten Seitenerweiterungen werden Überlaufseiten genannt. Der Klarheit halber bezeichnen wir die Originalseite in diesem Abschnitt als Primärseite.

Die meisten B-Tree-Implementierungen erlauben es, nur bis zu einer bestimmten Anzahl von Nutzdatenbytes direkt im B-Tree-Knoten zu speichern und den Rest auf die Überlaufseite zu verschieben. Dieser Wert wird berechnet, indem die Knotengröße durch den Fanout geteilt wird. Mit diesem Ansatz kann es nicht passieren, dass die Seite keinen freien Platz mehr hat, da sie immer mindestens max_payload_size Bytes hat. Weitere Informationen zu Überlaufseiten in SQLite findest du im SQLite-Quellcode-Repository; sieh dir auch die MySQL-InnoDB-Dokumentation an.

Wenn die eingefügte Nutzlast größer als max_payload_size ist, wird der Knoten daraufhin überprüft, ob er bereits über eine zugehörige Überlaufseite verfügt oder nicht. Wenn bereits eine Überlaufseite existiert und genügend Platz zur Verfügung steht, werden die zusätzlichen Bytes der Nutzlast dorthin verschoben. Andernfalls wird eine neue Überlaufseite zugewiesen.

In Abbildung 4-6 siehst du eine Primärseite und eine Überlaufseite mit Datensätzen, die von der Primärseite auf die Überlaufseite zeigen, wo ihre Nutzlast weitergeht.

dbin 0406
Abbildung 4-6. Überlaufseiten

Überlaufseiten erfordern eine zusätzliche Buchführung, da sie ebenso wie die Primärseiten fragmentiert werden können. Wir müssen in der Lage sein, diesen Platz für das Schreiben neuer Daten zurückzugewinnen oder die Überlaufseite zu verwerfen, wenn sie nicht mehr benötigt wird.

Wenn die erste Überlaufseite zugewiesen wird, wird ihre Seiten-ID in der Kopfzeile der Primärseite gespeichert. Wenn eine einzige Überlaufseite nicht ausreicht, werden mehrere Überlaufseiten miteinander verknüpft, indem die ID der nächsten Überlaufseite in der Kopfzeile der vorherigen Seite gespeichert wird. Unter Umständen müssen mehrere Seiten durchlaufen werden, um den Überlaufteil für die gegebene Nutzlast zu finden .

Da Schlüssel in der Regel eine hohe Kardinalität haben, ist es sinnvoll, einen Teil des Schlüssels zu speichern, da die meisten Vergleiche auf dem gekürzten Teil des Schlüssels durchgeführt werden können, der sich auf der Primärseite befindet.

Bei Datensätzen müssen wir ihre Überlaufteile finden, um sie an den Benutzer zurückzugeben. Das macht aber nicht viel aus, da es sich um einen seltenen Vorgang handelt. Wenn alle Datensätze übergroß sind, lohnt es sich, eine spezielle Blob Speicherung für große Werte in Betracht zu ziehen.

Binäre Suche

Wir haben auf bereits den B-Tree Lookup Algorithmus besprochen (siehe "B-Tree Lookup Algorithmus") und erwähnt, dass wir einen gesuchten Schlüssel innerhalb des Knotens mithilfe des binären Suchalgorithmus finden. Die binäre Suche funktioniert nur bei sortierten Daten. Wenn die Schlüssel nicht geordnet sind, können sie nicht binär durchsucht werden. Deshalb ist es wichtig, dass die Schlüssel geordnet sind und eine Sortierinvariante beibehalten wird.

Der binäre Suchalgorithmus erhält ein Array mit sortierten Elementen und einen gesuchten Schlüssel und gibt eine Zahl zurück. Wenn die zurückgegebene Zahl positiv ist, wissen wir, dass der gesuchte Schlüssel gefunden wurde und die Zahl gibt seine Position im Eingabefeld an. Ein negativer Rückgabewert zeigt an, dass der gesuchte Schlüssel nicht im Eingabefeld vorhanden ist und gibt uns einen Einfügepunkt an.

Der Einfügepunkt ist der Index des ersten Elements, das größer ist als der angegebene Schlüssel. Ein absoluter Wert dieser Zahl ist der Index, an dem der gesuchte Schlüssel eingefügt werden kann, um die Reihenfolge zu wahren. Das Einfügen kann durch das Verschieben von Elementen um eine Position, ausgehend von einem Einfügepunkt, erfolgen, um Platz für das eingefügte Element zu schaffen [SEDGEWICK11].

Die meisten Suchen auf höheren Ebenen führen nicht zu exakten Übereinstimmungen, und wir sind an der Suchrichtung interessiert. In diesem Fall müssen wir den ersten Wert finden, der größer ist als der gesuchte und dem entsprechenden Child-Link in den zugehörigen Teilbaum folgen.

Binäre Suche mit Indirektionszeigern

Die Zellen in der B-Baum-Seite werden in der Einfügereihenfolge gespeichert, und nur die Zellenversätze bewahren die logische Elementreihenfolge. Um eine binäre Suche durch die Seitenzellen durchzuführen, wählen wir den mittleren Zelloffset aus, folgen seinem Zeiger, um die Zelle zu finden, vergleichen den Schlüssel dieser Zelle mit dem gesuchten Schlüssel, um zu entscheiden, ob die Suche links oder rechts fortgesetzt werden soll, und setzen diesen Prozess rekursiv fort, bis das gesuchte Element oder der Einfügepunkt gefunden ist, wie in Abbildung 4-7 dargestellt.

Weitergabe von Splits und Merges

Wie wir in den vorherigen Kapiteln besprochen haben, können sich B-Tree-Splits und Merges auf höhere Ebenen ausbreiten. Dazu müssen wir in der Lage sein, eine Kette vom spaltenden Blatt oder einem Paar von zusammenführenden Blättern zurück zum Wurzelknoten zu durchlaufen.

B-Baum-Knoten können Zeiger auf übergeordnete Knoten enthalten. Da Seiten aus niedrigeren Ebenen immer ausgelagert werden, wenn sie von einer höheren Ebene aus referenziert werden, ist es nicht einmal notwendig, diese Informationen auf der Festplatte zu speichern.

Genau wie Geschwisterzeiger (siehe "Geschwisterverknüpfungen") müssen auch Elternzeiger immer dann aktualisiert werden, wenn sich der Elternknoten ändert. Dies geschieht in allen Fällen, in denen der Trennungsschlüssel mit der Seitenkennung von einem Knoten auf einen anderen übertragen wird: bei der Aufteilung, Zusammenlegung oder Neuordnung des übergeordneten Knotens.

Einige Implementierungen (z. B. WiredTiger) verwenden Parent-Pointer für das Durchlaufen von Blättern, um Deadlocks zu vermeiden, die bei der Verwendung von Sibling-Pointern auftreten können (siehe [MILLER78], [LEHMAN81]). Anstatt Geschwisterzeiger zum Durchlaufen von Blattknoten zu verwenden, setzt der Algorithmus Elternzeiger ein, wie wir in Abbildung 4-1 gesehen haben.

Um ein Geschwisterkind anzusprechen und zu finden, können wir einem Zeiger vom übergeordneten Knoten folgen und rekursiv bis zur unteren Ebene hinuntersteigen. Wenn wir das Ende des übergeordneten Knotens erreichen, nachdem wir alle Geschwister des übergeordneten Knotens durchlaufen haben, wird die Suche rekursiv nach oben fortgesetzt, bis wir schließlich die Wurzel erreichen und wieder auf die Blattebene hinuntergehen.

Rebalancing

Einige B-Tree-Implementierungen versuchen, Split- und Merge-Operationen zu verschieben, um ihre Kosten zu amortisieren, indem sie Elemente innerhalb der Ebene neu ausbalancieren oder Elemente so lange wie möglich von stärker besetzten Knoten auf weniger besetzte verschieben, bevor sie schließlich einen Split oder Merge durchführen. Dies trägt dazu bei, die Belegung der Knoten zu verbessern und kann die Anzahl der Ebenen innerhalb des Baums verringern, wobei die Kosten für die Neugewichtung möglicherweise höher sind .

Der Lastausgleich kann bei Einfüge- und Löschvorgängen durchgeführt werden [GRAEFE11]. Um die Platzausnutzung zu verbessern, können wir, anstatt den Knoten bei Überlauf zu teilen, einige Elemente auf einen der Geschwisterknoten übertragen und so Platz für die Einfügung schaffen. Ähnlich verhält es sich beim Löschen: Anstatt die Geschwisterknoten zusammenzulegen, können wir einige Elemente aus den Nachbarknoten verschieben, um sicherzustellen, dass der Knoten mindestens halb voll ist.

B*-Bäume verteilen die Daten so lange zwischen den benachbarten Knoten, bis beide Geschwister voll sind [KNUTH98]. Anstatt einen einzelnen Knoten in zwei halbleere aufzuteilen, teilt der Algorithmus dann zwei Knoten in drei Knoten auf, von denen jeder zu zwei Dritteln gefüllt ist. SQLite verwendet diese Variante in der Implementierung. Dieser Ansatz verbessert die durchschnittliche Auslastung durch die Verschiebung von Splits, erfordert aber zusätzliche Verfolgungs- und Ausgleichslogik. Eine höhere Auslastung bedeutet auch eine effizientere Suche, weil die Höhe des Baums kleiner ist und weniger Seiten auf dem Weg zum gesuchten Blatt durchlaufen werden müssen.

Abbildung 4-9 zeigt die Verteilung von Elementen zwischen den benachbarten Knoten, wobei der linke Geschwisterknoten mehr Elemente enthält als der rechte. Die Elemente des stärker besetzten Knotens werden auf den weniger besetzten verschoben. Da der Ausgleich die Min/Max-Invariante der Geschwisterknoten verändert, müssen wir die Schlüssel und Zeiger am übergeordneten Knoten aktualisieren, um sie zu erhalten.

dbin 0409
Abbildung 4-9. B-Baum Ausgleich: Verteilen von Elementen zwischen dem stärker besetzten und dem weniger besetzten Knoten

Der Lastausgleich ist eine nützliche Technik, die in vielen Datenbankimplementierungen verwendet wird. SQLite implementiert zum Beispiel den Algorithmus"Balancing Siblings", der dem in diesem Abschnitt beschriebenen Verfahren sehr ähnlich ist. Das Balancing macht den Code zwar etwas komplexer, aber da die Anwendungsfälle isoliert sind, kann es zu einem späteren Zeitpunkt als Optimierung implementiert werden.

Nur Rechtsanhänge

Viele Datenbanksysteme verwenden automatisch inkrementierende, monoton steigende Werte als primäre Indexschlüssel. In diesem Fall bietet sich eine Optimierungsmöglichkeit, da alle Einfügungen gegen Ende des Index (im ganz rechten Blatt) stattfinden, so dass die meisten Splits auf dem ganz rechten Knoten auf jeder Ebene stattfinden. Da die Schlüssel monoton inkrementiert werden und das Verhältnis von Anhängen zu Aktualisierungen und Löschungen gering ist, sind auch die Nicht-Blatt-Seiten weniger fragmentiert als im Fall von zufällig angeordneten Schlüsseln.

PostgreSQL nennt diesen Fall einen Fastpath. Wenn der eingefügte Schlüssel unbedingt größer ist als der erste Schlüssel in der rechten Seite und die rechte Seite genug Platz für den neu eingefügten Eintrag hat, wird der neue Eintrag an der entsprechenden Stelle im rechten Blatt im Cache eingefügt und der gesamte Lesepfad kann übersprungen werden.

SQLite hat ein ähnliches Konzept und nennt es quickbalance. Wenn der Eintrag ganz rechts eingefügt wird und der Zielknoten voll ist (d.h. er wird beim Einfügen zum größten Eintrag im Baum), wird, anstatt den Knoten neu auszubalancieren oder aufzuteilen, der neue Knoten ganz rechts zugewiesen und sein Zeiger zum übergeordneten Knoten hinzugefügt (mehr zur Implementierung von Balancing in SQLite siehe "Rebalancing"). Auch wenn dadurch die neu erstellte Seite fast leer bleibt (statt halb leer wie bei einer Knotenaufteilung), ist es sehr wahrscheinlich, dass der Knoten bald gefüllt wird.

Bulk Loading

Wenn wir vorsortierte Daten haben und diese in großen Mengen laden wollen oder den Baum neu aufbauen müssen (z. B. für eine Defragmentierung), können wir die Idee mit den nur rechts stehenden Anhängen noch weiter ausbauen. Da die Daten, die für die Erstellung des Baums benötigt werden, bereits sortiert sind, müssen wir beim Bulk-Loading nur die Elemente an der äußersten rechten Stelle des Baums anhängen.

In diesem Fall können wir Splits und Merges ganz vermeiden und den Baum von unten nach oben zusammensetzen, indem wir ihn Ebene für Ebene ausschreiben oder Knoten höherer Ebenen ausschreiben, sobald wir genügend Zeiger auf bereits geschriebene Knoten niedrigerer Ebenen haben.

Ein Ansatz für die Implementierung des Bulk Loading besteht darin, vorsortierte Daten auf der Blattebene seitenweise zu schreiben (anstatt einzelne Elemente einzufügen). Nachdem die Blattseite geschrieben wurde, propagieren wir ihren ersten Schlüssel an die übergeordnete Seite und verwenden einen normalen Algorithmus zum Aufbau höherer B-Baum-Ebenen [RAMAKRISHNAN03]. Da die angehängten Schlüssel in der sortierten Reihenfolge angegeben werden, finden alle Splits in diesem Fall am ganz rechten Knoten statt.

Da B-Bäume immer von der untersten (Blatt-)Ebene aus aufgebaut werden, kann die komplette Blattebene ausgeschrieben werden, bevor die Knoten der höheren Ebene zusammengesetzt werden. So haben wir alle Kindzeiger zur Hand, wenn die höheren Ebenen aufgebaut werden. Die Hauptvorteile dieses Ansatzes sind, dass wir keine Splits oder Merges auf der Festplatte durchführen müssen und gleichzeitig nur einen minimalen Teil des Baums (d. h. alle Eltern des aktuell füllenden Blattknotens) für die Zeit der Konstruktion im Speicher behalten müssen.

Unveränderliche B-Bäume können auf die gleiche Weise erstellt werden, aber im Gegensatz zu veränderbaren B-Bäumen benötigen sie keinen Platz für spätere Änderungen, da alle Operationen an einem Baum endgültig sind. Alle Seiten können vollständig ausgefüllt werden, was die Auslastung und damit die Leistung verbessert.

Komprimierung

Die unkomprimierten Rohdaten können einen erheblichen Overhead verursachen, und viele Datenbanken bieten Möglichkeiten, sie zu komprimieren, um Platz zu sparen. Der offensichtliche Kompromiss liegt hier zwischen der Zugriffsgeschwindigkeit und der Komprimierungsrate: Größere Komprimierungsraten können die Datengröße verbessern, so dass du mehr Daten in einem einzigen Zugriff abrufen kannst, benötigen aber möglicherweise mehr RAM und CPU-Zyklen, um sie zu komprimieren und zu dekomprimieren.

Die Komprimierung kann auf verschiedenen Granularitätsebenen erfolgen. Auch wenn die Komprimierung ganzer Dateien bessere Komprimierungsraten erzielen kann, ist sie nur begrenzt anwendbar, da die gesamte Datei bei einer Aktualisierung neu komprimiert werden muss. Die Komprimierung einer gesamten Indexdatei ist unpraktisch und schwer effizient zu implementieren: Um eine bestimmte Seite anzusprechen, muss die gesamte Datei (oder der Abschnitt mit den Komprimierungsmetadaten) aufgerufen (um einen komprimierten Abschnitt zu finden), dekomprimiert und verfügbar gemacht werden.

Eine Alternative ist, die Daten seitenweise zu komprimieren. Das passt gut zu unserer Diskussion, denn die Algorithmen, die wir bisher besprochen haben, verwenden Seiten mit fester Größe. Seiten können unabhängig voneinander komprimiert und dekomprimiert werden, so dass du die Komprimierung mit dem Laden und Flushen von Seiten verbinden kannst. Allerdings kann eine komprimierte Seite in diesem Fall nur einen Bruchteil eines Plattenblocks einnehmen, und da Übertragungen in der Regel in Einheiten von Plattenblöcken erfolgen, kann es notwendig sein, zusätzliche Bytes einzulagern [RAY95]. In Abbildung 4-10 siehst du eine komprimierte Seite (a), die weniger Platz benötigt als ein Plattenblock. Wenn wir diese Seite laden, blenden wir auch zusätzliche Bytes ein, die zu der anderen Seite gehören. Bei Seiten, die sich über mehrere Plattenblöcke erstrecken, wie (b) im gleichen Bild, müssen wir einen zusätzlichen Block lesen.

dbin 0410
Abbildung 4-10. Komprimierung und Blockauffüllung

Ein anderer Ansatz besteht darin, nur die Daten zu komprimieren, entweder zeilenweise (Komprimierung ganzer Datensätze) oder spaltenweise (Komprimierung einzelner Spalten). In diesem Fall sind die Seitenverwaltung und die Komprimierung entkoppelt.

Die meisten Open-Source-Datenbanken, die beim Schreiben dieses Buches überprüft wurden, verfügen über anpassbare Komprimierungsmethoden, die auf verfügbaren Bibliotheken wie Snappy, zLib, lz4 und vielen anderen basieren.

Da Kompressionsalgorithmen je nach Datensatz und möglichen Zielen (z. B. Kompressionsverhältnis, Leistung oder Speicher-Overhead) unterschiedliche Ergebnisse liefern, werden wir in diesem Buch nicht auf Vergleiche und Implementierungsdetails eingehen. Es gibt viele Übersichten, die verschiedene Kompressionsalgorithmen für unterschiedliche Blockgrößen bewerten (z. B. Squash Compression Benchmark) und sich dabei in der Regel auf vier Kennzahlen konzentrieren: Speicher-Overhead, Kompressionsleistung, Dekompressionsleistung und Kompressionsverhältnis. Diese Kennzahlen sind wichtig, wenn du eine Kompressionsbibliothek auswählst.

Vakuum und Wartung

Bisher haben wir hauptsächlich über die benutzerseitigen Vorgänge in B-Trees gesprochen. Es gibt jedoch noch andere Prozesse, die parallel zu den Abfragen ablaufen und die Integrität der Speicherung aufrechterhalten, Speicherplatz zurückgewinnen, den Overhead reduzieren und die Seiten in Ordnung halten. Indem wir diese Vorgänge im Hintergrund ausführen, können wir Zeit sparen und vermeiden, dass wir bei Einfügungen, Aktualisierungen und Löschungen den Preis für Aufräumarbeiten zahlen müssen.

Das beschriebene Design von slotted pages (siehe "Slotted Pages") erfordert, dass die Seiten gewartet werden, um sie in gutem Zustand zu halten. Zum Beispiel können nachfolgende Splits und Merges in internen Knoten oder Inserts, Updates und Deletes auf der Blattebene dazu führen, dass eine Seite genug logischen Platz hat, aber nicht genug zusammenhängenden Platz, da sie fragmentiert ist. Abbildung 4-11 zeigt ein Beispiel für eine solche Situation: Die Seite verfügt noch über einen gewissen logischen Speicherplatz, der jedoch fragmentiert ist und zwischen den beiden gelöschten (Garbage-)Datensätzen und dem verbleibenden freien Speicherplatz zwischen den Header-/Zellzeigern und Zellen aufgeteilt ist.

dbin 0411
Abbildung 4-11. Ein Beispiel für eine fragmentierte Seite

B-Trees werden von der Wurzelebene aus navigiert. Datensätze, die erreicht werden können, indem man vom Wurzelknoten aus Zeigern nach unten folgt, sind live (adressierbar). Nicht adressierbare Datensätze werden als Müll bezeichnet: Diese Datensätze werden nirgendwo referenziert und können weder gelesen noch interpretiert werden, sodass ihr Inhalt so gut wie nichtig ist.

Du kannst diesen Unterschied in Abbildung 4-11 sehen: Zellen, die noch Zeiger auf sie haben, sind adressierbar, im Gegensatz zu den entfernten oder überschriebenen Zellen. Aus Leistungsgründen wird das Auffüllen von Garbage Areas oft übersprungen, da diese Bereiche irgendwann sowieso von den neuen Daten überschrieben werden.

Durch Aktualisierungen und Löschungen verursachte Fragmentierung

Betrachten wir unter welchen Umständen Seiten in einen Zustand geraten, in dem sie nicht adressierbare Daten haben und verdichtet werden müssen. Auf der Blattebene werden beim Löschen nur die Offsets der Zelle aus der Kopfzeile entfernt, die Zelle selbst bleibt jedoch intakt. Danach ist die Zelle nicht mehr adressierbar, ihr Inhalt erscheint nicht in den Abfrageergebnissen, und es ist nicht nötig, sie zu löschen oder benachbarte Zellen zu verschieben.

Wenn die Seite geteilt wird, werden nur die Offsets gekürzt. Da der Rest der Seite nicht adressierbar ist, sind die Zellen, deren Offsets gekürzt wurden, nicht erreichbar, so dass sie überschrieben werden, wenn die neuen Daten ankommen, oder zu Müll werden, wenn der Vakuumprozess einsetzt.

Hinweis

Einige Datenbanken verlassen sich auf die Speicherbereinigung und lassen entfernte und aktualisierte Zellen für die Multiversions-Gleichzeitigkeitskontrolle stehen (siehe "Multiversions-Gleichzeitigkeitskontrolle"). Die Zellen bleiben für die gleichzeitig ausgeführten Transaktionen zugänglich, bis die Aktualisierung abgeschlossen ist, und können eingesammelt werden, sobald kein anderer Thread auf sie zugreift. Einige Datenbanken unterhalten Strukturen, die Ghost Records verfolgen, die eingesammelt werden, sobald alle Transaktionen, die sie möglicherweise gesehen haben, abgeschlossen sind [WEIKUM01].

Da beim Löschen nur die Offsets der Zellen verworfen werden und die verbleibenden Zellen nicht verschoben oder die Zielzellen physisch entfernt werden, um den freigewordenen Platz zu belegen, können die freigegebenen Bytes über die Seite verstreut sein. In diesem Fall sagen wir, dass die Seite fragmentiert ist und defragmentiert werden muss .

Für einen Schreibvorgang benötigen wir oft einen zusammenhängenden Block freier Bytes, in den die Zelle passt. Um die freigewordenen Fragmente wieder zusammenzufügen und diese Situation zu beheben, müssen wir die Seite neu schreiben.

Bei Einfügevorgängen bleiben die Tupel in ihrer Einfügereihenfolge. Das hat zwar keine so großen Auswirkungen, aber natürlich sortierte Tupel können beim Cache-Prefetch bei sequentiellen Lesevorgängen helfen.

Aktualisierungen werden hauptsächlich auf der Blattebene vorgenommen: Interne Seitenschlüssel werden für die geführte Navigation verwendet und definieren nur die Grenzen der Teilbäume. Außerdem werden Aktualisierungen pro Schlüssel durchgeführt und führen im Allgemeinen nicht zu strukturellen Änderungen im Baum, abgesehen von der Erstellung von Überlaufseiten. Auf der Blattebene hingegen ändern Aktualisierungsvorgänge die Reihenfolge der Zellen nicht und versuchen, das Neuschreiben von Seiten zu vermeiden. Das bedeutet, dass mehrere Versionen der Zelle, von denen nur eine adressierbar ist, gespeichert werden können.

Defragmentierung der Seite

Der Prozess, der sich um die Rückgewinnung von Speicherplatz und das Neuschreiben von Seiten kümmert, wird Verdichtung, Vakuum oder einfach Wartung genannt. Das Neuschreiben von Seiten kann synchron beim Schreiben erfolgen, wenn die Seite nicht genügend freien Platz hat (um zu vermeiden, dass unnötige Überlaufseiten erstellt werden), aber die Verdichtung wird meist als ein eigenständiger, asynchroner Prozess bezeichnet, bei dem Seiten durchlaufen, Speicherbereinigung durchgeführt und ihr Inhalt neu geschrieben wird.

Bei diesem Vorgang wird der von toten Zellen belegte Platz zurückgewonnen und die Zellen werden in ihrer logischen Reihenfolge neu geschrieben. Wenn Seiten neu geschrieben werden, können sie auch an neue Positionen in der Datei verschoben werden. Ungenutzte Seiten im Speicher werden verfügbar und gehen zurück in den Seiten-Cache. Die IDs der neu verfügbaren Festplattenseiten werden der Liste der freien Seiten hinzugefügt (manchmal auch Freelist genannt3). Diese Informationen müssen aufbewahrt werden, um Knotenabstürze und Neustarts zu überstehen und um sicherzustellen, dass kein freier Speicherplatz verloren geht oder verloren geht.

Zusammenfassung

In diesem Kapitel haben wir die Konzepte besprochen, die für B-Tree-Implementierungen auf der Festplatte spezifisch sind, wie z. B.:

Seitenüberschrift

Welche Informationen werden dort normalerweise gespeichert?

Zeiger ganz rechts

Diese sind nicht mit Trennungsschlüsseln gepaart, und wie man sie behandelt.

Hohe Tasten

Bestimme den maximal zulässigen Schlüssel, der in dem Knoten gespeichert werden kann.

Überlaufseiten

Ermöglicht es dir, Datensätze mit Übergröße und variabler Größe auf Seiten mit fester Größe zu speichern.

Danach haben wir uns einige Details zum Root-to-Leaf-Traversal angesehen:

  • Wie man eine binäre Suche mit Umleitungszeigern durchführt

  • Wie man den Überblick über Baumhierarchien mit Hilfe von Elternzeigern oder Breadcrumbs behält

Zum Schluss haben wir noch einige Optimierungs- und Wartungstechniken besprochen:

Rebalancing

Verschiebt Elemente zwischen benachbarten Knoten, um die Anzahl der Splits und Merges zu reduzieren.

Nur rechts anhängen

Hängt die neue Zelle ganz rechts an, anstatt sie zu teilen, in der Annahme, dass sie sich schnell füllen wird.

Schüttgutverladung

Eine Technik zur effizienten Erstellung von B-Trees aus sortierten Daten.

Speicherbereinigung

Ein Prozess, der die Seiten umschreibt, die Zellen in die richtige Reihenfolge bringt und den Platz von nicht adressierbaren Zellen zurückgewinnt.

Diese Konzepte sollen die Lücke zwischen dem grundlegenden B-Tree-Algorithmus und einer realen Implementierung schließen und dir helfen, besser zu verstehen, wie B-Tree-basierte Speichersysteme funktionieren.

1 Du findest diesen Algorithmus in der Funktion balance_deeper in der Projektdatenbank.

2 Du kannst mehr darüber in der Projektdatenbank lesen: https://databass.dev/links/21.

3 SQLite verwaltet zum Beispiel eine Liste von Seiten, die nicht von der Datenbank verwendet werden, wobei die Stammseiten in einer verknüpften Liste gehalten werden und die Adressen der freigegebenen Seiten enthalten.

Get Datenbank Interna now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial