Ich habe über Skip-Listen und MemSQL gelesen und habe mich gefragt, warum Skip-Listen in Datenbanken nicht häufiger verwendet werden? Gibt es große Nachteile bei der Verwendung von Skip-Listen?Warum werden Skip-Listen gegenüber B + -Bäumen für Datenbanken nicht bevorzugt?
Datenbanken sind in der Regel so groß, dass sie in einem externen Speicher wie einem riesigen Laufwerk gespeichert werden müssen. Daher ist der Flaschenhals bei den meisten Datenbankanwendungen die Häufigkeit, mit der wir eine Speicherübertragung vom Plattenlaufwerk in den Hauptspeicher durchführen müssen.
B-Bäume und ihre Varianten wurden speziell entwickelt, um die Anzahl der Lese- und Schreibvorgänge zu minimieren, die für die Ausführung der einzelnen Operationen erforderlich sind. Mathematisch ist die Anzahl der für jede B-Baum-Operation erforderlichen Speicherübertragungen O (log n/log B), wobei B die Blockgröße ist. Vergleichen Sie dies mit einer Auslagerungsliste, die O (log n) Speicherübertragungen nach Erwartung erfordert. Da B normalerweise in Megabyte gemessen wird, kann Log B in der Nähe von 15 bis 25 liegen, so dass der B-Baum wesentlich schneller sein kann. Selbst wenn sich die Datenbank im Hauptspeicher befindet, kann der Effekt der Speicherhierarchie (L1- und L2-Caches usw.) so ausgeprägt sein, dass B-Baum-Varianten in der Praxis immer noch schneller sind als viele andere Datenstrukturen. This Google blog post gibt einige Hintergrundinformationen dazu.
Obwohl jede Operation in einem B-Baum normalerweise mehr CPU-Arbeit erfordert als entsprechende Operationen in anderen Datenstrukturen, macht die Tatsache, dass sie so wenig Speichertransfers erfordern, sie in der Praxis wesentlich schneller als andere Datenstrukturen. Daher wäre es nicht ratsam, eine Überspringungsliste in einer Datenbank zu verwenden.
Es gibt noch einen anderen Grund, warum B-Bäume nett sind: Sie sind im schlechtesten Fall effizient. Obwohl deterministische Ausblendungslisten existieren, sind die meisten Ausdehnungslisten-Implementierungen randomisiert und geben erwartete Garantien für ihr Verhalten. In einer Datenbank ist dies möglicherweise inakzeptabel, da viele Anwendungsfälle in Datenbanken ein effizientes Verhalten im ungünstigsten Fall erfordern.
Hoffe, das hilft!
Obwohl es spät im Spiel war, aber ich verspürte den Drang, als seine bestbewertete Antwort zu antworten und vielleicht keine vollständige Nachricht zu vermitteln.
Skip-Listen unterscheiden sich von der Balanced-Tree-Datenstruktur, da mehrere Listen effizient kombiniert werden können. In Datenbankbegriffen erlaubt es Indizes, die auf Sprunglisten basieren, effizient zu kombinieren. Ein gutes Beispiel ist Lucene, das Suchmaschinen wie Solr/ElasticSeach antreibt. https://issues.apache.org/jira/browse/LUCENE-866.
B-Tree hat Probleme bei der Kombination mehrerer Indizes, ohne die gesamte a-priori-Kombination zu indizieren, was nicht effizient ist, da eine Neuindizierung historischer Datensätze erforderlich ist.
Wenn Datenspeicher also beliebige Abfragen auf Daten unterstützen müssen, sind Sprunglisten eine ideale Wahl.
Eine gut geschriebene und aufschlussreiche Antwort. Treffe alle Punkte, die ich wissen musste. Vielen Dank! –