я понимаю, что:
1. B+-Tree в отличии от LSM позволяет итерировать ключи только в порядке возрастания (потому что в листьях используется односвязный список)?
2. B+-Tree в среднем даёт лучший результат на чтение, чем LSM. Но если в LSM все лежит в одной SSTable (пусть даже очень большой - 1 Тб.), то он работает лучше на чтение по диапазону, потому что в B+-Tree значения могут быть в разных местах файла?
3. Как работает чтение в LSM по диапазону, когда есть несколько SSTable? Читаем сразу со всех, сортируем и выдаем клиенту?
Спасибо.
Лучше прочитать статью @kostja_osipov на Хабре про винил
С мобильного ответы лучше не будут :) 1. Нет, можно и в обратную сторону итерировать btree. 2. Не могу ответить. 3. Необязательно.
1. Если реализовано как односвязный список, то только вперёд. Но Postgresql реализует двухсвязный список, потому умеет в обе стороны. Кроме того, можно запоминать путь от корня, и использовать его для итерации назад.
Обсуждают сегодня