50 Mio Datensätze Zuordnung, Abfragen, Performance

[Rolf b]

Ein DB Server verwendet keinen binären Baum, sondern einen B-Tree oder eine Variante davon. Jeder Knoten im Baum enthält so viele Einträge, dass man damit eine Index-Page füllen kann (die Pagesize zu bestimmen ist je nach Engine eine Optimierungsaufgabe für SQL-Server, File-System oder DB-Admin). Ein Indexeintrag auf Blatt-Ebene enthält die Indexfeld-Daten plus eine Referenz auf die Daten-Page; Indexeinträge auf Knotenebene die Indexfeld-Daten des ersten Eintrags der untergeordneten Page sowie eine Referenz auf diese Page. Bei angenommenen 2K Pagesize und 16 Byte pro Eintrag sind das 128 Einträge, d.h. eine Suche auf 50.000.000 Rows muss maximal $$\log_{128}{50000000} \approx 3,65$$ Zugriffe machen. In den meisten Fällen also 4, und bei 5.000.000.000 Rows kommt nur eine weitere Ebene hinzu.

Grund für den B-Tree ist, dass die Daten von der Festplatte sowieso Page-weise angeliefert werden und ein Plattenzugriff VIEL Zeit braucht. Ist eine Page geladen, kann der Server darin binär den richtigen Eintrag suchen, das ist eine in-memory Operation, wahrscheinlich sogar im Datencache der CPU, und die dafür benötigte Zeit ist im Vergleich zur I/O Zeit komplett vernachlässigbar.

Bei einem Clustering-Index sieht es etwas anders aus, da stecken die Daten in den Indexblättern drin und man bekommt typischerweise einen Indexlevel mehr. Was aber im vorliegenden Fall egal ist; es sei denn, man braucht außer Spieler-ID und Frage-ID noch weitere Daten für die Spieler-Frage Relation.

Beim Schreiben wird's dann aufwändiger: sobald eine Page voll wird muss sie geteilt werden, überfüllt das die Parent-Page im Index, teilt sie sich auch, etc, ggf. bis zum Index-Root. Die geteilten Seiten liegen auf der Platte nicht mehr beieinander, was zu mehr Kopfbewegungen beim Lesen führt, d.h. viele INSERTS machen eine DB mit der Zeit immer langsamer (weshalb man schließlich einen Reorg braucht). Zugegeben, es heißt von MySQL InnoDB, dass es eine schleichende Fragmentierung gut bekämpft. Aber auch ein automatischer Defragmentierer kostet Leistung.

Rolf