Alle Tabs der Lerneinheit (Erklärung · B-Baum-Explorer · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Indexstrukturen (B-Baum & Hash-Index)
Du hast eine Tabelle mit 10 Millionen Studierenden und suchst die MatrNr 1.234.567. Ohne Index: die DB liest jede Zeile, einmal nach der anderen (Full Scan), 10M Vergleiche, langsam. Mit Index: ~3–4 Sprünge im B-Baum, fertig. Indexstrukturen sind der Performance-Hauptschalter für jede produktive DB. Klausur-Pflicht in 8/12 WInf-DB-Klausuren (P2).
Die Idee in einem Satz
Ein Index ist eine zusätzliche Datenstruktur, die die DB beim Suchen anstatt der Tabelle benutzt, schneller als linear durchgehen.
Wie ein Inhaltsverzeichnis in einem Buch: das Buch ist die Tabelle, das Inhaltsverzeichnis der Index. Du springst zur richtigen Seite, ohne alles durchzulesen.
Die zwei klassischen Index-Typen
1. B-Baum (B-Tree), der Standard
Balancierter Suchbaum mit hoher Verzweigung. Jeder Knoten hat mehrere Schlüssel + Verweise auf Kinder. Speziell: ein B+-Baum speichert alle echten Daten in den Blättern, innere Knoten haben nur Such-Schlüssel.
Eigenschaften:
- Höhe O(log n), bei 10M Einträgen ist die Höhe ~3–4.
- Such-Pfad: Wurzel → Verzweigung → Blatt. Bei jedem Knoten: binäre Suche, dann zum passenden Kind.
- Bereichs-Suchen sehr schnell (Blätter sind verkettet).
Beispiel. Eine MatrNr-Suche in einem B-Baum mit Ordnung 3 (max. 3 Schlüssel pro Knoten):
[50]
/ \
[20|40] [70|90]
/ | \ / | \
[10] [25][45] [60][80][95]
Suche nach 45: starte bei [50] → kleiner als 50 → gehe links zu [20|40] → größer als 40 → gehe rechts zu [45] → gefunden. 3 Vergleiche statt 9.
2. Hash-Index
Wert wird durch eine Hash-Funktion in einen Bucket gemappt. Sehr schnell bei exakter Gleichheit.
Eigenschaften:
- Such-Zeit O(1) im Durchschnitt, eine einzige Hash-Berechnung.
- Funktioniert nicht für Bereichs-Suchen (MatrNr BETWEEN 1000 AND 2000), die DB müsste alle Hash-Buckets durchgehen.
- Beispiel-Anwendung: Primärschlüssel-Lookups, JOIN-Indizes.
B-Baum vs. Hash, wann welcher?
| Operation | B-Baum | Hash |
|---|---|---|
| Exakte Gleichheit (=) | ✓ O(log n) | ✓ O(1) |
| Bereich (BETWEEN, <, >) | ✓ O(log n + Treffer) | ✗ Full Scan |
| Sortierte Reihenfolge | ✓ sequentiell aus Blättern | ✗ unsortiert |
| LIKE 'abc%' (Präfix) | ✓ (sortiert) | ✗ |
| LIKE '%abc' (Suffix) | ✗ | ✗ |
Faustregel: wenn du nicht genau weißt, was du brauchst → B-Baum. Hash nur, wenn du garantiert nur exakte Gleichheit suchst (z.B. PK-Lookups).
Index-Trade-offs
Indizes beschleunigen Lesen, verlangsamen Schreiben.
- INSERT: Index muss zusätzlich aktualisiert werden → langsamer als ohne Index.
- UPDATE einer indizierten Spalte: alter Eintrag löschen + neuen einfügen.
- DELETE: Index-Eintrag entfernen.
Faustregel: Indizes auf Spalten, die oft in WHERE/JOIN vorkommen, aber selten geändert werden. Klassiker: PK, FK, häufig gesuchte Felder.
Klausur-Klassiker: wann legt die DB automatisch einen Index an?
| Constraint | Automatischer Index? |
|---|---|
| PRIMARY KEY | ✓ ja (B-Baum) |
| UNIQUE | ✓ ja (B-Baum) |
| FOREIGN KEY | ✗ NEIN (manchmal Diskussion) |
| NOT NULL | ✗ NEIN |
Klausur-Falle: Foreign Keys haben keinen automatischen Index in den meisten DBs (PostgreSQL nicht; MySQL InnoDB ja). Wenn JOIN-Performance wichtig ist, manuell Index auf FK-Spalte anlegen.
Visualisierung
Schau, wie eine Suche in einem B-Baum den Pfad von der Wurzel zum Blatt verfolgt:
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Faustregeln
- B-Baum-Höhe ist O(log n). Bei Millionen Einträgen nur 3–4 Sprünge. Das ist der Hauptgrund warum DBs schnell sind.
- Hash nur für exakte Gleichheit. Bei Range-Queries → B-Baum.
- PK/UNIQUE = automatischer Index. FK = kein automatischer Index.
- Index kostet Schreib-Performance. Trade-off zwischen Lese-Speed und Schreib-Speed.
- EXPLAIN PLAN ist dein Freund. Wenn die Query langsam ist, prüfe ob ein Index benutzt wird (oder ob ein Full Scan passiert).
Typische Stolpersteine
1. Index auf jeder Spalte. Falsch, Indizes kosten Speicher und Schreib-Performance. Nur auf wirklich oft-gesuchte Spalten.
2. Index hilft bei LIKE '%xyz'. NEIN, Suffix-Suchen können keinen Index nutzen, weil der Anfang variabel ist. Nur bei 'xyz%' (Präfix) hilft B-Baum.
3. Hash-Index für Range-Queries. Funktioniert nicht. DB macht Full Scan trotz Index → manchmal sogar schlechter als ohne Index.
4. Composite Index (mehrere Spalten). Die Reihenfolge der Spalten im Index ist relevant. Index (A, B) hilft bei WHERE A=... und WHERE A=... AND B=..., aber NICHT bei WHERE B=... allein.
B-Baum-Explorer
B-Baum-Explorer
Klicke einen Suchwert und beobachte, wie sich der Suchpfad durch den B-Baum bewegt, wenige Sprünge selbst bei tausenden Einträgen.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "wie schnell findet man Wert X in einem B-Baum mit n Einträgen?" → O(log n). Bei n=10M ist das ~23 Vergleiche, bei n=1Mrd ~30. Linear wäre 10M bzw. 1Mrd.
Praxis-Übung
Indexstrukturen, Praxis-Übung
6 Aufgaben zu B-Baum, Hash-Index, Index-Auswahl, Trade-offs.
Klausurfragen mit Lösungen (6)
- F1.Welche Such-Komplexität hat ein B-Baum-Index?
Antwort: O(log n)
Erklärung: B-Baum ist balanciert mit hoher Verzweigung → Höhe O(log n). Bei 10M Einträgen sind das ~23 Vergleiche binär, in Praxis (typ. Verzweigung 100+) sogar nur 3–4.
- F2.Wann ist ein Hash-Index NICHT geeignet?
Antwort: Bei Range-Queries (BETWEEN, <, >)
Erklärung: Hash-Indizes machen keine Sortierung, die Werte sind 'gehasht' auf zufällig verteilte Buckets. Range-Queries würden alle Buckets durchgehen müssen, also faktisch Full Scan. Für Range immer B-Baum.
- F3.Welche Constraints führen meist zu automatisch erzeugten Indizes?
Antwort: PRIMARY KEY und UNIQUE
Erklärung: PRIMARY KEY und UNIQUE bekommen automatisch einen B-Baum-Index. FOREIGN KEY NICHT in PostgreSQL/Oracle (Klausur-Falle); MySQL InnoDB tut es. Wenn JOIN-Performance wichtig ist, FK-Index manuell anlegen.
- F4.Mehr Indizes machen die Datenbank in jeder Hinsicht schneller.
Antwort: Falsch
Erklärung: FALSCH. Indizes beschleunigen Lesen (SELECT), verlangsamen Schreiben (INSERT/UPDATE/DELETE), weil der Index jedes Mal aktualisiert werden muss. Plus Speicher-Overhead. Faustregel: Indizes auf häufig gesuchte, selten geänderte Spalten.
Typ: Wahr/Falsch
- F5.Ordne die Operation der besten Index-Struktur zu:
Zuordnungen:
- WHERE MatrNr = 1001 → Hash oder B-Baum
- WHERE Note BETWEEN 1.0 AND 2.0 → B-Baum
- WHERE Name LIKE 'Mül%' → B-Baum (Sortierung)
- WHERE Beschreibung LIKE '%suche%' → Kein Standard-Index (Full-Text Search)
Erklärung: B-Baum ist universeller, funktioniert für Gleichheit, Range, Präfix. Hash nur für exakte Gleichheit. Suffix/Substring-Suchen brauchen spezielle Full-Text-Indizes (z.B. PostgreSQL GIN).
Typ: Zuordnung
- F6.Welche Aussage über Composite-Indizes (auf mehrere Spalten) ist KORREKT?
Antwort: Index (A, B) hilft bei WHERE A=... AND B=...
Erklärung: Composite (A, B) ist ein einziger sortierter B-Baum mit A als Hauptsortierung, B als Sekundär. Hilft bei A=... oder A=... AND B=..., aber NICHT bei B=... allein (Spalten-Reihenfolge zählt). Klausur-Klassiker.
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Eine Tabelle hat 1M Zeilen. Ohne Index: 1M Vergleiche. Wie viele mit B-Baum (typ. Verzweigung 100)?
Antwort: ~3
Erklärung: log₁₀₀(1.000.000) = 3. Drei Sprünge im B-Baum statt 1.000.000 sequentiell. Das ist der Grund warum Datenbanken überhaupt skalierbar sind.
- F2.Welcher Index-Typ unterstützt Range-Queries (WHERE x BETWEEN a AND b)?
Antwort: B-Baum / B+-Baum
Erklärung: B-Baum/B+-Baum: Blätter sind sequenziell verkettet (B+-Baum), Range-Scan startet bei a-Position und läuft sequenziell bis b. Hash kann das nicht.
- F3.In den meisten Datenbanken (PostgreSQL, Oracle) wird beim Anlegen eines FOREIGN KEY automatisch ein Index auf die FK-Spalte erzeugt.
Antwort: Falsch
Erklärung: FALSCH. PostgreSQL und Oracle legen KEINEN automatischen Index auf FK. Das ist eine häufige Quelle für JOIN-Performance-Probleme. MySQL InnoDB legt einen an. Klausur-Trick.
Typ: Wahr/Falsch
- F4.Sortiere die Schritte einer B-Baum-Suche für MatrNr=1005:
Richtige Reihenfolge:
- Starte an der Wurzel: vergleiche MatrNr mit Schlüsseln
- Folge dem passenden Kind-Pointer
- Im inneren Knoten: erneut vergleichen, weiter zum Kind
- Erreiche das Blatt mit dem Schlüssel (oder Disqualifikation)
- Hole die zugehörigen Daten (oder bestätige Nicht-Vorhanden)
Erklärung: Klassischer Top-Down-B-Baum-Search. Jeder Schritt entscheidet welches Kind. Bei B+-Baum sind nur die Blätter Daten, innere Knoten dienen nur als Wegweiser.
Typ: Reihenfolge
- F5.Welche Operation kann KEIN Index beschleunigen?
Antwort: WHERE LOWER(x) = 'abc'
Erklärung: Funktion auf indizierte Spalte (LOWER(x)) verhindert Index-Nutzung, DB muss für jede Zeile LOWER() ausrechnen. Lösung: Funktionsbasierter Index (PostgreSQL: CREATE INDEX ... ON tbl(LOWER(x))). Klausur-Stolperstein.
- F6.Ein B-Baum-Index hat Suchzeit {{1}} und unterstützt Range-Queries. Ein Hash-Index hat Suchzeit {{2}} für Gleichheit, aber {{3}} für Range. PK und UNIQUE bekommen meist {{4}} einen Index.
Lösungen pro Lücke:
- {{1}}: O(log n)
- {{2}}: O(1)
- {{3}}: O(n) / Full Scan
- {{4}}: automatisch
Erklärung: Klausur-Pflichtwissen-Lückentext. B-Baum-O(log n), Hash-O(1), Hash-keine Range, PK/UNIQUE = automatischer Index.
Typ: Lückentext
