Datenbankindizes: Der Schlüssel zur Performance-Optimierung

Datenbanken sind das Rückgrat moderner Anwendungen, aber mit zunehmender Datenmenge entstehen Herausforderungen, insbesondere im Hinblick auf die Abfragegeschwindigkeit. Datenbankindizes, insbesondere der B-Tree-Index, stehen im Mittelpunkt dieser Betrachtung, um zu verstehen, wie sie zur Beschleunigung von Datenbankabfragen beitragen.

Datenbankindizes spielen in der Welt der Oracle-Datenbanken eine entscheidende Rolle. Mit zunehmendem Datenvolumen haben Datenbankbenutzer oft mit langsamen Abfragegeschwindigkeiten zu kämpfen. Um dieses Problem zu lösen, werden Tabellen mit Indizes versehen. Es reicht jedoch nicht aus, einfach neue Indizes zu erstellen, um Abfragen zu beschleunigen. Um das volle Potenzial von Indizes auszuschöpfen, ist ein tiefes Verständnis ihrer Funktionsweise erforderlich. In diesem Artikel werfen wir einen genaueren Blick auf die Funktionsweise von Indizes am Beispiel von Oracle-Datenbanken.

Ziel bei Datenbankabfragen

Wenn eine SELECT-Abfrage auf eine oder mehrere Tabellen angewendet wird, besteht eines der Hauptziele darin, die Abfragezeit zu minimieren. Die Daten werden in Blöcken, den sogenannten DB Pages, auf der Festplatte gespeichert. Das Lesen und Schreiben von der Festplatte ist ein zeitaufwendiger Prozess. Daten, die häufig abgefragt werden, werden im begrenzten Buffer Cache vorgehalten. Je häufiger von der Festplatte gelesen werden muss, desto länger dauert eine Abfrage.

Wenn nun im SELECT-Statement Daten durch Filterkriterien (WHERE-Bedingung) eingeschränkt werden und keine Indizes vorhanden sind, müssen alle Datensätze dieser Tabelle von der Platte gelesen und gegen das gegebene Filterkriterium geprüft werden.

Bei kleinen Tabellen mag ein solcher sogenannter Full Table Scan kein Problem darstellen. Bei Tausenden oder Millionen von Datensätzen führt dieses Verfahren jedoch zu längeren Wartezeiten. Insbesondere dann, wenn mehrere Tabellen miteinander verknüpft sind, wie es bei normalisierten Datenbanken im Star-Schema der Fall ist.

Um die Wartezeiten zu verkürzen und die Anzahl der Lesevorgänge auf der Festplatte zu minimieren, werden Indizes verwendet.

Der B-Tree Index

Einer der am häufigsten verwendeten Indextypen ist der B-Tree-Index. Dabei handelt es sich um eine hierarchische Baumstruktur, die auf einem bestimmten Regelwerk basiert, um ein schnelleres und speichereffizienteres Suchen, Einfügen und Löschen von Daten zu ermöglichen. Der Name "B-Tree" bezieht sich auf die ausgewogene Struktur des Baumes („Balenced-Tree“). Das bedeutet, dass sich alle Blattknoten auf der gleichen Ebene befinden und der Verzweigungsgrad relativ niedrig gehalten wird, um einen schnellen Zugriff auf die Blattknoten zu gewährleisten. Der B-Tree-Index speichert Daten in sortierter Reihenfolge, was ihn sehr effizient für Bereichsabfragen (WHERE X BETWEEN Y AND Z) und Gleichheitsprüfungen (WHERE X = Y) macht. B-Tree ist der Standard-Index-Typ für verschiedene Datenbanksysteme wie Oracle und MySQL. Das folgende Beispiel zeigt einen einfachen B-Tree-Index, der auf einer Liste von Zahlen basiert.

Aufbau eines B-Tree Index

Im diesem Beispiel haben wir eine sortierte Liste von Zahlenwerten [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28], die den Index darstellen. Der Baum ist ausgeglichen, da alle untersten Blätter (Leafs), hier grün dargestellt, auf der gleichen Ebene (3) liegen. Die Blätter, auch Blattknoten genannt, enthalten die eigentlichen Daten oder Verweise auf Datensätze in der Datenbanktabelle. Im Beispiel von Oracle enthalten diese Blätter die ROWID, die eine schnelle Identifizierung des gewünschten Datensatzes auf der Festplatte ermöglicht.

Über den Blättern befinden sich die Knoten (Branches), hier gelb dargestellt. Im gegebenen Beispiel kann jeder Knoten nur drei Werte aufnehmen und dementsprechend auch nur drei Kindknoten/-blätter haben. Die Knoten repräsentieren immer nur einen Bereich für die in ihnen gespeicherten Knoten oder Blätter. Der oberste Knoten wird Wurzel (Root) genannt, ist hier blau dargestellt und stellt den Anfang des B-Tree-Index dar.

