Почему списки пропусков не предпочтительнее деревьев B+ для баз данных?

Question

Я читал о списках пропусков и MemSQL, и мне было интересно, почему списки пропусков не так широко используются в базах данных? Существуют ли серьезные недостатки в использовании скиплистов?

Answer 1

Базы данных, как правило, настолько огромны, что их необходимо хранить во внешней памяти, например на гигантском диске. В результате узким местом в большинстве приложений баз данных является количество раз, когда нам приходится выполнять передачу памяти с диска в основную память.

B-деревья и их варианты специально разработаны для минимизации количества операций чтения и записи блоков, необходимых для выполнения каждой из их операций. Математически количество операций передачи памяти, необходимых для каждой операции B-дерева, составляет O(log n / log B), где B - размер блока. Сравните это со списком пропусков, который требует O(log n) передачи памяти в ожидании. Поскольку B обычно измеряется в мегабайтах, log B может находиться в районе 15 - 25, поэтому B-дерево может быть значительно быстрее. Даже когда база данных находится в основной памяти, влияние иерархии памяти (кэши L1 и L2 и т. Д.) Может быть настолько выраженным, что варианты B-дерева на практике все же быстрее, чем многие другие структуры данных. Это сообщение в блоге Google дает некоторую справку об этом.

Хотя каждая операция в B-дереве обычно требует больше ресурсов процессора, чем соответствующие операции в других структурах данных, тот факт, что им требуется так мало передач памяти, на практике делает их значительно быстрее, чем другие структуры данных. Поэтому не рекомендуется использовать список пропуска в базе данных.

Есть еще одна причина, по которой B-деревья хороши: они эффективны в худшем случае. Хотя детерминированные списки пропусков существуют, большинство реализаций списков пропусков рандомизированы и дают ожидаемые гарантии их поведения. В базе данных это может быть неприемлемо, поскольку для многих сценариев использования в базах данных требуется наихудшее эффективное поведение.

Надеюсь это поможет!

Answer 2

Хотя это уже поздно в игре, но я почувствовал желание ответить, так как он получил самый высокий рейтинг и, возможно, не передает полное сообщение.

Пропуск списков отличается от сбалансированной древовидной структуры данных, поскольку позволяет эффективно комбинировать несколько списков. В терминах базы данных это позволяет эффективно комбинировать индексы на основе пропускаемых списков. Хорошим примером является Lucene, который работает с поисковыми системами, такими как Solr / ElasticSeach. https://issues.apache.org/jira/browse/LUCENE-866.

У B-Tree есть проблемы в объединении нескольких индексов без индексации всей комбинации априори, что неэффективно, поскольку требует повторной индексации исторических записей.

Следовательно, всякий раз, когда хранилище данных должно поддерживать произвольные запросы в списках пропуска данных, это идеальный выбор.

Answer 3

Для кэширования СУБД на диске в блоках страниц я согласен с ответом templatetypedef и комментарием ниже.

@JosephGarvin: список пропуска, в котором хранится B элементов на узел, потребует O(log(n / B)) = O(log(n) - log (B)) поиска (коэффициент ветвления по-прежнему равен 2). Чтобы сопоставить B-дерево, вам нужно также сгруппировать ссылки «пропустить» внутри каждого слоя в блоки, и в этот момент у вас в основном есть B-дерево.

Списки пропуска также имеют недостаток с точки зрения обработки одновременного доступа.

В разделе «Реализация списка одновременных пропусков на диске для альтернативы индексу B-дерева» описывается, как показано ниже.

• Эффективного параллельного доступа достичь труднее, чем варианты B-дерева.
  • В вариантах Skip List и B-tree потоки начинают свой поиск с одной и той же начальной точки, и если один из потоков, идущих по одному и тому же маршруту, первым получит W-блокировку узла, это вызовет конкуренцию с другим потоки и пропускная способность параллельного доступа снижается из-за этих
  • Однако в списке пропуска, если поток получает W-блокировку узла, другие потоки, которые хотят пройти через заблокированный узел, блокируются на узле на всех уровнях вплоть до уровня узла.
    • Принципиальное отличие может заключаться в том, что блокировки ветвей и листьев (узлов) не разделены в Skip List, в отличие от вариантов B-дерева.

Кроме того, в статье описан еще один недостаток.

• Сканирование диапазона (≒ итерация путем указания диапазона) записей может выполняться только в направлении, определенном во время проектирования структуры данных.
  • Хотя это может быть возможно сделать в обоих направлениях, сложность логики (особенно для параллельного доступа) может значительно возрасти, если вы хотите достичь этого, не слишком снижая эффективность обработки.