Betrachten wir einen Datensatz mit N Elementen, von denen P Elemente dem Prädikat entsprechen und von der Abfrage zurückgegeben werden.
1a.Eine lineare Suche, unsortierte Daten. Der Algorithmus kann erst dann erkennen, ob ein Wert mit dem Prädikat übereinstimmt, wenn dieser Wert gelesen wird. Daher besteht die einzige Lösung darin, alle Werte zu lesen und diejenigen zu ignorieren, die nicht mit dem Prädikat übereinstimmen. Der Aufwand wird O (N) sein.
1b.Eine lineare Suche, Daten sortiert nach M. In diesem Fall wird sichergestellt, dass alle Werte, die mit dem Prädikat übereinstimmen, in den Daten zusammenhängend sind. Es gibt jedoch keine Möglichkeit, den Versatz des ersten Werts zu ermitteln. Daher ist das Lesen von Anfang an der einzige Ansatz. Sobald ein Wert gelesen wurde, der größer als die Obergrenze ist, kann der Algorithmus anhalten. Im Allgemeinen ist dieser Ansatz also schneller als der unsortierte Ansatz. Es ist jedoch immer noch O (N).
2. Binäre Suche in M. Für eine binäre Suche müssen die Daten sortiert werden. Das Finden der unteren / oberen Grenze erfordert weniger Operationen - es ist ein O (log N) -Algorithmus. Das Lesen aller Werte zwischen der unteren und oberen Grenze ist jedoch O (P). Insgesamt ist dies also die Komplexität der Abfrage.
3.BTree-Index für M. In diesem Zusammenhang ist ein BTree eine allgemeinere Form der binären Suche. Beide arbeiten, indem ein Bruchteil der möglichen Ergebnisse bei jeder Iteration des Algorithmus eliminiert wird. Diese Fraktion wird als Fan-Out bezeichnet. Bei einer binären Suche beträgt der Fan-Out 2, dh 1/2, die Werte bleiben nach jeder Iteration erhalten. Bei einem BTree wird das Fan-Out durch die Anzahl der Indexzeilen bestimmt, die auf einer Datenseite gespeichert werden können, die normalerweise viel größer als 2 ist. Daher können bestimmte Werte in weniger Iterationen gefunden werden. Die Komplexität ist jedoch bei O (log N) zum Finden der unteren Grenze und bei O (P) zum Lesen der Werte gleich.
- BTree on A. Dies ist nutzlos, da die Abfrage den Wert von A nicht einschränkt.
Wenn ein Abfrageoptimierer Optimierungspläne auswählt, welche der angegebenen Optionen er auswählt
Es wird das billigste auswählen. Es ist die Aufgabe des Optimierers, verschiedene physische Implementierungen der Abfrage zu untersuchen (verwenden und indizieren, alle Zeilen scannen, die Daten sortieren usw.), Heuristiken anzuwenden, um jeder Permutation Kosten zuzuweisen und die billigsten (in Bezug auf die geschätzte verstrichene Zeit) zu liefern die Ausführungs-Engine als Abfrageplan. Beachten Sie, dass das billigste in Big-O-Begriffen nicht das am wenigsten komplexe sein muss. Die Big-O-Notation zeigt, wie sich der erforderliche Aufwand ändert, wenn sich die Anzahl der Elemente einer sehr großen Grenze nähert. Die meisten Datenbanken haben jedoch nicht unendlich viele Zeilen. Der Optimierer verfügt über Informationen zur tatsächlichen Anzahl und Verteilung der Werte innerhalb des Datensatzes. Diese werden in internen Statistikobjekten gespeichert.
Nehmen wir ein Beispiel, in dem wir einen BTree auf M haben, der 3 Ebenen tief ist. Die vollständige Tabelle belegt 1.000 Seiten auf der Festplatte. Denken Sie daran, dass alle Datenbewegungen seitenweise erfolgen. Wenn die angegebene Abfrage wahrscheinlich nur eine einzelne Zeile zurückgeben würde, wäre es effizient, einen Index für M zu verwenden, um insgesamt vier Seiten zu lesen (3 aus dem Index für M und eine aus der Tabelle, um den entsprechenden Wert von A zu erhalten). Wenn die Statistiken jedoch darauf hinweisen, dass die meisten Datenseiten gelesen werden, ist es effizienter, den Index zu speichern und alle Datenseiten zu scannen, wobei diejenigen ignoriert werden, die nicht mit dem Prädikat übereinstimmen.
Ich habe noch nie von einer in einem DBMS implementierten binären Suche gehört. BTrees bieten die gleiche Funktionalität bei höherer Leistung.
Die lineare Suche (auch als Tabellenscan bezeichnet) wird entweder verwendet, wenn kein Index vorhanden ist oder wenn der Aufwand für die Verwendung des Index mehr als der Vorteil der Identifizierung einzelner Zeilen ist.
BTrees sind nicht die einzige Art von Index. Single-Value-Lookup und Table-Scan sind nicht die einzig möglichen Algorithmen.
