Индексы на основе журнала - не самый популярный тип индексов. | dev notes

Индексы на основе журнала - не самый популярный тип индексов. Чаще используются индексы на основе B-дерева.
В отличии от журналированных индексов, которые индексируют базу данных сегментами по несколько мегабайт и всегда записывают эти сегменты на диск последовательно, B-деревья разбивают базу на сегменты по несколько килобайт (часто - по 4Kb) и читают/пишут по 1 странице за раз. Такое разбитие и такой размер сегментов отлично накладываются на нижележащие аппаратные слои.
Все страницы имеют свой адрес, и на основе таких ссылок строится дерево. Одна из страниц - корень, с него начинается любой поиск ключа. Все ключи во всех сегментах - отсортированы, и любой узел дерева содержит некоторый диапазон сегментов и несколько ссылок на поддиапазоны.
Если на странице заканчивается место, то создаётся ещё одна ссылка, и страница делится на две полу-пустых страницы.
Такой алгоритм гарантирует, что дерево будет сбалансированным, т.е. любой поиск будет занимать O(log n), что весьма быстро.
Чтобы обезопасить данные от потери во время сбоя, на диске так же хранится журнал упреждающей записи, в который все добавляемые данные записываются перед тем, как попасть в B-дерево.

А зачем тогда нужны LSM-деревья, если есть B-деревья? LSM-деревья реализуют как одну из подсистем во многих СУБД из-за того, что они быстрее при записи. Нам не нужно идти по дереву и искать место, куда добавить ключ. Нам достаточно записать данные в in-memory-структуру и сдублировать их в журнал, и всё. И для таких задач LSM-деревья до сих пор используются.
В свою очередь, B-деревья быстрее при чтении.