Datenbank richtig nutzen (1) – Indizes

Die meisten Web-Anwendungen nutzen zur Datenspeicherung Datenbanken. Das aus einem guten Grund, haben sie doch den Ruf, sehr performant mit Datenabfragen umgehen zu können. Das stimmt zwar, doch leider sehe ich immer wieder Fälle, in denen die Datenbank diesem Ruf nicht gerecht wird; nicht weil sie es nicht könnte, sondern weil sie nicht entsprechend aufgebaut wurde. Deshalb möchte ich nun auf wichtige Punkte eingehen, die oft fehlerhaft sind. Im ersten Teil sind das Indizes.

Der korrekte Einsatz von Indizes macht wohl mit Abstand den größten Geschwindigkeitsunterschied in Abfragen aus. Es ist deshalb extrem wichtig, den richtigen Index auszuwählen, um eine Grundvoraussetzung für eine performante Datenbank zu erfüllen. Hierzu muss man sich erstmal klar machen, was für Typen es gibt. In mySQL sind es die Typen

  • Primary Key
  • Unique Key
  • Index
  • Fulltext

Jetzt muss man natürlich wissen, für was diese Typen stehen.

Primary Key
Der Primary Key (dt. Primärschlüssel) ist mit Abstand der wichtigste Index in einer Tabelle. Er kann je Tabelle einmal verwendet werden und darf dabei über einer Spalte vergeben werden als auch über mehrere Spalten definiert sein (siehe später). Jeder Wert des Primärschlüssels darf nur einmal vorkommen, NULL ist nicht zulässig.

Unique Key
Der Unique Key ähnelt dem Primärschlüssel in der Eigenschaft, dass jeder Wert nur einmal vorkommen darf. Dieser Wert darf jedoch auch NULL sein. Er kann je Tabelle mehrmals vergeben werden, sowohl über einzelne Spalten als auch über Spalten-Kombinationen.

Index
Der Index ist die schwächste Form der Datenbankindizes. In ihm dürfen Werte mehrmals vorkommen. Er kann je Tabelle mehrmals vergeben werden, sowohl über einzelne Spalten als auch über Spalten-Kombinationen.

Fulltext
Fulltext ist ein spezieller Index, welcher die Volltextsuche in mySQL wesentlich vereinfacht. Er ist jedoch auf myISAM-Tabellen beschränkt.

Sinn und Zweck
Jetzt stellt sich natürlich die Frage: was ist der Sinn der Indizes. Stellen wir uns vor, wir haben eine Tabelle mit 100.000 Einträgen. Nun wollen wir den Eintrag herausfiltern, welcher in der Spalte „id“ den Wert „501“ enthält. Ohne Index muss die Datenbankengine nun Zeile für Zeile durchgehen und den Spaltenwert „id“ mit „501“ vergleichen. Dies kann schlimmstenfalls (worst case) die letzte Zeile sein. Wir mussten also alle 100.000 Einträge anschauen, um eine einzelne Zeile zu finden. Der Theoretiker spricht hier von einer Komplexität von O(n), weil für n Einträge n Daten angeschaut werden müssen. Mit der Summe an Anfragen wird das natürlich ein Flaschenhals für den Server.

Indizes bringen nun die Lösung. Alle Typen sind in der Regel als B-Baum realisiert (andere Methoden sind möglich und werden auch von mySQL unterstützt – wer sich der Bedeutung des B-Baums nicht klar ist, sollte den Wikipedia-Artikel zum Verständnis lesen). Da der Index immer über mindestens ein Feld definiert werden muss, steht der Inhalt dieses Feldes im B-Baum sowie ein Verweis zum korrekten Speicherplatz des Eintrages. Mit Hilfe der Sortierung des Baumes ist es nun möglich, nicht alle Einträge anschauen zu müssen, so dass im schlimmsten Fall eine Komplexität von O(log n) existert. Dies lässt sich leicht erklären, wenn man sich folgendes verdeutlicht (anhand einer Vereinfachung: des Binär-Baums – er hat nur zwei Kinder): Bei jedem Vergleich der Daten weiß man, ob man im Baum nun links oder rechts absteigen muss. Ist der Baum gleichmäßig aufgebaut, so würde sich die Anzahl der übrigen Vergleiche mindestens halbieren. Das gleiche passiert beim nächsten Vergleich wieder und so weiter. Die Logarithmus-Funktion zeigt dabei sehr anschaulich, dass mit höherer Anzahl an Einträgen ein Index extreme Verbesserungen mit sich bringt (siehe Grafik: grün ist die Logarithmus-Funktion, violett die Gerade).


