Hallo, Habr! Ich präsentiere Ihnen eine Übersetzung des Artikels.
"Wie funktioniert eine relationale Datenbank?".

Wenn es um relationale Datenbanken geht, kann ich nicht anders, als zu denken, dass etwas fehlt. Sie werden überall verwendet. Es gibt viele verschiedene Datenbanken: von der kleinen und nützlichen SQLite bis hin zur leistungsstarken Teradata. Aber es gibt nur wenige Artikel, die erklären, wie eine Datenbank funktioniert. Sie können selbst nach "howdoesarelationaldatabasework" suchen, um zu sehen, wie wenig Ergebnisse es gibt. Darüber hinaus sind diese Artikel kurz. Wenn Sie jedoch nach den neuesten Technologien suchen (BigData, NoSQL oder JavaScript), finden Sie mehr tiefgehende Artikel, die erklären, wie sie funktionieren.

Sind relationale Datenbanken zu alt und zu langweilig, um sie außerhalb von Universitätskursen, Forschungsarbeiten und Büchern erklären zu können?

Als Entwickler hasse ich es, etwas zu verwenden, das ich nicht verstehe. Und wenn Datenbanken seit über 40 Jahren verwendet werden, muss es einen Grund dafür geben. Im Laufe der Jahre habe ich Hunderte von Stunden damit verbracht, diese seltsamen schwarzen Kisten, die ich täglich benutze, wirklich zu verstehen. Relationale Datenbanken sehr interessant, weil sie auf nützlichen und wiederverwendbaren Konzepten basieren.Wenn Sie daran interessiert sind, Datenbanken zu verstehen, aber nie die Zeit oder den Wunsch hatten, sich mit diesem weiten Thema zu beschäftigen, wird Ihnen dieser Artikel gefallen.

Obwohl der Titel dieses Artikels offensichtlich ist, besteht das Ziel dieses Artikels nicht darin, zu verstehen, wie man eine Datenbank nutzt.Daher sollten Sie bereits wissen, wie man eine einfache Verbindung und grundlegende Abfragen schreibt, CRUD; andernfalls verstehen Sie möglicherweise diesen Artikel nicht. Das ist alles, was Sie wissen müssen, ich werde alles andere erklären.

Ich werde mit einigen Grundlagen der Informatik beginnen, wie z. B. der zeitlichen Komplexität von Algorithmen (BigO). Ich weiß, dass einige von Ihnen dieses Konzept nicht mögen, aber ohne es werden Sie die Feinheiten innerhalb einer Datenbank nicht verstehen können. Da dies ein riesiges Thema ist, werde ich mich darauf konzentrieren, was ich für wichtig halte,: wie eine Datenbank verarbeitet, SQL Antrag. Ich werde nur die grundlegenden Konzepte von Datenbanken vorstellen,damit Sie am Ende des Artikels eine Vorstellung davon haben, was im Hintergrund passiert.

Da dies ein langer und technischer Artikel ist, der viele Algorithmen und Datenstrukturen umfasst, nehmen Sie sich Zeit, um ihn zu lesen. Einige Konzepte können schwierig zu verstehen sein; Sie können sie überspringen und dennoch ein allgemeines Verständnis gewinnen.

Für die besser informierten unter Ihnen ist dieser Artikel in 3 Teile gegliedert:

Überblick über Low-Level- und High-Level-Datenbankkomponenten
Überblick über den Prozess der Abfrageoptimierung
Überblick über Transaktionsmanagement und Buffer-Pool

Zurück zu den Grundlagen

Vor vielen Jahren (in einer weit, weit entfernten Galaxie…) mussten Entwickler genau wissen, wie viele Operationen sie codierten. Sie kannten ihre Algorithmen und Datenstrukturen auswendig, weil sie es sich nicht leisten konnten, CPU und Speicher ihrer langsamen Computer zu verschwenden.

In diesem Abschnitt werde ich Sie an einige dieser Konzepte erinnern, da sie für das Verständnis von Datenbanken notwendig sind. Ich werde auch das Konzept der Datenbankindizes.

