Die Hauptaufgabe eines Indexes ist es, die indizierten Daten in der Indexreihenfolge zu verwalten. Dazu genügt es nicht, die Einträge hintereinander abzuspeichern, da jede insert-Anweisung die dahinterliegenden Einträge verschieben müsste, um Platz für den neuen Eintrag zu schaffen. Das Verschieben großer Datenmengen ist jedoch sehr zeitaufwendig, 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.
Hinweis in eigener Sache
Ich lebe von SQL-Schulungen, SQL-Tuning und Beratung sowie dem Verkauf meines Buches „SQL Performance Explained“. Mehr auf winand.at.
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 eingefügt werden, ohne große Datenmengen zu bewegen – es müssen nur wenige Blätter neu verkettet werden.
Doppelt verkettete Listen werden auch für Container und Collections in Programmiersprachen verwendet.
| Programmiersprache | Name |
|---|---|
| Java | java.util.LinkedList |
| .NET Framework | System.Collections.Generic.LinkedList |
| C++ | std::list |
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 Index Blattknoten und Tabellendaten
Abbildung 1.1 stellt einige Blattknoten und die entsprechenden Tabellendaten dar. Jeder Blattknoten-Eintrag besteht aus einer Kopie der indizierten Spalte (Spalte 2) und einem Verweis auf den entsprechenden Tabelleneintrag (ROWID oder RID). Im Gegensatz zu den Indexeinträgen sind die Tabelleneinträ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.
