Почему фильтры Блума не могут обрабатывать запросы диапазона?

Question

Контекст: я читаю о деревьях RocksDB и LSM, насколько я понимаю, фильтр Блума используется, чтобы избежать множественных операций ввода-вывода для извлечения элементов на всех уровнях хранения. И я в порядке с этим.

Очевидно, одна из проблем заключается в том, что фильтр Блума не может использоваться в запросах диапазона. Какова причина? Если я хочу проверить, есть ли ключ между 32 и 200, я могу выполнить поиск по одному ключу для каждого значения между (или остановиться на первом «истинном» ответе). Это действительно неэффективно?

Answer 1

Вы можете сделать это, но это неэффективно, потому что поиск в одной точке медленен (даже с фильтрами Блума) по сравнению с поиском первого значения (32) и итерацией к 200. Leveldb / rocksdb оптимизирован для таких итераций.

Кроме того, в вашем случае вам просто нужен любой первый ключ между 32 и 200 - вы просто делаете один поиск, и все, в противном случае вам придется делать в худшем случае 200-32 = 168 поисков. Фильтр Блума может быстро ответить, нет ли ключа, если нет коллизий, но он все равно требует поиска диска, если он есть.