Ребятки, у меня вопрос по алгоритмам B+-Tree и LSM. Правильно ли

Question

Ребятки, у меня вопрос по алгоритмам B+-Tree и LSM. Правильно ли

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

Спасибо.

#database #programming #russian #software #tarantool

0

20.08.2018

3 ответов

30 просмотров

Anatoly

С мобильного ответы лучше не будут :) 1. Нет, можно и в обратную сторону итерировать btree. 2. Не могу ответить. 3. Необязательно.

0

20.08.2018

Yura Sokolov

1. Если реализовано как односвязный список, то только вперёд. Но Postgresql реализует двухсвязный список, потому умеет в обе стороны. Кроме того, можно запоминать путь от корня, и использовать его для итерации назад.

0

20.08.2018

Anatoly · Accepted Answer

Anatoly

Лучше прочитать статью @kostja_osipov на Хабре про винил

0

20.08.2018

215 похожих чатов

Ребятки, у меня вопрос по алгоритмам B+-Tree и LSM. Правильно ли

3 ответов

Похожие вопросы