Zum Inhalt

Index-Interna: B-Tree, GIN, GiST & BRIN Architektur unter Linux

Erstellt: 08.11.2026  ·  Zuletzt aktualisiert: 08.11.2026  ·  Nejat Hakan

Management Summary: Ein Index tauscht Speicherplatz auf der NVMe und Schreib-Overhead gegen drastische Reduktionen der Lese-Latenz ein – und verwandelt einen teuren O(N)-Tabellenscan in einen schnellen O(log N)-Baumdurchlauf oder einen O(1)-Bitmap-Lookup. Wer jedoch Standard-B-Trees wahllos auf JSON-Dokumente, geometrische Datenbereiche oder Multi-Terabyte-Append-Only-Zeitreihen anwendet, erzeugt massiven Speicher-Bloat und verstopft den Pufferpool. Dieser Leitfaden analysiert die physischen Datenstrukturen und Algorithmen von B-Tree, GIN, GiST und BRIN sowie die Produktivmuster Covering-Indizes (INCLUDE), partielle Indizes und das unterbrechungsfreie CREATE INDEX CONCURRENTLY.

  • B-Tree-Architektur

    Balancierte N-näre Suchbäume durchlaufen: Wurzel- und Verzweigungsknoten passieren und über doppelt verkettete Blattknoten Bereiche scannen.

  • GIN für JSONB & Arrays

    Semi-strukturierte Dokumente in invertierte Posting-Listen aufbrechen: Blitzschnelle Containment- (@>) und Key-Lookups in JSONB ermöglichen.

  • :material-compress:{ .lg .middle } BRIN Zeitreihen-Kompression

    Multi-Terabyte-Tabellen mit 99 % weniger Speicherplatz indizieren: Minimal- und Maximalwerte je physischem 1-MB-Blockbereich zusammenfassen.

  • Covering- & Partielle Indizes

    Heap-Zeiger-Hops über INCLUDE für Index-Only-Scans eliminieren und gezielt nur aktive Datensätze (WHERE status = 'PENDING') indizieren.

1. Index-Architektur & mathematische Komplexität

Die Auswahl des richtigen Indextyps richtet sich nach den mathematischen Eigenschaften der Daten und der Abfrage-Operatoren:

Indextyp Zugrundeliegende Datenstruktur Optimale Abfrage-Operatoren Primärer Produktiv-Einsatzzweck
B-Tree (Standard) Balancierter N-närer Baum mit horizontal verknüpften Blattknoten =, <, <=, >, >=, BETWEEN, IN, ORDER BY Hochkardinale Skalarwerte (id, email, created_at, Fremdschlüssel).
GIN (Generalized Inverted) Invertierte Nachschlagetabelle: Einzelner Schlüssel → Posting-Liste von ctids @>, ?, ?&, ?|, @@ (Volltextsuche) Verschachtelte JSONB-Dokumente, Arrays (TEXT[]) und Volltextsuche (tsvector).
GiST (Generalized Search Tree) Balancierter Suchbaum mit beliebigen Hüllkörpern (Bounding Boxes) && (Überlappung), <-> (KNN-Distanz), @> PostGIS Geokoordinaten, IP-Netzwerk-Bereiche (INET) und Exclusion-Constraints.
BRIN (Block Range Index) Min/Max-Grenzwerte je physischem Blockbereich (Standard: 128 Pages = 1 MB) <, >, BETWEEN auf physisch sortierten Daten Riesige chronologische Log-Tabellen, Sensor- und IoT-Telemetrie. 
%%{init: {'flowchart': {'wrappingWidth': 350}}}%%
flowchart TB
    subgraph BTree ["1. B-Tree: Hochpräzises O(log N)"]
        direction TB
        B_ROOT["Wurzelknoten (Root)<br/>Schlüssel: [1000 | 5000]"]
        B_INT["Interner Routing-Knoten<br/>Schlüssel: [250 | 750]"]
        B_LEAF1["Blattseite 1<br/>ctid → (Block 4, Slot 1)"]
        B_LEAF2["Blattseite 2<br/>ctid → (Block 4, Slot 2)"]
        B_ROOT --> B_INT
        B_INT --> B_LEAF1
        B_INT --> B_LEAF2
        B_LEAF1 <-->|"Scan"| B_LEAF2
    end

    subgraph GIN ["2. GIN: Invertierte Key-Map"]
        direction TB
        G_KEY["JSON-Schlüssel: 'role'"]
        G_POST["Posting-Liste<br/>ctid: [(1,2), (5,8), (9,1)]"]
        G_KEY --> G_POST
    end

    subgraph BRIN ["3. BRIN: Block-Zusammenfassung"]
        direction TB
        BR_RANGE["Blöcke 0–127 (1 MB)"]
        BR_SUM["Min: 2026-01-01<br/>Max: 2026-01-07"]
        BR_RANGE --> BR_SUM
    end

    BTree ==> GIN ==> BRIN

