von Markus Winand.

Der Suchbaum (B-Tree) macht den Index schnell


Die physische Reihenfolge der Indexseiten ist willkürlich und lässt keinen Rückschluss auf die logische Position im Index zu. Die Suche darin ist also so, als wären die Seiten eines Telefonbuches durcheinander. Wenn man nach „Schmied“ sucht und das Telefonbuch bei „Müller“ öffnet, ist keineswegs sichergestellt, dass „Schmied“ weiter hinten kommt. Um die Indexeinträge dennoch schnell zu finden, wird eine zweite Struktur verwaltet: ein balancierter Suchbaum, kurz B-Tree genannt.

Abbildung 1.2 Struktur eines Suchbaumes

Abbildung 1.2 zeigt einen Index mit 30 Einträgen. Die Reihenfolge der Blattkno­ten (engl. Leaf-Nodes) wird durch die doppelte Verkettung hergestellt. Die Wurzel- und Zweigknoten (Root- und Branch-Nodes) dienen der Suche nach bestimmten Einträgen.

Die Abbildung hebt hervor, wie ein Zweigknoten auf die darunter liegenden Blattknoten verweist. Dabei entspricht jeder Eintrag im Zweigknoten dem größten Wert im Blattknoten. Da der größte Wert im ersten Blattknoten 46 ist, ist der erste Eintrag im Zweigknoten ebenfalls 46. Dasselbe gilt für alle weiteren Blattknoten, sodass der Zweigknoten letztendlich die Einträge 46, 53, 57 und 83 enthält. Nach diesem Schema wird eine Verzweigungsschicht aufgebaut, bis alle Blattknoten von einem Zweigknoten erfasst sind.

Hinweis in eigener Sache

Wenn Dir dieser Artikel gefällt, könnte mein Buch SQL Performance Explained oder mein Training auch etwas für Dich sein.

Die nächste Schicht ist ebenso aufgebaut, nur dass dabei auf die Zweigknoten verwiesen wird. Das Ganze wiederholt sich so lange, bis eine Schicht entsteht, die nur aus einem Knoten besteht – dem Wurzelknoten oder Root-Node. Das Besondere an dieser Baumstruktur ist, dass sie eine einheitliche Tiefe hat: Der Weg zwischen dem Wurzelknoten und den Blattknoten ist überall gleich lang.

Beachte

Ein B-Tree ist ein Balanced Tree – kein Binary Tree.

Abbildung 1.3 Durchwandern des Suchbaumes

Abbildung 1.3 zeigt, wie der Suchbaum genutzt wird, um den Eintrag „57“ zu finden. Die Suche beginnt links, beim Wurzelknoten. Die Einträge des Wurzelknotens werden der Reihe nach mit dem Suchbegriff „57“ verglichen, bis ein Eintrag gefunden wird, der größer-gleich (>=) dem Suchbegriff ist. In der Abbildung trifft das auf den Eintrag „83“ zu. Die Datenbank folgt dem Verweis auf den entsprechenden Zweigknoten und wiederholt die Prozedur so lange, bis sie einen Blattknoten erreicht.

Wichtig

Mit dem Indexbaum findet man einen Blattknoten sehr schnell.

Logarithmische Skalierbarkeit

Mathematisch gesprochen ist der Logarithmus die Umkehroperation des Potenzierens. Er löst also die Gleichung a = bx nach dem Exponenten x auf [Wikipedia].

Bei einem Suchbaum entspricht die Anzahl der Einträge pro Zweigknoten der Basis b und die Baumtiefe dem Exponenten x. Der Index aus Abbildung 1.2 kann offenbar bis zu vier Einträge pro Zweigknoten fassen und hat eine Tiefe von drei. Daraus resultiert, dass die Blattknoten bis zu 64 (43) Einträge fassen können. Wenn der Index um eine Verzweigungsschicht wächst, kann er bereits 256 (44) Einträge fassen. Jede neue Schicht vervierfacht also die Anzahl der möglichen Einträge. Der Logarithmus kehrt dieses Verhältnis um. Die Baumtiefe entspricht also log4(Indexeinträge).

BaumtiefeIndexeinträge
364
4256
51.024
64.096
716.384
865.536
9262.144
101.048.576

Durch das logarithmische Wachs­tum kann der Beispiel­index eine Million Einträge mit nur zehn Ebenen abdecken. Ein echter In­dex ist aber noch effektiver. Denn der Hauptfaktor für die Baum­tiefe ist die Anzahl der Ein­träge pro Zweig­knoten – mathematisch gesprochen, die Basis des Loga­rithmus. Je größer die Basis, desto flacher bleibt der Baum.

Datenbanken nutzen diesen Effekt aus und speichern so viele Einträge wie möglich in den einzelnen Knoten – oft hundert oder mehr. Das bedeutet, dass jede weitere Verzweigungsschicht die Indexkapazität verhundertfacht.

Über den Autor

Foto von Markus Winand

Markus Winand lehrt effizientes SQL – inhouse und online. Er minimiert die Entwicklungszeit durch modernes SQL und optimiert die Laufzeit durch schlaue Indizierung – dazu hat er auch das Buch SQL Performance Explained veröffentlicht.

Sein Buch bei Amazon kaufen

Titelbild von „SQL Performance Explained“: Eichhörnchen läuft durchs Grass

Die Essenz: SQL-Tuning auf 200 Seiten

Bei Amazon kaufen
(Taschenbuch)

Taschenbuch und PDF auch auf Markus' Webseite erhältlich.

Sein Training

Sein beliebtes Training stimmt Entwickler auf SQL Performance ein.

Erfahren Sie mehr»

„Use The Index, Luke!“ von Markus Winand ist unter einer Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported License lizenziert.
Impressum | Kontakt | KEINE GEWÄHR | Handelsmarken | Datenschutz | CC-BY-NC-ND 3.0 Lizenz