Um die Funktionsweise zu verdeutlichen, betrachten wir nun einen einzelnen Zahlenblock. Zum Beispiel verweist der zweite Eintrag in der Wurzel (18-28) auf alle Werte zwischen den Zahlen 18 und 28. Da wir insgesamt 6 Zahlen speichern müssen und die maximale Speicherkapazität auf drei Werte pro Blatt festgelegt wurde, muss ein neuer Knoten erstellt werden. Dieser neue Knoten enthält wiederum zwei Einträge (18-23 | 24-28), die sich wiederum auf einen Zahlenbereich beziehen. In diesem Beispiel sind nur zwei der drei Positionen belegt. Auf der untersten Ebene (Ebene 3) werden nun die einzelnen Werte gespeichert. Auch hier gilt das für den gesamten Baum definierte Limit von drei Werten pro Knoten/Blatt.

Im Beispiel ist an der Wurzel (blau) und am zweiten Knoten (gelb) noch eine Position frei. Das bedeutet, dass die maximale Anzahl der zu speichernden Werte noch nicht erreicht ist. Wenn nun die Werte 32 und 36 hinzugefügt werden, wird auf der rechten Seite ein neues Blatt erzeugt. Dieses Blatt erzeugt einen neuen Eintrag im Knoten, der nun drei Einträge hat. Somit kann dieser Baum, der auf drei Einträge pro Knoten begrenzt ist, 27 Einträge auf der dritten Ebene (33) speichern. Wenn die Anzahl der zu speichernden Werte 27 übersteigt, muss eine neue Ebene erzeugt werden. Nun könnte der Baum auf Ebene 4 bis zu 81 Werte speichern (34).

In einer Oracle-Datenbank kann die Größe der Knoten/Blöcke bei der Erstellung der Datenbank festgelegt werden. Nehmen wir als Beispiel eine Blockgröße von 8 KB. Wenn nun Daten wie Strings, Zeitstempel oder Integer mit einer Größe von 8 Byte gespeichert werden, kann ein Block mehr als 400 Einträge speichern. Wie in der Tabelle zu sehen ist, kann dieser Baumtyp bereits bis zu 64 Millionen Einträge auf Ebene 3 und bis zu 25 Milliarden Einträge auf Ebene 4 speichern. In der Praxis sind B-Bäume daher in der Regel nicht tiefer als 4 Ebenen.

Veränderung im B-Tree Index

Ein wesentlicher Aspekt des B-Tree-Index ist seine Fähigkeit, sich selbst auszugleichen. Wenn sich die zugrunde liegenden Daten ändern, sei es durch das Hinzufügen neuer Datensätze oder durch das Löschen vorhandener Datensätze, wird der Baum automatisch umstrukturiert, um seine Ausgewogenheit beizubehalten. Das bedeutet, dass die Blattknoten des B-Baums immer auf der gleichen Ebene bleiben. Dieses automatische Balancing stellt sicher, dass die Suchleistung auch bei dynamischen Änderungen der Daten auf einem konstant hohen Niveau bleibt. Es ist jedoch zu beachten, dass regelmäßige Anpassungen des Index zu einer Verlangsamung beim Einfügen (INSERT), Aktualisieren (UPDATE) und Löschen (DELETE) von Daten im Vergleich zu Tabellen ohne Index führen können.

Um dies zu veranschaulichen, betrachten wir wieder die zuvor indizierten Zahlenwerte von 0 bis 28 und fügen die Werte 13, 15 und 17 hinzu. Durch das Einfügen dieser Werte muss der Baum bis zur Wurzel umstrukturiert werden. Das bedeutet, dass auf jeder Ebene die Zahlenbereiche angepasst werden müssen und ein neues Blatt hinzugefügt werden muss. Die neue Struktur mit den geänderten Werten in Fettdruck ist in der folgenden Abbildung dargestellt.

B-Tree Indizes in Oracle

Der B-Tree-Index bleibt trotz seiner möglichen Schwierigkeiten ein unverzichtbares Werkzeug zur Optimierung von Datenbankabfragen und zur Steigerung der Performance. Um einen B-Tree-Index in Oracle zu erstellen, muss der folgende Code ausgeführt werden:CREATE INDEX index_name ON table_name(attribut_name);

Es ist auch möglich, Indizes über mehrere Attribute einer Tabelle zu erstellen. Dabei ist jedoch zu beachten, dass die Reihenfolge der angegebenen Attribute wichtig ist. Nur wenn die angegebenen Attribute auch in den Filteroperationen (WHERE) der SELECT-Anweisung verwendet werden, kann eine Performance-Optimierung durch den definierten Index erreicht werden. Ist dies nicht der Fall und wird nur ein Teil der Attribute im WHERE-Statement gefiltert, führt der Query Optimizer einen Full Table Scan durch oder verwendet eventuell andere, kleinere Indizes. Dies kann zu einer Verlangsamung der Abfrage führen und die angestrebte Performanceverbesserung verhindern. Um einen Index aus mehreren Attributen in Oracle zu erstellen, wird der folgende Code verwendet:CREATE INDEX index_name ON table_name(attribut_name_1, attribut_name_2);

