Mit Datenbankperformance und SQL hat das Beispiel scheinbar gar nichts zu tun. Um jedoch zu verstehen, worum es bei effizientem Performance-Tuning überhaupt geht und wie es eigentlich funktioniert, ist es ausgesprochen lehrreich.
Und da es nebenbei sehr schön demonstriert, wieso ein Index eigentlich so wichtig ist, hat es eigentlich doch schon wieder mit Datenbanken zu tun.

 

Naive oder lineare Suche:

 

Dieser einfachste Suchalgorithmus durchläuft einfach alle Elemente einer Liste, bis das gewünschte gefunden ist. Im Mittel werden daher bei n Elementen n/2 Suchschritte benötigt.

 

Der Algorithmus ist auf allen Datenmengen anwendbar.
Bei einer Verdoppelung der Datenmenge verdoppelt sich auch die durchschnittlich benötigte Anzahl der Suchschritte.
Für 65536 Elemente braucht der Naive Algorithmus im Mittel.

 

Binäre Suche:

 

Dieser Algorithmus ist ein sogenannter Divide-et-Impera-Algorithmus und zur Suche erheblich effizienter, insbesondere bei großen Datenmengen.
Er nimmt an, daß das gesuchte Element in der Mitte der Liste liegt, und prüft das Vorliegen ab. Wenn – erwartungsgemäß – dieses Element doch kein Treffer ist, wird verglichen, ob das gewünschte Element größer oder kleiner als die Mitte ist. Wenn es beispielsweise kleiner ist, kann die größere Hälfte für die weitere Suche entfallen.
Die Hälfte, in der jetzt zu suchen ist, wird jetzt nach dem gleichen Schema wieder halbiert und so weiter.

 

 

Kein Licht ohne Schatten: Der Algorithmus ist nur auf sortierten Datenmengen anwendbar, da die Annahme, ein Element aufgrund eines Vergleichs in einer bestimmten Hälfte zu finden, sonst keinen Boden hat.
Bei einer Verdoppelung der Datenmenge kommt jedoch nur ein (1!) Suchschritt hinzu.
Für 65536 Elemente braucht der Binäre Algorithmus maximal 16, im Mittel 8(!) Schritte.
Da viele Datenbankmechanismen (Sortierung , Selektion oder Join seien hier genannt) das Vorliegen einer Vorsortierung nutzen können bzw. müssen, erklärt sich hoffentlich anschaulich die überragende Bedeutung der Indizes, die, wie wir noch sehen werden, nichts anderes als eine Sortierinformation sind, für die Datenbank-Performance.

 

Moral:

 

Performance-Tuning basiert i. d. R. nicht auf „geheimen“ High-Speed-Befehlen, sondern auf Mathematik: Wie viele Bytes werden bewegt, wie viele Schritte sind erforderlich, welche Zusatzkosten entstehen für RAM-Verwaltung, Prozessorbelastung, Plattenzugriffe.
Im Beispiel oben ist der bessere Algorithmus für einen Durchlauf sogar spürbar langsamer als sein Konkurrent, da er mehr Vergleiche durchführt, in der Schleife rechnet und die langsame Do-Loop-Konstruktion statt des schnelleren For-Next benutzt. Der Vorteil beruht allein auf dem effizienteren logischen Prinzip.
Solche und ähnliche Algorithmen werden von Datenbanksystemen intern eingesetzt, um z. B. Anforderungen durch eine WHERE-Klausel o. ä. zu erfüllen.