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.

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.

Nachdem ein Index angelegt wurde, wird er von der Datenbank au­to­ma­tisch gepflegt. Der Index wird also mit jeder insert-, delete- und update-Anweisung aktualisiert. Die Datenbank hält den Index auch „im Gleichgewicht“ (balanced). Der dadurch entstandene Wartungsaufwand kann durchaus signifikant werden. Kapitel 8, „Schreiboperationen, geht genauer darauf ein.

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.

Das Durchwandern des Suchbaumes ist sehr effektiv. So effektiv, dass ich diesen Vorgang als die erste Macht der Indizierung bezeichne. Das liegt einerseits daran, dass der Baum immer balanciert ist. Andererseits wächst der Suchbaum nur sehr langsam in die Tiefe. Ein Baum mit vier oder fünf Verzweigungen kann bereits einige Millionen Einträge abdecken. Eine Indextiefe von sechs wird nur ausgesprochen selten erreicht. Der Kasten Logarithmische Skalierbarkeit erklärt das Indexwachstum etwas genauer.

Wenn dir gefällt, wie ich die Dinge erkläre, wirst du meine Kurse lieben.

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.

„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