B-Bäume und Datenbankindizes

Was ist ein B-Baum?

• B-Bäume bilden die Grundlage vieler Software-Systeme, insbesondere von Datenbankmanagementsystemen (DBMS)

• MySQL, Postgres, MongoDB, Dynamo und andere verlassen sich auf B-Bäume, um über Indizes effiziente Datenabfragen durchzuführen

• Es wird erklärt, wie B-Bäume und B+-Bäume funktionieren, warum Datenbanken sie für Indizes verwenden und warum die Verwendung von UUIDs als Primärschlüssel eine schlechte Idee sein kann

• Ein B-Baum speichert Datenpaare, die als Schlüssel und Werte bekannt sind, in einer Struktur, die Programmierer als baumartig bezeichnen

• Ein B-Baum besteht aus Knoten (Rechtecke) und Kind-Pointern (Linien, die die Knoten verbinden)

• Der oberste Knoten wird Wurzelknoten, die unterste Ebene Blattknoten und alle übrigen Knoten interne Knoten genannt

• Hier ist die Definition eines B-Baums:

  • Jeder Knoten speichert N Schlüssel/Wert-Paare (wobei N größer als 1 und kleiner oder gleich K ist)
  • Jeder interne Knoten hat mindestens N/2 Schlüssel/Wert-Paare (interne Knoten sind keine Blatt- oder Wurzelknoten)
  • Jeder Knoten hat N+1 Kinder
  • Der Wurzelknoten hat mindestens einen Wert und zwei Kinder, sofern er nicht der einzige Knoten ist
  • Alle Blätter befinden sich auf derselben Ebene

• Eine weitere Kerneigenschaft von B-Bäumen ist die Sortierung. Innerhalb jedes Knotens werden die Elemente in Reihenfolge gehalten

• Dadurch lassen sich Schlüssel sehr effizient suchen. Die Suche beginnt am Wurzelknoten und läuft so ab:

  1. Prüfen, ob der gesuchte Schlüssel im Knoten enthalten ist
  2. Falls nicht, die Position im Knoten finden, an der der Schlüssel bei einer Einfügung eingefügt würde
  3. An diesem Punkt dem Kind-Pointer zur nächsten Ebene folgen und den Prozess wiederholen

• Bei einer Suche auf diese Weise muss zur Suche nach einem einzelnen Schlüssel auf jeder Ebene des Baums nur ein Knoten besucht werden

• B-Bäume wurden speziell dafür entwickelt, gut mit sehr großen Datenmengen zu arbeiten, die dauerhaft im Langzeitspeicher (Festplatte) abgelegt werden müssen. Der Grund dafür ist, dass jeder Knoten eine feste Anzahl an Bytes verwendet

• Wie viele Werte jeder Knoten in einem B-Baum speichern kann, hängt von der ihm zugewiesenen Byte-Anzahl und der Zahl der Bytes ab, die jedes Schlüssel/Wert-Paar verbraucht

B+-Baum (für Datenbanken optimiert)

• Ein B+-Baum ist einem B-Baum ähnlich, aber mit folgenden geänderten Regeln:
  • Schlüssel/Wert-Paare werden nur in Blattknoten gespeichert
  • Nicht-Blattknoten speichern nur Schlüssel und die damit verknüpften Kind-Pointer
• Bei der Implementierung von B+-Bäumen in MySQL-Indizes gibt es zwei zusätzliche spezifische Regeln:
  • Nicht-Blattknoten speichern N Kind-Pointer statt N+1
  • Alle Knoten enthalten zusätzlich einen „Nächster“- und „Vorheriger“-Pointer, sodass jede Ebene des Baums auch als doppelt verkettete Liste dienen kann
• Es gibt zwei Gründe, warum B+-Bäume besser für Datenbanken geeignet sind:
  1. Da interne Knoten keine Werte speichern müssen, passen mehr Schlüssel pro internem Knoten hinein. Das hilft, die Tiefe des Baums zu verringern
  2. Alle Werte werden auf derselben Ebene gespeichert und können über die verkettete Liste der untersten Ebene der Reihe nach durchlaufen werden

Verwendung von B+-Bäumen in MySQL

• MySQL unterstützt mehrere Storage Engines, und die am häufigsten verwendete ist InnoDB, die stark auf B+-Bäume angewiesen ist
• Tatsächlich ist InnoDB so stark davon abhängig, dass alle Tabellendaten in einem B+-Baum gespeichert werden, wobei der Primärschlüssel der Tabelle als Baumschlüssel dient
• Jedes Mal, wenn eine neue InnoDB-Tabelle erstellt wird, muss ein Primärschlüssel angegeben werden
• MySQL erstellt für jede neue Tabelle einen B+-Baum, und der als Primärschlüssel definierte Wert wird zum Schlüssel des Baums. Der Wert besteht aus den übrigen Spaltenwerten jeder Zeile und wird nur in Blattknoten gespeichert
• Die Knotengröße jedes solchen B+-Baums ist standardmäßig auf 16k gesetzt
• Immer wenn MySQL auf einen Datenteil zugreifen muss (Schlüssel, Wert usw.), lädt es die gesamte zugehörige Seite (den B+-Baum-Knoten) von der Festplatte, auch wenn keine anderen Schlüssel oder Werte benötigt werden
• Es ist außerdem üblich, auf InnoDB-Tabellen Sekundärindizes anzulegen. Für jeden Sekundärindex wird ein zusätzlicher persistenter B+-Baum aufgebaut, dessen Schlüssel die vom Benutzer für den Index gewählte Spalte ist und dessen Wert der Primärschlüssel der verknüpften Zeile ist

