Индекс на основе фильтра Блума
Индекс на основе фильтра Блума — вероятностной структуры данных, которая быстро отвечает «строка точно не подходит» или «возможно, подходит». В PostgreSQL это расширение bloom, удобное для таблиц со множеством столбцов, по которым запрашивают в произвольных сочетаниях.
Задача, которую он решает: если столбцов десять, а запросы затрагивают разные их подмножества, для B-дерева понадобилось бы множество индексов. Bloom-индекс компактно покрывает все столбцы и отсеивает большинство неподходящих строк, а немногие «возможно» проверяются по самой таблице. Компромисс: бывают ложноположительные срабатывания (ложноотрицательных нет), поэтому индекс годится для сужения выборки, но не для точного поиска. Фильтры Блума применяются и внутри систем: ClickHouse, Parquet и LSM-деревья (RocksDB, Cassandra) используют их, чтобы пропускать блоки данных и SSTable без обращения к диску. Размер настраивается и определяет долю ложных срабатываний.