Datenbankindizierung: ein Deep Dive

Langsame Queries sind selten ein Datenbankproblem — sie sind ein Indizierungsproblem. Ein fehlender Index macht aus einem 2ms-Lookup einen 2-Sekunden-Full-Table-Scan. Ein falsch platzierter Index verschwendet Speicherplatz und verlangsamt Schreibvorgänge, ohne irgendeinen Lesevorteil zu bringen. Zu verstehen, wie Indizes wirklich funktionieren, verändert die Art, wie man Schemas entwirft und Queries schreibt.

Wie B-Tree-Indizes funktionieren

Der Standard-Indextyp in PostgreSQL, MySQL und den meisten relationalen Datenbanken ist ein B-Tree. Er ist eine sortierte, balancierte Baumstruktur, die O(log n)-Lookups statt O(n)-sequenzieller Scans ermöglicht.

-- Without an index, this scans every row in the table
SELECT * FROM orders WHERE customer_id = 'cust_abc123';
-- Seq Scan on orders: rows=1,000,000, time=1,847ms
 
-- With an index, it traverses a tree to find matching rows
CREATE INDEX idx_orders_customer_id ON orders (customer_id);
-- Index Scan using idx_orders_customer_id: rows=47, time=0.8ms

Der Index speichert customer_id-Werte sortiert mit Zeigern auf die tatsächlichen Tabellenzeilen. Statt eine Million Zeilen zu lesen, durchläuft die Datenbank einen Baum von vielleicht 3-4 Ebenen Tiefe.

Zusammengesetzte Indizes und Spaltenreihenfolge

Ein zusammengesetzter Index deckt mehrere Spalten ab. Die Spaltenreihenfolge bestimmt, welche Queries davon profitieren.

-- ❌ Two separate indexes — only one gets used per query
CREATE INDEX idx_status ON orders (status);
CREATE INDEX idx_date ON orders (created_at);
 
-- This query can only use ONE of these indexes, then filters the rest
SELECT * FROM orders
WHERE status = 'shipped' AND created_at > '2020-01-01';
 
-- ✅ Composite index — covers the entire WHERE clause
CREATE INDEX idx_orders_status_date ON orders (status, created_at);
 
-- Now the database uses one index seek for both conditions

Die Leftmost-Prefix-Regel ist entscheidend: Ein zusammengesetzter Index auf (status, created_at) unterstützt Queries, die nur nach status filtern, oder nach status + created_at, aber nicht nach created_at allein. Man kann es sich wie ein Telefonbuch vorstellen — man findet alle Müllers, oder Müller + Hans, aber man kann nicht effizient alle Hans über alle Nachnamen hinweg finden.

-- ✅ Uses the composite index (leftmost prefix)
SELECT * FROM orders WHERE status = 'pending';
SELECT * FROM orders WHERE status = 'pending' AND created_at > '2020-01-01';
 
-- ❌ Cannot use the composite index efficiently
SELECT * FROM orders WHERE created_at > '2020-01-01';

Covering Indexes

Ein Covering Index enthält alle Spalten, die eine Query benötigt, wodurch das Lesen der eigentlichen Tabellenzeile entfällt. Das ist ein Index-Only Scan — der schnellstmögliche Lesepfad.

-- Query needs customer_id and total
SELECT customer_id, total FROM orders WHERE status = 'completed';
 
-- Regular index — finds rows via index, then fetches from table (heap)
CREATE INDEX idx_status ON orders (status);
 
-- Covering index — all needed columns are IN the index
CREATE INDEX idx_status_covering ON orders (status) INCLUDE (customer_id, total);
-- Index Only Scan: no heap fetches needed

Der Trade-off: Covering Indexes sind größer und langsamer zu aktualisieren. Nutze sie für lesehäufige Queries auf Spalten, die sich selten ändern.

Partielle Indizes

Warum Zeilen indizieren, die man nie abfragt? Partielle Indizes decken eine Teilmenge der Tabelle ab und sparen Speicherplatz und Schreib-Overhead.

-- ❌ Full index — includes millions of completed orders you rarely query
CREATE INDEX idx_orders_status ON orders (status);
 
-- ✅ Partial index — only indexes the rows you actually filter on
CREATE INDEX idx_orders_active ON orders (status)
WHERE status IN ('pending', 'processing', 'shipped');

// Common use case: "active" records in a soft-delete system
// Only 5% of users are active, but 95% of queries filter on active
 
// The partial index is 20x smaller and 20x faster to maintain

Wenn Indizes schaden

Indizes sind nicht kostenlos. Jeder INSERT, UPDATE und DELETE muss alle relevanten Indizes aktualisieren. Zu viele Indizes verlangsamen Schreibvorgänge und verschwenden Speicherplatz.

-- ❌ Over-indexed table — every write updates 8 indexes
-- orders table with indexes on:
-- (id), (customer_id), (status), (created_at), (updated_at),
-- (total), (shipping_method), (payment_status)
 
-- Each INSERT now writes to 9 locations (1 table + 8 indexes)

EXPLAIN ist dein bester Freund

Bevor du einen Index hinzufügst, nutze EXPLAIN ANALYZE, um den aktuellen Query-Plan zu verstehen. Nachdem du ihn hinzugefügt hast, überprüfe, ob der Index tatsächlich genutzt wird.

EXPLAIN ANALYZE
SELECT * FROM orders
WHERE customer_id = 'cust_abc123'
  AND status = 'pending'
ORDER BY created_at DESC
LIMIT 10;
 
-- Look for:
-- "Seq Scan" → needs an index
-- "Index Scan" → using an index
-- "Index Only Scan" → best case, covering index
-- "Bitmap Index Scan" → multiple indexes combined
-- "actual time" → real execution time, not estimates

Vertraue nicht den Schätzungen des Query-Planers — nutze immer ANALYZE, um die tatsächlichen Ausführungszeiten zu sehen. Und führe ANALYZE auf der Tabelle aus, nachdem du Daten hinzugefügt hast, damit der Planer aktuelle Statistiken hat.

Die wichtigsten Punkte

1. B-Tree-Indizes machen aus O(n)-Scans O(log n)-Lookups — ein einziger fehlender Index kann eine Query 1000-mal langsamer machen
2. Die Spaltenreihenfolge in zusammengesetzten Indizes ist entscheidend — die Leftmost-Prefix-Regel bestimmt, welche Queries profitieren
3. Covering Indexes eliminieren Tabellenzugriffe — binde häufig selektierte Spalten mit INCLUDE ein
4. Partielle Indizes sparen Speicherplatz — indiziere nur die Zeilen, die deine Queries tatsächlich filtern
5. Zu viele Indizes verlangsamen Schreibvorgänge — jeder Index wird bei jeder Mutation mitgepflegt
6. Validiere immer mit EXPLAIN ANALYZE — rate nicht, miss