как запросы диапазона работают в LSM (дерево слияния структуры журнала)?

Question

Недавно я изучал общие структуры индексации в базах данных, такие как B + -деревья и LSM. У меня есть твердое представление о том, как точка чтения / записи / удаления / сжатия будет работать в LSM.

Например, (в RocksDB / levelDB) при чтении точечного запроса мы сначала проверяем индекс в памяти (memtable), а затем некоторое количество файлов SST, начиная с самых последних и заканчивая самыми последними. На каждом уровне в LSM мы будем использовать бинарный поиск, чтобы ускорить поиск каждого файла SST для данного ключа. Для данного файла SST мы можем использовать фильтры Блума, чтобы быстро проверить, существует ли ключ, что сэкономит нам время.

Чего я не вижу, так это того, как именно работает диапазон чтения. Должен ли LSM открывать итератор на каждом уровне SST (включая memtable) и выполнять итерацию по всем уровням для получения окончательного отсортированного результата? Реализовано ли это как просто серия точечных запросов (почти наверняка нет). Все ли потенциальные ключи сначала извлекаются, а затем сортируются? Буду признателен за любые идеи, которые кто-то имеет здесь.

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

Answer 1

RocksDB имеет множество реализаций итераторов, таких как Memtable Iterator, File Iterator, Iterator Merging и т. Д.

Во время чтения диапазона итератор будет искать начальный диапазон, аналогичный поиску точки (используя бинарный поиск в SST), используя вызов SeekTo(). После поиска начального диапазона будут созданы серии итераторов, по одному для каждой запоминаемой таблицы, по одному для каждого файла уровня 0 (из-за пересекающейся природы SST в L0) и по одному для каждого уровня позже. Итератор слияния собирает ключи от каждого из этих итераторов и выдает данные в отсортированном порядке до достижения конечного диапазона.

См. эту документацию по реализации итератора.