@beduin01

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

Если тип индекса - hash, то что происходит если возникает коллизия? Как БД обрабатывает эту ситуацию?
  • Вопрос задан
  • 299 просмотров
Решения вопроса 1
@rPman
Хеш индекс для базы данных не требует уникальности хеша (т.е. это может быть 2-байтовый хеш с 65536 количеством значений для базы в миллион строк на каждое значение будет много коллизий), это механизм нужен больше чтобы поделить трудоемкость сканирования всей таблицы на возможное количество значений хеша, т.е. в индексе для записей с равным хешем запрос пройдет по всем таким (если у хеша коллизия для id равным 1 и 10 то в таблице индекса у этого хеша будет 2 записи и при поиске нужной обе они будут просканированы).

тут или тут чуток про это есть
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
dimonchik2013
@dimonchik2013
non progredi est regredi
никак, а какие там коллизии? запрос - хеш - возврат по хешу, ты сам жертвуешь точностью в угоду скорости

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы