2

Какой поиск быстрее работает: по первичному ключу типа long, или по первичному ключу типа String, и какая разница?

Где-то слышал, что бд устроена примерно как HashMap, и поиск по любому key, независимо от типа key, занимает const.

1
  • 3
    Даже когда дерево строится по значению хеш-функции сам ключ в индекс все равно включается. А чем длинее ключ, тем больше места на диске занимает индекс. А чем больше он занял места тем больше вероятность, что следующая ветвь дерева лежит в отдельной странице, следовательно больше страниц придется поднимать с диска да и головкам дальше бегать по большому индексу (хотя конечно часто файлы используют, а не сырые диски и там может менее заметно из за фрагментации)
    – Mike
    2 фев 2016 в 12:47

1 ответ 1

4

PostgreSQL только в тегах, но ответ зависит от РСУБД, так что предположу его.


Где-то слышал, что бд устроена примерно как HashMap, и поиск по любому key независимо от типа key занимает const.

Необязательно, по умолчанию нет. Это зависит от типа индекса. Для первичных ключей в PostgreSQL по умолчанию используется структура данных B-дерево:

Adding a primary key will automatically create a unique btree index on the column or group of columns used in the primary key.

Хэш-индекс, заставляющий базу делать поиск на манер хэш-таблицы, не рекомендован:

Hash index operations are not presently WAL-logged, so hash indexes might need to be rebuilt with REINDEX after a database crash if there were unwritten changes. Also, changes to hash indexes are not replicated over streaming or file-based replication after the initial base backup, so they give wrong answers to queries that subsequently use them. For these reasons, hash index use is presently discouraged.

(далее вольный перевод) ...поскольку может потребовать полного перестроения при падении БД, а также изменения в нём не реплицируются через файлы и потоки, из-за чего запросы с их использованием могут давать неправильные ответы.


Что касается "что быстрее", ответ всегда один: измерьте в ваших условиях и получите однозначный ответ. Типа данных long в PostgreSQL нет.

Асимптотика поиска в хэш-таблице (ваш "const", aka O(1)) не имеет к этому никакого отношения, поскольку в асимптотику не включен "константный множитель". Множитель в данном случае зависит от скорости одного сравнения двух значений одного типа. Для разных типов он будет разным, а асимптотика при той же структуре данных (том же типе индекса) будет прежней.

Для 4 или 8-байтных целых чисел сравнение в общем случае быстрее, чем для строк, хотя бы потому что они фиксированной (и маленькой) длины.

1
  • спасибо за развёрнутый ответ 2 фев 2016 в 14:01

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.