Abbildung 1.2 zeigt einen Index mit 30 Einträgen. Die Reihenfolge der Blattknoten (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.
… meine Newsletter bestellen, gratis Sticker erhalten, mein Buch kaufen oder an einer Schulung teilnehmen.
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.
Ein B-Tree ist ein Balanced Tree – kein Binary Tree.
>=
) 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.Mit dem Indexbaum findet man einen Blattknoten sehr schnell.
Du kannst nicht alles an einem Tag lernen. Abonniere den Newsletter via E-Mail, Bluesky oder RSS um sukzessive aufzuholen. Und sieh dir auch modern-sql.com an.
Markus verwandelt veraltetes SQL-92-Wissen in solides und zeitgemäßes SQL-Know-how