Сортированная таблица строк (SSTable) или B + Дерево для индекса базы данных?

Использование двух баз данных для иллюстрации этого примера: CouchDB и Cassandra.

CouchDB

CouchDB использует дерево B + для индексов документа (используя умную модификацию для работы в среде только для добавления) - более конкретно, поскольку документы изменяются (вставка/обновление/delete), они добавляются к исполняемому файлу базы данных, а также полный путь Leaf → Node из дерева B + всех узлов, выполняемых обновленной версией сразу после документа.

Эти исправления с измененным индексом вставляются прямо рядом с модификациями, так что полный индекс представляет собой объединение самых последних модификаций индекса, добавленных в конце файла, вместе с дополнительными частями далее в файле данных, которые все еще актуальны и еще не были изменены.

Поиск дерева B + - это O (logn).

Cassandra

Cassandra хранит в памяти таблицы записей, отсортированные в памяти (пусть думают о них как массивы для этого вопроса) и записывает их как отдельные (отсортированные) таблицы отсортированной строки время от времени.

Мы можем представить коллекцию всех этих таблиц как "индекс" (из того, что я понимаю).

Cassandra требуется compact/объединить эти таблицы отсортированной строки время от времени, создавая более полное представление файла индекса.

Поиск отсортированного массива - это O (logn).

Вопрос

Предполагая аналогичный уровень сложности между сохранением частичных кусков дерева B + в CouchDB по сравнению с частичными индексами отсортированной строки в Cassandra и учитывая, что оба обеспечивают время поиска O (logn), которое, по вашему мнению, будет лучше представлять базу данных индекс и почему?

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

Спасибо за мысли.

Ответ 1

При сравнении индекса BTree с индексом SSTable следует учитывать сложность записи:

При случайном письме на запись по принципу "копирование на запись" вы будете подвергать случайным чтениям (сделать копию листа node и путь). Таким образом, в то время как записи меня будут последовательными на диске, для наборов данных, больших, чем ОЗУ, эти случайные чтения быстро превратятся в горлышко бутылки. Для индекса, подобного SSTable, такое чтение не возникает при записи - там будут только последовательные записи.
Вы также должны учитывать, что в худшем случае каждое обновление для BTree может повлечь за собой log_b N IO - то есть вы можете записать 3 или 4 блока для каждого ключа. Если размер ключа намного меньше размера блока, это чрезвычайно дорого. Для индекса, подобного SSTable, каждая запись IO будет содержать столько свежего ключа, сколько может, поэтому стоимость ввода-вывода для каждой клавиши больше похожа на 1/B.

На практике это делает SSTable-подобное в тысячи раз быстрее (для случайных записей), чем BTrees.

При рассмотрении деталей реализации мы обнаружили, что гораздо проще реализовать SSTable-подобные индексы (почти) без блокировки, где стратегия блокировки для BTrees стала довольно сложной.

Вы также должны пересмотреть свои расходы на чтение. Вы правы, чем BTree - это O (log_b N) случайные IO для случайных считываний точек, но индекс, подобный SSTable, на самом деле является O (#sstables. Log_b N). Без подходящей схемы слияния #sstables пропорциональна N. Существуют различные трюки, чтобы обойти это (например, с помощью Bloom Filters), но это не помогает при небольших запросах произвольного диапазона. Это мы нашли с Кассандрой:

http://www.acunu.com/blogs/richard-low/cassandra-under-heavy-write-load-part-ii/

Вот почему Castle, наш движок хранения (GPL), сливается несколько иначе и может добиться намного лучшего (O (log ^ 2 N)) диапазона запросов с небольшим компромиссом в производительности записи (O (log ^ 2 N/B)). На практике мы находим, что это быстрее, чем индекс Cassandra SSTable для записи.

Если вы хотите узнать больше об этом, я рассказал о том, как это работает:

Ответ 2

Я думаю, что фрактальные деревья, используемые Tokutek, являются лучшим индексом для базы данных. Они предлагают улучшения в реальном времени от 20x до 80x по сравнению с b-деревьями.

Есть отличные объяснения того, как индексы фрактальной древесины работают здесь.

Ответ 3

LSM-деревья лучше, чем B-деревья в структуре хранилища. Он преобразует случайную запись в aof в некотором роде. Вот LSM-Tree src: https://github.com/shuttler/lsmtree