Datenbank Interna

Kapitel 6. B-Baum-Varianten

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

B-Tree-Varianten haben ein paar Dinge gemeinsam: die Baumstruktur, den Ausgleich durch Splits und Merges sowie Lookup- und Delete-Algorithmen. Andere Details, die die Gleichzeitigkeit, die Darstellung der Seiten auf der Festplatte, die Verbindungen zwischen Geschwisterknoten und die Wartungsprozesse betreffen, können zwischen den Implementierungen variieren.

In diesem Kapitel werden wir verschiedene Techniken besprechen, mit denen sich effiziente B-Trees und Strukturen, die sie verwenden, implementieren lassen:

• Copy-on-write B-Trees sind wie B-Trees strukturiert, aber ihre Knoten sind unveränderlich und werden nicht an Ort und Stelle aktualisiert. Stattdessen werden die Seiten kopiert, aktualisiert und an neue Stellen geschrieben.

• Lazy B-Trees reduzieren die Anzahl der E/A-Anfragen durch nachfolgende Schreibvorgänge an denselben Knoten, indem sie Aktualisierungen an den Knoten puffern. Im nächsten Kapitel befassen wir uns auch mit Zwei-Komponenten-LSM-Bäumen (siehe "Zwei-Komponenten-LSM-Baum"), bei denen die Pufferung noch einen Schritt weiter geht, um vollständig unveränderliche B-Bäume zu implementieren.

• FD-Trees verfolgen einen anderen Ansatz bei der Pufferung, ähnlich wie LSM-Trees (siehe "LSM-Trees"). FD-Trees puffern Aktualisierungen in einem kleinen B-Tree. Sobald dieser Baum voll ist, wird sein Inhalt in ...