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

Ich biete SQL Schulungen, Optimierung und Beratung an. Auch der Kauf meines Buches „SQL Performance Explained“ (ab €9,95) unterstützt meine Arbeit an dieser Webseite.

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.

Vorherige SeiteNächste Seite

Du kannst nicht alles an einem Tag lernen. Abonniere den Newsletter via E-Mail, Twitter oder RSS um sukzessive aufzuholen. Und sieh dir auch modern-sql.com an.

Über den Autor

Foto von Markus Winand

Markus Winand gibt auf modern-sql.com Einblick in SQL und zeigt, wie es von verschiedenen Systemen unterstützt wird. Zuvor machte er use-the-index-luke.com, was er noch immer wartet. Markus kann als Trainer, Sprecher und Berater auf winand.at engagiert werden.

Sein Buch kaufen

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

Die Essenz: SQL-Tuning auf 200 Seiten

Jetzt Kaufen
(Taschenbuch und/oder PDF)

Sein Training

Markus verwandelt veraltetes SQL-92-Wissen in solides und zeitgemäßes SQL-Know-how

Erfahren Sie mehr»

Mit Markus Winand verbinden

Markus Winand auf LinkedInMarkus Winand auf XINGMarkus Winand auf Twitter
„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 und DSGVO | CC-BY-NC-ND 3.0 Lizenz