- Beim jüngsten Lesen von Alex Petrovs Database Internals bin ich darauf gestoßen, wie DBMS-Storage-Engines implementiert werden, insbesondere im Zusammenhang mit Optimierungen der B-Tree-Datenstruktur
- Als ich B-Bäume an der Universität gelernt habe, verstand ich sie nur als eine Art „besserer BST“, weshalb mir ihr tatsächlicher Einsatznutzen nicht wirklich klar wurde
- Für das Speichern großer Datenmengen und schnelle Suchen unter Berücksichtigung von Festplatten-I/O eignet sich die B-Tree-Struktur gut
- Dieser Artikel stellt vor, warum B-Bäume notwendig sind, wie sie funktionieren und welche Optimierungen in realen Implementierungen möglich sind
- Zu den wichtigsten Merkmalen gehört, viele Schlüssel in einem Knoten zu bündeln, um die Zahl der Festplattenzugriffe zu verringern
Einschränkungen durch die Festplatte
- Es wird von einer Situation ausgegangen, in der nicht alle Daten in den Speicher passen
- Festplatten lesen und schreiben grundsätzlich in Seiten
- Festplattenzugriffe sind im Vergleich zu Speicherzugriffen sehr langsam
- Deshalb muss eine Datenstruktur Daten seitenzentriert anordnen und mit möglichst wenigen Festplattenzugriffen möglichst viele Schlüsselvergleiche durchführen
- Speichert man einen BST unverändert auf der Festplatte, liegen die Knoten verstreut, sodass mit jeder Suche auch die Zahl der Festplattenzugriffe steigt
- Ein B-Tree bündelt mehrere Schlüssel in einem Knoten, damit schon ein einzelner Festplattenzugriff den Vergleich mehrerer Schlüssel ermöglicht
Slotted Pages
- Beim Ablegen von Daten auf der Festplatte wird in „Pages“ verwaltet
- Jede Page enthält einen Header, Zellen für Daten variabler Länge und ein Array von Offset-Pointern mit den Zellpositionen
- Die Struktur von Slotted Pages hat den Vorteil, dass sich die Sortierreihenfolge auch bei variabler Schlüssellänge ohne großen Umordnungsaufwand erhalten lässt
- Beim Löschen oder Einfügen von Schlüsseln ist es deutlich effizienter, nur Pointer neu anzuordnen, statt die eigentlichen Daten zu verschieben
- SQLite verwendet beispielsweise innerhalb dieser Seitenstruktur eine Free List, um den Platz gelöschter Zellen wiederzuverwenden
B-Tree-Abfrage
- Der B-Tree-Suchalgorithmus ist einfach:
- Am Wurzelknoten beginnen
- Anhand der Separator Keys des aktuellen Knotens den Kindknoten finden, in dem sich der Suchschlüssel vermutlich befindet
- Den Baum rekursiv durchsuchen
- Ist der Blattknoten mit dem Suchschlüssel gefunden, ist die Suche abgeschlossen; andernfalls gilt der Schlüssel als nicht vorhanden
- In internen Knoten müssen statt der eigentlichen Daten oft nur Separator Keys liegen; die tatsächlichen Daten werden üblicherweise nur in Blattknoten gespeichert
- Damit sich Schlüssel innerhalb eines Knotens effizient per binärer Suche finden lassen, bleiben sie dort sortiert
Kürzung von Separator Keys
- Separator Keys in internen Knoten müssen nicht den vollständigen eigentlichen Schlüssel enthalten; es genügt, wenn sie Bereiche voneinander abgrenzen können
- Um etwa zwischen 0xAAAAAA und 0xBBBBBB zu unterscheiden, muss nicht zwingend 0xBBBBBB vollständig gespeichert werden; eine kürzere Präfixform kann zur Abgrenzung ausreichen
- In Datenbanken mit langen Schlüsseln kann diese Kürzung erheblich Speicherplatz sparen
- Neben der Kürzung von Separator Keys gibt es auch Strategien, Präfixe und Suffixe effizient zu verkleinern
- Da es sehr viel mehr Blattknoten gibt, wird teils die Ansicht vertreten, dass Präfixkompression stärker zur Performance beiträgt
Overflow Pages
- Wenn ein Knoten so viele Schlüssel enthält, dass sie nicht in eine einzelne Page passen, werden Overflow Pages verwendet
- Statt den vollständigen Schlüssel unverändert in eine Overflow Page zu verschieben, bleibt im Knoten nur ein kurzes Präfix zurück, während der Rest separat gespeichert wird
- So wird bei Existenzprüfungen oder Bereichsabfragen zunächst nur das Präfix im Knoten geprüft, und die Overflow Page wird nur gelesen, wenn es wirklich nötig ist
- Auch wenn dafür zusätzliche Pages allokiert werden, lassen sich so die gesamten Suchkosten senken
Geschwister-Pointer
- Es gibt Implementierungen, in denen Knoten Pointer auf ihre linken und rechten Geschwisterknoten speichern
- Dadurch kann man bei Bereichsabfragen von einem Blattknoten direkt zu Geschwisterknoten springen und zusammenhängende Schlüssel schnell durchsuchen
- Ohne solche Geschwister-Pointer müsste man wiederholt zum Elternknoten hinauf- und von dort wieder hinabsteigen, was die I/O-Kosten erhöht
- Da sich die Schlüsselbereiche zwischen Geschwisterknoten nicht überlappen, garantiert ein Wechsel über den rechten Geschwister-Pointer den Übergang zum „nächsten Schlüsselbereich“
B-Tree-Varianten
- Neben dem B⁺-Tree gibt es verschiedene weitere Varianten
- „Lazy B-Tree“ wie in WiredTiger oder der Lazy-Adaptive Tree erhöhen die Performance, indem sie Schreiboperationen puffern
- Der FD-Tree ist eine auf SSD-Eigenschaften abgestimmte Struktur, die physische Einschränkungen wie blockweises Schreiben berücksichtigt
- Der Bw-Tree (Buzzword Tree) ist eine Datenstruktur, die für hohe Parallelität und Baumzugriffe im Speicher optimiert ist
Fazit
- Zwischen dem abstrakten Konzept des „B⁺-Tree“ und einer realen Implementierung wie dem „DB-Format von SQLite“ liegen viele Optimierungen und feine Implementierungsunterschiede
- Optimierungen ändern zwar nicht die Big-O-Komplexität, haben in der Praxis aber großen Einfluss auf Datenbank-Performance und Nutzbarkeit
- Zusätzlich zu den hier vorgestellten Inhalten ist in jedem konkreten Storage-System noch viel Feintuning nötig
- Hinter der Formulierung „es braucht nur ein wenig Zusatzinformation“ verbergen sich Implementierungskomplexität und schwieriges Debugging
- Als anschauliches Beispiel für eine realistischere Darstellung der B-Tree-Struktur ist das B-Tree-Diagramm in Designing Data Intensive Applications besonders eindrucksvoll
1 Kommentare
Hacker-News-Kommentare
Die Struktur der Seite besteht aus Header, Zellen und Offset-Zeigern und hat den Vorteil, Daten variabler Größe speichern zu können
Ein hervorragender Artikel über B-Bäume, einschließlich Animationen
Vor einigen Jahren wurde auf Basis der Forschung von Ibrahim Jaluta ein gleichzeitig wiederherstellbarer B-link-Tree implementiert
Es wurde ein SQLite-Disk-Page-Explorer erstellt, um B-Bäume besser zu verstehen
Inhalte zu B-link-Trees, Nebenläufigkeit und Sperren fehlen, aber das könnte mehr Information sein als nötig
Früherer Kommentar: Hacker News
Ein großartiger Artikel, der die Bedeutung von Details gut erklärt
Gutes Material zur Implementierung von B-Bäumen mit Golang
Ich bin ein großer Fan dieses Artikels und hatte eine ähnliche "vage Vorstellung" wie der Autor