Почему HashMap не используется в качестве структуры индексов в СУБД?

HashMap (или хэш-таблица) не подходит для индексов в СУБД из-за фундаментальных ограничений своей структуры:

1. Отсутствие упорядоченности — Элементы не отсортированы, что делает неэффективными диапазонные запросы (BETWEEN, >, <, ORDER BY ... LIMIT). Для них требуется полный перебор O(n).
2. Нет префиксного поиска — Невозможно эффективно искать по части ключа (например, LIKE 'abc%').
3. Непредсказуемая производительность при коллизиях — В худшем случае деградация до O(n). Для СУБД критична стабильная и предсказуемая скорость.
4. Затратное рехеширование — Процесс увеличения размера таблицы вызывает задержки, что неприемлемо для систем, работающих под нагрузкой.

Сравнение на примере диапазонного запроса:

// HashMap: Нет гарантированного порядка. Найти ключи от 10 до 20 можно только перебором.
HashMap<Integer, String> map = new HashMap<>();
map.put(15, "val1");
map.put(5, "val2");
map.put(25, "val3");
// Для получения записей WHERE key BETWEEN 10 AND 20 нужен полный scan.

// B-дерево: Данные отсортированы. Диапазон находится за O(log n + m).

Что используют СУБД вместо этого:

• B-деревья и B+-деревья — для сбалансированных workload (чтение/запись), поддерживают сортировку и диапазонные запросы.
• LSM-деревья — для workload с интенсивной записью.
• Хэш-индексы — только в специфичных случаях для точечного поиска по полному ключу (например, в PostgreSQL для условий WHERE column = value).