Wie Datenbankindizes wirklich funktionieren

„Füg einfach einen Index hinzu" ist der häufigste Datenbanktipp und zugleich der am häufigsten falsch angewendete – auf langsame Abfragen geworfen, ohne zu verstehen, was der Index eigentlich tut, weshalb er genauso oft gar nichts ändert. Ein Index ist eine zweite, separat sortierte Kopie eines Ausschnitts deiner Daten, die mit der Tabelle synchron gehalten wird und Schreibkosten und Speicher gegen Lesegeschwindigkeit bei bestimmten Zugriffsmustern tauscht.

Ohne Index: der vollständige Scan

Eine Tabelle ohne Index auf einer Spalte ist, für eine auf diese Spalte filternde Abfrage, ein ungeordneter Haufen Zeilen. Um die Zeilen mit email = 'user@example.com' zu finden, bleibt der Datenbank nichts anderes übrig, als jede einzelne Zeile zu prüfen.

SELECT * FROM users WHERE email = 'user@example.com';
-- Seq Scan on users (cost=0.00..18334.00 rows=1 width=120)
--   Filter: (email = 'user@example.com'::text)

Bei einer Tabelle mit ein paar hundert Zeilen ist das sofort erledigt. Bei einer Tabelle mit zehn Millionen Zeilen sind es zehn Millionen Vergleiche für jeden einzelnen Lookup – und es wird linear schlechter, wenn die Tabelle wächst.

Was ein Index tatsächlich ist

Die meisten Indizes (der Standard in Postgres, InnoDB von MySQL, SQL Server) sind B-Bäume: eine balancierte Baumstruktur, in der jeder Knoten sortierte Schlüsselwerte und Zeiger hält, entweder auf Kindknoten oder, auf Blattebene, auf die eigentliche Zeile.

CREATE INDEX idx_users_email ON users (email);

Das baut einen nach email sortierten Baum auf. Das Finden von 'user@example.com' bedeutet nun, im Baum abzusteigen – mit den Werten eines Knotens vergleichen, dem Zeiger zum Zweig folgen, der deinen Schlüssel enthalten könnte, wiederholen – statt die ganze Tabelle zu scannen. Ein B-Baum über eine Million Zeilen braucht typischerweise in der Größenordnung von 20 Vergleichen, um einen Treffer zu finden, nicht eine Million.

EXPLAIN SELECT * FROM users WHERE email = 'user@example.com';
-- Index Scan using idx_users_email on users (cost=0.42..8.44 rows=1 width=120)
--   Index Cond: (email = 'user@example.com'::text)

Dass die cost-Schätzung in der EXPLAIN-Ausgabe von 18334 auf 8.44 fällt, ist das gesamte Argument für Indizes in einer Zeile.

Der Index hilft nur für die Spalten, die er abdeckt

Ein Index auf email nützt einer Abfrage, die auf created_at filtert, nichts. Und er hilft entscheidenderweise auch nicht mehr, sobald die am weitesten links stehende Spalte eines mehrspaltigen Index nicht Teil deines Filters ist.

CREATE INDEX idx_orders_user_status ON orders (user_id, status);

-- uses the index: user_id is the leftmost column
SELECT * FROM orders WHERE user_id = 42;
SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';

-- does NOT use this index: status alone isn't the leftmost column
SELECT * FROM orders WHERE status = 'shipped';

Stell dir einen mehrspaltigen Index wie ein Telefonbuch vor, sortiert nach Nachname, dann Vorname. Du kannst direkt zu „Schmidt" springen und von dort zu „Schmidt, Johann" – aber du kannst es nicht nutzen, um alle mit dem Vornamen „Johann" zu finden, ohne jeden Nachnamen zu prüfen. Die Spaltenreihenfolge in einem zusammengesetzten Index ist keine Kosmetik; sie bestimmt, welche Abfragen der Index tatsächlich bedienen kann.

Indizes sind nicht gratis

Jeder Index muss bei jedem INSERT, UPDATE oder DELETE aktualisiert werden, der eine indizierte Spalte berührt – das ist mehr Arbeit pro Schreibvorgang und mehr Speicher. Eine Tabelle mit acht Indizes zahlt diesen Preis bei jedem Insert achtfach. Deshalb ist blindes Indizieren jeder Spalte ein eigener Fehler: Es verlangsamt Schreibvorgänge und bläht die Datenbank für Indizes auf, die Abfragen nie nutzen.

Prüfe auf Indizes, die niemand verwendet:

-- Postgres: indexes with zero scans since the last stats reset
SELECT relname AS table, indexrelname AS index, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0;

Ein ungenutzter Index ist reine Kostenstelle – kein Nutzen, aber die Schreib- und Speichersteuer wird weiter gezahlt.

LIKE und warum es manchmal deinen Index ignoriert

SELECT * FROM users WHERE email LIKE '%example.com';  -- can't use a standard B-tree index
SELECT * FROM users WHERE email LIKE 'user@%';         -- can

Ein B-Baum-Index ist sortiert und kann deshalb effizient alles finden, was mit einem bestimmten Präfix beginnt ('user@%' – zu dieser Stelle in der Sortierung springen und vorwärts lesen), aber nicht alles, was auf ein bestimmtes Suffix endet ('%example.com' – das kann überall in der Sortierung liegen und fällt daher auf einen vollständigen Scan zurück). Ist Suffix- oder Teilstring-Suche eine echte Anforderung, sind dafür Trigramm-Indizes (pg_trgm in Postgres) oder eine dedizierte Suchmaschine da – ein B-Baum ist dafür nicht das richtige Werkzeug.

EXPLAIN vor dem Indizieren, nicht danach

Der Instinkt, „einfach einen Index hinzuzufügen", überspringt den Schritt, der tatsächlich sagt, ob es helfen wird: zuerst den Abfrageplan ansehen.

EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';

EXPLAIN ANALYZE führt die Abfrage aus und berichtet, was tatsächlich passiert ist – Seq Scan versus Index Scan, wie viele Zeilen untersucht versus zurückgegeben wurden, und reale Laufzeiten. Nutzt eine Abfrage bereits einen Index und ist trotzdem langsam, kann die Lösung ein anderer Index sein (der mehr Spalten der Abfrage abdeckt), eine klügere Abfrage (ein Funktionsaufruf auf der indizierten Spalte, der den Index ebenfalls aushebelt, wird vermieden), oder die Einsicht, dass manche Abfragen – ein Report über ein ganzes Jahr an Daten – von Natur aus viele Zeilen scannen werden.

Fazit

Ein Index verwandelt „jede Zeile prüfen" in „einen sortierten Baum durchlaufen", aber nur für die Spalten, die er abdeckt, und die Zugriffsmuster, die er unterstützt – er ist kein pauschaler Performance-Schalter. Füge Indizes für die Abfragen hinzu, die du wirklich ausführst, in der Spaltenreihenfolge, nach der diese Abfragen tatsächlich filtern, und prüfe mit EXPLAIN, dass die Datenbank nutzt, was du gebaut hast, statt es nur anzunehmen.