Ich habe gerade über Skip-Listen und MemSQL gelesen und mich gefragt, warum Skip-Listen in Datenbanken nicht häufiger verwendet werden? Gibt es große Nachteile für die Verwendung von Skip-Listen?
Datenbanken sind normalerweise so groß, dass sie in einem externen Speicher wie einem riesigen Laufwerk gespeichert werden müssen. Daher besteht der Flaschenhals bei den meisten Datenbankanwendungen darin, wie oft wir eine Speicherübertragung vom Festplattenlaufwerk in den Hauptspeicher durchführen müssen.
B-Bäume und ihre Varianten wurden speziell entwickelt, um die Anzahl von Blocklese- und -schreibvorgängen zu minimieren, die notwendig sind, um jede ihrer Operationen auszuführen. 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 die Wirkung 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. Dieser Google-Blog-Beitrag gibt Hintergrundwissen das.
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 schlimmsten 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 im schlimmsten Fall ein effizientes Verhalten erfordern.
Hoffe, das hilft!
Obwohl es spät im Spiel war, fühlte ich den Drang, als seine bestbewertete Antwort zu antworten, und vermittelt vielleicht keine vollständige Botschaft.
Skip-Listen unterscheiden sich von der Balanced-Tree-Datenstruktur, da sie die effiziente Kombination mehrerer Listen ermöglicht. In Datenbankbegriffen erlaubt es Indizes, die auf Sprunglisten basieren, effizient kombiniert zu werden. Ein gutes Beispiel ist Lucene, das Suchmaschinen wie Solr / ElasticSeach antreibt. Ссылка .
B-Tree hat Probleme beim Kombinieren mehrerer Indizes, ohne die gesamte a-priori-Kombination zu indizieren, was nicht effizient ist, da es eine Neuindizierung von historischen Datensätzen erfordert.
Wenn Datenspeicher also beliebige Abfragen auf Daten unterstützen soll, sind Sprunglisten eine ideale Wahl.
Tags und Links database data-structures b-tree skip-lists