Indizierungs- und Zugriffsmethoden

Indizes und Zugriffsmethoden sind Hilfsdatenstrukturen – hauptsächlich B+-Bäume und Hash-Indizes –, die es einer Datenbank ermöglichen, passende Tupel zu lokalisieren, ohne eine gesamte Tabelle zu durchsuchen, und bieten die schnellen Zugriffspfade, auf die sich der Optimierer verlässt.

Definition

Ein Index ist eine Hilfsdatenstruktur für ein oder mehrere Attribute einer Relation, die Schlüsselwerte den Speicherorten passender Tupel zuordnet und so den Abruf in einer Zeit ermöglicht, die sublinear zur Tabellengröße ist; eine Zugriffsmethode ist der Mechanismus, den eine Abfrage zum Lesen von Daten verwendet, wie z. B. ein vollständiger Scan oder ein Index-Scan.

Scope

Dieses Thema behandelt die Strukturen und Konzepte hinter Datenzugriffspfaden: die Unterscheidung zwischen geclusterten und ungeclusterten, primären und sekundären Indizes; den B+-Baum als das zentrale geordnete Indexsystem, das Gleichheits- und Bereichssuchen unterstützt; Hash-basierte Indizes für die Gleichheitssuche; und die Rolle von Indizes bei der Selektion, dem Join und der Vermeidung von Sortierungen. Es wird behandelt, wie die Indexwahl die Abfragekosten und den Aktualisierungsaufwand beeinflusst. Die Auswahl des Gesamtplans durch den kostenbasierten Optimierer, die ein separates Thema ist, wird ausgeschlossen.

Core questions

• Wie unterstützt ein B+-Baum effizient sowohl Gleichheits- als auch Bereichsabfragen?
• Was ist der Unterschied zwischen geclusterten und ungeclusterten, primären und sekundären Indizes?
• Wann ist ein Hash-Index einem Baum-Index vorzuziehen?
• Wie beschleunigen Indizes Selektionen, Joins und geordnete Abrufe?
• Welche Kosten entstehen bei der Pflege von Indizes bei Einfügungen, Aktualisierungen und Löschungen?

Key concepts

• B+-Baum-Index
• Hash-Index
• geclusterter versus ungeclusterter Index
• primäre und sekundäre Indizes
• dichte und dünne Indizes
• Bereichs- und Gleichheitssuche
• erweiterbares und lineares Hashing
• Kosten der Indexpflege

Key theories

B+-Baum-Indizes

Der B+-Baum ist ein balancierter Suchbaum mit hohem Verzweigungsgrad, der Schlüssel in sortierter Reihenfolge speichert, wobei alle Datenreferenzen in den Blättern liegen; er unterstützt Gleichheits- und Bereichsabfragen sowie geordnete Scans mit logarithmischer E/A und bleibt unter Einfügungen und Löschungen balanciert.

Geclusterte versus ungeclusterte Indizes

Ein geclusterter Index hält die Zeilen der Tabelle physisch nach dem Indexschlüssel geordnet, was Bereichsscans sehr effizient macht, während ein ungeclusterter (sekundärer) Index auf eine ungeordnete Datei verweist, sodass das Abrufen vieler passender Zeilen eine E/A pro Zeile kosten kann.

Hash-Indizes

Hash-basierte Indizes ordnen Schlüssel Buckets für erwartete konstante Zeit-Gleichheits-Lookups zu, unterstützen jedoch keine Bereichsabfragen; dynamische Schemata wie erweiterbares und lineares Hashing ermöglichen es ihnen, mit den Daten elegant zu wachsen.

Clinical relevance

Die Indizierung ist der häufigste praktische Hebel für die Datenbankleistung: Die Wahl der richtigen Indizes kann vollständige Tabellenscans in Millisekunden-Lookups für Transaktions- und Analyseabfragen verwandeln, während eine Überindizierung Aktualisierungen verlangsamt, sodass das Indexdesign eine wiederkehrende Entscheidung beim Betrieb realer Systeme ist.

History

Bayer und McCreight führten den B-Baum 1972 ein, um große geordnete Indizes auf der Festplatte zu verwalten; die B+-Baum-Variante, die alle Daten in den Blättern speichert, wurde zum Standard-Datenbankindex, wie in Comers 'Ubiquitous B-tree' von 1979 beschrieben. Hash-basierte Zugriffsmethoden und dynamische Hash-Verfahren entwickelten sich parallel, und beide Familien bleiben Kernbestandteil jedes relationalen Systems.

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

Warum werden B+-Bäume anstelle von binären Suchbäumen in Datenbanken verwendet?

Datenbanken speichern Daten auf der Festplatte, wo die Kosten hauptsächlich durch die Anzahl der Seitenlesevorgänge bestimmt werden. B+-Bäume haben einen hohen Verzweigungsgrad, sodass jeder Knoten eine Festplattenseite füllt und der Baum sehr flach ist, wodurch nur wenige E/As erforderlich sind, um einen beliebigen Datensatz zu erreichen. Ein binärer Baum wäre wesentlich tiefer und würde viel mehr Festplattenzugriffe verursachen.

Wann sollte ich einen Hash-Index anstelle eines B+-Baums verwenden?

Verwenden Sie einen Hash-Index, wenn Sie nur Gleichheits-Lookups benötigen (z. B. die Zeile mit einer bestimmten ID finden) und einen erwarteten konstanten Zeit-Zugriff wünschen. Verwenden Sie einen B+-Baum, wenn Sie auch Bereichsabfragen, geordnete Scans oder Präfix-Matching benötigen, da Hash-Indizes die Schlüsselreihenfolge nicht beibehalten und Bereichsbedingungen nicht effizient beantworten können.