O(1) vs O(n2)

Heutzutage kümmern sich viele Entwickler nicht um die zeitliche Komplexität von Algorithmen ... und sie haben Recht!

Aber wenn Sie es mit großen Datenmengen zu tun haben (ich spreche nicht von Tausenden) oder wenn Sie um Millisekunden kämpfen, wird es kritisch wichtig, dieses Konzept zu verstehen. Und wie Sie verstehen, müssen Datenbanken mit beiden Situationen umgehen! Ich werde Sie nicht dazu bringen, mehr Zeit als nötig aufzuwenden, um das Wesentliche zu erfassen. Dies wird uns später helfen, das Konzept der kostenbasierten Optimierung zu verstehen (Kosten basiert Optimierung).

Konzept

Die zeitliche Komplexität eines Algorithmus wird verwendet, um zu sehen, wie viel Zeit die Ausführung eines Algorithmus für eine bestimmte Datenmenge in Anspruch nimmt. Um diese Komplexität zu beschreiben, werden mathematische Notationen des großen O verwendet. Diese Notation wird mit einer Funktion verwendet, die beschreibt, wie viele Operationen der Algorithmus für eine bestimmte Menge an Eingabedaten benötigt.

Wenn ich also sage: "Dieser Algorithmus hat eine Komplexität von O (some_function() )", bedeutet dies, dass der Algorithmus zur Verarbeitung einer bestimmten Datenmenge some_function(a_certain_amount_of_data) Operationen benötigt.

Dabei Es geht nicht um die Anzahl der Daten**, sondern darum, ** wie die Anzahl der Operationen bei zunehmender Datenmenge ansteigt. Die zeitliche Komplexität gibt keine genaue Anzahl von Operationen an, ist jedoch eine gute Möglichkeit, die Ausführungszeit abzuschätzen.

In diesem Diagramm können Sie die Abhängigkeit der Anzahl der Operationen vom Volumen der Eingangsdaten für verschiedene Typen von zeitlichen Komplexitäten der Algorithmen sehen. Ich habe eine logarithmische Skala verwendet, um sie darzustellen. Mit anderen Worten, die Menge der Daten wächst schnell von 1 auf 1 Milliarde. Wir können sehen, dass:

O(1) oder konstante Komplexität bleibt konstant (ansonsten würde es nicht als konstante Komplexität bezeichnet werden).
O(log(n)) bleibt auch bei Milliarden von Daten niedrig.
Die schlimmste Komplexität ist O(n2), wobei die Anzahl der Operationen schnell wächst.
Die beiden anderen Komplexitäten steigen ebenfalls schnell an.

Beispiele

Bei einer geringen Datenmenge ist der Unterschied zwischen O(1) und O(n2) gering. Nehmen wir an, Sie haben einen Algorithmus, der 2000 Elemente verarbeiten muss.

Der O(1) Algorithmus kostet Sie 1 Operation
Der O(log (n)) Algorithmus kostet Sie 7 Operationen
Der O(n) Algorithmus kostet Sie 2000 Operationen
Der O(n * log (n)) Algorithmus kostet Sie 14.000 Operationen
Der O(n2) Algorithmus kostet Sie 4.000.000 Operationen

Der Unterschied zwischen O(1) und O(n2) scheint groß zu sein (4 Millionen Operationen), aber Sie verlieren höchstens 2 ms, einfach die Zeit, um die Augen zu blinzeln. Tatsächlich können moderne Prozessoren Hunderte Millionen Operationen pro Sekunde verarbeiten. Deshalb ist Performance und Optimierung in vielen IT-Projekten kein Problem.

Wie ich bereits sagte, ist es dennoch wichtig, dieses Konzept zu kennen, wenn man mit großen Datenmengen arbeitet. Angenommen, der Algorithmus muss diesmal 1.000.000 Elemente verarbeiten (was für eine Datenbank nicht so viel ist):

