Blatt · Datenbank
Indexbaum — warum zwei Zeilen aus einer Million schnell gehen
Eine Datenbank liest keine Zeilen, sie liest Seiten. Das ist die einzige Einheit, in der Geschwindigkeit gemessen wird — und der Grund, warum ein Index bei zwei Treffern gewinnt und bei einer halben Tabelle verliert. Hier ist der Baum gebaut, jede angefasste Seite gezählt und der Abfrageplaner dabei zu beobachten, wie er sich vertut.
Oben die Wurzel, unten die Blätter — nur Blätter tragen Daten, alle liegen auf derselben Tiefe, und sie sind untereinander verkettet. Deshalb kostet ein Bereich nicht mehr als der Einstieg plus das Weiterlaufen in der Kette. angefasste Knoten der laufenden Abfrage.
Ein Index, der falsche Zeilen liefert, ist schlimmer als kein Index. Deshalb wird jede Bereichsabfrage gegen einen stumpfen Durchlauf durch die ganze Tabelle gestellt — alle Grenzenpaare eines Wertebereichs, nicht ein paar Stichproben. Dazu werden die Baumbedingungen nach jeder einzelnen Einfügung und jedem Löschen nachgerechnet: gleiche Tiefe aller Blätter, Sortierung, Mindestfüllung, richtige Trennschlüssel, vollständige Blattkette.
noch nicht geprüft
Warum ein Baum und keine Liste
Mit Verzweigungsgrad 128 fasst eine Ebene 128 Knoten, zwei Ebenen 16 384, drei Ebenen zwei Millionen. Deshalb ist die Höhe eines echten Index praktisch immer drei oder vier — und deshalb kostet ein Punktzugriff auf eine Milliarde Zeilen kaum mehr als auf tausend.
Warum der Index verliert
Bei vielen Treffern springt der Index für jede Zeile in eine beliebige Tabellenseite. Liegen die Zeilen verstreut, wird jede Seite mehrfach geholt oder es sind mehr Zugriffe als Seiten insgesamt. Der vollständige Durchlauf liest dieselben Seiten genau einmal, in Reihenfolge — und gewinnt.
Was Clustering ändert
Liegen die Zeilen in Schlüsselreihenfolge auf der Platte, liest der Index sie zusammenhängend, und der Kipppunkt verschiebt sich weit nach oben. Das ist der ganze Unterschied zwischen einem clustered index und einem gewöhnlichen — im Schalter oben umzustellen, in der Kurve sofort zu sehen.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Alle Blätter: ssims437.github.io