Wie funktionieren Indizes: Datenstruktur und Suchalgorithmen

Heute tauchen wir tiefer in die Architektur von Indizes ein und schauen uns an, wie sie eigentlich unter der Haube funktionieren. Denn wenn du weißt, wie ein Index aufgebaut ist, verstehst du nicht nur, warum Abfragen schneller laufen, sondern auch, wie du die optimalen Indizes für verschiedene Aufgaben auswählst.

Wenn wir über die Struktur eines Index sprechen, meinen wir, wie die Daten im Index organisiert sind, damit die Suche schnell abläuft. Stell dir einen Aktenschrank vor. Wenn die Dokumente einfach wild übereinander liegen, ist es schwer, das richtige zu finden. Aber wenn der Schrank alphabetisch sortiert ist, geht die Suche viel schneller. Genau so funktionieren Indizes: Sie ordnen die Daten so, dass die Suche nach Infos maximal schnell abläuft.

B-TREE-Indexstruktur

B-TREE (balanced tree — balancierter Baum) ist der am häufigsten genutzte Index-Typ in PostgreSQL. Im Grunde ist das eine Baumstruktur, bei der die Daten in Knoten organisiert sind und die Suche durch Navigation vom Wurzelknoten zu den Blättern erfolgt.

Wie das aussieht:

         Wurzel
          /       |       \
      Knoten 1  Knoten 2  Knoten 3
     /   \       |       /   \
Blatt1 Blatt2  Blatt3  Blatt4 Blatt5

Jeder Knoten enthält Schlüsselwerte, die die Suche steuern. Zum Beispiel, wenn der Wurzelknoten die Werte [10, 20, 30] enthält, dann gilt:

• Alle Daten kleiner als 10 liegen in Blatt 1.
• Alle Daten zwischen 10 und 20 — in Blatt 2, und so weiter.

Vorteile des B-TREE-Index:

• Schnelle Datensuche: Die Suchkomplexität ist O(log n), was deutlich schneller ist als eine lineare Suche.
• Geeignet für Bereichssuchen (zum Beispiel: Finde alle Werte zwischen 10 und 50).

Beispiel: Angenommen, wir haben eine Tabelle students mit einer Spalte age. Wenn wir einen B-TREE-Index auf diese Spalte anlegen:

CREATE INDEX age_idx ON students (age);

PostgreSQL baut dann einen balancierten Baum für die Alterswerte auf, sodass man schnell Studenten mit einem bestimmten Alter oder Altersbereich finden kann.

Suchalgorithmus im B-TREE

Wenn du eine Abfrage machst, nutzt PostgreSQL den Index zur Suche so:

1. Bestimmt den Suchschlüssel (zum Beispiel Alter 25).
2. Startet beim Wurzelknoten.
3. Vergleicht den Schlüssel mit den Wertebereichen im Knoten und geht in den passenden Kindknoten.
4. Wiederholt Schritt 3, bis ein Blatt erreicht ist.
5. Gibt die Daten aus dem Blatt zurück, die zum Schlüssel passen.

Beispielabfrage:

SELECT * FROM students WHERE age = 25;

Der Index reduziert die Menge der zu scannenden Daten und sorgt so für eine schnelle Suche.

Suchalgorithmen und Performance

Indizes beschleunigen die Suche, weil weniger Zeilen gescannt werden müssen. Ohne Index scannt PostgreSQL die ganze Tabelle (das nennt man sequentieller Scan oder Seq Scan). Mit Index läuft ein Index-Scan (Index Scan), was viel schneller ist.

Vergleich: Sequentieller Scan vs. Index-Scan

• Sequentieller Scan (Seq Scan):

  • PostgreSQL liest jede Zeile der Tabelle, prüft die Abfragebedingungen und gibt passende Zeilen zurück.
  • Wird genutzt, wenn kein Index existiert oder wenn die Abfrage fast alle Zeilen betrifft.

• Index-Scan (Index Scan):

  • PostgreSQL nutzt den Index, um passende Zeilen zu finden, und greift dann nur für diese auf die Tabelle zu.
  • Deutlich schneller bei großen Tabellen, wenn die Abfrage nur einen kleinen Teil der Daten betrifft.

Beispiel: ohne Index Suche nach Alter

SELECT * FROM students WHERE age = 25;

Das Ergebnis kann erfordern, dass 1 Million Zeilen gelesen werden. Mit B-TREE-Index liest das System zum Beispiel nur 100 Zeilen.

Einfluss der Indexstruktur auf die Performance

Indizes sind schneller, weil sie die Menge der gescannten Daten reduzieren. Wenn eine Tabelle Millionen Zeilen hat, organisiert der Index sie so, dass die Abfrage nur ein paar Knoten lesen muss statt die ganze Tabelle.

Es ist super wichtig, die Indexstruktur zu verstehen. Wenn du weißt, wie Indizes funktionieren, kannst du nachvollziehen, warum manche Abfragen langsam sind und wie du sie schneller machst.

Außerdem ist es wichtig zu wissen, welche Indizes du brauchst. Für Bereichssuchen ist B-TREE top. Für Arrays oder JSONB — GIN. Die falsche Indexwahl kann die Datenbank sogar langsamer machen.

Echte Beispiele

Schauen wir uns an, wie Indizes uns im Alltag helfen.

Index für Sortierung

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

Mit einem B-TREE-Index kann PostgreSQL die sortierten Daten direkt aus dem Index holen, ohne extra zu sortieren.

Index für Bereiche

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

Der B-TREE-Index macht es einfach, Zeilen im gewünschten Bereich zu finden.

Häufige Fragen und Stolperfallen

Warum sollte man nicht immer Indizes nutzen? Indizes brauchen Speicherplatz auf der Festplatte und verlangsamen INSERT-, UPDATE- und DELETE-Operationen, weil die Indexstruktur mitgepflegt werden muss. Deshalb solltest du Indizes nur für oft genutzte Spalten anlegen.

Wann helfen Indizes nicht? Bei Abfragen, die fast die ganze Tabelle betreffen (zum Beispiel WHERE true), nimmt PostgreSQL lieber einen Seq Scan, weil das Lesen der Indexknoten keinen Vorteil bringt.