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

Wenn es um relationale Datenbanken geht, habe ich oft das Gefühl, dass etwas fehlt. Sie werden überall verwendet. Es gibt viele verschiedene Datenbanken: von der kleinen und nützlichen SQLite bis hin zu leistungsstarken Systemen wie Teradata. Dennoch gibt es nur wenige Artikel, die erklären, wie eine Datenbank funktioniert. Eine Suche nach "howdoesarelationaldatabasework" zeigt auf, wie wenige Ergebnisse es gibt. Zudem sind diese Artikel oft sehr kurz. Wenn Sie hingegen nach den neuesten Trends wie Big Data, NoSQL oder JavaScript suchen, finden Sie viele detaillierte Artikel, die erklären, wie diese Technologien funktionieren.

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

Als Entwickler hasse ich es, mit Dingen zu arbeiten, die ich nicht verstehe. Und wenn Datenbanken seit über 40 Jahren verwendet werden, muss es einen Grund dafür geben. In all diesen Jahren habe ich Hunderte von Stunden damit verbracht, wirklich zu verstehen, wie diese seltsamen schwarzen Kästen funktionieren, die ich jeden Tag benutze. Relationale Datenbanken sind sehr interessant, weil sie basieren auf nützlichen und vielfach verwendeten Konzepten. Wenn Sie sich für das Verständnis von Datenbanken interessieren, aber nie die Zeit oder den Wunsch hatten, sich in dieses weitreichende Thema zu vertiefen, wird Ihnen dieser Artikel gefallen.

Obwohl der Titel dieses Artikels eindeutig ist, ist das Ziel dieses Artikels nicht, wie man eine Datenbank verwendet. Daher sollten Sie bereits wissen, wie man einfache Joins und grundlegende Abfragen schreibt CRUD; andernfalls werden Sie diesen Artikel möglicherweise nicht verstehen. Das ist das einzige, was Sie wissen müssen; ich erkläre alles weitere.

Ich beginne mit einigen Grundlagen der Informatik, wie 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. Da es sich um ein umfangreiches Thema handelt, werde ich mich auf das konzentrieren, was ich für wichtig halte,: wie eine Datenbank verarbeitet, SQL Anfrage. Ich werde nur die grundlegenden Konzepte von Datenbankenvorstellen, damit Sie am Ende des Artikels eine Vorstellung davon haben, was im Hintergrund passiert.

Da es sich um einen langen und technischen Artikel handelt, der viele Algorithmen und Datenstrukturen umfasst, nehmen Sie sich Zeit, um ihn zu lesen. Einige Konzepte könnten schwer verständlich sein; Sie können sie übergehen und trotzdem ein gutes Gesamtkonzept erhalten.

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

• Überblick über niedrig- und hochstufige Datenbankkomponenten
• Überblick über den Prozess der Abfrageoptimierung
• Überblick über Transaktionsmanagement und den Pufferpool

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, da sie es sich nicht leisten konnten, die CPU und den Speicher ihrer langsamen Computer zu verschwenden.

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

O(1) vs O(n²)

Heutzutage kümmert sich viele Entwickler nicht mehr um die zeitliche Komplexität von Algorithmen … und sie liegen richtig!

Wenn Sie jedoch mit großen Datenmengen umgehen (und ich spreche nicht von Tausenden) oder wenn Sie um Millisekunden kämpfen, wird es entscheidend, dieses Konzept zu verstehen. Und wie Sie wissen, müssen Datenbanken mit beiden Situationen umgehen! Ich werde Sie nicht länger aufhalten, als nötig, um das Wesentliche zu erfassen. Das wird uns später helfen, das Konzept der kostenbasierten Optimierung zu verstehen.Kosten basiert Optimierung).

Die Idee

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

Wenn ich zum Beispiel sage: "Dieser Algorithmus hat eine 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.

Dabei Wichtig ist nicht die Menge der Daten,sondern wie die Anzahl der Operationen mit zunehmendem Datenvolumen wächst.. Die Zeitkomplexität gibt keine genaue Anzahl an Operationen an, ist aber eine gute Methode zur Schätzung der Ausführungszeit.