Wahl des Primärschlüssels: Einfügungen

• Da die Anordnung der Tabellendaten im B+-Baum vom gewählten Schlüssel abhängt, beeinflusst die Wahl des PRIMARY KEY das Festplattenlayout aller Daten der Tabelle
• Zwei häufig gewählte Primärschlüssel sind:
  • eine Ganzzahl-Sequenz (BIGINT UNSIGNED AUTO_INCREMENT usw.)
  • UUID (davon gibt es mehrere Versionen)
• Betrachtet man die Folgen eines UUIDv4-Primärschlüssels, dann gilt beim Einfügen:
  1. Der für das Einfügen besuchte Knoten lässt sich nicht im Voraus vorhersagen
  2. Der Ziel-Blattknoten für das Einfügen lässt sich nicht vorhersagen
  3. Die Werte in den Blättern sind nicht sortiert
• Problem 1 und 2 entstehen, weil bei vielen Einfügungen viele Knoten (Seiten) des Baums besucht werden müssen. Dieses übermäßige Lesen und Schreiben führt zu schlechterer Performance
• Wird BIGINT UNSIGNED AUTO_INCREMENT als Primärschlüssel verwendet:
  1. Beim Einfügen neuer Werte wird immer dem rechtesten Pfad gefolgt
  2. Blätter werden nur auf der rechten Seite des Baums hinzugefügt
  3. Auf der Blattebene sind die Daten in der Reihenfolge der Einfügung sortiert
• Wegen 1 und 2 besuchen viele aufeinanderfolgende Einfügungen denselben Seitenpfad erneut, wodurch beim Einfügen vieler Schlüssel/Wert-Paare weniger I/O-Anfragen nötig sind

Wahl des Primärschlüssels: Daten in Reihenfolge lesen

• Es ist in Datenbanken üblich, Daten in zeitlicher Reihenfolge abzufragen
• Wird UUIDv4 als Primärschlüssel verwendet, verteilt sich die Ergebniswertsequenz über mehrere nicht aufeinanderfolgende Blattknoten
• Sucht man nach nacheinander eingefügten Werten, liegen die Seiten mit den Suchergebnissen direkt nebeneinander. Beim Abruf mehrerer Zeilen können sie sogar alle auf einer einzigen Seite direkt beieinander liegen
• Für solche Abfragemuster kann ein sequenzieller Primärschlüssel die Anzahl der zu lesenden Seiten verringern

Wahl des Primärschlüssels: Größe

• Auch die Größe des Primärschlüssels ist ein wichtiger Faktor. Ein Primärschlüssel sollte immer:
  1. groß genug sein, damit ihm nicht die Werte ausgehen
  2. klein genug sein, damit er nicht übermäßig viel Speicherplatz verbraucht
• Für Ganzzahl-Sequenzen kann man bei kleineren Tabellen MEDIUMINT (16 Millionen eindeutige Werte) oder INT (4 Milliarden eindeutige Werte) verwenden
• Für große Tabellen ist BIGINT die sichere Wahl (18 Trillionen mögliche Werte). BIGINT hat 64 Bit (8 Byte)
• UUIDs haben typischerweise 128 Bit (16 Byte) und sind damit doppelt so groß wie der größte Integer-Typ von MySQL
• Da B+-Baum-Knoten eine feste Größe haben, passen mit BIGINT mehr Schlüssel pro Knoten hinein als mit UUID. Das führt zu flacheren Bäumen und schnelleren Lookups

B+-Bäume, Seiten und InnoDB

• Einer der großen Vorteile von B+-Bäumen ist, dass sich die Knotengröße nach Bedarf festlegen lässt
• In InnoDB ist die Größe eines B+-Baum-Knotens normalerweise auf 16k gesetzt, also auf die Größe einer InnoDB-Seite
• Bei der Verarbeitung von Abfragen (und damit beim Traversieren des B+-Baums) liest InnoDB nicht einzelne Zeilen und Spalten von der Festplatte. Immer wenn auf einen Datenteil zugegriffen werden muss, wird die gesamte zugehörige Seite von der Festplatte geladen
• Um das abzumildern, verwendet InnoDB einige Techniken, von denen die wichtigste der Buffer Pool ist. Der Buffer Pool ist ein In-Memory-Cache für InnoDB-Seiten zwischen den Seiten auf der Festplatte und der Ausführung von MySQL-Abfragen
• Wenn MySQL eine Seite lesen muss, prüft es zuerst, ob sie bereits im Buffer Pool vorhanden ist. Falls ja, wird sie von dort gelesen und der Festplatten-I/O übersprungen. Falls nicht, wird die Seite auf der Festplatte gesucht, in den Buffer Pool geladen und dann die Ausführung der Abfrage fortgesetzt
• Der Buffer Pool verbessert die Query-Performance massiv. Ohne Buffer Pool wären sehr viel mehr Festplatten-I/O-Operationen nötig, um die Query-Workload zu verarbeiten

