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 biete SQL Schulungen, Optimierung und Beratung an. Auch der Kauf meines Buches „SQL Performance Explained“ (ab €9,95) unterstützt meine Arbeit an dieser Webseite.

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.

Vorherige SeiteNächste Seite

Du kannst nicht alles an einem Tag lernen. Abonniere den Newsletter via E-Mail, Twitter oder RSS um sukzessive aufzuholen. Und sieh dir auch modern-sql.com an.

Über den Autor

Foto von Markus Winand

Markus Winand gibt auf modern-sql.com Einblick in SQL und zeigt, wie es von verschiedenen Systemen unterstützt wird. Zuvor machte er use-the-index-luke.com, was er noch immer wartet. 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»

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