Я читал о списках пропуска и MemSQL и задавался вопросом, почему списки пропуска более широко не используются в базах данных? Есть ли какие-то серьезные недостатки в использовании скипистов?Почему списки пропуска не являются предпочтительными для B + -trees для баз данных?
Базы данных, как правило, настолько огромны, что их необходимо хранить во внешней памяти, например, на гигантском диске. В результате узкое место в большинстве приложений для баз данных - это количество раз, которое мы должны делать с переносом памяти с диска в основную память.
B-деревья и их варианты специально разработаны для сведения к минимуму количества чтения и записи блоков, необходимых для выполнения каждой из их операций. Математически количество передач памяти, необходимых для каждой операции B-дерева, равно O (log n/log B), где B - размер блока. Сравните это с skiplist, для которого требуется ожидание памяти O (log n) при ожидании. Поскольку B обычно измеряется в мегабайтах, журнал B может находиться в районе 15-25, поэтому B-дерево может быть значительно быстрее. Даже когда база данных находится в основной памяти, эффект иерархии памяти (кеши L1 и L2 и т. Д.) Может быть настолько выраженным, что варианты B-дерева на практике все же быстрее, чем многие другие структуры данных. This Google blog post дает некоторое представление об этом.
Хотя каждая операция на B-дереве обычно требует большей работы ЦП, чем соответствующие операции в других структурах данных, тот факт, что они требуют так мало передач памяти, как правило, делает их значительно более быстрыми на практике, чем другие структуры данных. Поэтому было бы нецелесообразно использовать список переходов в базе данных.
Есть еще одна причина, по которой B-деревья хороши: они в худшем случае эффективны. Хотя детерминированные списки пропусков существуют, большинство реализаций скрипистов рандомизированы и дают ожидаемые гарантии их поведения. В базе данных это может быть неприемлемым, поскольку многие случаи использования в базах данных требуют наихудшего эффективного поведения.
Надеюсь, это поможет!
Несмотря на то, что он опоздал в игре, но я почувствовал желание ответить в качестве его наилучшего ответа и, возможно, не передал полное сообщение.
Списки пропусков отличаются от сбалансированной древовидной структуры данных, поскольку она позволяет эффективно комбинировать несколько списков. В терминах базы данных он позволяет эффективно комбинировать индексы на основе списков пропуска. Хорошим примером является Lucene, который поддерживает поисковые системы, такие как Solr/ElasticSeach. https://issues.apache.org/jira/browse/LUCENE-866.
B-Tree имеет проблемы с объединением нескольких индексов без индексации общей комбинации a-priori, которая неэффективна, поскольку требует повторной индексации исторических записей.
Следовательно, всякий раз, когда хранилище данных должно поддерживать произвольные запросы в списках пропуска данных, это идеальный выбор.
Хорошо написанный и проницательный ответ. Хит все, что мне нужно знать. Спасибо! –