Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur

In der Spalte Redis-Tutorial finden Sie eine detaillierte Erklärung der Sprungtabelle der Redis-Datenstruktur. Ich hoffe, dass sie für Freunde in Not hilfreich ist!

Vorwort: Die Sprungliste ist eine In der geordneten Datenstruktur werden in jedem Knoten mehrere Zeiger auf andere Knoten verwaltet, um den Zweck eines schnellen Zugriffs auf Knoten zu erreichen. Auf diese Weise ist es für uns möglicherweise schwierig zu verstehen. Wir können uns zunächst an die verknüpfte Liste erinnern.

1. Überprüfung von Sprungtabellen

1.1 Was ist eine Sprungtabelle? Bei einer einfach verknüpften Liste können wir nur dann bestimmte Daten finden, wenn die in der verknüpften Liste gespeicherten Daten geordnet sind Von vorne beginnen Enddurchlauf der verknüpften Liste. Auf diese Weise ist die Sucheffizienz sehr gering und die zeitliche Komplexität sehr hoch, nämlich O (n).

Wenn wir die Sucheffizienz verbessern möchten, können wir erwägen, einen Index für die verknüpfte Liste zu erstellen. Extrahieren Sie einen Knoten für jeweils zwei Knoten auf der oberen Ebene, und wir nennen die extrahierte Ebene den Index.

Zu diesem Zeitpunkt gehen wir davon aus, dass wir Knoten 8 finden möchten. Wir können zuerst die Indexschicht durchqueren. Wenn wir in der Indexschicht zum Knoten mit dem Wert 7 durchqueren, stellen wir fest, dass der nächste Knoten 9 ist , also muss der Knoten 8, den wir finden möchten, zwischen diesen beiden Knoten liegen. Wir stiegen auf die Ebene der verknüpften Liste ab und setzten die Durchquerung fort, um den Knoten 8 zu finden. Ursprünglich mussten wir 8 Knoten durchlaufen, um Knoten 8 in einer einfach verknüpften Liste zu finden, aber jetzt müssen wir mit dem Index der ersten Ebene nur noch fünf Knoten durchlaufen.

Aus diesem Beispiel können wir ersehen, dass nach dem Hinzufügen einer Indexebene die Anzahl der Knoten, die nach einem Knoten durchsucht werden müssen, verringert wird, was bedeutet, dass die Sucheffizienz auf die gleiche Weise verbessert wird wie eine Indexebene wird hinzugefügt.

Auf dem Bild können wir sehen, dass sich die Sucheffizienz erneut verbessert hat. In unserem Beispiel haben wir sehr wenige Daten. Wenn eine große Datenmenge vorhanden ist, können wir mehrstufige Indizes hinzufügen und die Sucheffizienz erheblich verbessern.

​​​​​

Eine Struktur wie diese verknüpfte Liste plus mehrstufiger Index ist eine Sprungliste!

2. Redis-Sprungtabelle Redis verwendet die Sprungtabelle als eine der zugrunde liegenden Implementierungen von geordneten Mengenschlüsseln, wenn eine geordnete Menge eine große Anzahl von Elementen enthält oder die

Mitglieder der Elemente in der geordneten Menge sind Bei langen Zeichenfolgen verwendet Redis Sprungtabellen als zugrunde liegende Implementierung geordneter Satzschlüssel.

Hier müssen wir über eine Frage nachdenken: Warum verwendet Redis eine Sprungtabelle, wenn die Anzahl der Elemente relativ groß ist oder die Mitglieder relativ lange Zeichenfolgen sind?

Aus dem oben Gesagten können wir erkennen, dass die Sprungliste der verknüpften Liste einen mehrstufigen Index hinzufügt, um die Sucheffizienz zu verbessern. Es handelt sich jedoch um eine Raum-Zeit-Lösung, die unweigerlich ein Problem mit sich bringt – den Index nimmt Speicher in Anspruch. Die ursprüngliche verknüpfte Liste speichert möglicherweise sehr große Objekte, der Indexknoten muss jedoch nur Schlüsselwerte und einige Zeiger speichern und benötigt keine Objekte. Daher ist der Knoten selbst relativ groß oder die Anzahl der Elemente ist relativ groß relativ groß, sein Vorteil ist Die Vorteile werden zwangsläufig vergrößert, während die Mängel ignoriert werden können. 2.1 Implementierung der Skip-Tabelle in Redis