2. B-Tree-Interna: Warum doppelt verkettete Blattknoten entscheiden

In einem B-Tree-Index liegen alle Blattknoten auf exakt derselben Tiefe ausgehend von der Wurzel (was eine gleichmäßige O(log N)-Suchzeit garantiert).

Schnelle Bereichsscans ohne erneuten Wurzel-Durchlauf

Fragt eine Anwendung WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31' ab: 1. Traversiert die Engine den Baum von der Wurzel (Root) über die internen Verzweigungsknoten nach unten, bis sie den ersten passenden Blattknoten für '2026-01-01' findet. 2. Ab diesem Moment durchläuft die Engine die Wurzel nie wieder. Sie folgt den horizontalen, doppelt verketteten Zeigern (next_page / prev_page) direkt von Blattseite zu Blattseite, bis '2026-01-31' erreicht ist. 3. Dadurch laufen sequenzielle Bereichsscans und ORDER BY-Sortierungen mit der vollen Bandbreite des Arbeitsspeichers.

3. GIN (Generalized Inverted Index) für JSONB

Klassische B-Trees indizieren den Wert einer Spalte als unteilbare Gesamtheit. Ein GIN-Index zerlegt semi-strukturierte Werte (wie JSONB-Dokumente oder Arrays) in ihre einzelnen Schlüssel und Werte:

Dokument 1: {"role": "admin", "team": "devops"}
Dokument 2: {"role": "viewer", "team": "devops"}

GIN-Invertierte Map:
  "admin"  --> [Doc 1]
  "viewer" --> [Doc 2]
  "devops" --> [Doc 1, Doc 2]

jsonb_ops vs. jsonb_path_ops

PostgreSQL stellt zwei Operatorklassen für GIN-Indizes bereit: - jsonb_ops (Standard): Indiziert jeden Pfad, Schlüssel und Wert separat. Unterstützt alle Operatoren (?, ?|, @>), führt jedoch zu größeren Indizes. - jsonb_path_ops: Bildet Hashes aus kompletten Pfad-Wert-Paaren (z. B. hash("team.devops")). Der Index ist bis zu 60 % kleiner und schneller, unterstützt aber ausschließlich Containment-Abfragen (@>).

-- Best Practice: Schneller Containment-Index auf JSONB
CREATE INDEX CONCURRENTLY idx_customer_metadata_gin 
    ON customer_orders USING GIN (metadata jsonb_path_ops);

4. BRIN (Block Range Index): Skalierung im Terabyte-Bereich

Auf riesigen Zeitreihen-Tabellen (z. B. 500 Millionen Zeilen an Server-Telemetrie) würde ein B-Tree hunderte Gigabyte an RAM verschlingen.

Werden Daten in natürlicher chronologischer Reihenfolge per INSERT angehängt, sind sie auf der Festplatte bereits physisch vorsortiert:

Physischer Speicher auf NVMe:
  Blöcke 0–127   --> Zeitstempel von 2026-01-01 bis 2026-01-05
  Blöcke 128–255 --> Zeitstempel von 2026-01-06 bis 2026-01-10
  Blöcke 256–383 --> Zeitstempel von 2026-01-11 bis 2026-01-15

