Hey Habr! Ich präsentiere Ihnen die Übersetzung des Artikels
„Wie funktioniert eine relationale Datenbank?“.

Wenn es um relationale Datenbanken geht, denke ich, dass etwas fehlt. Sie werden überall verwendet. Es stehen viele verschiedene Datenbanken zur Verfügung, von der kleinen und nützlichen SQLite bis hin zur leistungsstarken Teradata. Es gibt jedoch nur wenige Artikel, die die Funktionsweise der Datenbank erklären. Sie können mithilfe von „howdoesarelationaldatabasework“ selbst suchen, um zu sehen, wie wenige Ergebnisse es gibt. Darüber hinaus sind diese Artikel kurz. Wenn Sie auf der Suche nach den neuesten, angesagten Technologien (BigData, NoSQL oder JavaScript) sind, finden Sie ausführlichere Artikel, in denen deren Funktionsweise erläutert wird.

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

Als Entwickler hasse ich es, etwas zu verwenden, das ich nicht verstehe. Und wenn Datenbanken schon länger als 40 Jahre genutzt werden, muss das einen Grund haben. Im Laufe der Jahre habe ich Hunderte von Stunden damit verbracht, diese seltsamen Black Boxes, die ich jeden Tag benutze, wirklich zu verstehen. Relationale Datenbanken sehr interessant, weil sie basierend auf nützlichen und wiederverwendbaren Konzepten. Wenn Sie daran interessiert sind, eine Datenbank zu verstehen, aber nie die Zeit oder Lust hatten, sich mit diesem breiten Thema zu befassen, sollte Ihnen dieser Artikel gefallen.

Obwohl der Titel dieses Artikels explizit ist, Der Zweck dieses Artikels besteht nicht darin, zu verstehen, wie die Datenbank verwendet wird. daher Sie sollten bereits wissen, wie man eine einfache Verbindungsanfrage und grundlegende Abfragen schreibt GRAUSAM; Andernfalls verstehen Sie diesen Artikel möglicherweise nicht. Das ist das Einzige, was Sie wissen müssen, den Rest erkläre ich Ihnen.

Ich beginne mit einigen Grundlagen der Informatik, wie zum Beispiel der Zeitkomplexität von Algorithmen (BigO). Ich weiß, dass einige von Ihnen dieses Konzept hassen, aber ohne es werden Sie die Feinheiten innerhalb der Datenbank nicht verstehen können. Da dies ein großes Thema ist, Ich werde mich darauf konzentrieren was ich für wichtig halte: wie die Datenbank verarbeitet SQL Anfrage. Ich werde es nur vorstellen Grundlegende Datenbankkonzeptedamit Sie am Ende des Artikels eine Vorstellung davon haben, was unter der Haube vor sich geht.

Da dies ein langer und technischer Artikel ist, der viele Algorithmen und Datenstrukturen beinhaltet, nehmen Sie sich die Zeit, ihn durchzulesen. Einige Konzepte sind möglicherweise schwer zu verstehen; Sie können sie überspringen und sich trotzdem einen Überblick verschaffen.

Für die Erfahreneren unter Ihnen: Dieser Artikel ist in drei Teile unterteilt:

Übersicht über Low-Level- und High-Level-Datenbankkomponenten
Überblick über den Abfrageoptimierungsprozess
Überblick über die Transaktions- und Pufferpoolverwaltung

Zurück zum Wesentlichen

Vor 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, die CPU und den Speicher ihrer langsamen Computer zu verschwenden.

In diesem Teil werde ich Sie an einige dieser Konzepte erinnern, da sie für das Verständnis der Datenbank von wesentlicher Bedeutung sind. Ich werde auch das Konzept vorstellen Datenbankindex.

O(1) vs. O(n2)

Heutzutage ist vielen Entwicklern die zeitliche Komplexität von Algorithmen egal ... und sie haben Recht!