Die Skip-Tabelle von Redis wird durch zwei Strukturen definiert, Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur und Skiplist. Die Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur-Struktur wird zur Darstellung von Skip-Tabellenknoten verwendet, während die zskiplist-Struktur zum Speichern relevanter Informationen der Skip-Tabelle verwendet wird Knoten, wie z. B. Knoten, sowie Zeiger auf den Kopfknoten und den Endknoten usw.

Die obige Abbildung zeigt ein Beispiel einer Skip-Liste, ganz links ist die Skiplist-Struktur, die die folgenden Attribute enthält.

header: Zeigt auf den Kopfknoten der Sprungtabelle. Die zeitliche Komplexität des Auffindens des Kopfknotens durch dieses Zeigerprogramm beträgt O(1)

tail: Zeigt auf den Endknoten der Sprungtabelle Dieses Zeigerprogramm Die zeitliche Komplexität des Auffindens des Knotens am Ende der Tabelle beträgt O(1)

• Ebene: Zeichnen Sie die Anzahl der Schichten des Knotens mit der größten Anzahl von Schichten in der aktuellen Sprungtabelle auf (die Anzahl der Die Schichten des Kopfknotens sind nicht enthalten. Durch dieses Attribut kann die Schichtnummer des Knotens mit der besten Schichthöhe in der O(1)-Zeitkomplexität ermittelt werden.

• Länge: Zeichnen Sie die Länge der Sprungtabelle auf, dh die Anzahl der derzeit in der Sprungtabelle enthaltenen Knoten (Kopfknoten sind nicht enthalten). Durch dieses Attribut kann das Programm den Sprung innerhalb der Zeitkomplexität von O zurückgeben (1) Die Länge der Tabelle.

  Rechts von der Struktur befinden sich vier Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur-Strukturen, die die folgenden Attribute enthalten:

• Level (Ebene):

  Die Knoten sind mit 1, 2, L3 und anderen Wörtern gekennzeichnet, um jede Ebene des Knotens zu markieren. L1 repräsentiert die erste Ebene. L repräsentiert die zweite Ebene und so weiter.

  Jede Ebene hat zwei Eigenschaften: Vorwärtszeiger und Spanne. Der Vorwärtszeiger wird verwendet, um auf andere Knoten am Ende der Tabelle zuzugreifen, während die Spanne den Abstand zwischen dem Knoten, auf den der Vorwärtszeiger zeigt, und dem aktuellen Knoten aufzeichnet (je größer die Spanne, desto weiter der Abstand). Im Bild oben stellt der Pfeil mit einer Zahl auf der Verbindungslinie den Vorwärtszeiger dar, und diese Zahl ist die Spanne. Wenn das Programm vom Anfang der Tabelle zum Ende der Tabelle wechselt, erfolgt der Zugriff entlang des Vorwärtszeigers der Ebene.

  Jedes Mal, wenn ein neuer Sprungtabellenknoten erstellt wird, generiert das Programm basierend auf dem Potenzgesetz zufällig einen Wert zwischen 1 und 32 als Größe des Ebenenarrays (je größer die Zahl, desto geringer ist die Wahrscheinlichkeit des Auftretens dieser Größe). ist die „Höhe“ der Ebene.

• Rückwärtszeiger:

  Der Rückwärtszeiger des mit BW markierten Knotens im Knoten, der auf den vorherigen Knoten zeigt, der sich am aktuellen Knoten befindet. Der Rückzeiger wird verwendet, wenn das Programm vom Ende der Tabelle zum Anfang wechselt. Der Unterschied zum Vorwärtszeiger besteht darin, dass jeder Knoten nur einen Rückwärtszeiger hat und sich daher jeweils nur um einen Knoten rückwärts bewegen kann.

• Score:

  1,0, 2,0 und 3,0 in jedem Knoten sind die vom Knoten gespeicherten Punkte. In der Sprungtabelle werden die Knoten entsprechend ihrer gespeicherten Punktzahl von klein nach groß angeordnet.

• Mitgliedsobjekt (oj):

  Die o1, o2 und o3 in jedem Knoten sind die vom Knoten gespeicherten Mitgliedsobjekte. In derselben Sprungtabelle müssen die von jedem Knoten gespeicherten Mitgliedsobjekte eindeutig sein, aber die von mehreren Knoten gespeicherten Bewertungen können gleich sein: Knoten mit derselben Bewertung werden nach der Größe der Mitgliedsobjekte in lexikografischer Reihenfolge sortiert. Knoten mit kleineren Mitgliedsobjekten werden vorne angeordnet (Richtung näher zum Kopf der Tabelle), während Knoten mit größeren Mitgliedsobjekten hinten angeordnet werden (Richtung näher zum Ende der Tabelle).

2.2 Zeitliche Komplexität allgemeiner Operationen der Redis-Sprungtabelle

操作	时间复杂度
创建一个Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur	O(1)
释放给定Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur以及其中包含的节点	O(N)
添加给定成员和分值的新节点	平均O(logN),最坏O(logN)(N为Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur的长度)
删除除Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur中包含给定成员和分值的节点	平均O(logN),最坏O(logN)(N为Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur的长度)
返回给定成员和分值的节点再表中的排位	平均O(logN),最坏O(logN)(N为Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur的长度)
返回在给定排位上的节点	平均O(logN),最坏O(logN)(N为Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur的长度)
给定一个分值范围,返回Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur中第一个符合这个范围的节点	O(1)
给定一个分值范围,返回Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur中最后一个符合这个范围的节点	平均O(logN),最坏O(logN)(N为Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur的长度)
给定一个分值范围,除Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur中所有在这个范围之内的节点	平均O(logN),最坏O(logN)(N为Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur的长度)
给定一个排位范围,鼎除Detaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur中所有在这个范围之内的节点	O(N),N为被除节点数量
给定一个分值范固(range),比如0到15,20到28,诸如此类,如果跳氏表中有至少一个节点的分值在这个范間之内,那么返回1,否则返回0	O(N),N为被除节点数量

Der Schwerpunkt dieses Artikels

• Die Sprungliste wird basierend auf einer einfach verknüpften Liste plus Indizierung implementiert
• Die Sprungtabelle verbessert die Suchgeschwindigkeit durch den Austausch von Raum gegen Zeit
• Der geordnete Redis-Satz wird mithilfe einer Sprungtabelle implementiert, wenn der Knoten Elemente sind groß oder die Anzahl der Elemente ist groß
• Die Skip-Table-Implementierung von Redis besteht aus zwei Strukturen: zskiplist und zskiplistnode. Unter diesen wird zskiplist zum Speichern von Skip-Tabelleninformationen (z. B. Tabellenkopfknoten, Tabellenendknoten, Länge) verwendet ) und zskiplistnode wird verwendet, um Sprungtabellenknoten darzustellen.
• Redis Die Ebenenhöhe jedes Sprungtabellenknotens ist eine Zufallszahl zwischen 1 und 32.
• In derselben Sprungliste können mehrere Knoten dieselbe Punktzahl, aber das Mitglied enthalten Das Objekt jedes Knotens muss in der Sprungliste eindeutig sein. Die Knoten werden nach der Punktzahl sortiert. Wenn die Punktzahlen gleich sind, werden die Knoten nach der Größe der Mitgliedsobjekte sortiert.

Zusammenfassung

Die Sprungtabelle ist für uns möglicherweise eine etwas ungewohnte Datenstruktur. In diesem Artikel wird kurz die Datenstruktur der Skip-Tabelle vorgestellt und die Verwendung der Skip-Tabelle in Redis analysiert. Im nächsten Artikel wird weiterhin die in Redis verwendete Datenstruktur-Ganzzahlsammlung vorgestellt. Bleiben Sie dran!

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Sprungtabelle der Redis-Datenstruktur. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!