Сравнение B- и LSM-деревьев

LSM-деревья

➕ Зачастую быстрее при записи
➕ Способны обеспечить бóльшую пропускную способность, поскольку они последовательно записывают компактные файлы SS-таблиц вместо перезаписи нескольких страниц дерева (особенно существенно для HDD, на которых последовательные операции записи
работают намного быстрее, чем произвольные)
➕ Лучше сжимаются, ниже избыточность, а следовательно занимают меньше места на диске

➖ Зачастую медленнее при чтении, потому что приходится просматривать несколько различных структур данных и SS-таблиц, находящихся на разных стадиях уплотнения. Если объемы записи велики, а уплотнение плохо настроено и не успевает за ними, то чтение замедляется ещё сильнее
➖Параллельно работающий процесс уплотнения может сделать время отклика основных запросов менее предсказуемым

B-деревья

➕ Зачастую быстрее при чтении
➕ Удобнее для транзакций: каждый ключ встречается в индексе только в одном месте, в то время как в LSM может быть несколько копий одного ключа в разных сегментах. Во многих реляционных БД изоляция транзакций реализуется с помощью блокировок для диапазонов ключей, и в индексах на основе B-деревьев такие блокировки можно непосредственно привязать к дереву.
➕ Время отклика более предсказуемо

➖Зачастую медленнее при записи: индекс на основе B-дерева должен записывать каждый элемент данных по крайней мере дважды: один раз в WAL и второй — на саму страницу дерева (и, вероятно, снова при разбиении страниц). Кроме того, записывать приходится сразу всю страницу, даже если в ней поменялось лишь несколько байтов.
➖Занимают больше места на диске в силу фрагментации: когда страница разбивается на части или строка не помещается на существующую страницу, некий объем пространства на странице остается незадействованным.

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

#кабанчик #сисдиз