2012-03-22Der 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 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 der jeder Eintrag Zweigkoten 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.

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 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.

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.