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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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).
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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).
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.
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:
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.
Wert wird durch eine Hash-Funktion in einen Bucket gemappt. Sehr schnell bei exakter Gleichheit.
Eigenschaften:
| 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).
Indizes beschleunigen Lesen, verlangsamen Schreiben.
Faustregel: Indizes auf Spalten, die oft in WHERE/JOIN vorkommen, aber selten geändert werden. Klassiker: PK, FK, häufig gesuchte Felder.
| 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.
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.
- 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).
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.
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.
6 Aufgaben zu B-Baum, Hash-Index, Index-Auswahl, Trade-offs.
Klausurfragen mit Lösungen (6)
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.
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.
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.
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
Zuordnungen:
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
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.
Klausurfragen mit Lösungen (6)
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.
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.
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
Richtige Reihenfolge:
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
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.
Lösungen pro Lücke:
Erklärung: Klausur-Pflichtwissen-Lückentext. B-Baum-O(log n), Hash-O(1), Hash-keine Range, PK/UNIQUE = automatischer Index.
Typ: Lückentext