Как происходит разрешение коллизий в хэшах PostgreSQL?

Question

[beduin01]

Если тип индекса - hash, то что происходит если возникает коллизия? Как БД обрабатывает эту ситуацию?

Answer 1

[rPman]

Хеш индекс для базы данных не требует уникальности хеша (т.е. это может быть 2-байтовый хеш с 65536 количеством значений для базы в миллион строк на каждое значение будет много коллизий), это механизм нужен больше чтобы поделить трудоемкость сканирования всей таблицы на возможное количество значений хеша, т.е. в индексе для записей с равным хешем запрос пройдет по всем таким (если у хеша коллизия для id равным 1 и 10 то в таблице индекса у этого хеша будет 2 записи и при поиске нужной обе они будут просканированы).

тут или тут чуток про это есть

Comments

[beduin01]

Спасибо! Скажите, а в каком случае на ваш взгляд хэши лучше btree?

Answer 2

[Dimonchik]

никак, а какие там коллизии? запрос - хеш - возврат по хешу, ты сам жертвуешь точностью в угоду скорости

где точность - там B-Tree

Comments

[beduin01]

Как будет происходить выбор строки если один и два разных ключа будет иметь одинаковый хэш?

Answer 3

[Melkij]

При записи данных tuple id просто сохраняются как есть в индексе. Неважно, это другая версия строки или неудачно попали на коллизию хеш-функции с другими данными
При чтении hash индекс сообщает executor'у, что возвращаемые tuple id необходимо перепроверить по реальным данным (проставляет xs_recheck для indexscan либо выбирается bitmap scan с recheck condition) - механизм lossy поиска.