Ein kurzer Vortrag über den MySQL-Index und die Redis-Sprungtabelle

Zusammenfassung

Bei der Diskussion über MySQL-Indexprobleme stellte ich im Interview fest, dass einige Leute zwar über die Unterschiede zwischen B+-Baum, B-Baum und ausgeglichenem Binärbaum sprechen konnten, aber nicht den Unterschied zwischen B+-Baum und Hash-Index erkennen konnten. Es ist offensichtlich, dass es sich hier um reines Auswendiglernen handelt und nicht um ein Verständnis für die Essenz der Indizierung. Dieser Artikel zielt darauf ab, die Prinzipien dahinter zu analysieren. Gerne können Sie eine Nachricht hinterlassen, um zu diskutieren

Frage

Wenn Sie verwirrt sind oder die folgenden Fragen nur vage verstehen, lesen Sie bitte weiter. Ich glaube, dieser Artikel wird Ihnen auf jeden Fall helfen.

• So implementieren Sie einen MySQL-Index
• Was ist der Unterschied zwischen der MySQL-Indexstruktur B+-Baum und Hash? Für welche Szenarien sind sie geeignet?
• Gibt es andere Möglichkeiten, Datenbankindizes zu implementieren?
• Wie wird die Redis-Jump-Tabelle implementiert?
• Was sind die Unterschiede zwischen Skip-Listen, B+-Bäumen und LSM-Bäumen?

Analyse

Warum sollten wir zunächst MySQL-Index und Redis-Skip-Tabelle gemeinsam besprechen? Weil sie dasselbe Problem lösen, nämlich den Speicherort (oder den entsprechenden Wert) eines Datensatzes schnell anhand des angegebenen Schlüssels zu finden.

Wenn Sie aus dieser Perspektive über das Problem nachdenken, kennen Sie immer noch nicht den Unterschied zwischen dem B+-Baumindex und dem Hash-Index?

Das Problem, einen Datensatz zu finden

Jetzt haben wir die Grenzen des Problembereichs klar definiert, um das Problem der Suche nach Datensätzen zu lösen. Welche Aspekte müssen in diesem Zusammenhang berücksichtigt werden?

1. Welche Suchmethoden müssen unterstützt werden, Einzelschlüssel-/Mehrfachschlüssel-/Bereichssuche,
2. Einfügungs-/Löscheffizienz
3. Sucheffizienz (d. h. Zeitkomplexität)
4. Speichergröße (Speicherkomplexität)

Schauen wir uns einige häufig verwendete Suchstrukturen an

Hash

Hash liegt in Form von Schlüssel und Wert vor. Über eine Hash-Funktion kann der Wert anhand des Schlüssels schnell ermittelt werden.

B+ Baum

Der B+-Baum entwickelte sich aus dem balancierten Binärbaum. Warum haben wir im Algorithmusunterricht nichts über Strukturen wie den B+-Baum und die Skip-Liste gelernt? Denn sie sind allesamt Erkenntnisse der Ingenieurpraxis und auf der Basis der Theorie kompromittiert.

Der B+-Baum ist zunächst einmal eine geordnete Struktur. Um zu verhindern, dass der Baum zu hoch wird und die Suchleistung beeinträchtigt, wird auf dem Blattknoten eine Seite mit Daten statt einzelner Daten gespeichert, was die Suchleistung verbessert. Um Bereichsabfragen besser zu unterstützen, speichert der B+-Baum Daten, die keine Blattknoten sind, redundant auf den Blattknoten. Um das Umblättern zu unterstützen, sind die Blattknoten durch Zeiger verbunden.

Sprungtabelle

Die Sprungliste wird auf Basis der verknüpften Liste erweitert, um die sortierte Datenstruktur von Redis zu implementieren. Ebene 0: Hier werden die Originaldaten gespeichert. Es handelt sich um eine geordnete verknüpfte Liste. Jeder Knoten befindet sich in der Kette. Ebene 0+: Die Knoten sind durch Zeiger in Reihe verbunden. Es handelt sich um eine Teilmenge der Originaldaten. Je höher die Ebene, desto weniger Daten sind in Reihe verbunden. Dies kann die Suchleistung erheblich verbessern.

Zusammenfassen

Wenn Sie sich für die Struktur von LSM interessieren, können Sie Cassandra vs Mongo (1) Storage Engine lesen.

Cassandra vs. Mongo (1) Speicher-Engine

Zusammenfassung

Speicher-Engine:

B-Baum

Cache-Verwaltung

Der Kern der Cache-Verwaltung liegt im Ersetzungsalgorithmus. Zu den gängigen Ersetzungsalgorithmen gehören FIFO (First In First Out) und LRU (Least Recently Used). Relationale Datenbanken wurden auf der Grundlage von LRU verbessert, hauptsächlich durch Verwendung von LIRS (Low Inter-reference Recency Set).
Der Cache ist in zwei Ebenen unterteilt. Die erste Ebene verwendet LRU. Die zuletzt verwendeten Daten gelangen in die erste Ebene. Wenn innerhalb kurzer Zeit zweimal oder öfter auf die Daten zugegriffen wird, werden sie zu Hot Data und gelangen in die zweite Ebene. Dadurch wird die Situation vermieden, dass bei der Durchführung eines vollständigen Tabellenscans möglicherweise eine große Menge an Hot Data im Cache ersetzt wird.