O(log(n)) vs O(n)

Der Einsatz eines Indizes lohnt sich also. Je nach Einsatzzweck muss man „nur“ den richtigen wählen.

Verwendung
MySQL verwendet die Indizes automatisch, sobald ein passender vorhanden ist. Mittels SQL-Befehl „EXPLAIN“ vor einer normalen SQL-Anweisung kann man prüfen, ob ein Index (und welcher) verwendet wird. So wird bei der Abfrage …


SELECT * FROM user WHERE userID=50

… ein Index über die Spalte userID verwendet (sofern sie vorhanden ist). MySQL ist dabei egal, ob es sich um einen Primary-Key, Unique-Key oder einfachen Index handelt. Diese spielen Ihre Unterschiede wesentlich nur beim Speichern aus. Der Fulltext-Index spielt hier eine andere Rolle (hier bitte die Doku lesen)

Wichtig ist nun anzumerken, dass mySQL lediglich einen Index je Abfrage verwenden kann. Dies ist wichtig zu wissen. Stellen wir uns vor, wir haben in einer Benutzertabelle jeweils einen Index über „nickName“ und „password“ erstellt und starten nun die Abfrage zur Verifikation der Benutzerdaten:


SELECT * FROM user WHERE nickName="wurstbrot" AND
                                       password="sdfe46tgfgdsg34"

So könnte mySQL lediglich den Index über „nickName“ oder „password“ verwenden, nicht jedoch beide, womit wir einen Geschwindigkeitsnachteil erfahren (sofern beide Felder nicht eindeutig sind). Die Lösung ist aber denkbar einfach: man erstellt einfach einen Index über beide Felder. Damit kann der Index voll ausgenutzt werden. mySQL erkennt selbständig, dass dieser Index besser passt, auch wenn Indizes über einzelne Spalten vorhanden sind.

Datenbankbesonderheiten
Jetzt sollte man berücksichtigen, dass man die Indizes nicht blind verwenden sollte. So ist bei sqLite leider ein Schwachpunkt bei der Verwendung von Indizes zu berücksichtigen:

Every time the database is opened, all CREATE INDEX statements are read from the sqlite_master table and used to regenerate SQLite’s internal representation of the index layout.

Das bedeutet, dass bei jedem Öffnen der Datenbank der Index neu erzeugt wird. Das ist für PHP-Anwendungen möglichst dämlich, da mit jeder Anfrage die Datenbank neu geöffnet wird. Es wird also mit jeder Anfrage der Index neu erzeugt, womit auch gleich ohne Index gearbeitet werden kann. Im schlimmsten Fall hat man die gleiche Komplexität. Leider ein großer Schwachpunkt der ansonsten netten Datenbank.

10 Kommentare zu “Datenbank richtig nutzen (1) – Indizes

  1. Der Index mit 2 Feldern ist in mysql 5 nicht mehr zwingend erforderlich. Ab dieser Version erkennt der mysql-Optimizer sehr wohl „Einzel-Indexe“ und kann sie optimieren.
    Ein Hinweis auf die Möglichkeit, sich anzusehen, welche Probleme eine SQL-Abfrage unter mysql machen kann, ist folgender: „Explain SELECT … “
    Hier werden auch die benutzen Indices erwähnt.

  2. Hi, interessanter Artikel
    nutze Indexe gerne über mehre Spalten.
    Zb für Options tabellen in der form
    GruppenID, OptionsName, OptionsWert

    dann unique key über gruppenid und den namen und dann kann man wunderbar REPLACE nutzen, denn schließlich bruahc man erstmal nicht prüfen ob der wert schon vorhanden ist und dann gegebenfalls INSERT oder halt UPDATE
    Spart immerhin eine Abfrage 🙂
    MfG

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *