Diese Vorlesung ist inspiriert von den Präsentationen zu dem Kurs: „Architecture and Implementation of Database Systems“ von Jens Teubner an der eth zürich

Diese Vorlesung ist inspiriert von den Präsentationen zu dem Kurs: „Architecture and Implementation of Database Systems“ von Jens Teubner an der ETH Zürich

• Diese Vorlesung ist inspiriert von den Präsentationen zu dem Kurs: „Architecture and Implementation of Database Systems“ von Jens Teubner an der ETH Zürich

• Graphiken wurden mit Zustimmung des Autors aus diesem Kurs übernommen

• Sortierung der Tabelle CUSTOMERS auf der Platte (nach ZIPCODE )

• Zur Evaluierung von Anfragen Verwendung von binärer Suche, um erstes Tupel zu finden, dann Scan solange ZIPCODE < 8999

• Sequentieller Zugriff während der Scan-Phase

• Es müssen log2(#Tupel) während der Such-Phase gelesen werden

• Für jeden Zugriff eine Seite!

• Weite Sprünge sind die Idee der binären Suche
• Kein Prefetching möglich

Idee: Beschleunige die Suchphase durch sog. Index

• Idee: Beschleunige die Suchphase durch sog. Index

• Knoten von der Größe einer Seite

• Hunderte Einträge pro Seite
• Hohe Verzweigung, kleine Tiefe

• Suchaufwand: logVerzweigung(#Tupel)

ISAM-Indexe sind statisch

• ISAM-Indexe sind statisch

• Löschen einfach: Lösche Datensatz von Datenseite

• Einfügen von Daten aufwendig

• Falls noch Platz auf Blattseite, füge Datensatz ein (z.B. nach einer vorherigen Löschung)
• Sonst füge Überlauf-Seite ein (zerstört sequentielle Ordnung)
• ISAM-Index degeneriert

Das Vorsehen von Freiraum bei der Indexerzeugung reduziert das Einfügeproblem (typisch sind 20% Freiraum)

• Das Vorsehen von Freiraum bei der Indexerzeugung reduziert das Einfügeproblem (typisch sind 20% Freiraum)

• Da Seiten statisch, keine Zugriffskoordination nötig

• Zugriffskoordination (Sperren) vermindert gleichzeitigen Zugriff (besonders nahe der Wurzel) für andere Anfragen

• ISAM ist nützlich für (relativ) statische Daten

B+-Bäume von ISAM-Index abgeleitet, sind aber dynamisch

• B+-Bäume von ISAM-Index abgeleitet, sind aber dynamisch

• Keine Überlauf-Ketten

• Balancierung wird aufrechterhalten

• Behandelt insert und delete angemessen

• Minimale Besetzungsregel für B+-Baum-Knoten (außer der Wurzel): 50% (typisch sind 67%)

• Verzweigung nicht zu klein (Zugriff O(log n))

• Indexknotensuche nicht zu linear

B+-Bäume ähnlich zu ISAM-Index, wobei

• B+-Bäume ähnlich zu ISAM-Index, wobei

• Blattknoten üblicherweise nicht in seq. Ordnung

• Blätter zu doppelt verketteter Liste verbunden

• Blätter enthalten tatsächliche Daten (wie ISAM-Index) oder Referenzen (Rids) auf Datenseiten

• Wir nehmen im Folgenden Letzteres an

• Jeder Knoten enthält zwischen d und 2d Einträge (d heißt Ordnung des Baumes, Wurzel ist Ausnahme)

Funktionsaufruf search(k) bestimmt Blatt, das potentielle Treffer für eine Suche nach Elementen mit Schlüssel k enthält

• Funktionsaufruf search(k) bestimmt Blatt, das potentielle Treffer für eine Suche nach Elementen mit Schlüssel k enthält

B+-Baum soll nach Einfügung balanciert bleiben

• B+-Baum soll nach Einfügung balanciert bleiben

• keine Überlauf-Seiten

• Algorithmus für insert(k, p) für Schlüsselwert k und Datenseite p

• Finde Blattseite n, in der Eintrag für k sein kann
• Falls n genug Platz hat (höchstens 2d-1 Einträge), füge Eintrag in n ein
• Sonst muss Knoten n aufgeteilt werden in n und n‘ – weiterhin muss ein Separator in den Vater von n eingefügt werden
• Die mögliche Aufspaltung erfolgt rekursiv nach oben, eventuell bis zur Wurzel (wodurch sich der Baum erhöht)

Einfügung eines Eintrags mit Schlüssel 4222

• Einfügung eines Eintrags mit Schlüssel 4222

• Es ist genug Platz in Knoten 3, einfach einfügen
• Erhalte Sortierung innerhalb der Knoten

Einfügung eines Eintrags mit Schlüssel 4222

• Einfügung eines Eintrags mit Schlüssel 4222

• Es ist genug Platz in Knoten 3, einfach einfügen
• Erhalte Sortierung innerhalb der Knoten

Einfügung eines Eintrags mit Schlüssel 6330

• Einfügung eines Eintrags mit Schlüssel 6330

• Knoten 4 aufgespalten
• Neuer Separator in Knoten 1

Einfügung eines Eintrags mit Schlüssel 6330

• Einfügung eines Eintrags mit Schlüssel 6330

• Knoten 4 aufgespalten
• Neuer Separator in Knoten 1

Einfügung von 8180, 8245...

• Einfügung von 8180, 8245...

Nach 8180, 8245, füge 4104 ein

• Nach 8180, 8245, füge 4104 ein

• Aufspaltung von Knoten 3 und 9

• Knoten 1 läuft über  Aufspaltung

• Neuer Separator für Wurzel

• Separatorschlüssel aus inneren Knoten können sich verschieben

Aufspaltung beginnt auf Blattebene und verläuft nach oben solange Indexknoten vollständig belegt

• Aufspaltung beginnt auf Blattebene und verläuft nach oben solange Indexknoten vollständig belegt

• Schließlich kann die Wurzel aufgespalten werden

• Aufspaltung wie bei inneren Knoten
• Separator für einen neuen Wurzelknoten verwenden

• Nur Wurzelknoten mit Füllgrad < 50% möglich

• Erhöhung nur bei Einfügung einer neuen Wurzel

insert(k, rid) wird von außen aufgerufen

• insert(k, rid) wird von außen aufgerufen

• Blattknoten enthalten Rids, innere Knoten enthalten Zeiger auf andere B+-Baum-Knoten

Falls Knoten genügend gefüllt (mindestens d+1 Einträge), Eintrag einfach löschen

• Falls Knoten genügend gefüllt (mindestens d+1 Einträge), Eintrag einfach löschen

• Hinterher können innere Knoten Schlüssel enthalten, die zu Einträgen gehören, die nicht mehr existieren.
• Das ist OK

• Sonst verschmelze Knoten wegen Unterfüllung

• Ziehe Separator in den verschmolzenen Knoten

Leider ist die Situation nicht immer so einfach

• Leider ist die Situation nicht immer so einfach

• Verschmelzung nur, wenn Nachbarknoten zu 50% voll

• Sonst muss Neuverteilung erfolgen

• Rotiere Eintrag über den Elternknoten

Implementierungen verzichten auf die Kosten der Verschmelzung und der Neuverteilung und weichen die Regel der Minimumbelegung auf

• Implementierungen verzichten auf die Kosten der Verschmelzung und der Neuverteilung und weichen die Regel der Minimumbelegung auf

• Beispiel: IBM DB2 UDB

• MINPCTUSED als Parameter zur Steuerung der Blattknotenverschmelzung (Online-Indexreorganisation)
• Innere Knoten werden niemals verschmolzen (nur bei Reorganisation der gesamten Tabelle)

• Zur Verbesserung der Nebenläufigkeit evtl. nur Markierung von Knoten als gelöscht (keine aufwendige Neuverzeigerung)

Drei Alternativen

• Drei Alternativen

• Vollständiger Datensatz k* (ein solcher Index heißt geclustert, siehe unten)

• Ein Paar , wobei rid (record ID) ein Zeiger auf einen Datensatz darstellt

• Ein Paar , wobei alle Rids den Suchschlüssel k haben

• Varianten 2. und 3. bedingen, dass Rids stabil sein müssen, also nicht (einfach) verschoben werden können

• Alternative 2 scheint am meisten verwendet zu werden

Implizite Indexe

• Implizite Indexe

• Indexe automatisch erzeugt für Primärschlüssel und Unique-Integritätsbedingungen

• Explizite Indexe

• Einfache Indexe:

• Zusammengesetzte Indexe (Verbundindexe):

B+-Bäume können verwendet werden, um Dinge mit einer definierten totalen Ordnung zu indizieren (im Prinzip1)

• B+-Bäume können verwendet werden, um Dinge mit einer definierten totalen Ordnung zu indizieren (im Prinzip1)

• Integer, Zeichenketten, Datumsangaben, ...,

• und auch eine Hintereinandersetzung davon (basierend auf einer lexikographischen Ordnung)

• Beispiel:

• Eine weitere Anwendung sind partitionierte B+-Bäume

• Führende artifizielle Indexattribute partitionieren den B+-Baum horizontal (z.B. zur verteilten Verarbeitung)

Eine typische Situation nach Alternative 2 sieht so aus:

• Eine typische Situation nach Alternative 2 sieht so aus:

• Was passiert, wenn man Folgendes ausführt?

Wenn die Datei mit den Datensätzen sortiert und sequentiell gespeichert ist, erfolgt der Zugriff schneller

• Wenn die Datei mit den Datensätzen sortiert und sequentiell gespeichert ist, erfolgt der Zugriff schneller

• Ein so organisierter Index heißt geclusterter Index

• Sequentieller Zugriff während der Scan-Phase

• Besonders für Bereichsanfragen geeignet

Alternative 1 von oben ist ein Spezialfall eines geclusterten Index

• Alternative 1 von oben ist ein Spezialfall eines geclusterten Index

• Indexdatei = Datensatz-Datei

• Eine solche Datei nennt man index-organisiert

• Oracle:

B+-Baum-Verzweigung proportional zur Anzahl der Einträge pro Seite, also umgekehrt proportional zur Schlüsselgröße

• B+-Baum-Verzweigung proportional zur Anzahl der Einträge pro Seite, also umgekehrt proportional zur Schlüsselgröße

• Ziel: Schlüsselgröße verringern (insb. relevant bei Zeichenketten variabler Länge)

• Suffix-Abschneidung: Beschränkung der Separatoren auf relevante Präfixe

• Separatoren benötigen Datenwerte nicht

Häufig treten Zeichenketten mit gleichem Präfix auf

• Häufig treten Zeichenketten mit gleichem Präfix auf

• Speichere gemeinsamen Präfix nur einmal (z.B. als k0)

• Schlüssel sind nun stark diskriminierend

• Außerkraftsetzen der 50%-Füllungsregel kann Effektivität der Präfixabschneidung verbessern

Aufbau eines B+-Baums ist einfach bei sortierter Eingabe

• Aufbau eines B+-Baums ist einfach bei sortierter Eingabe

• Aufbau des B+-Baumes von links nach rechts möglich

• Eventuell mit Freiraum für Updates

Bisher B+-Bäume diskutiert

• Bisher B+-Bäume diskutiert

• Ursprünglicher Vorschlag von Bayer und McCreight enthielt sog. B-Bäume

• Innere Knoten enthalten auch Datensätze

• Es gibt auch B*-Bäume

• Fülle innere Knoten zu 2/3 statt nur zur 1/2

• Umverteilung beim Einfügen (bei zwei vollen Knoten auf drei Knoten umverteilen)

• B-Baum meint irgendeine dieser Formen, meist werden in realen DBs die B+-Bäume implementiert

• B+-Bäume auch außerhalb von DBs verwendet

Zugriff auf Daten von O(n) ungefähr auf O(log n)

• Zugriff auf Daten von O(n) ungefähr auf O(log n)

• Kosten der Indexierung aber nicht zu vernachlässigen

• Nicht bei „kleinen“ Tabellen
• Nicht bei häufigen Update- oder Insert-Anweisungen
• Nicht bei Spalten mit vielen Null-Werten

• Standardisierung nicht gegeben

• MYSQL oder PostgreSQL (Ausschnitt):

B+-Bäume dominieren in Datenbanken

• B+-Bäume dominieren in Datenbanken

• Eine Alternative ist die hash-basierte Indexierung

• Hash-Indexe eignen sich nur für Gleichheitsprädikate

• Insbesondere für (lange) Zeichenketten und Verbundindexe

• Statt Kollisionslisten: Lineares Sondieren, o.a. Techniken

Problem: Wie groß soll die Anzahl n der Hash-Felder sein?

• Problem: Wie groß soll die Anzahl n der Hash-Felder sein?

• n zu groß  schlechte Platznutzung und –Lokalität

• n zu klein  Viele Überlaufseiten, lange Listen

• Datenbanken verwenden daher dynamisches Hashen (dynamisch wachsende und schrumpfende Bildbereiche)

• Erweiterbares Hashen (Vermeidung des Umkopierens)

Index-Sequentielle Zugriffsmethode (ISAM-Index)

• Index-Sequentielle Zugriffsmethode (ISAM-Index)

• Statisch, baum-basierte Indexstruktur

• B+-Bäume

• Die Datenbank-Indexstruktur, auf linearer Ordnung basierend, dynamisch, kleine Baumhöhe für fokussierten Zugriff auf Bereiche

• Geclusterte vs. ungeclusterte Indexe

• Sequentieller Zugriff vs. Verwaltungsaufwand

• Hash-basierte Indexe

• Dynamische Anpassung des Index auf die Daten