Weitere Fälle

• Der Fokus lag hier zwar hauptsächlich auf dem Vergleich zwischen sequenziellen Schlüsseln und zufälligen/UUID-Schlüsseln, aber diese Prinzipien sind unabhängig von der Art des betrachteten Primär- oder Sekundärschlüssels nützlich
• Beispielsweise könnte man erwägen, den Zeitstempel user.created_at als Indexschlüssel zu verwenden. Er hat ähnliche Eigenschaften wie eine sequenzielle Ganzzahl. Solange keine Altdaten eingefügt werden, laufen Einfügungen normalerweise immer über den rechtesten Pfad
• Umgekehrt hat eine Zeichenkette wie user.email_address eher ähnliche Eigenschaften wie ein zufälliger Schlüssel. Nutzer erstellen ihre Konten nicht in alphabetischer Reihenfolge ihrer E-Mail-Adresse, daher verteilen sich Einfügungen über den gesamten B+-Baum

Fazit

• Es wurde viel zu B+-Bäumen, Indizes und der Wahl des Primärschlüssels behandelt
• Oberflächlich wirkt das vielleicht einfach, aber wenn man die Datenbank-Performance maximal ausreizen will, gibt es einige feine Unterschiede zu beachten
• Für weitere Experimente lohnt sich ein Besuch der interaktiven B+-Baum-Website

[GN⁺]

Hacker-News-Kommentare

• Nutzt eine Strategie, bei der ein Wiki wie ein B-Tree verwaltet wird, um es nützlich zu halten

  • Wenn es zu viele Landingpages gibt, werden Links und Absätze auf Unterseiten verschoben
  • Ähnliche und alte Links werden auf thematisch passende Geschwisterseiten verschoben
  • Am Ende werden alte Dokumente von der Landingpage drei Ebenen nach unten verschoben
  • Dokumentation läuft letztlich auf ein Suchproblem hinaus
  • Eine gute Art, einen Freitagnachmittag produktiv zu verbringen

• Habe schon lange nach so etwas gesucht, ein erstaunlicher Beitrag

  • Ich wünschte, es gäbe einen Abschnitt über zusammengesetzte Indizes

• Vielen Dank für die erstaunlichen Visualisierungen

  • Habe an BTree+-Indexing-Support auf Aerospike gearbeitet
  • Das Entfernen abgelaufener Schlüssel aus BTree+ war eine Herausforderung
  • Wir haben beschlossen, nur eine Verzweigung auf einer Ebene innerhalb des ersten benachbarten Leaf-Nodes zusammenzuführen
  • Wir haben Sharding über BTree+ hinzugefügt, um es zu beschleunigen und Lock-Contention zu verringern
  • Während des Bereinigungsprozesses kann BTree+ unausgewogen werden
  • Wir haben eine Funktion zum Neuaufbau des Index bereitgestellt, um zusätzliche Bereinigungsarbeit zu vermeiden

• Das Cookie-Modal funktioniert in Firefox Mobile nicht

  • Es sollte den Nutzern ermöglichen, es im Browser einzustellen

• UUID-Spalten sollten nicht als Primärschlüssel verwendet werden

  • Man muss eine 128-Bit-Int in jeden Aspekt der Beziehungen kopieren
  • In den meisten Fällen ist sie vollständig zufällig
  • Für interne Tabellenbeziehungen sollte man bigserial(64-Bit)-PKs verwenden und UUIDs(128-Bit) für Identifikatoren auf Anwendungsebene und natürliche Schlüssel
  • Die Datenbank wird sehr glücklich sein

• Hervorragendes Lehrmaterial

  • Solche interaktiven Demos helfen enorm

• Wenn Disk-Blocks und B-Tree-Nodes 16k groß sind und Key, Value und Child-Pointer jeweils 8 Bit haben, dann kann man pro Node 682 Key/Value-Paare und 683 Child-Pointer speichern

  • Ein Baum mit drei Ebenen kann mehr als 300 Millionen Key/Value-Paare speichern
  • Es müssten 8 Bytes pro Element sein

• Großartiger Artikel

  • Dass InnoDB Daten im B-Tree selbst speichert, nennt man Clustered Index
  • MyISAM war ein Non-Clustered-Index
  • Oracle usw. lassen einem die Wahl

• Fragt, was v0, v1, ...v10 im Diagramm bedeuten

  • Fragt sich, ob sie andere Seiten bedeuten

• Wunderschöne interaktive Visualisierung

  • Spitzenklasse in Bezug auf Bildung und Popularisierung