Aber wenn Sie mit vielen Daten zu tun haben (ich spreche nicht von Tausenden) oder wenn Sie mit Millisekunden zu kämpfen haben, ist es wichtig, dieses Konzept zu verstehen. Und wie Sie sich vorstellen können, müssen Datenbanken beide Situationen bewältigen! Ich werde nicht verlangen, dass Sie mehr Zeit als nötig aufwenden, um das Wesentliche rüberzubringen. Dies wird uns später helfen, das Konzept der kostenbasierten Optimierung zu verstehen (kosten basierend Optimierung).

Konzept

Zeitliche Komplexität des Algorithmus Wird verwendet, um zu sehen, wie lange ein Algorithmus für die Fertigstellung einer bestimmten Datenmenge benötigt. Um diese Komplexität zu beschreiben, verwenden wir die mathematische Notation Big O. Diese Notation wird mit einer Funktion verwendet, die beschreibt, wie viele Operationen ein Algorithmus für eine bestimmte Anzahl von Eingaben benötigt.

Wenn ich zum Beispiel sage: „Dieser Algorithmus hat die Komplexität O(some_function())“, bedeutet das, dass der Algorithmus some_function(a_certain_amount_of_data)-Operationen benötigt, um eine bestimmte Datenmenge zu verarbeiten.

In diesem Fall Es kommt nicht auf die Datenmenge an**, ansonsten ** wie die Anzahl der Operationen mit steigendem Datenvolumen zunimmt. Die Zeitkomplexität liefert keine genaue Anzahl von Operationen, ist aber eine gute Möglichkeit, die Ausführungszeit abzuschätzen.

In diesem Diagramm sehen Sie die Anzahl der Operationen im Vergleich zur Menge der Eingabedaten für verschiedene Arten von Algorithmus-Zeitkomplexitäten. Zur Darstellung habe ich eine logarithmische Skala verwendet. Mit anderen Worten, die Datenmenge steigt schnell von 1 auf 1 Milliarde. Wir können Folgendes sehen:

O(1) oder konstante Komplexität bleibt konstant (andernfalls würde man es nicht als konstante Komplexität bezeichnen).
O(Log(n)) bleibt selbst bei Milliarden von Daten gering.
Schlimmste Schwierigkeit - O(n2), wobei die Anzahl der Operationen schnell wächst.
Die anderen beiden Komplikationen nehmen ebenso schnell zu.

Примеры

Bei einer kleinen Datenmenge ist der Unterschied zwischen O(1) und O(n2) vernachlässigbar. Nehmen wir zum Beispiel 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 2 Operationen
Der O(n*log(n))-Algorithmus kostet Sie 14 Operationen
Der O(n2)-Algorithmus kostet Sie 4 Operationen

Der Unterschied zwischen O(1) und O(n2) scheint groß zu sein (4 Millionen Operationen), aber Sie verlieren maximal 2 ms, gerade Zeit, mit den Augen zu blinzeln. Tatsächlich können moderne Prozessoren verarbeiten Hunderte Millionen Operationen pro Sekunde. Deshalb sind Performance und Optimierung in vielen IT-Projekten kein Thema.

