Ich bin ziemlich neu in Datenbanken, also vergib mir, wenn das eine dumme Frage ist.Datenbank Abfrage Zeit Komplexität
In modernen Datenbanken, wenn ich einen Index verwenden, um auf eine Zeile zuzugreifen, glaube ich, dass dies O (1) Komplexität sein wird. Aber wenn ich eine Abfrage mache, um eine andere Spalte auszuwählen, wird es O (1) oder O (n) sein? Muss die Datenbank alle Zeilen durchlaufen oder erstellt sie für jede Spalte eine sortierte Liste?
Eigentlich denke ich, Zugriff basierend auf einem Index wird O (log (n)) sein, weil Sie immer noch durch eine B-Tree-esque Organisation suchen, um zu Ihrem Datensatz zu gelangen.
Sie haben Indizes. Clustered-Indizes werden physisch auf dem Datenträger sortiert, Sie können nur einen pro Tabelle haben. Unclustered-Indizes sind logisch sortiert, und Sie können viele davon haben (achten Sie darauf, sie nicht zu missbrauchen, da dies die Schreibaktionen verlangsamen könnte). Wenn es keinen Index für Ihre Spalte gibt, dann glaube ich, dass es die gute alte Zeile für Zeile Methode ist.
Indizes sind pro Spalte. Wenn Sie also eine where-Klausel in einer nicht indizierten Spalte verwenden, wird ein sogenannter tablescan verwendet, der O (n) ist.
Um Ihre literale Frage zu beantworten, ja, wenn es keinen Index für eine Spalte gibt, muss die Datenbank-Engine alle Zeilen betrachten. Im interessanteren Fall der Auswahl durch mehrere Spalten, mit und ohne Index, wird die Situation komplexer: Wenn der Abfrageoptimierer den Index verwendet, wählt er zuerst die Zeilen basierend auf dem Index und dann aus Wenden Sie einen Filter mit den verbleibenden Einschränkungen an. Dadurch wird die zweite Filteroperation von O (Anzahl der Zeilen) auf O (Anzahl der ausgewählten Zeilen nach Index) reduziert. Das Verhältnis zwischen diesen beiden Zahlen heißt Selektivität und eine wichtige Statistik bei der Auswahl des zu verwendenden Index.
Es gibt verschiedene Arten von Indizes, verschiedene Ausführungspläne und verschiedene Implementierungen für verschiedene Datenbanken. Der größte Teil der Code-of-Relation-Datenbank befindet sich in suchoptimierenden Algorithmen. Es gibt keine einzige Antwort auf Ihre Frage. Sie können ein Tool verwenden, um den Ausführungsplan zu visualisieren, wenn Sie wissen möchten, wie eine Abfrage ausgeführt wird.
wahr ist, aber immer noch eine gute Näherung (und was er sucht) ist: O (log (n)), wenn indiziert und O (n) wenn nicht – Javier
Das stimmt, aber Indizes sind nicht immer der limitierende Faktor in Abfragen.In einigen Fällen bemerken Sie möglicherweise nicht den Unterschied zwischen der Verwendung eines Indexes oder nicht. – Paco
@Paco: Welches ist das beste Werkzeug, um den Ausführungsplan zu visualisieren? – Miranda
Ich kenne die Antwort nicht, aber bedenken Sie, dass die Groß-O-Notation nur einen Hinweis auf die Leistung für beliebig große Datensatzgrößen gibt.
Zum Beispiel ist der Flaschenhals für die Datenbankleistung in der Regel Festplatte sucht. Daher wird die Leistung stark erhöht, wenn der Arbeitsdatensatz im Speicher gehalten werden kann. Die Big-O-Notation sagt nichts über solche Optimierungen aus, da sie nur für endliche Datenmengen relevant sind.
B-Bäume ergeben nicht O (logN), das ist die Komplexität eines binären Baumes.
Ein B-Baum ist so organisiert, dass er einen ganzen Block pro Knoten hat. Wenn also ein Knoten gefunden wird, kann eine einzelne E/A-Operation einen ganzen Block lesen.
Mit der Anzahl der Elemente pro Knoten = Blockierungsfaktor (# records/block) {bfr} ergibt eine B-Tree-optimierte Suche O (log bfr ≈ 2 +1 N) E/A-Operationen statt O (N) E/A-Operationen, die eine Aufzeichnung nach Schlüssel suchen.
Entschuldigung, wenn ich dich aus heiterem Himmel frage, aber gibt es ein Buch, dass du mir vorschlagen könntest, wo ich solche Informationen finden könnte? – jackb
Beachten Sie, dass O (log_kn) = O (log n/log k) = O (log n) für jede Konstante k, also technisch, B-Tree-Lookups brauchen O (log n) Zeit. Sie sind jedoch viel schneller als Binärbäume, aber nur um einen konstanten Faktor. – cfstras
Bis auf einen Hash-Index, wo es O (Eimerkettenlänge) –