Индекс PostgreSQL HASH
Кто-нибудь знает ситуацию, когда вместо B-TREE следует использовать PostgreSQL HASH, потому что мне кажется, что это ловушка. На СОЗДАНИЕ или обслуживание им требуется намного больше времени, чем для B-TREE (по крайней мере, в 10 раз больше), они также занимают больше места (для одного из моих table.columns B-TREE занимает 240 МБ, а HASH будет возьмите 4 ГБ), и я, кажется, понял из моего поиска в Google, что они не выбирают быстрее, чем B-TREE; однако, возможно, недавно HASH был оптимизирован или Google ошибался.
В любом случае, я хотел узнать мнение и опыт вашего парня. Если эти HASH злы, люди должны знать.
Спасибо Также: как насчет MySQL HASH?
Ответы 4
Хеши работают быстрее, чем B-деревья, в случаях, когда у вас есть известное значение ключа, особенно известное уникальное значение.
Хеши следует использовать, если рассматриваемый столбец никогда предназначен для сканирования сравнительно с командами < или >.
Хэши - это сложность O(1), B-деревья - сложность O(log n) (iirc), следовательно, для больших таблиц с уникальными записями получение ITEM = "foo" будет наиболее эффективным способом его поиска.
Это особенно практично, когда эти уникальные поля используются в условии соединения.
Следует отметить, что в версии 8.4 решена проблема, когда хеш-индексы были менее эффективны и медленнее, чем индексы в виде b-дерева. postgresql.org/docs/8.4/static/release-8-4.html#AEN95616
Только один вопрос, насколько я знаю, поиск по двоичному дереву - это O (logn), а не O (n * logn), я прав?
Хазинг - это O(1)в памяти, но с базой данных данные часто находятся на диске, индекс также может быть на диске, а время доступа к диску >> время доступа к ОЗУ. Я не помню из класса базы данных, как именно это работало, но в некоторых случаях это не O(1). Я бы все равно ожидал, что хэш будет намного быстрее, но в Postgres 9.5 хеш, как сообщается, лишь немногим быстрее, чем b-tree, к тому же он не полностью безопасен.
Ага. По правде говоря, вы редко получаете постоянную производительность в «реальном мире», всегда есть какая-то реальность, которая усложняет задачу. Например, доступ к памяти может быть O(1), но в зависимости от того, о какой памяти вы говорите, это могут быть очень большие или очень маленькие значения 1;). L1 / L2 / L3 / Ram / Swap не имеют одинаковой скорости, но сам алгоритм по-прежнему считается O(1).
Поскольку точка http://www.postgresql.org/docs/9.2/static/sql-createindex.html Хеш-индекс все еще не является безопасным для WAL; это означает, что они не на 100% надежны для сбоев (индекс должен быть восстановлен, и при репликации может произойти неправильный ответ). Проверьте также http://www.postgresql.org/docs/9.1/static/wal-intro.html
Это также верно для потоковой или файловой репликации и по-прежнему актуально для версии 9.5. postgresql.org/docs/9.5/static/indexes-types.html
Начиная с версии 10, это уже не так. предприимчивыйb.com/blog/postgresqls-hash-indexes-are-now-cool
Я не пробовал этого, но рассматриваю этот подход, чтобы использовать хеш-индексы в незарегистрированных временных таблицах.
Насколько я понимаю, они строятся быстрее, занимают меньше места и запрашивают немного быстрее, чем b-tree.
Согласно этот тест, хеш-индексы немного быстрее и немного меньше, чем индексы BTree. Однако вы не можете создать с ними уникальный хеш-индекс - кроме того, они не регистрируются в WAL.
Лучше использовать хеш-индекс для текстовых столбцов, поиск по которым выполняется только с помощью оператора =. Например, столбец URL-адреса, который необходимо проиндексировать для поиска.
Хеш-индекс составляет примерно 30% от размера индекса B-дерева для чего-то вроде URL.
Уменьшенный размер позволяет PostgreSQL более эффективно использовать свою кеш-память (также известную как shared_buffers).
На самом деле, это в значительной степени то, о чем я думал, прежде чем изучать взгляды разработчиков PostgreSQL. Но кажется, что даже для описанной вами ситуации HASH не превосходят B-TREE с точки зрения эффективности и результативности, поскольку кажется, что теоретический алгоритм не был настолько практичным. Спасибо