von Markus Winand.

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

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.

ProgrammierspracheName
Javajava.util.LinkedList
.NET FrameworkSystem.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 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.

Über den Autor

Foto von Markus Winand

Markus Winand ist der SQL Renaissance Botschafter auf der Mission, Entwickler auf die Evolution von SQL im 21. Jahrhundert aufmerksam zu machen. Markus kann als Trainer, Sprecher und Berater auf winand.at engagiert werden.

Sein Buch kaufen

Titelbild von „SQL Performance Explained“: Eichhörnchen läuft durchs Grass

Die Essenz: SQL-Tuning auf 200 Seiten

Jetzt Kaufen
(Taschenbuch und/oder PDF)

Sein Training

Markus verwandelt veraltetes SQL-92-Wissen in solides und zeitgemäßes SQL-Know-how

Erfahren Sie mehr»

Nicht mit OFFSET blättern

Mehr info

Besuche meine Schwester-Seite!Seit SQL-92 hat sich einiges getan!

Die Use The Index, Luke! Tasse

Aufkleber, Bierdeckel, Bücher und Kaffeetassen. Alles was man beim Lernen braucht!

Zum Shop

Mit Markus Winand verbinden

Markus Winand auf LinkedInMarkus Winand auf XINGMarkus Winand auf Twitter
„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 und DSGVO | CC-BY-NC-ND 3.0 Lizenz