Ist ein Index nicht mit einem Wörterbuch vergleichbar? Wenn Sie den Schlüssel haben, können Sie sofort darauf zugreifen?Warum hat die Indexsuche logarithmische Komplexität?
Scheinbar Indizes werden manchmal als B-Trees gespeichert ... warum ist das?
Wörterbücher sind nicht implizit sortiert, B-Tree s sind.
WHERE col1 BETWEEN value1 AND value2
oder Bestellung, wie folgt aus::
ORDER BY col1
Sie können nicht sofort eine Seite in einem B-Tree Zugriff Index:
Ein B-Tree Index kann für Fernzugriff, wie diese verwendet werden, die Sie benötigen um die untergeordneten Seiten zu durchlaufen, deren Anzahl logarithmisch zunimmt.
Einige Datenbanken unterstützen auch Wörterverzeichnis-Indizes, nämlich HASH Indizes, in welchem Fall die Suchzeit konstant ist. Solche Indizes können jedoch nicht für Fernzugriff oder -reihenfolge verwendet werden.
Datenbank Indizes werden normalerweise (fast immer) als B-Bäume gespeichert. Und alle ausgeglichenen Baumstrukturen haben eine O (log n) -Komplexität zum Suchen.
'Dictionary' ist ein 'Abstract Data Type' (ADT), dh es ist eine funktionale Beschreibung, die keine Implementierung bezeichnet. Einige Wörterbücher könnten eine Hashtable für O (1) suchen, andere könnten einen Baum verwenden und O (log n) erreichen.
Der Hauptgrund, ein DB B-trees verwendet (über jede andere Art von Baum) ist, dass B-Bäume Selbstausgleich und sind sehr ‚flach‘ (die wenig Disk-I/O)
Alle ausgewogenen Bäume tun. Ein ausreichend entarteter Baum ist eine verkettete Liste. – Vatine
@Vatine: Du hast Recht, ich werde das bearbeiten. –
Einer der nur sind Datenstrukturen, auf die Sie sofort mit einem Schlüssel zugreifen können, sind Vektoren, die für eine große Datenmenge beim Einfügen und Entfernen von Elementen ineffizient werden. Es benötigt auch eine zusammenhängende Speicherzuweisung.
Ein Hash kann effizient sein, benötigt aber mehr Speicherplatz und führt zu Kollisionen.
Ein B-Baum hat eine gute Balance zwischen Suchleistung und Raum.
hashindex (zB in mysql und postgres) hat konstante Komplexität (O (1)) für die Suche.
CREATE INDEX ... USING HASH
hätte es keine konstante Zeitkomplexität? Linear ist das schlechteste mögliche, d. H. Suchen ohne einen Index. –
@ Il-Bhima, oh .. ja :) das war eine Art von Gedanken-Tippfehler. – osgx
Wenn nur Abfragen Gleichheitstests sind dann, seine wahre, Wörterbücher sind eine gute Wahl, da sie Lookups in den fortgeführten Anschaffungs O tun (1) Zeit. Wenn Sie jedoch Abfragen um Bereichsüberprüfungen erweitern möchten, z. B. (select * from students where age > 10), verlieren Ihre Wörterbücher plötzlich ihren Vorteil vollständig. Hier kommen baumbasierte Indizes ins Spiel. Mit einem baumbasierten Index können Sie Gleichheits- und Bereichsüberprüfungen durchführen in logarithmischer Zeit.
Es gibt ein Problem mit naiven Baumstrukturen. Sie werden unausgewogen, das bedeutet, dass nach dem Hinzufügen bestimmter Werte zum Index die Baumstruktur einseitig (ex wie eine lange Linie) wird und die Suchvorgänge wieder O (N) -Zeit nehmen. Dies kann durch Balancieren Ihres Baumes gelöst werden. Der B-Tree ist ein solcher Ansatz, der auch Systeme ausnutzt, die in der Lage sind, große E/A-Blöcke zu machen, und ist daher am besten für Datenbanken geeignet.
Sie können O(1) erreichen, wenn Sie N Einträge ein Array und Hash der Schlüssel zu diesem N Werte vorbelegt.
Aber wenn Sie mehr als N Einträge gespeichert haben, gibt es eine Kollision. Für jeden Schlüssel im Array haben Sie also eine Werteliste. Also ist es nicht mehr genau O(1). Das Scannen der Liste selbst wird O(m) sein, wobei m die durchschnittliche Anzahl der Kollisionen ist.
Example with hash = n mod 3
0 --> [0,a] [3,b] ...
1 --> [1,a] [4,b] [7,b] ...
2 --> [2,a] [5,b] ...
Zu einem Zeitpunkt, wird es einig schlecht, dass Sie mehr Zeit durchlaufen die Liste des Wertes für einen möglichen Schlüssel als mit einer anderen Struktur mit O(log n) Lookup Zeit damit verbringen, wobei n die Gesamtzahl der Einträge ist.
Sie könnten natürlich N so groß, dass das Array/Hash schneller als der B-Baum wäre. Aber das Array hat eine feste vorbelegte Größe. Wenn also N = 1000 ist und Sie 3 Werte speichern, haben Sie 997 Steckplätze im Array verschwendet.
So ist es im Wesentlichen ein Performance-Raum Kompromiss. Für kleine Werte, array und Hashing ist ausgezeichnet. Für große Werte sind B-Tree am effizientesten.
Hashes sind die schnellsten Datenstrukturen aussehen, aber einige Probleme:
a) b nicht sortiert werden), egal wie gut der Hash ist, wird Kollisionen haben, dass problematisch wird, wenn viele Daten c) Einen Hash-Wert in einer Hash-indizierten Datei zu finden, dauert sehr lange, so dass die meisten Zeit-Hashes nur für In-Memory- (RAM-) Daten sinnvoll sind - was sie für Datenbanken nicht geeignet macht -, die meistens nicht passen Daten im RAM
Sortierte Bäume adressieren diese Probleme, und insbesondere B-Trees-Operationen können effizient mit Dateien implementiert werden. Der einzige Nachteil ist, dass sie langsamere Lookup-Zeiten als Hash-Struktur haben.
Keine Datenstruktur ist in allen Fällen perfekt, abhängig von der geschätzten Größe der Daten und wie Sie sie verwenden, ist eine besser.
Ein Wörterbuch könnte sortiert werden. Es muss einfach nicht sein. –
@Henk: korrigiert, um dies zu verdeutlichen. – Quassnoi
@Henk: Ich denke, Wörterbücher beziehen sich auf Hashtables mit O (1) Zugriff. Ein Dictionary könnte sortiert werden, aber um das zu tun, haben Sie entweder eine lineare Struktur (d. H. O (N) -Abfragen) oder eine Baumstruktur (O (logN)) darunter. –