Der O(1) Algorithmus kostet Sie 1 Operation
Der O(log (n)) Algorithmus kostet Sie 14 Operationen
Der O(n) Algorithmus kostet Sie 1.000.000 Operationen
Der O(n * log (n)) Algorithmus kostet Sie 14.000.000 Operationen
Der O(n2) Algorithmus kostet Sie 1.000.000.000.000 Operationen

Ich habe keine Berechnungen angestellt, aber ich würde sagen, dass Sie mit dem O(n2) Algorithmus Zeit haben, um einen Kaffee zu trinken (sogar zwei!). Wenn Sie eine 0 an das Datenvolumen anhängen, haben Sie Zeit, ein Nickerchen zu machen.

Lasst uns tiefer eintauchen

Zur Info:

Die Suche in einer guten Hash-Tabelle findet ein Element in O(1).
Die Suche in einem gut balancierten Baum liefert das Ergebnis in O(log(n)).
Die Suche in einem Array liefert das Ergebnis in O(n).
Die besten Sortieralgorithmen haben eine Komplexität von O(n * log(n)).
Ein schlechter Sortieralgorithmus hat eine Komplexität von O(n2).

Hinweis: In den folgenden Teilen werden wir diese Algorithmen und Datenstrukturen sehen.

Es gibt mehrere Arten der zeitlichen Komplexität eines Algorithmus:

Szenario des durchschnittlichen Falls
besten Fall
und schlimmsten Fall

Die zeitliche Komplexität ist oft das schlechteste Szenario.

Ich habe nur über die zeitliche Komplexität des Algorithmus gesprochen, aber die Komplexität ist auch anwendbar für:

Speicherverbrauch des Algorithmus
Festplatten-Eingabe/Ausgabe des Algorithmus

Natürlich gibt es Komplexitäten, die schlechter sind als n2, zum Beispiel:

n4: das ist schrecklich! Einige der erwähnten Algorithmen haben eine solche Komplexität.
3n: das ist noch schlimmer! Einer der Algorithmen, die wir in der Mitte dieses Artikels sehen werden, hat diese Komplexität (und er wird tatsächlich in vielen Datenbanken verwendet).
Fakultät n: Sie werden Ihre Ergebnisse nie erhalten, selbst mit einer geringen Datenmenge.
nn: wenn Sie mit dieser Komplexität konfrontiert werden, sollten Sie sich fragen, ob dies wirklich Ihr Tätigkeitsbereich ist …

Hinweis: Ich habe Ihnen keine reale Definition der Bezeichnung „großes O“ gegeben, sondern nur eine Idee. Sie können diesen Artikel lesen in Wikis für die reale (asymptotische) Definition.

MergeSort (Mergesort)

Was tun Sie, wenn Sie eine Sammlung sortieren müssen? Was? Sie rufen die Funktion sort() auf… Okay, gute Antwort… Aber für Datenbanken müssen Sie verstehen, wie diese Funktion sort() funktioniert.

Es gibt mehrere gute Sortieralgorithmen, daher konzentriere ich mich auf das Wichtigste: Mergesort. Vielleicht verstehen Sie jetzt noch nicht, warum das Sortieren von Daten nützlich ist, aber Sie werden es nach dem Abschnitt zur Optimierung von Abfragen verstehen müssen. Darüber hinaus wird das Verständnis von Mergesort uns später helfen, die allgemeine Datenbankoperation join zu verstehen, die genannt wird , also Merge-Vorgänge. join (Merging Join).

Merge (Vereinigung)

Wie viele nützliche Algorithmen basiert Mergesort auf einer Cleverness: Das Zusammenführen von 2 sortierten Arrays der Größe N/2 in ein N-Element sortiertes Array kostet nur N Operationen. Dieser Vorgang wird Merging genannt.

Lassen Sie uns sehen, was das in einem einfachen Beispiel bedeutet:

Auf diesem Bild sehen Sie, dass Sie, um ein endgültiges sortiertes Array von 8 Elementen zu erstellen, nur einmal in 2 jeweils 4-elementige Arrays iterieren müssen. Da beide 4-elementigen Arrays bereits sortiert sind:

1) Vergleichen Sie die aktuellen Elemente in den beiden Arrays (zu Beginn ist das aktuelle = dem ersten)
2) dann nehmen Sie das kleinste, um es in ein Array mit 8 Elementen zu platzieren
3) und gehen Sie zum nächsten Element im Array über, wo Sie das kleinste Element genommen haben
und wiederholen Sie 1, 2, 3, bis Sie das letzte Element eines der Arrays erreichen.
Dann nehmen Sie die restlichen Elemente des anderen Arrays, um sie in ein Array mit 8 Elementen zu platzieren.

Das funktioniert, weil beide 4-elementigen Arrays sortiert sind, und daher müssen Sie in diesen Arrays nicht "zurückgehen".

Jetzt, wo wir diesen Trick verstanden haben, hier ist mein Pseudocode für Merge:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //rekursive Aufrufe
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //Zusammenführen der 2 kleinen sortierten Arrays in ein großes
   array result := merge(new_left_array,new_right_array);
   return result;

Das Merging-Sort zerlegt das Problem in kleinere Aufgaben und findet dann die Ergebnisse der kleineren Aufgaben, um das Ergebnis der ursprünglichen Aufgabe zu erhalten (Hinweis: Diese Art von Algorithmus wird als Teile und herrsche bezeichnet). Wenn Sie diesen Algorithmus nicht verstehen, keine Sorge; ich habe ihn beim ersten Mal, als ich ihn gesehen habe, auch nicht verstanden. Wenn es Ihnen hilft, betrachte ich diesen Algorithmus als einen zweiphasigen Algorithmus:

Teilen-Phase, in der das Array in kleinere Arrays unterteilt wird
Sortieren-Phase, in der kleine Arrays kombiniert werden (unter Verwendung von Merge), um ein größeres Array zu bilden.

Teilen-Phase (Division phase)

In der Teilen-Phase wird das Array in unitäre Arrays in 3 Schritten unterteilt. Die formale Anzahl der Schritte ist log(N) (da N=8, log(N) = 3).

Woher weiß ich das?

Ich bin ein Genie! Kurz gesagt – Mathematik. Die Idee ist, dass jeder Schritt die Größe des ursprünglichen Arrays halbiert. Die Anzahl der Schritte ist die Anzahl der Male, die Sie das ursprüngliche Array in zwei Teile teilen können. Das ist die genaue Definition des Logarithmus (Basis 2).

Sortieren-Phase (Sorting phase)

In der Sortieren-Phase beginnen Sie mit unitären (einzel-elementigen) Arrays. In jeder Phase wenden Sie mehrere Merge-Operationen an, und die Gesamtkosten betragen N = 8 Operationen:

In der ersten Phase haben Sie 4 Merges, die jeweils 2 Operationen kosten
In der zweiten Phase haben Sie 2 Merges, die jeweils 4 Operationen kosten
In der dritten Phase haben Sie 1 Merge, das 8 Operationen kostet

Da es log(N) Schritte gibt, beträgt die Gesamtkosten N * log(N) Operationen.

Vorteile des Merging-Sorts

Warum ist dieser Algorithmus so mächtig?

Denn:

Sie können ihn ändern, um den Speicherverbrauch zu verringern, sodass Sie keine neuen Arrays erstellen, sondern das Eingangsarray direkt ändern.

Hinweis: Diese Art von Algorithmen wird genannt in—place (Sortieren ohne zusätzlichen Speicher).

Sie können ihn so anpassen, dass er gleichzeitig den Speicherplatz auf der Festplatte und einen kleinen Speicherverbrauch nutzt, ohne erhebliche Kosten für Ein- und Ausgabe auf der Festplatte. Die Idee besteht darin, nur die Teile in den Speicher zu laden, die gerade verarbeitet werden. Dies ist wichtig, wenn Sie eine Tabelle mit mehreren Gigabyte nur mit einem 100 Megabyte großen Speicherpuffer sortieren müssen.

Hinweis: Diese Art von Algorithmen wird genannt externe Sortierung.

Sie können ihn so anpassen, dass er auf mehreren Prozessen / Threads / Servern läuft.

Zum Beispiel ist die verteilte Merge-Sortierung eines der Schlüsselelemente Hadoop (das eine Struktur in Big Data darstellt).

Dieser Algorithmus kann Blei in Gold verwandeln (ja, wirklich!).

Dieser Sortieralgorithmus wird in den meisten (wenn nicht allen) Datenbanken verwendet, aber er ist nicht der einzige. Wenn Sie mehr erfahren möchten, können Sie diese Forschungsarbeit, die die Vor- und Nachteile gängiger Sortieralgorithmen in Datenbanken diskutiert.

Array, Baum und Hash-Tabelle

Jetzt, wo wir die Idee der zeitlichen Komplexität und des Sortierens verstehen, muss ich Ihnen von 3 Datenstrukturen erzählen. Dies ist wichtig, da sie die Grundlage moderner Datenbanken sind. Ich werde auch das Konzept einführen Datenbankindizes.

Array

Ein zweidimensionales Array ist die einfachste Datenstruktur. Eine Tabelle kann als Array betrachtet werden. Zum Beispiel:

Dieses 2D-Array stellt eine Tabelle mit Zeilen und Spalten dar:

Jede Zeile repräsentiert eine Entität
Spalten speichern Eigenschaften, die die Entität beschreiben.
Jede Spalte speichert Daten eines bestimmten Typs (Integer, String, Datum …).

Es ist zwar praktisch, Daten zu speichern und zu visualisieren, jedoch, wenn Sie einen bestimmten Wert finden müssen, ist es nicht geeignet.

Wenn Sie beispielsweise alle Personen finden möchten, die im Vereinigten Königreich arbeiten, müssen Sie jede Zeile durchsehen, um festzustellen, ob diese Zeile zum Vereinigten Königreich gehört. Das wird Ihnen N Operationen kosten.

N — die Anzahl der Zeilen ist nicht schlecht, aber könnte es einen schnelleren Weg geben? Jetzt ist es Zeit, uns mit Bäumen vertraut zu machen.

Hinweis: Die meisten modernen Datenbanken bieten erweiterte Arrays für eine effiziente Speicherung von Tabellen: heap-organisierte Tabellen und index-organisierte Tabellen. Aber das ändert nichts an dem Problem der schnellen Suche nach einem bestimmten Kriterium in einer Gruppe von Spalten.

Datenbankbaum und Index

Ein binärer Suchbaum ist ein binärer Baum mit einer speziellen Eigenschaft, der Schlüssel in jedem Knoten muss sein:

größer als alle Schlüssel, die im linken Teilbaum gespeichert sind
kleiner als alle Schlüssel, die im rechten Teilbaum gespeichert sind

Lassen Sie uns sehen, was das visuell bedeutet

Idee

Dieser Baum hat N = 15 Elemente. Angenommen, ich suche 208:

Ich beginne mit der Wurzel, deren Schlüssel 136 ist. Da 136 < 208, schaue ich mir den rechten Teilbaum von Knoten 136 an.
398 > 208, daher schaue ich mir den linken Teilbaum von Knoten 398 an.
250 > 208, daher schaue ich mir den linken Teilbaum von Knoten 250 an.
200 < 208, daher schaue ich mir den rechten Teilbaum von Knoten 200 an. Aber 200 hat keinen rechten Teilbaum, das Wert nicht existiert (weil, wenn es existieren würde, es im rechten Teilbaum von 200 wäre).

Nun, sagen wir, ich suche 40

Ich beginne mit der Wurzel, deren Schlüssel 136 ist. Da 136 > 40, schaue ich mir den linken Teilbaum von Knoten 136 an.
80 > 40, daher schaue ich mir den linken Teilbaum von Knoten 80 an.
40= 40, der Knoten existiert. Ich extrahiere die Zeilen-ID innerhalb des Knotens (das ist im Bild nicht zu sehen) und schaue in der Tabelle für die gegebene Zeilen-ID nach.
Das Wissen um die Zeilen-ID ermöglicht es mir zu wissen, wo genau die Daten in der Tabelle liegen, und deshalb kann ich sie sofort abrufen.

Insgesamt werden beide Suchen für mich in der Anzahl der Ebenen innerhalb des Baumes anfallen. Wenn Sie den Teil über das Merging-Sort genau gelesen haben, sollten Sie sehen, dass es hier log (N) Ebenen gibt. Es ergibt sich, die Kosten der Suche betragen log(N), nicht schlecht!

Kehren wir zu unserem Problem zurück

Aber das ist sehr abstrakt, also lassen Sie uns zu unserem Problem zurückkehren. Anstatt eines einfachen Integers, stellen Sie sich einen String vor, der das Land einer Person in der vorherigen Tabelle darstellt. Angenommen, Sie haben einen Baum, der das Feld "country" (Spalte 3) der Tabelle enthält:

Wenn Sie wissen möchten, wer im Vereinigten Königreich arbeitet
sehen Sie sich den Baum an, um den Knoten zu erhalten, der das Vereinigte Königreich darstellt.
Innerhalb des "UKnode" finden Sie die Position der Mitarbeiteraufzeichnungen im Vereinigten Königreich.

Diese Suche wird log(N) Operationen kosten, anstatt N Operationen, wenn Sie das Array direkt verwenden. Das, was Sie gerade dargestellt haben, war Datenbankindex.

Sie können einen Indexbaum für jede Gruppe von Feldern (Text, Zahl, 2 Texte, Zahl und Text, Datum …) erstellen, solange Sie eine Funktion zum Vergleichen der Schlüssel (d.h. Gruppen von Feldern) haben, damit Sie die Reihenfolge der Schlüssel festlegen können (was für alle grundlegenden Typen in der Datenbank gilt).

B+TreeIndex

Obwohl dieser Baum gut funktioniert, um einen bestimmten Wert zu erhalten, gibt es ein GROSSES Problem, wenn Sie mehrere Elemente zwischen zwei Werten erhalten müssen. Das wird O(N) kosten, da Sie jeden Knoten im Baum betrachten und prüfen müssen, ob er zwischen diesen beiden Werten liegt (zum Beispiel durch eine geordnete Baumdurchquerung). Darüber hinaus ist diese Operation für den Datentransfer von der Festplatte nicht geeignet, da Sie den gesamten Baum lesen müssen. Wir müssen einen Weg finden, um Bereichsanfragen effizient durchzuführen. Zur Lösung dieses Problems verwenden moderne Datenbanken eine modifizierte Version des vorherigen Baumes, die B+Tree genannt wird. Im B+Tree-Baum:

nur die untersten Knoten (Blätter) speichern Informationen (Positionen von Zeilen in der verknüpften Tabelle)
die anderen Knoten sind hier um weiterzuleiten zum richtigen Knoten während der Suche.

Wie Sie sehen können, gibt es hier mehr Knoten (doppelt so viele). In der Tat haben Sie zusätzliche Knoten, die "Entscheidungsknoten" sind, die Ihnen helfen, den richtigen Knoten zu finden (der die Positionen der Zeilen in der verknüpften Tabelle speichert). Aber die Komplexität der Suche bleibt weiterhin O(log(N)) (es gibt nur eine zusätzliche Ebene). Der große Unterschied ist, dass die Knoten auf der unteren Ebene mit ihren Nachfolgern verbunden sind..

Mit diesem B+Tree, wenn Sie nach Werten von 40 bis 100 suchen:

Sie müssen nur 40 suchen (oder den nächstgrößeren Wert nach 40, wenn 40 nicht existiert), wie Sie es mit dem vorherigen Baum gemacht haben.
Dann sammeln Sie die Nachfolger von 40 über direkte Links zu den Nachfolgern, bis Sie 100 erreicht haben.

Angenommen, Sie haben M Nachfolger gefunden, und der Baum hat N Knoten. Die Suche nach einem bestimmten Knoten kostet log(N) ähnlich wie beim vorherigen Baum. Aber nachdem Sie diesen Knoten gefunden haben, erhalten Sie M Nachfolger in M Operationen mit Verweisen auf ihre Nachfolger. Diese Suche kostet nur M+log(N) Operationen im Vergleich zu N Operationen mit dem vorherigen Baum. Darüber hinaus müssen Sie den vollständigen Baum nicht lesen (nur M + log (N) Knoten), was zu einem geringeren Speicherverbrauch führt. Wenn M klein ist (z.B. 200 Zeilen) und N groß (1.000.000 Zeilen), wird dies einen GROSSEN Unterschied machen.

Doch hier gibt es neue Probleme (schon wieder!). Wenn Sie eine Zeile in der Datenbank hinzufügen oder löschen (und somit im zugehörigen Index B+Tree):

müssen Sie die Reihenfolge zwischen den Knoten im B+Tree beibehalten, sonst können Sie Knoten im unsortierten Baum nicht finden.
Sie müssen die minimal mögliche Anzahl an Ebenen im B+Tree erhalten, sonst wird die zeitliche Komplexität von O(log(N)) zu O(N).

Mit anderen Worten, B+Tree muss selbstordnend und ausgewogen sein. Glücklicherweise ist dies mit intelligenten Lösch- und Einfügeoperationen möglich. Aber das ist teuer: Einfügen und Löschen im B+-Baum kosten O(log(N)). Deshalb haben einige von Ihnen gehört, dass die Verwendung von zu vielen Indizes keine sehr gute Idee ist. Tatsächlich verlangsamen Sie das schnelle Einfügen / Aktualisieren / Löschen einer Zeile in der Tabelle, da die Datenbank die Indizes der Tabelle mit einer teuren Operation O(log(N)) für jeden Index aktualisieren muss. Darüber hinaus bedeutet das Hinzufügen von Indizes eine größere Belastung für den Transaktionsmanager (der am Ende des Artikels beschrieben wird).

Für weitere Informationen können Sie den Wikipedia-Artikel über B+Tree. Wenn Sie ein Beispiel für die Implementierung eines B+Trees in einer Datenbank sehen möchten, schauen Sie sich diesen Artikel und diesen Artikel die von einem führenden MySQL-Entwickler an. Beide konzentrieren sich darauf, wie InnoDB (MySQL-Engine) Indizes behandelt.

Hinweis: Ein Leser hat mir gesagt, dass aufgrund von Low-Level-Optimierungen der B+Tree vollständig ausgewogen sein sollte.

Hashtable (Hash-Tabelle)

Unsere letzte wichtige Datenstruktur ist die Hash-Tabelle. Sie ist sehr nützlich, wenn Sie schnell Werte suchen möchten. Darüber hinaus wird das Verständnis der Hash-Tabelle uns später helfen, die allgemeine Joins-Operation mit Datenbanken, die als Hash-Join bekannt ist, zu verstehen ( hash join). Diese Datenstruktur wird auch von der Datenbank verwendet, um einige interne Dinge zu speichern (zum Beispiel, Sperrtabelle oder Pufferpool, wir werden beide Konzepte später sehen).

Eine Hashtabelle ist eine Datenstruktur, die ein Element schnell anhand seines Schlüssels findet. Um eine Hashtabelle zu erstellen, müssen Sie Folgendes bestimmen:

Schlüssel für Ihre Elemente
eine Hash-Funktion für die Schlüssel. Die berechneten Hashes der Schlüssel geben die Position der Elemente an (die als Segmente ).
eine Funktion zum Vergleich der Schlüsseldienen. Sobald Sie das richtige Segment gefunden haben, müssen Sie das Element, das Sie suchen, innerhalb des Segments finden, indem Sie diesen Vergleich verwenden.