Ein BRIN-Index speichert keine Zeiger für einzelne Datensätze. Er merkt sich lediglich die Minimal- und Maximalwerte für jeden zusammenhängenden Blockbereich (Standard: 128 Pages = 1 MB): - Bei einer Abfrage nach WHERE recorded_at = '2026-01-08' überspringt die Engine die Blöcke 0–127 und 256–383 komplett. - Ein BRIN-Index ist typischerweise 100- bis 1000-mal kleiner als ein B-Tree und passt vollständig in den L3-Cache des Prozessors.

-- Best Practice: Extrem schlanker BRIN-Index für chronologische Log-Tabellen
CREATE INDEX CONCURRENTLY idx_server_metrics_brin 
    ON server_metrics USING BRIN (recorded_at) 
    WITH (pages_per_range = 128);

5. Fortgeschrittene Indizierungsmuster

A. Covering-Indizes (INCLUDE) für Index-Only-Scans

Muss eine Abfrage Spalten zurückliefern, die nicht im Index stehen, muss die Engine für jeden Treffer einen wahlfreien I/O-Sprung auf die Heap-Tabelle ausführen.

Mit INCLUDE werden zusätzliche Nutzdaten an die Blattknoten des B-Trees angehängt, ohne den Suchschlüssel zu vergrößern:

-- Ermöglicht Index-Only Scans: Abfrage wird vollständig aus dem Index beantwortet!
CREATE INDEX CONCURRENTLY idx_orders_customer_covering 
    ON customer_orders (customer_id) 
    INCLUDE (total_cents, created_at);

-- Abfrage:
SELECT customer_id, total_cents, created_at 
FROM customer_orders 
WHERE customer_id = 101; -- Null Heap-Hops, wenn die Visibility-Map sauber ist!

B. Partielle Indizes: Nur das Wesentliche indizieren

Sind 99 % aller Bestellungen im Status COMPLETED und nur 1 % im Status PENDING, verschwendet ein Index über die gesamte Tabelle Speicherplatz. Ein partieller Index filtert bereits bei der Indexerstellung:

-- Der Index schrumpft um 99 %, Schreibvorgänge auf abgeschlossene Bestellungen verursachen 0 Index-Overhead!
CREATE INDEX CONCURRENTLY idx_orders_pending_queue 
    ON customer_orders (created_at) 
    WHERE status = 'PENDING';

6. Die goldene Produktionsregel: CREATE INDEX CONCURRENTLY

Ein Standard-CREATE INDEX-Befehl fordert eine SHARE-Sperre auf der Tabelle an und blockiert damit alle parallelen INSERT-, UPDATE- und DELETE-Operationen für die gesamte Dauer der Indexerstellung:

-- NIEMALS IM PRODUKTIVBETRIEB AUF GROSSEN TABELLEN AUSFÜHREN:
CREATE INDEX idx_orders_customer ON customer_orders (customer_id);
-- Blockiert alle Kassiervorgänge und Bezahlungen, bis der Index fertig ist!

-- IMMER CONCURRENTLY VERWENDEN:
CREATE INDEX CONCURRENTLY idx_orders_customer ON customer_orders (customer_id);
-- Scannt die Tabelle im Hintergrund in zwei Durchläufen; Schreibvorgänge laufen ungehindert weiter!

Umgang mit fehlgeschlagenen Concurrent Builds

Bricht ein gleichzeitiger Indexaufbau ab (z. B. durch einen Deadlock), markiert PostgreSQL den Index als INVALID. Ungültige Indizes belegen Speicher und bremsen Schreibvorgänge aus, ohne Abfragen zu beschleunigen. Bereinige diese Indizes: 

-- Ungültige Indizes ermitteln:
SELECT indisvalid, indexrelid::regclass FROM pg_index WHERE NOT indisvalid;
-- Ungültigen Index sicher entfernen:
DROP INDEX CONCURRENTLY IF EXISTS index_name;