Wie gesagt, es ist immer noch wichtig, dieses Konzept zu kennen, wenn man mit großen Datenmengen arbeitet. Wenn der Algorithmus dieses Mal 1 Elemente verarbeiten muss (was für eine Datenbank nicht 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 Operationen
Der O(n*log(n))-Algorithmus kostet Sie 14 Operationen
Der O(n2)-Algorithmus kostet Sie 1 Operationen

Ich habe nicht nachgerechnet, aber ich würde sagen, dass man mit dem O(n2)-Algorithmus Zeit hat, einen Kaffee zu trinken (sogar zwei!). Wenn Sie das Datenvolumen um weitere 0 erhöhen, haben Sie Zeit für ein Nickerchen.

Gehen wir tiefer

Zu Ihrer Information:

Eine gute Hash-Tabellensuche findet ein Element in O(1).
Die Suche in einem ausgewogenen Baum führt zu Ergebnissen in O(log(n)).
Das Durchsuchen eines Arrays führt zu Ergebnissen in O(n).
Die besten Sortieralgorithmen haben eine Komplexität von O(n*log(n)).
Ein schlechter Sortieralgorithmus hat die Komplexität O(n2).

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

Es gibt verschiedene Arten der zeitlichen Komplexität von Algorithmen:

durchschnittliches Fallszenario
Best-Case-Szenario
und Worst-Case-Szenario

Zeitkomplexität ist oft das Worst-Case-Szenario.

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

Speicherverbrauch des Algorithmus
Festplatten-I/O-Verbrauchsalgorithmus

Natürlich gibt es schlimmere Komplikationen als n2, zum Beispiel:

n4: Das ist schrecklich! Einige der genannten Algorithmen weisen diese Komplexität auf.
3n: Das ist noch schlimmer! Einer der Algorithmen, die wir in der Mitte dieses Artikels sehen werden, weist diese Komplexität auf (und er wird tatsächlich in vielen Datenbanken verwendet).
Fakultät n: Selbst mit einer kleinen Datenmenge erhalten Sie nie Ihre Ergebnisse.
nn: Wenn Sie auf diese Komplexität stoßen, sollten Sie sich fragen, ob das wirklich Ihr Tätigkeitsfeld ist ...

Hinweis: Ich habe Ihnen nicht die tatsächliche Definition der großen O-Bezeichnung gegeben, sondern nur eine Idee. Sie können diesen Artikel unter lesen Wikipedia für die reale (asymptotische) Definition.

Zusammenführen, sortieren

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

Es gibt mehrere gute Sortieralgorithmen, daher konzentriere ich mich auf die wichtigsten: Zusammenführen, sortieren. Möglicherweise verstehen Sie im Moment nicht, warum das Sortieren von Daten nützlich ist, sollten es aber nach dem Teil zur Abfrageoptimierung tun. Darüber hinaus wird uns das Verständnis der Zusammenführungssortierung später dabei helfen, die so genannte allgemeine Datenbankverknüpfungsoperation zu verstehen fusionieren join (Fusionsverein).

Verschmelzen

Wie viele nützliche Algorithmen basiert auch die Zusammenführungssortierung auf einem Trick: Die Kombination zweier sortierter Arrays der Größe N/2 zu einem sortierten N-Element-Array kostet nur N Operationen. Dieser Vorgang wird Zusammenführen genannt.

Sehen wir uns anhand eines einfachen Beispiels an, was das bedeutet:

Diese Abbildung zeigt, dass Sie zum Erstellen des endgültigen sortierten Arrays mit 8 Elementen nur einmal über die beiden Arrays mit 2 Elementen iterieren müssen. Da beide 4-Element-Arrays bereits sortiert sind:

1) Sie vergleichen beide aktuellen Elemente in zwei Arrays (am Anfang aktuell = zuerst)
2) Nehmen Sie dann das kleinste, um es in ein Array mit 8 Elementen einzufügen
3) und gehen Sie zum nächsten Element im Array, 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 verbleibenden Elemente des anderen Arrays, um sie in ein Array mit 8 Elementen einzufügen.

Dies funktioniert, weil beide 4-Element-Arrays sortiert sind und Sie in diesen Arrays nicht „zurückgehen“ müssen.

Nachdem wir nun den Trick verstanden haben, ist hier mein Pseudocode für die Zusammenführung:

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

   //recursive calls
   [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);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Durch die Zusammenführungssortierung wird ein Problem in kleinere Probleme aufgeteilt und dann die Ergebnisse der kleineren Probleme ermittelt, um das Ergebnis des ursprünglichen Problems zu erhalten (Hinweis: Diese Art von Algorithmus wird „Divide and Conquer“ genannt). Wenn Sie diesen Algorithmus nicht verstehen, machen Sie sich keine Sorgen. Ich habe es nicht verstanden, als ich es zum ersten Mal sah. Wenn es Ihnen helfen kann, betrachte ich diesen Algorithmus als einen Zwei-Phasen-Algorithmus:

Teilungsphase, in der das Array in kleinere Arrays unterteilt wird
In der Sortierphase werden kleine Arrays (mittels Union) zu einem größeren Array kombiniert.

Teilungsphase

In der Teilungsphase wird das Array in drei Schritten in einheitliche Arrays unterteilt. Die formale Anzahl der Schritte ist log(N) (da N=3, log(N) = 8).

Woher weiß ich das?

Ich bin ein Genie! Mit einem Wort: Mathematik. Die Idee ist, dass jeder Schritt die Größe des ursprünglichen Arrays durch 2 teilt. Die Anzahl der Schritte gibt an, wie oft Sie das ursprüngliche Array in zwei Teile teilen können. Dies ist die genaue Definition eines Logarithmus (Basis 2).

Sortierphase

In der Sortierphase beginnen Sie mit einheitlichen (einzelnen) Arrays. Bei jedem Schritt wenden Sie mehrere Zusammenführungsvorgänge an und die Gesamtkosten betragen N = 8 Vorgänge:

In der ersten Phase haben Sie 4 Zusammenführungen, die jeweils 2 Operationen kosten
Im zweiten Schritt haben Sie 2 Zusammenführungen, die jeweils 4 Operationen kosten
Im dritten Schritt führen Sie eine Zusammenführung durch, die 1 Operationen kostet

Da es log(N) Schritte gibt, Gesamtkosten N * log(N)-Operationen.

Vorteile der Zusammenführungssortierung

Warum ist dieser Algorithmus so mächtig?

Denn:

Sie können es ändern, um den Speicherbedarf zu reduzieren, sodass Sie keine neuen Arrays erstellen, sondern das Eingabearray direkt ändern.

Hinweis: Diese Art von Algorithmus wird aufgerufen in-Ort (Sortieren ohne zusätzlichen Speicher).

Sie können es ändern, um gleichzeitig Speicherplatz und eine kleine Menge Arbeitsspeicher zu nutzen, ohne dass es zu einem erheblichen Festplatten-E/A-Overhead kommt. Die Idee besteht darin, nur die Teile in den Speicher zu laden, die gerade verarbeitet werden. Dies ist wichtig, wenn Sie eine Multi-Gigabyte-Tabelle mit nur einem 100-Megabyte-Speicherpuffer sortieren müssen.

Hinweis: Diese Art von Algorithmus wird aufgerufen externe Sortierung.

Sie können es so ändern, dass es auf mehreren Prozessen/Threads/Servern ausgeführt wird.

Beispielsweise ist die verteilte Zusammenführungssortierung eine der Schlüsselkomponenten Hadoop (das ist eine Struktur in Big Data).

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

Dieser Sortieralgorithmus wird in den meisten (wenn nicht allen) Datenbanken verwendet, ist aber nicht der einzige. Wenn Sie mehr wissen möchten, können Sie dies lesen Forschungsarbeit, in dem die Vor- und Nachteile gängiger Datenbanksortieralgorithmen erörtert werden.

Array, Baum und Hash-Tabelle

Nachdem wir nun die Idee der zeitlichen Komplexität und Sortierung verstanden haben, sollte ich Ihnen drei Datenstrukturen vorstellen. Das ist wichtig, weil sie sind die Grundlage moderner Datenbanken. Ich werde auch das Konzept vorstellen Datenbankindex.

Array

Ein zweidimensionales Array ist die einfachste Datenstruktur. Eine Tabelle kann man sich als Array vorstellen. Zum Beispiel:

Dieses zweidimensionale Array ist eine Tabelle mit Zeilen und Spalten:

Jede Zeile stellt eine Entität dar
In Spalten werden Eigenschaften gespeichert, die die Entität beschreiben.
Jede Spalte speichert Daten eines bestimmten Typs (Ganzzahl, Zeichenfolge, Datum ...).

Dies ist zum Speichern und Visualisieren von Daten praktisch, wenn Sie jedoch einen bestimmten Wert suchen müssen, ist dies nicht geeignet.

Wenn Sie beispielsweise alle Männer finden möchten, die im Vereinigten Königreich arbeiten, müssen Sie sich jede Zeile ansehen, um festzustellen, ob diese Zeile zum Vereinigten Königreich gehört. Es kostet Sie N TransaktionenWo N - Anzahl der Zeilen, was nicht schlecht ist, aber könnte es einen schnelleren Weg geben? Jetzt ist es an der Zeit, uns mit den Bäumen vertraut zu machen.

