Home > Lernmodule > Modul 10

 

8 Indexstrukturen und Anfragebearbeitung

Der B⁺-Baum

In dieser Lerneinheit gehen wir auf Techniken zur effizienten Anfrageauswertung ein. Wesentlicher Schwerpunkt ist die Diskussion des B⁺-Baumes als grundlegende Indexstruktur zur schnellen (logarithmischen) Suche in sehr großen Datenmengen.
Bei einem B⁺-Baum handelt es sich um einen balancierten Suchbaum, bei dem die Daten (bzw. Verweise auf die eigentlichen Daten) ausschließlich in den Blättern verwaltet werden. Aufgrund der vorgegebenen Ordnung dieser Einträge können nicht nur direkte Anfragen nach einzelnen Datensätzen, sondern auch Bereichsanfragen (d.h. alle Daten aus einem vorgegebenen Intervall) effizient unterstützt werden.
Diskutiert werden die Algorithmen zum Suchen, Einfügen und Löschen von Datensätzen.

 

Anfragebearbeitung

SQL ist eine deskriptive Sprache, d.h., der Benutzer beschreibt nicht den Auswertungsvorgang, sondern das gewünschte Ergebnis. Dies führt dazu, dass eine gegebene SQL-Anfrage in der Regel auf unterschiedliche Art und Weise ausgewertet werden kann. Es ist die Aufgabe des Optimierers, die günstigste Auswertungsvariante zu finden. Der hierbei mögliche Performanzgewinn wird an einem Beispiel aufgezeigt.