2012-03-22Die Index-Blätter: Eine doppelt verkettete Liste

Die Hauptaufgabe eines Indexes ist es, die indizierten Daten in der Indexreihenfolge zu verwalten. Dazu genügt es nicht, die Ein­trä­ge hintereinander abzuspeichern, da jede insert-Anweisung die dahinter­liegenden Einträge verschieben müsste, um Platz für den neuen Eintrag zu schaffen. Das Verschieben großer Datenmengen ist jedoch sehr zeit­aufwendig, sodass die insert-Anweisung sehr langsam werden würde. Die Lösung des Problems besteht darin, eine logische Reihenfolge herzustellen, die unabhängig von der physischen Reihenfolge im Speicher ist.

Die logische Reihenfolge der Indexeinträge wird durch eine doppelt verkettete Liste hergestellt. Ähnlich einer Kette hat jeder Listeneintrag (Knoten, engl. Node) eine Verbindung zu zwei Nachbargliedern. Neue Einträge werden zwischen zwei bestehenden eingefügt, indem die Verweise der beiden angrenzenden Einträge auf den neuen umgebogen werden. Der physische Speicherplatz des neuen Eintrags ist dabei irrelevant – die logische Reihenfolge wird nur durch die Verkettung hergestellt.

Da jeder Knoten dieser Struktur sowohl eine Referenz auf den vorangehenden Knoten als auch auf den folgenden Knoten hat, heißt diese Datenstruktur doppelt verkettete Liste. Die doppelte Verkettung ermöglicht es, den Index nach Bedarf vorwärts oder rückwärts zu lesen. Dennoch können neue Einträge in konstanter Zeit – das heißt unabhängig von der Listenlänge – eingefügt werden.

Doppelt verkettete Listen werden auch für Container und Collections in Programmiersprachen verwendet.

Datenbanken verwenden eine doppelt verkettete Liste, um die sogenannten Blattknoten (engl. Leaf-Nodes) miteinander zu verbinden. Dabei wird jeder Knoten in einem Datenblock (auch Seite oder Page) gespeichert. Alle Datenblöcke eines Indexes haben dieselbe Größe – meist einige Kilobyte. Die Datenbank nutzt den Platz optimal aus und speichert in jedem Block so viele Indexeinträge wie möglich. Daraus folgt, dass die Indexreihenfolge auf zwei Ebenen gewartet werden muss: einmal innerhalb der einzelnen Blöcke und dann die Blöcke untereinander durch die Verkettung.

Abbildung 1.1 stellt einige Blattknoten und die entsprechenden Tabellen­daten dar. Jeder Blattknoten-Eintrag besteht aus einer Kopie der in­di­zie­rten Spalte (Spalte 2) und einem Verweis auf den entsprechenden Tabelleneintrag (ROWID oder RID). Im Gegensatz zu den Indexeinträgen sind die Tab­ellen­einträge in einer Heap-Struktur unsortiert gespeichert. Es gibt keinerlei Verbindung zwischen den Einträgen im selben Tabellenblock, noch sind die Tabellenblöcke untereinander verbunden.