Hinweis: Die meisten modernen Datenbanken bieten erweiterte Arrays zum effizienten Speichern von Tabellen: Heap-organisierte Tabellen und indexorganisierte Tabellen. Dies ändert jedoch nichts an dem Problem, eine bestimmte Bedingung in einer Gruppe von Spalten schnell zu finden.

Datenbankbaum und Index

Ein binärer Suchbaum ist ein binärer Baum mit einer besonderen Eigenschaft. Der Schlüssel an jedem Knoten muss sein:

größer als alle im linken Teilbaum gespeicherten Schlüssel
weniger als alle im rechten Teilbaum gespeicherten Schlüssel

Mal sehen, was das visuell bedeutet

Idee

Dieser Baum hat N = 15 Elemente. Nehmen wir an, ich suche 208:

Ich beginne bei der Wurzel, deren Schlüssel 136 ist. Da 136<208 ist, schaue ich mir den rechten Teilbaum von Knoten 136 an.
398>208, daher schaue ich auf den linken Teilbaum von Knoten 398
250>208, daher schaue ich auf den linken Teilbaum von Knoten 250
200<208, daher betrachte ich den rechten Teilbaum von Knoten 200. Aber 200 hat keinen rechten Teilbaum, Wert existiert nicht (denn wenn es existiert, befindet es sich im rechten Teilbaum 200).

Nehmen wir an, ich suche 40

Ich beginne bei der Wurzel, deren Schlüssel 136 ist. Da 136 > 40, schaue ich mir den linken Teilbaum von Knoten 136 an.
80 > 40, daher betrachte ich den linken Teilbaum von Knoten 80
40= 40, Knoten existiert. Ich rufe die Zeilen-ID innerhalb des Knotens ab (im Bild nicht dargestellt) und suche in der Tabelle nach der angegebenen Zeilen-ID.
Wenn ich die Zeilen-ID kenne, weiß ich genau, wo sich die Daten in der Tabelle befinden, sodass ich sie sofort abrufen kann.

Am Ende kosten mich beide Suchvorgänge die Anzahl der Ebenen innerhalb des Baums. Wenn Sie den Teil über die Zusammenführungssortierung sorgfältig lesen, sollten Sie feststellen, dass es Log(N)-Ebenen gibt. Es stellt sich heraus, Suchkostenprotokoll(N), nicht schlecht!

Kehren wir zu unserem Problem zurück

Aber das ist sehr abstrakt, also kehren wir zu unserem Problem zurück. Stellen Sie sich anstelle einer einfachen Ganzzahl eine Zeichenfolge vor, die das Land einer Person in der vorherigen Tabelle darstellt. Nehmen wir an, Sie haben einen Baum, der das Feld „Land“ (Spalte 3) der Tabelle enthält:

Wenn Sie wissen möchten, wer in Großbritannien arbeitet
Sie schauen sich den Baum an, um den Knoten zu finden, der Großbritannien darstellt
In „UKnode“ finden Sie den Speicherort der britischen Arbeitnehmerdatensätze.

Diese Suche kostet log(N) Operationen anstelle von N Operationen, wenn Sie das Array direkt verwenden. Was Sie gerade präsentiert haben, war Datenbankindex.

Sie können einen Indexbaum für jede beliebige Gruppe von Feldern erstellen (Zeichenfolge, Zahl, 2 Zeilen, Zahl und Zeichenfolge, Datum ...), solange Sie über eine Funktion zum Vergleichen von Schlüsseln (d. h. Feldgruppen) verfügen, damit Sie diese festlegen können Ordnung unter den Schlüsseln (was für alle Basistypen in der Datenbank der Fall ist).

B+TreeIndex

Während dieser Baum gut zum Abrufen eines bestimmten Werts geeignet ist, gibt es bei Bedarf ein GROßES Problem Holen Sie sich mehrere Elemente zwischen zwei Werten. Dies wird O(N) kosten, da Sie sich jeden Knoten im Baum ansehen und prüfen müssen, ob er zwischen diesen beiden Werten liegt (z. B. bei einer geordneten Durchquerung des Baums). Darüber hinaus ist dieser Vorgang nicht datenträger-e/a-freundlich, da Sie den gesamten Baum lesen müssen. Wir müssen einen Weg finden, dies effizient umzusetzen Reichweitenanfrage. Um dieses Problem zu lösen, verwenden moderne Datenbanken eine modifizierte Version des vorherigen Baums namens B+Tree. In einem B+Tree-Baum:

