Какой поиск быстрее работает: по первичному ключу типа long, или по первичному ключу типа String, и какая разница?
Где-то слышал, что бд устроена примерно как HashMap, и поиск по любому key, независимо от типа key, занимает const.
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуКакой поиск быстрее работает: по первичному ключу типа long, или по первичному ключу типа String, и какая разница?
Где-то слышал, что бд устроена примерно как HashMap, и поиск по любому key, независимо от типа key, занимает const.
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-байтных целых чисел сравнение в общем случае быстрее, чем для строк, хотя бы потому что они фиксированной (и маленькой) длины.