In diesem Diagramm sehen Sie die Abhängigkeit der Anzahl der Operationen vom Umfang der Eingabedaten für verschiedene Arten von Zeitkomplexitäten von Algorithmen. Ich habe eine logarithmische Skala verwendet, um diese darzustellen. Mit anderen Worten, die Datenmenge wächst schnell von 1 auf 1 Milliarde. Wir können erkennen, dass:

• O(1) oder konstante Komplexität bleibt konstant (sonst würde man dies nicht konstante Komplexität nennen).
• D(log(n)) bleibt selbst bei Milliarden von Daten niedrig.
• Die schlechteste Komplexität ist O(n2), wo die Anzahl der Operationen schnell wächst.
• Die beiden anderen Komplexitäten wachsen ebenso schnell.

Beispiele

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

• Der Algorithmus O(1) erfordert 1 Operation
• Der Algorithmus O(log(n)) erfordert 7 Operationen
• Der Algorithmus O(n) erfordert 2.000 Operationen
• Der Algorithmus O(n * log(n)) erfordert 14.000 Operationen
• Der Algorithmus O(n2) erfordert 4.000.000 Operationen

Der Unterschied zwischen O(1) und O(n²) mag groß erscheinen (4 Millionen Operationen), aber Sie verlieren maximal 2 ms – ungefähr die Zeit, um einmal zu blinzeln. Tatsächlich können moderne Prozessoren Hunderte Millionen Operationen pro Sekunde verarbeiten.Das ist der Grund, warum Leistung und Optimierung in vielen IT-Projekten keine Probleme darstellen.

Wie bereits erwähnt, ist es jedoch wichtig, dieses Konzept zu kennen, wenn man mit großen Datenmengen arbeitet. Wenn der Algorithmus diesmal 1.000.000 Elemente verarbeiten muss (was für eine Datenbank nicht viel ist):

• Der Algorithmus O(1) erfordert 1 Operation
• Ein O(log(n))-Algorithmus benötigt 14 Operationen.
• Ein O(n)-Algorithmus benötigt 1.000.000 Operationen.
• Ein O(n * log(n))-Algorithmus benötigt 14.000.000 Operationen.
• Ein O(n²)-Algorithmus benötigt 1.000.000.000.000 Operationen.

Ich habe keine Berechnungen angestellt, aber ich würde sagen, dass Sie mit einem O(n²)-Algorithmus Zeit haben, um einen Kaffee zu trinken (vielleicht sogar zwei!). Wenn Sie eine Null zur Datenmenge hinzufügen, sollten Sie Zeit für ein Nickerchen haben.

Lassen Sie uns tiefer eintauchen.

Zur Referenz:

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

Hinweis: In den folgenden Abschnitten werden wir diese Algorithmen und Datenstrukturen betrachten.

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

• Durchschnittsszenario
• beste Fallentwicklung
• und schlimmstes Szenario.

Die zeitliche Komplexität ist oft das schlimmste Szenario.

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

• den Speicherverbrauch des Algorithmus
• den Festplatteneingang/-ausgang des Algorithmus.

Natürlich gibt es noch schlimmere Komplexitäten als n², zum Beispiel:

• n⁴: das ist schrecklich! Einige der erwähnten Algorithmen haben eine solche Komplexität.
• 3ⁿ: das ist noch schlimmer! Einer der Algorithmen, den wir in der Mitte dieses Artikels sehen werden, hat diese Komplexität (und wird tatsächlich in vielen Datenbanken verwendet).
• n! (fakultativ): Sie werden Ihre Ergebnisse selbst bei kleinen Datenmengen nie erhalten.
• nⁿ: Wenn Sie auf diese Komplexität stoßen, sollten Sie sich fragen, ob das wirklich Ihr Fachgebiet ist…

Hinweis: Ich habe Ihnen keine exakte Definition von 'Big O' gegeben, sondern lediglich eine Idee. Sie können diesen Artikel unter Wikis für die tatsächliche (asymptotische) Definition lesen.

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 eine Datenbank sollten Sie verstehen, wie diese Funktion sort() funktioniert.

Es gibt mehrere gute Sortieralgorithmen, aber ich will mich auf den wichtigsten konzentrieren: Mergesort. Vielleicht verstehen Sie jetzt noch nicht, warum das Sortieren von Daten nützlich ist, aber Sie werden es nach dem Abschnitt über die Optimierung von Abfragen verstehen. Darüber hinaus wird das Verständnis von Mergesort uns später dabei helfen, die allgemeine Datenbankoperation Join zu verstehen, die als Zusammenführen beitreten (Merge-Join) bezeichnet wird..