nur die untersten Knoten (Blätter) Information speichern (Position der Zeilen in der zugehörigen Tabelle)
Der Rest der Knoten ist hier zum Routing zum richtigen Knoten während der Suche.

Wie Sie sehen, gibt es hier mehr Knoten (zweimal). Tatsächlich verfügen Sie über zusätzliche Knoten, „Entscheidungsknoten“, die Ihnen dabei helfen, den richtigen Knoten zu finden (der die Position der Zeilen in der zugehörigen Tabelle speichert). Die Suchkomplexität beträgt jedoch immer noch O(log(N)) (es gibt nur noch eine weitere Ebene). Der große Unterschied besteht darin Knoten auf der unteren Ebene sind mit ihren Nachfolgern verbunden.

Wenn Sie bei diesem B+Baum nach Werten zwischen 40 und 100 suchen:

Sie müssen nur nach 40 suchen (oder nach dem nächsten Wert nach 40, wenn 40 nicht existiert), wie Sie es beim vorherigen Baum getan haben.
Sammeln Sie dann 40 Erben über direkte Erben-Links, bis Sie 100 erreicht haben.

Nehmen wir an, Sie finden M Nachfolger und der Baum hat N Knoten. Das Finden eines bestimmten Knotens kostet log(N) wie beim vorherigen Baum. Aber sobald Sie diesen Knoten erhalten, erhalten Sie M Nachfolger in M Operationen mit Verweisen auf deren Nachfolger. Diese Suche kostet nur M+log(N) Operationen im Vergleich zu N Operationen im vorherigen Baum. Darüber hinaus müssen Sie nicht den gesamten Baum lesen (nur M+log(N)-Knoten), was eine geringere Festplattennutzung bedeutet. Wenn M klein ist (z. B. 200 Zeilen) und N groß ist (1 Zeilen), gibt es einen GROSSEN Unterschied.

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

Sie müssen die Reihenfolge zwischen den Knoten innerhalb eines B+Baums aufrechterhalten, sonst können Sie die Knoten in einem unsortierten Baum nicht finden.
Sie müssen die minimal mögliche Anzahl von Ebenen in B+Tree beibehalten, sonst wird die Zeitkomplexität 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ügevorgängen möglich. Dies hat jedoch seinen Preis: Einfügungen und Löschungen in einem B+-Baum kosten O(log(N)). Deshalb haben einige von Ihnen das gehört Die Verwendung zu vieler Indizes ist keine gute Idee. Wirklich, Sie verlangsamen das schnelle Einfügen/Aktualisieren/Löschen einer Zeile in einer Tabelleweil die Datenbank die Indizes der Tabelle mithilfe einer teuren O(log(N))-Operation für jeden Index aktualisieren muss. Darüber hinaus bedeutet das Hinzufügen von Indizes einen höheren Arbeitsaufwand für Transaktionsmanager (wird am Ende des Artikels beschrieben).

Weitere Einzelheiten finden Sie im Wikipedia-Artikel unter B+Baum. Wenn Sie ein Beispiel für die Implementierung von B+Tree in einer Datenbank wünschen, werfen Sie einen Blick darauf dieser Artikel и dieser Artikel von einem führenden MySQL-Entwickler. Beide konzentrieren sich darauf, wie InnoDB (die MySQL-Engine) mit Indizes umgeht.

Hinweis: Ein Leser sagte mir, dass der B+-Baum aufgrund von Optimierungen auf niedriger Ebene vollständig ausgeglichen sein sollte.

Hash-tabelle

Unsere letzte wichtige Datenstruktur ist die Hash-Tabelle. Dies ist sehr nützlich, wenn Sie schnell Werte nachschlagen möchten. Darüber hinaus wird uns das Verständnis einer Hash-Tabelle später dabei helfen, eine gängige Datenbank-Join-Operation namens Hash-Join zu verstehen ( Hash-Join). Diese Datenstruktur wird auch von der Datenbank verwendet, um einige interne Dinge zu speichern (z. B. Sperrtabelle oder Pufferpool, wir werden diese beiden Konzepte später sehen).

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

