Комментарии 7
Непонятно главное, как в дереве происходит эффективный поиск по ключу. Перебор всех SST-таблиц с использованием фильтра Блума? Но он даёт лишь вероятности.
Фильтр Блума — это, условно, побитный OR по хешам элементов. Он позволяет быстро проверить отсутствие, но не гарантирует наличие в случае попадания.
Таким образом, насколько я понимаю, среди таблиц-кандидатов достаточно бинарным поиском посмотреть индекс (где ключи сортированы).
И объединение SSTable не требует пересортировки данных, потому что слияние индексов выполняется за линейное время.
Побитный OR выдаст почти все единицы даже с небольшим кол-вом ключей, так что все равно непонятно. Но ладно, замнем для ясности)
Это смотря какая хеш-функция. Формально это определено, как «семейство k хеш-функций, каждая из которых возвращает число от 1 до m, где m — количество разрядов в фильтре», но мне удобнее представлять это семейство как одну хеш-функцию, чьё бинарное значение разрядностью m никогда не содержит более k единиц.
Не понятно как эта структура справляется с выборкой по нескольким параметрам, как организована эта часть?
Статья скорее тянет на обзор, чем на глубокое погружение.
Глубокое погружение в LSM-дерево