Ein einfaches Beispiel

Lassen Sie uns ein anschauliches Beispiel betrachten:

Diese Hashtabelle hat 10 Segmente. Da ich faul bin, habe ich nur 5 Segmente dargestellt, aber ich weiß, dass Sie schlau sind, also lasse ich Sie die anderen 5 selbst vorstellen. Ich habe die Hash-Funktion modulo 10 des Schlüssels verwendet. Mit anderen Worten, ich behalte nur die letzte Ziffer des Schlüssels des Elements, um sein Segment zu finden:

Wenn die letzte Ziffer 0 ist, fällt das Element in Segment 0,
wenn die letzte Ziffer 1 ist, fällt das Element in Segment 1,
wenn die letzte Ziffer 2 ist, fällt das Element in Segment 2,
…

Die Vergleichsfunktion, die ich verwendet habe, ist einfach die Gleichheit zwischen zwei Ganzzahlen.

Angenommen, Sie möchten das Element 78 erhalten:

Die Hashtabelle berechnet den Hash-Code für 78, der 8 entspricht.
Die Hashtabelle schaut in Segment 8, und das erste Element, das sie findet, ist 78.
Sie gibt Ihnen das Element 78 zurück.
Die Suche kostete nur 2 Operationen, (eine zur Berechnung des Wertes der Hash-Funktion und eine andere zur Suche des Elements im Segment).

Nun, nehmen wir an, Sie möchten das Element 59 erhalten:

Die Hashtabelle berechnet den Hash-Code für 59, der 9 entspricht.
Die Hashtabelle sucht im Segment 9, das erste gefundene Element ist 99. Da 99!=59, ist das Element 99 nicht das richtige Element.
Mit derselben Logik wird das zweite Element (9), das dritte (79), …, das letzte (29) genommen.
Das Element wurde nicht gefunden.
Die Suche kostete 7 Operationen..

Eine gute Hash-Funktion

Wie Sie sehen, ist der Preis je nach dem gesuchten Wert nicht konstant!

Wenn ich jetzt die Hash-Funktion modulo 1.000.000 des Schlüssels ändere (das heißt, die letzten 6 Ziffern nehme), würde die zweite Suche nur 1 Operation kosten, da im Segment 000059 keine Elemente vorhanden sind. Die echte Herausforderung besteht darin, eine gute Hash-Funktion zu finden, die Segmente erstellt, die sehr wenige Elemente enthalten..

In meinem Beispiel ist es einfach, eine gute Hash-Funktion zu finden. Aber das ist ein einfaches Beispiel; es ist schwieriger, eine gute Hash-Funktion zu finden, wenn der Schlüssel:

eine Zeichenfolge (zum Beispiel – Nachname)
2 Zeichenfolgen (zum Beispiel – Nachname und Vorname)
2 Zeichenfolgen und ein Datum (zum Beispiel – Nachname, Vorname und Geburtsdatum)
…

Mit einer guten Hash-Funktion beträgt die Suche in der Hashtabelle O(1).

Array vs. Hashtabelle

Warum nicht ein Array verwenden?

Hmm, gute Frage.

Eine Hashtabelle kann teilweise im Speicher geladen sein, während die anderen Segmente auf der Festplatte bleiben können.
Bei einem Array müssen Sie kontinuierlichen Speicherplatz verwenden. Wenn Sie eine große Tabelle laden, ist es sehr schwierig, genügend kontinuierlichen Speicherplatz zu finden..
Bei einer Hashtabelle können Sie den gewünschten Schlüssel wählen (zum Beispiel das Land und den Nachnamen einer Person).

Für zusätzliche Informationen können Sie den Artikel über JavaHashMaplesen, die eine effiziente Implementierung einer Hashtabelle ist; Sie müssen Java nicht verstehen, um die in diesem Artikel dargestellten Konzepte zu erfassen.

Quelle: habr.com