ключ für deine Elemente
Hash-Funktion für Schlüssel. Die berechneten Schlüssel-Hashes geben den Ort der Elemente an (genannt Segmente ).
Funktion zum Vergleichen von Schlüsseln. Sobald Sie das richtige Segment gefunden haben, müssen Sie mithilfe dieses Vergleichs das gesuchte Element innerhalb des Segments finden.

Einfaches Beispiel

Nehmen wir ein klares Beispiel:

Diese Hash-Tabelle besteht aus 10 Segmenten. Weil ich faul bin, habe ich mir nur 5 Segmente vorgestellt, aber ich weiß, dass Sie schlau sind, also lasse ich Sie die anderen 5 selbst fotografieren. Ich habe eine Hash-Funktion Modulo 10 des Schlüssels verwendet. Mit anderen Worten, ich speichere 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,
ist die letzte Ziffer 2, fällt das Element in Bereich 2,
...

Die von mir verwendete Vergleichsfunktion ist einfach die Gleichheit zwischen zwei ganzen Zahlen.

Nehmen wir an, Sie möchten Element 78 erhalten:

Die Hash-Tabelle berechnet den Hash-Code für 78, also 8.
Die Hash-Tabelle untersucht Segment 8 und das erste gefundene Element ist 78.
Sie gibt Artikel 78 an Sie zurück
Die Suche kostet nur 2 Operationen (eines zum Berechnen des Hash-Werts und das andere zum Nachschlagen des Elements innerhalb des Segments).

Nehmen wir nun an, Sie möchten Element 59 erhalten:

Die Hash-Tabelle berechnet den Hash-Code für 59, also 9.
Die Hash-Tabelle sucht in Segment 9, das erste gefundene Element ist 99. Da 99!=59 ist, ist Element 99 kein gültiges Element.
Mit der gleichen Logik werden das zweite Element (9), das dritte (79), ..., das letzte (29) genommen.
Element nicht gefunden.
Die Suche kostete 7 Operationen.

Gute Hash-Funktion

Wie Sie sehen, sind die Kosten je nach gesuchtem Wert unterschiedlich!

Wenn ich nun die Hash-Funktion modulo 1 des Schlüssels ändere (also die letzten 000 Ziffern nehme), kostet die zweite Suche nur 000 Operation, da im Segment 6 keine Elemente vorhanden sind. Die eigentliche Herausforderung besteht darin, eine gute Hash-Funktion zu finden, die Buckets mit einer sehr kleinen Anzahl von Elementen erstellt.

In meinem Beispiel ist es einfach, eine gute Hash-Funktion zu finden. Dies ist jedoch ein einfaches Beispiel. Das Finden einer guten Hash-Funktion ist schwieriger, wenn der Schlüssel lautet:

Zeichenfolge (z. B. Nachname)
2 Zeilen (zum Beispiel – Nachname und Vorname)
2 Zeilen und Datum (z. B. Nachname, Vorname und Geburtsdatum)
...

Mit einer guten Hash-Funktion kosten Hash-Tabellensuchen O(1).

Array vs. Hash-Tabelle

Warum nicht ein Array verwenden?

Hmm, gute Frage.

Die Hash-Tabelle kann sein teilweise in den Speicher geladen, und die restlichen Segmente können auf der Festplatte verbleiben.
Bei einem Array müssen Sie zusammenhängenden Speicherplatz im Speicher verwenden. Wenn Sie eine große Tabelle laden Es ist sehr schwierig, ausreichend durchgehenden Platz zu finden.
Für eine Hash-Tabelle können Sie den gewünschten Schlüssel auswählen (z. B. Land und Nachname der Person).

Weitere Informationen finden Sie im Artikel über JavacHashMap, was eine effiziente Implementierung einer Hash-Tabelle ist; Sie müssen Java nicht verstehen, um die in diesem Artikel behandelten Konzepte zu verstehen.

Source: habr.com

Wie relationale Datenbanken funktionieren (Teil 1)