Merge (Verschmelzung)

Wie viele nützliche Algorithmen basiert der Mergesort auf einem Trick: Das Mischen von 2 sortierten Arrays der Größe N/2 in ein N-elementiges sortiertes Array kostet nur N Operationen. Dieser Vorgang wird als Mischen bezeichnet.

Schauen wir uns an, was das an einem einfachen Beispiel bedeutet:

Auf diesem Bild sehen Sie, dass zur Erstellung eines endgültigen sortierten Arrays aus 8 Elementen lediglich eine Iteration durch zwei 4-Element-Arrays erforderlich ist. Da beide 4-Element-Arrays bereits sortiert sind:

• 1) vergleichen Sie die aktuellen Elemente in beiden Arrays (zu Beginn ist das aktuelle Element das erste)
• 2) nehmen Sie dann das kleinste Element, um es im 8-Element-Array abzulegen
• 3) und gehen Sie zum nächsten Element im Array, aus dem Sie das kleinste Element genommen haben
• und wiederholen Sie die Schritte 1, 2, 3, bis Sie das letzte Element eines der Arrays erreicht haben.
• Dann nehmen Sie die restlichen Elemente aus dem anderen Array, um sie im 8-Element-Array abzulegen.

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

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 beiden kleinen sortierten Arrays in ein großes
   array result := merge(new_left_array,new_right_array);
   return result;

Der Merge-Sort-Algorithmus zerlegt die Aufgabe in kleinere Aufgaben und findet die Ergebnisse dieser kleineren Aufgaben, um das Ergebnis der ursprünglichen Aufgabe zu erhalten (Hinweis: Diese Art von Algorithmus wird als Divide-and-Conquer bezeichnet). Wenn Sie diesen Algorithmus nicht verstehen, machen Sie sich keine Sorgen; ich verstand es beim ersten Mal, als ich es sah, auch nicht. Wenn es Ihnen hilft, sehe ich diesen Algorithmus als einen zweiphasigen Algorithmus:

• Teilen-Phase, in der das Array in kleinere Arrays aufgeteilt wird
• Sortier-Phase, in der die kleinen Arrays (unter Verwendung der Vereinigung) zusammengeführt werden, um ein größeres Array zu bilden.

Teilen-Phase

In der Teilungsphase wird das Array in unitäre Arrays in 3 Schritten aufgeteilt. Die formale Anzahl der Schritte beträgt log(N) (da N=8, ist 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 durch zwei teilen können. Dies ist die genaue Definition des Logarithmus (zur Basis 2).

Sortier-Phase

In der ersten Phase der Sortierung starten Sie mit eindimensionalen (einzelnelement) Arrays. Während jeder Phase führen Sie mehrere Zusammenführungsoperationen durch, und die Gesamtkosten betragen N = 8 Operationen:

• In der ersten Phase haben Sie 4 Zusammenführungen, die jeweils 2 Operationen kosten.
• In der zweiten Phase bestehen 2 Zusammenführungen, die jeweils 4 Operationen kosten.
• In der dritten Phase haben Sie 1 Zusammenführung, die 8 Operationen kostet.

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

Vorteile des Merge-Sort-Algorithmus

Warum ist dieser Algorithmus so leistungsstark?

Denn:

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

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

• Sie können diese Einstellung anpassen, um den Speicherplatz auf der Festplatte und den geringen Arbeitsspeicher gleichzeitig effizient zu nutzen, ohne hohe Kosten für die Dateneingabe/-ausgabe zu verursachen. Der Gedanke dahinter ist, nur die Teile in den Speicher zu laden, die gerade bearbeitet werden. Dies ist entscheidend, wenn Sie eine mehrere Gigabyte große Tabelle sortieren müssen, während Sie nur über einen 100 Megabyte großen Arbeitsspeicher verfügen.

Hinweis: Diese Art von Algorithmen wird genannt externe Sortierung.

• Sie können dies so ändern, dass es auf mehreren Prozessen / Threads / Servern läuft.

Verteilte Merge-Sortierung ist beispielsweise eines der Schlüsselelemente Hadoop (das eine Struktur im Bereich Big Data darstellt).

• Dieser Algorithmus kann Blei in Gold verwandeln (tatsächlich!).

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

Array, Baum und Hash-Tabelle

Jetzt, wo wir das Konzept der zeitlichen Komplexität und des Sortierens verstehen, möchte ich Ihnen drei Datenstrukturen vorstellen. Das ist wichtig, weil sie die Grundlage moderner Datenbanken bilden.Ich werde auch das Konzept einführen, Datenbankindizes.

Array

Das zweidimensionale 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.
• Die Spalten speichern Eigenschaften, die die Entität beschreiben.
• Jede Spalte speichert Daten eines bestimmten Typs (Integer, String, Datum …).

Es ist praktisch, Daten so zu speichern und zu visualisieren, aber wenn Sie einen bestimmten Wert finden möchten, ist es nicht ideal.

Wenn Sie beispielsweise alle Personen finden möchten, die in Großbritannien arbeiten, müssen Sie jede Zeile durchsuchen, um festzustellen, ob diese Zeile zu Großbritannien gehört. Das würde Ihnen N Operationen kosten,, wobei N die Anzahl der Zeilen, was nicht schlecht ist, aber gibt es einen schnelleren Weg? Jetzt ist es an der Zeit, Bäume kennenzulernen.

Hinweis: Die meisten modernen Datenbanken bieten erweiterte Arrays für die effiziente Speicherung von Tabellen: heap-organisierte Tabellen und index-organisierte Tabellen. Doch das ändert nichts an dem Problem der schnellen Suche nach einer bestimmten Bedingung 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 Unterbaum gespeichert sind
• kleiner als alle Schlüssel, die im rechten Unterbaum gespeichert sind

Schauen wir uns an, was das visuell bedeutet

Die 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 Unterbaum des Knotens 136 an.
• 398 > 208, daher schaue ich mir den linken Unterbaum des Knotens 398 an
• 250 > 208, daher schaue ich mir den linken Unterbaum des Knotens 250 an
• 200 < 208, daher schaue ich mir den rechten Unterbaum des Knotens 200 an. Aber 200 hat kein rechtes Unterbaum, der Wert existiert nicht (denn wenn er existieren würde, wäre er im rechten Unterbaum von 200).

Angenommen, ich suche jetzt 40

• Ich beginne mit der Wurzel, deren Schlüssel 136 ist. Da 136 > 40, schaue ich mir den linken Unterbaum des Knotens 136 an.
• 80 > 40, daher schaue ich mir den linken Teilbaum des Knotens 80 an.
• 40= 40, Der Knoten existiert.. Ich hole die Zeilen-ID innerhalb des Knotens (diese ist im Bild nicht zu sehen) und schaue in der Tabelle nach der entsprechenden Zeilen-ID.
• Die Kenntnis der Zeilen-ID ermöglicht es mir, die genaue Position der Daten in der Tabelle zu bestimmen, sodass ich sie sofort abrufen kann.

Insgesamt werden beide Suchen mir die Anzahl der Ebenen im Baum kosten. Wenn Sie den Abschnitt über Mergesort aufmerksam lesen, sollten Sie sehen, dass es hier log(N) Ebenen gibt. Das bedeutet, die Suchkosten 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. Anstelle einer einfachen Ganzzahl stellen Sie sich eine Zeichenkette vor, die ein Land aus 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 in Großbritannien arbeitet,
• sehen Sie sich den Baum an, um den Knoten zu finden, der Großbritannien darstellt.
• Innerhalb des "UKnode" finden Sie die Position der Aufzeichnungen von Mitarbeitern in Großbritannien.

Diese Suche erfordert log(N) Operationen anstelle von N Operationen, wenn Sie das Array nicht direkt verwenden. Was Sie gerade dargestellt haben, ist der Datenbankindex.

Sie können einen Indexbaum für jede Gruppe von Feldern erstellen (z. B. Zeichenfolgen, Zahlen, zwei Zeichenfolgen, eine Zahl und eine Zeichenfolge, Datum usw.), solange Sie eine Funktion zum Vergleichen der Schlüssel (d. h. der Feldgruppen) haben, um die Reihenfolge der Schlüssel festzulegen (was für alle grundlegenden Datentypen in der Datenbank gilt).

B+TreeIndex

Obwohl dieser Baum gut geeignet ist, um einen bestimmten Wert abzurufen, gibt es ein GROßES Problem, wenn Sie mehrere Elemente zwischen zwei Werten abrufen müssen.Das wird O(N) kosten, da Sie jeden Knoten im Baum überprüfen müssen, um festzustellen, ob er zwischen diesen beiden Werten liegt (z. B. bei einer geordneten Baumdurchquerung). Darüber hinaus ist diese Operation nicht optimiert für den diskbasierten Ein- und Ausgabe, da Sie den gesamten Baum lesen müssen. Wir müssen einen Weg finden, um eine Bereichsanfrage effizient auszuführen.. Um dieses Problem zu lösen, verwenden moderne Datenbanken eine modifizierte Version des vorherigen Baums, die als B+Tree bezeichnet wird. Im B+Tree:

• speichern nur die untersten Knoten (Blätter) Informationen (Standort von Zeilen in der verknüpften Tabelle)
• Die anderen Knoten befinden sich hier zum Routing zum richtigen Knoten während der Suche..

Wie Sie sehen können, gibt es hier mehr Knoten (doppelt so viele). Tatsächlich verfügen Sie über zusätzliche Knoten, die „Entscheidungsknoten“ genannt werden und Ihnen helfen, den richtigen Knoten zu finden (der den Standort der Zeilen in der verknüpften Tabelle speichert). Aber die Suchkomplexität bleibt bei O(log(N)) (es gibt nur eine weitere 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:

• müssen Sie nur 40 (oder den nächstgelegenen Wert nach 40, wenn 40 nicht vorhanden ist) suchen, so wie Sie es mit dem vorherigen Baum gemacht haben.
• Dann sammeln Sie die Nachfolger von 40, indem Sie direkte Verweise auf die Nachfolger verwenden, bis Sie 100 erreichen.

Angenommen, Sie haben M Nachfolger gefunden und der Baum hat N Knoten. Die Suche nach einem bestimmten Knoten kostet log(N), ähnlich wie bei dem vorherigen Baum. Doch sobald Sie diesen Knoten erhalten, haben Sie M Nachfolger in M Verlinkungsoperationen. Diese Suche kostet lediglich M+log(N) Operationen im Vergleich zu N Operationen mit dem vorherigen Baum. Darüber hinaus müssen Sie nicht den gesamten Baum lesen (nur M + log(N) Knoten), was eine geringere Nutzung des Speicherplatzes bedeutet. Wenn M klein ist (zum Beispiel 200 Zeilen) und N groß (1.000.000 Zeilen), wird der Unterschied erheblich sein.

Aber hier entstehen neue Probleme (schon wieder!). Wenn Sie eine Zeile in der Datenbank hinzufügen oder entfernen (und damit im verlinkten B+Tree-Index):

• müssen Sie die Reihenfolge zwischen den Knoten innerhalb des B+Tree aufrechterhalten, andernfalls können Sie die Knoten innerhalb des unsortierten Baums nicht finden.
• müssen Sie so wenige Ebenen wie möglich im B+Tree beibehalten, sonst wird die zeitliche Komplexität von O(log(N)) zu O(N).

Mit anderen Worten, ein B+Tree muss selbstsortierend und balanciert sein. Glücklicherweise ist dies mit intelligenten Lösch- und Einfügeoperationen möglich. Aber das ist kostspielig: Das Einfügen und Löschen in einem B+Tree kostet O(log(N)). Deshalb haben einige von Ihnen gehört, dass die Verwendung einer zu großen Anzahl von Indizes keine besonders gute Idee ist.In der Tat, verlangsamen Sie das schnelle Einfügen/Update/Löschen von Zeilen in der Tabelle, da die Datenbank die Indizes der Tabelle durch die kostspielige Operation O(log(N)) für jeden Index aktualisieren muss. Darüber hinaus bedeutet das Hinzufügen von Indizes eine höhere Belastung für den Transaktionsmanager (der am Ende des Artikels beschrieben wird).

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

Hinweis: Ein Leser sagte mir, dass das B+Tree aufgrund von Low-Level-Optimierungen vollständig balanciert sein sollte.

Hashtabelle

Unsere letzte wichtige Datenstruktur ist die Hash-Tabelle. Sie ist äußerst hilfreich, wenn Sie schnell nach Werten suchen möchten. Darüber hinaus wird das Verständnis der Hash-Tabelle uns später helfen, die gesamte Datenbankoperation zu verstehen, die als Hash-Join bezeichnet wird ( hash join). Diese Datenstruktur wird auch von der Datenbank verwendet, um einige interne Dinge zu speichern (zum Beispiel, Sperrtabelle oder Pufferpool, beide Konzepte werden wir später betrachten).

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

• Schlüssel für Ihre Elemente
• Hash-Funktion für die Schlüssel. Die berechneten Hashes der Schlüssel geben die Position der Elemente (die als Segmente ).
• vergleichsfunktion für Schlüssel). Sobald Sie das richtige Segment gefunden haben, müssen Sie das gesuchte Element innerhalb des Segments mithilfe dieses Vergleichs finden.

Ein einfaches Beispiel

Lassen Sie uns ein anschauliches Beispiel betrachten:

Diese Hash-Tabelle hat 10 Segmente. Da ich faul bin, habe ich nur 5 Segmente dargestellt, aber ich weiß, dass Sie klug sind, also überlasse ich es Ihnen, sich die anderen 5 selbst vorzustellen. Ich habe die Hash-Funktion modulo 10 des Schlüssels verwendet. Anders ausgedrückt, ich behalte nur die letzte Ziffer des Elementschlüssels, um sein Segment zu finden:

• wenn die letzte Ziffer 0 ist, gehört das Element zu Segment 0,
• wenn die letzte Ziffer 1 ist, gehört das Element zu Segment 1,
• wenn die letzte Ziffer 2 ist, gehört das Element zu Segment 2,
• …

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

Angenommen, Sie möchten das Element 78 abrufen:

• Die Hash-Tabelle berechnet den Hash-Code für 78, der 8 entspricht.
• Die Hash-Tabelle schaut in Segment 8, und das erste Element, das sie findet, ist 78.
• Sie gibt Ihnen das Element 78 zurück.
• Die Suche kostet nur 2 Operationen (eine zur Berechnung des Hash-Werts und eine zum Suchen des Elements im Segment).

Jetzt, nehmen wir an, Sie möchten das Element 59 abrufen:

• Die Hash-Tabelle berechnet den Hash-Code für 59, der 9 entspricht.
• Die Hash-Tabelle sucht im Segment 9, das erste gefundene Element ist 99. Da 99!=59, ist das Element 99 kein korrektes Element.
• Auf die gleiche Weise wird das zweite Element (9), das dritte (79), …, das letzte (29) genommen.
• Element nicht gefunden.
• Die Suche kostete 7 Operationen..

Eine gute Hash-Funktion.

Wie Sie sehen, variiert die Kosten je nach Wert, den Sie suchen!

Wenn ich jetzt die Hash-Funktion modulo 1.000.000 vom Schlüssel ändere (das heißt, die letzten 6 Ziffern nehme), kostet die zweite Suche nur 1 Operation, da im Segment 000059 keine Elemente vorhanden sind. Die eigentliche Aufgabe besteht darin, eine gute Hash-Funktion zu finden, die Segmente erstellt, die nur 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 ist die Suche in der Hash-Tabelle O(1)..

Array vs. Hash-Tabelle.

Warum nicht ein Array verwenden?

Hmm, gute Frage.

• Die Hash-Tabelle kann teilweise im Speicher geladen sein., und die übrigen Segmente können auf der Festplatte bleiben.
• Mit einem Array müssen Sie kontinuierlichen Speicher verwenden. Wenn Sie eine große Tabelle laden, ist es sehr schwierig, genügend kontinuierlichen Speicher zu finden..
• Für eine Hash-Tabelle können Sie den gewünschten Schlüssel auswählen (zum Beispiel das Land und den Nachnamen einer Person).

Für weitere Informationen können Sie den Artikel über JavaHashMap, der eine effiziente Implementierung einer Hash-Tabelle darstellt; Sie müssen Java nicht verstehen, um die Konzepte in diesem Artikel zu erfassen.

Quelle: habr.com