Best Practice

Bei der Verwendung von B-Tree-Indizes sind verschiedene Aspekte zu beachten, um unerwünschte Verringerungen der Abfragegeschwindigkeit zu vermeiden. Im Folgenden sind die wichtigsten Regeln und Best Practices für die Verwendung von B-Tree-Indizes zusammengefasst:

• Primary Key und Foreign Key: Um die Performance von Abfragen mit einem oder mehreren Joins über Tabellen zu verbessern, ist es ratsam, Indizes für Primär- und Fremdschlüssel anzulegen. Dadurch können Joins schneller ausgeführt werden und bei großen Tabellen muss kein Full Table Scan durchgeführt werden.
• Hohe Kardinalität: Die für den Index ausgewählten Attribute sollten eine hohe Kardinalität aufweisen, also viele eindeutige Werte enthalten. Zum Beispiel hat das Attribut Geburtsdatum eine hohe Kardinalität und das Attribut Geschlecht eine sehr niedrige Kardinalität. Wenn Sie einen B-Tree Index mit niedriger Kardinalität erstellen, wird der Query Optimizer diesen Index mit hoher Wahrscheinlichkeit nicht verwenden. Hier sind andere Index-Typen wie beispielsweise der Bitmap-Index besser geeignet.
• Korrekte Operatoren: Um einen Index in einer Abfrage verwenden zu können, müssen die korrekten Vergleichsoperatoren in der WHERE-Bedingung verwendet werden. Dies sind insbesondere Gleichheitsoperatoren (größer, kleiner, gleich) und Bereichsoperatoren (BETWEEN). Negierende Operatoren wie NOT oder "!=" verhindern die Verwendung eines Index.
• Kleine Anfragemengen: Ein Index wird vom Query Optimizer nur dann verwendet, wenn das Ergebnis eine kleine Teilmenge der Gesamtdaten darstellt. Optimal ist es, wenn die ausgewählten Daten weniger als 1% der verfügbaren Datenmenge ausmachen. Zwischen einem Prozent und zehn Prozent kann der Index noch verwendet werden, bei mehr als zehn Prozent kann ein vollständiger Tabellenscan schneller sein.
• Use Case: Um optimale Indizes zu erstellen, ist es hilfreich, die zu erwartenden SQL-Abfragen zu kennen und die Indizes entsprechend anzupassen.
• Mehrere Attribute: Für komplexe Abfragen und Joins kann es sinnvoll sein, einen Index aus mehreren Attributen zu erstellen. Dabei sollten Attribute mit hoher Kardinalität an erster Stelle stehen, um ein schnelleres Durchlaufen des Indexbaums zu ermöglichen.
• Anzahl der Indizes: Es sollte vermieden werden, zu viele Indizes anzulegen, da dies Speicherplatz verbraucht und SQL-Operationen wie INSERT, UPDATE und DELETE verlangsamen kann.
• Abfrageplan: Um zu überprüfen, ob ein Index in SELECT-Abfragen verwendet wird, kann der Abfrageplan verwendet werden. Dieser zeigt an, ob ein vollständiger Tabellenscan oder ein Index für die zu filternden Attribute verwendet wird.

Fazit

Zusammenfassend lassen sich aus den oben diskutierten Punkten die Gründe für die Verwendung von B-Tree-Indizes in Datenbanksystemen ableiten:

• Effizienz: B-Trees bieten eine effiziente Suchoperation mit einer schlimmstenfalls logarithmischen Komplexität von O(log n), wobei n die Anzahl der Einträge im Baum ist. Dies bedeutet, dass die Suchzeit logarithmisch mit der Anzahl der Einträge wächst, was B-Tree für große Datensätze sehr effizient macht.
• Balancing: B-Trees sind selbstbalancierend, das heißt, wenn Daten hinzugefügt oder entfernt werden, wird der Baum automatisch umstrukturiert, um ein Gleichgewicht zwischen den linken und rechten Teilbäumen aufrechtzuerhalten. Dies stellt sicher, dass Suchoperationen für alle Knoten im Baum ungefähr die gleiche Zeit benötigen und verbessert die Gesamtleistung der Datenbank.
• Bereichsabfragen: B-Tree unterstützt Bereichsabfragen effizient, da die Daten in aufeinander folgenden Blöcken auf der Festplatte gespeichert werden. Dies ermöglicht einen schnellen Zugriff auf Daten innerhalb eines Wertebereichs in einer Spalte.
• Festplattenspeicher: B-Trees sind für die speziellen Anforderungen an Festplattenspeicher optimiert, was bei Datenbanken von entscheidender Bedeutung ist. B-Tree-Indizes minimieren die Anzahl der Suchvorgänge auf der Festplatte, die erforderlich sind, um einen Datensatz zu finden, und verbessern die Gesamtleistung des Systems.

Ihr möchtet mehr über spannende Themen aus der adesso-Welt erfahren? Dann werft auch einen Blick in unsere bisher erschienenen Blog-Beiträge.