Warum beschleunigt das Hinzufügen eines Index zu einem Datenbankfeld die Suche über dieses Feld?

Question

Ich bin neu in Datenbanken und habe gelesen, dass das Hinzufügen eines Index zu einem Feld, über das Sie suchen müssen, die Suchzeiten dramatisch beschleunigen kann. Ich verstehe diese Realität, bin aber gespannt, wie es tatsächlich funktioniert. Ich habe ein wenig nach dem Thema gesucht, aber keine gute, prägnante und nicht zu technische Antwort gefunden, wie es funktioniert.

Ich habe die Analogie gelesen, es ist wie ein Index auf der Rückseite eines Buches, aber im Falle eines Datenfeldes von eindeutigen Elementen (wie E-Mail-Adressen in einer Benutzerdatenbank), mit der Rückseite der Buchanalogie würde die gleiche lineare Nachschlagezeit wie eine nicht indizierte Suche bereitstellen.

Was passiert hier, um die Suchzeiten zu beschleunigen? Ich habe ein wenig über die Suche mit B+-Trees gelesen, aber die Beschreibungen waren ein wenig zu tief. Was ich suche, ist ein Überblick über das, was vor sich geht, etwas, das meinem konzeptionellen Verständnis hilft, nicht technische Details.

Answer 1

Okay, nach einem wenig Forschung und Diskussion, hier ist das, was ich gelernt habe:

Konzeptionell ein Index ist eine sortierte Kopie des Datenfeldes es Indizierung ist, wobei jeder Indexwert zeigt auf es original ist (unsortiert) Reihe. Da die Datenbank weiß, wie Werte sortiert werden, kann sie ausgeklügeltere Suchalgorithmen anwenden, als nur nach dem Wert von Anfang bis Ende zu suchen. Die binary search algorithm ist ein einfaches Beispiel eines Suchalgorithmus für sortierte Listen und reduziert die maximale Suchzeit von O (n) zu O (log n). Als Randnotiz: Ein anständiger Sortieralgorithmus wird normalerweise O (n log n) zu vervollständigen, was bedeutet (wie wir alle wahrscheinlich schon einmal gehört haben) sollten Sie nur Indizes auf Felder setzen, die Sie oft suchen , da es etwas teurer ist, den Index (der eine Sortierung enthält) hinzuzufügen, als eine vollständige Suche ein paar Mal durchzuführen. Zum Beispiel ist es in einer großen Datenbank mit> 1.000.000 Einträgen in der Größenordnung von 20x teurer zu sortieren als einmal zu suchen.

Bearbeiten: Siehe @Jarod Elliotts answer für einen eingehenderen Blick auf Sucheffizienzen, insbesondere in Bezug auf das Lesen von Datenträger-Operationen.

Answer 2

Um Ihre Buch-Analogie fortzusetzen, wenn die Seiten in der Reihenfolge von diesem Element wären, wäre es die gleiche Nachschlagezeit wie eine nicht indizierte Suche, ja.

Was wäre jedoch, wenn Ihr Buch eine Liste von Buchrezensionen wäre, die vom Autor bestellt wurden, aber Sie nur die ISBN kannten. Die ISBN ist einzigartig, ja, aber Sie müssten trotzdem jede Rezension einscannen, um die gesuchte zu finden.

Fügen Sie nun einen Index auf der Rückseite des Buchs hinzu, sortiert nach ISBN. Boom, schnelle Suchzeit. Dies entspricht dem Datenbankindex, der vom Indexschlüssel (ISBN) zur eigentlichen Datenzeile (in diesem Fall eine Seitennummer Ihres Buchs) geht.

Answer 3

Die Effizienz des Suchalgorithmus wird erweitert. Ein Schlüsselbereich der Datenbankleistung besteht darin, wie schnell auf die Daten zugegriffen werden kann. Im Allgemeinen ist das Lesen von Daten von einer Festplatte viel langsamer als das Lesen von Daten aus dem Speicher.

Um einen Punkt zu veranschaulichen, nehmen wir an, dass alles auf der Festplatte gespeichert ist. Wenn Sie jede Datenzeile in einer Tabelle durchsuchen müssen, um nach bestimmten Werten in einem Feld zu suchen, müssen Sie immer noch die gesamte Datenzeile von der Festplatte lesen, um festzustellen, ob sie übereinstimmt - dies wird üblicherweise als Tabellensuche bezeichnet ".

Wenn Ihre Tabelle 100 MB ist, müssen Sie 100 MB von der Festplatte lesen.

Wenn Sie jetzt die Spalte indexieren, nach der Sie suchen möchten, speichert der Index in vereinfachter Form jeden eindeutigen Wert der Daten und einen Verweis auf die genaue Position der entsprechenden vollständigen Datenzeile. Dieser Index darf jetzt nur 10 MB im Vergleich zu 100 MB für die gesamte Tabelle betragen.

Das Lesen von 10 MB Daten von der Festplatte (und vielleicht ein bisschen mehr, um die vollständigen Zeilendaten für jede Übereinstimmung zu lesen) ist ungefähr 10 mal schneller als das Lesen der 100 MB.

Verschiedene Datenbanken speichern Indizes oder Daten im Speicher auf verschiedene Arten, um diese Dinge viel schneller zu machen. Wenn Ihr Datensatz jedoch groß ist und nicht in den Speicher passt, kann die Geschwindigkeit der Festplatte einen großen Einfluss haben und die Indexierung kann enorme Vorteile aufweisen. Im Speicher können immer noch große Leistungszuwächse (neben anderen Effizienzen) auftreten.

Im Allgemeinen bemerken Sie deshalb möglicherweise keinen spürbaren Unterschied bei der Indizierung eines kleinen Datensatzes, der leicht in den Speicher passt.

Die zugrunde liegenden Details werden zwischen den Systemen variieren und tatsächlich wird viel komplizierter sein, aber ich habe immer die Disk-Lesevorgänge vs Speicher liest eine leicht verständliche Möglichkeit, dies zu erklären.