Die Frage „Was ist eigentlich ein Index?“ kann man auf verschiedene Arten beantworten. Im Idealfall sorgt ein Index dafür, dass eine Abfrage durch den SQL Server schneller abgearbeitet werden kann und weniger Ressourcen verbraucht werden. Natürlich gibt es auch eine technische Erklärung dazu. Ein Index ist eine Datenstruktur im SQL Server. Mit Hilfe dieser Datenstruktur können Abfragen effizienter verarbeitet werden.

Tabellen

Zuerst müssen wir dafür betrachten wie der SQL Server Daten speichert. Ein einfaches CREATE TABLE Statement erzeugt ermöglicht es im SQL Server Daten innerhalb einer Tabelle zu speichern. Die Daten werden dann erstmal als Heap abgelegt. Heap kann man hierbei wirklich wörtlich übersetzen mit Haufen. Es ist ein ungeordneter Haufen an Daten. Die Daten werden wenn sie gespeichert werden sollen durch den SQL Server gerade dort abgelegt wo Platz ist. Es ist keinerlei Ordnung in den Daten. Beim Einfügen der Daten sind wir damit unglaublich schnell, da der Server nicht darauf achten muss wo er die Daten ablegt. Leider ist im Gegenzug das Abfragen der Daten sehr langsam, durch die fehlende Sortierung.

Je nach Aufgabe der Datenbanktabelle ist ein Heap durchaus sinnvoll als Verwendung. Werden Daten sehr oft geschrieben und nur ganz selten gelesen wie es zum Beispiel bei einer Log-Tabelle oft der Fall ist, wird oft ein Heap verwendet. Es gibt noch einige andere sinnvolle Einsatzbereiche für den Heap.

In den meisten Fällen wollen wir unsere Daten aber sortiert haben. Hier kommt dann der Index ins Spiel. Stellen wir uns mal einen Supermarkt vor. Würden hier alle Waren so wie sie angeliefert werden einfach irgendwo in ein Regal gelegt, in dem gerade Platz frei ist, finden wir nicht die Waren die wir als Kunde suchen. Hier müssen Daten sortiert sein. Normalerweise passiert das dann nach Gruppen an Waren. So stehen zum Beispiel alle Getränke immer in einem Bereich, alle Konserven stehen in einem Gang etc. So ist es viel einfacher die Waren zu finden die man letztendlich kaufen will und wenn ich den Supermarkt kenne, weiß ich genau zu welchen Regalen ich laufen muss um das zu finden was ich suche. Ähnlich funktioniert es in einem Index in der Datenbank. Sind die Daten dort sortiert, weiß der SQL Server genau wo er suchen muss um die passenden Daten zu finden. So muss er nicht die ganze Tabelle lesen bis er die Daten hat. Damit können meine Daten viel schneller ausgelesen werden und ich verbrauche viel weniger Rechenzeit.

Wie sieht denn nun so ein Index aus?

Ein Index wird immer in einer Baumstruktur gespeichert. Baum kann man hier tatsächlich relativ wörtlich nehmen. Wir haben einen Einstiegspunkt, den Stamm. Von dort aus gehen Äste ab und verzweigen sich. Irgendwann kommen wir am Ende an und haben ein Blatt erreicht. Auf diesem Blatt stehen dann unsere Daten.

In der Informatik ist der Baum eine sehr häufig verwendete Struktur. Mit Hilfe eines Baumes lassen sich Daten sehr gut strukturieren und können schnell gefunden werden. Mit jeder Gabelung – der Stelle an der sich ein Ast teilt – definieren wir einen neuen Bereich an Werten. Ein ganz einfaches Beispiel wäre eine Sortierung der Zahlen 1 – 8. Wir beginnen mit einem Wurzelknoten. Dieser teilt sich auf 2 Äste auf. Im Bereich des ersten Astes stehen alle Zahlenwerte von 1 – 4 und der zweite Ast hat die Werte von 5 – 8. In der zweiten Ebene haben wir dann schon 4 Äste. Im Bereich des ersten Astes liegen die Zahlen 1 und 2, beim zweiten Ast die Zahlen 3 und 4, beim dritten Ast die Zahlen 5 und 6 und im vierten Ast die Zahlen 7 und 8. In der dritten Ebene haben wir dann die Blätter mit den Zahlen. Das klingt erstmal kompliziert wenn man es sich einmal aufzeichnet wird es aber schnell deutlich. Wenn wir nun beispielsweise die Zahl 5 suchen können wir mit wenigen Schritten zu ihr gelangen. Wir fangen an unserem Wurzelknoten an und sehen wir müssen auf den zweiten Ast. Der erste fällt für unsere Suche komplett raus. Wir folgen den ersten Ast und sehen auf der zweiten Ebene, dass wir dort auf den linken Ast – den dritten Ast der Ebene – müssen um auf das Blatt mit unserer Zahl zu kommen. Somit haben wir 3 Schritten unser Ziel erreicht. Stellen wir uns vor wir haben keinen Baum. Dann fangen wir beim ersten Eintrag an und finden einen Zahl. Entweder es ist die 5 oder nicht. Selbst wenn wir davon ausgehen, dass die 5 nur einmal vorkommt müssen wir im schlechtesten Fall 10 Einträge anschauen. In der Realität hätten wir die Zahlen vermutlich nicht nur einmal sondern jede einzelne Zahl beliebig oft. Wenn wir dann alle Einträge mit der 5 haben wollen, können wir sie über den Baum in unserem Beispiel mit 3 Schritten erreichen. Haben wir keinen Baum müssen wir alle Einträge anschauen da wir nicht sagen können ob nicht nochmal ein Eintrag mit einer 5 kommt. Selbst wenn dann direkt der erste eine 5 ist könnte auch der letzte oder jeder andere noch eine 5 sein. Hier zeigt sich wie der Baum hilft Daten schneller zu finden. Im SQL Server wird der Baum etwas anders umgesetzt. Das Prinzip bleibt aber das gleiche. In dem gerade beschrieben Beispiel würde man in der Informatik von einem Binär Baum sprechen. Wir haben an jeder Astgabelung nur zwei Wege. Für den SQL Server wurde hier eine effektivere Variante der Bäume gewählt. An einer Astgabelung können nicht nur zwei Wege sein sondern mehrere. Zusätzlich wird beim Baum im SQL Server darauf geachtet, dass alle Wege immer gleich lang sind. Egal welchen Wert ich suche sind immer gleich viel Schritte notwendig um den Eintrag zu finden. Dieser Baum heißt B-Tree. Das B steht hierbei aber nicht für Binär sondern für Balanced. Der Baum ist immer balanciert, alle Blattknoten mit Daten liegen auf einer Ebene und garantieren somit dass die Wege immer gleich lang sind. Wenn man jetzt Daten in den Baum einfügen will muss er unter Umständen umsortiert werden was je nach Größe des Baumes schon mal etwas länger dauern kann. Auch das Einfügen ohne dass der ganz Baum umsortiert werden muss ist aufwändiger als das Speichern in einem Heap.

Wie der SQL Server die Daten speichert und welche Arten von Index es im SQL Server zeige ich euch in Teil 2.