Почему для индексов в базах данных используют деревья поиска, а не hashmap

Что проверяют

Видите ли вы разницу между структурой данных в памяти и индексом, который лежит на диске страницами. В Go под рукой map с константой в среднем, и вопрос ровно про то, почему база этой константой не соблазняется.

Как отвечать

Главный аргумент: порядок. B-дерево хранит ключи отсортированными, поэтому один индекс закрывает и точный поиск, и диапазон, и неравенство, и префикс LIKE 'abc%', и ORDER BY без отдельной сортировки, и MIN/MAX за один спуск. Хеш-индекс умеет ровно одну операцию: равенство. Всё остальное для него полный перебор.

Второй аргумент: дисковая природа. Узел B-дерева это страница, в неё влезают сотни ключей, поэтому фактор ветвления огромен и глубина дерева на миллиардах строк остаётся три или четыре уровня, верхние из которых всегда в кэше. Считают не сравнения, а обращения к страницам. Хеш даёт в среднем одно обращение, но случайное, и при росте требует перестройки таблицы.

Третий: предсказуемость. Логарифм у дерева это гарантия на худший случай, а константа у хеша средняя оценка, которая рассыпается на перекосе ключей.

Стоит добавить, что составной индекс работает по левому префиксу именно благодаря порядку, и что хеш-индексы в базах всё-таки есть и выигрывают на точечном поиске по длинным ключам. Хорошая параллель с Go: у map порядок обхода намеренно рандомизирован, и это ровно то свойство, которого база позволить себе не может.

Где спотыкаются

Сводят ответ к сравнению асимптотик и заключают, что хеш быстрее. Для индекса важна не скорость одной операции в памяти, а число случайных чтений с диска и то, какие запросы структура вообще способна обслужить.

Повторяют, что дерево экономнее по памяти. Это не так: индекс занимает место и замедляет запись, каждый лишний индекс это плата на каждой вставке и обновлении. Аргумент за дерево не в экономии, а в наборе операций.

Путают B-дерево с бинарным деревом поиска. Бинарное дерево на диске было бы катастрофой: глубина в десятки уровней и столько же случайных чтений на один поиск. Вся идея B-дерева в широком узле размером со страницу.