LSM

Log-strukturierter Zusammenführungsbaum: Die Kernidee des strukturierten Zusammenführungsbaums besteht nicht darin, Daten sofort vom Speicher auf die Festplatte zu schreiben, sondern sie zuerst im Speicher zu speichern und sie dann, nachdem eine bestimmte Datenmenge angesammelt wurde, auf die Festplatte zu übertragen.

LSM VS. B-Baum

LSM opfert etwas Leseleistung, um eine bessere Schreibleistung auf B-Tree-Basis zu erzielen, und verwendet andere Implementierungen, um die Leseleistung auszugleichen, wie z. B. Boom-Filter.

1. Schreiben

Beim Schreiben in einen B-Baum besteht der erste Schritt darin, die entsprechende Blockposition zu finden und dann die neuen Daten einzufügen. Da immer mehr Daten geschrieben werden, müssen Knoten aufgeteilt werden, um die B-Baumstruktur beizubehalten. Dadurch erhöht sich die Wahrscheinlichkeit von zufälligen Schreibvorgängen beim Einfügen von Daten und die Leistung wird verringert.

LSM bildet einen kleinen sortierten Baum im Speicher und führt ihn dann beim Leeren auf die Festplatte kontinuierlich zusammen. Da alle Schreibvorgänge im Speicher und nicht auf der Festplatte erfolgen, sind Schreibvorgänge sehr effizient.

2. Lesen

Der B-Baum beginnt mit einer binären Abfrage vom Stammknoten zum Blattknoten, wobei jeweils ein Knoten gelesen wird. Wenn die entsprechende Seite nicht im Speicher vorhanden ist, wird die Festplatte gelesen, um die Daten zwischenzuspeichern.

Die gesamte Struktur des LSM-Baums ist nicht geordnet, daher wissen wir nicht, wo sich die Daten befinden. Wir müssen von jeder kleinen geordneten Struktur aus eine binäre Abfrage durchführen. Wenn wir die Daten finden, geben wir sie zurück. Wenn wir die Daten nicht finden, suchen wir weiter nach der nächsten geordneten Struktur. Daher geht bei LSM die Leseleistung verloren. Der Grund, warum LSM als Datenspeichersystem im großen Maßstab verwendet werden kann, liegt jedoch darin, dass die Leseleistung auf andere Weise verbessert werden kann. Beispielsweise hängt die Leseleistung eher von der Speicher-/Cache-Trefferquote als vom Festplattenlesevorgang ab.

Kassandra

Cassandra ist eine NoSQL-Datenbank mit besserer Schreib- als Leseleistung. Ein Grund für die gute Schreibleistung ist die Verwendung der LSM-Speicher-Engine.

Mongo

MMAPv1

Mongo 3.2 und früher verwendeten standardmäßig die MMAPv1-Speicher-Engine, die auf dem B-Tree-Typ basiert.

Polsterung

Die MMAPv1-Speicher-Engine verwendet einen Prozess namens „Datensatzzuweisung“, um Speicherplatz für die Dokumentspeicherung zuzuweisen. Der Unterschied zwischen MongoDB und Cassandra besteht darin, dass Sie das Originaldokument aktualisieren müssen. Wenn der ursprüngliche Dokumentplatz nicht ausreicht, müssen Sie das Dokument an einen neuen Speicherort verschieben und den entsprechenden Index aktualisieren. Dies führt zu einigen unnötigen Aktualisierungen und Datenfragmentierung.

Um die oben beschriebene Situation zu vermeiden, gibt es das Konzept der Grenzen, bei dem Speicherplatz für das Dokument vorab zugewiesen wird. Dies kann jedoch zu einer Verschwendung von Ressourcen führen. Mongo nimmt eine Vorzuteilung nach der Zweierpotenzstrategie von 64 M, 128 M, 256 M ... 2 G mit einem Maximum von 2 G vor. Bei kleinen Datenmengen ist das Problem nicht offensichtlich, bei 2 GB wird die große Festplattennutzung jedoch zum Problem.

Dies unterscheidet sich auch von relationalen Datenbanken, die lange Datensatzdaten separat speichern.

Sperren

MMAPv1 verwendet Sperren auf Sammlungsebene, was bedeutet, dass immer nur eine Sammlung hinzugefügt, gelöscht oder geändert werden kann. Bei der Ausführung gleichzeitiger Vorgänge kommt es zu Wartezeiten.

WiredTiger

Die Standardspeicher-Engine für 3.2 und höher basiert ebenfalls auf B-Tree. Es verwendet gleichzeitige Technologien wie Lock-Free und Risk Pointer, um eine bessere Leistung auf Multi-Core-Maschinen zu erzielen.

Die Sperrebene ist „Dokument“. Außerdem wurde die Komprimierung eingeführt, um die Festplattennutzung zu reduzieren.

Zusammenfassen

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels einen gewissen Lernwert für Ihr Studium oder Ihre Arbeit hat. Vielen Dank für Ihre Unterstützung von 123WORDPRESS.COM.