Почему индексы БД используют сбалансированные деревья, а не хеш-таблицы?

Question

Хеш-таблицы выглядят предпочтительнее с точки зрения доступа к диску. Какова реальная причина того, что индексы обычно реализуются с помощью дерева? Извините, если это инфантильно, но я не нашел прямого ответа на SO.

Answer 1

Размер, деревья начинаются с малого и идеально сформированы и хорошо растут до огромных размеров. Хэши имеют фиксированный размер, который может быть слишком большим (10 000 сегментов для 1000 записей) или слишком маленьким (10 000 блоков для 1 000 000 000 записей) для объема имеющихся у вас данных.

Answer 2

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

Таким образом, хеш-таблицы не подходят для этого общего случая, благодаря этому ответу

SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000

или

SELECT * FROM MyTable ORDER BY x

Очевидно, что есть случаи, когда хеш-таблицы лучше, но лучше всего сначала разобраться с основными случаями.

Answer 3

Хеш-таблицы не дают никакой пользы для этого случая:

SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000

Answer 4

Нужно только взглянуть на реализацию хеш-индекса MySQL , связанную с MEMORY механизмом хранения, чтобы увидеть его недостатки:

1. Они могут использоваться с операторами равенства, такими как =, но не с операторами сравнения, такими как <
2. Оптимизатор не может использовать хеш-индекс для ускорения операций ORDER BY.
3. Для поиска строки можно использовать только целые ключи. (С индексом B-дерева любой крайний левый префикс ключа может использоваться для поиска строк.)
4. Оптимизатор не может приблизительно определить количество строк между двумя значениями (это используется оптимизатором диапазона, чтобы решить, какой индекс использовать).

И обратите внимание, что вышесказанное относится к хеш-индексам, реализованным в памяти, без дополнительного рассмотрения вопросов доступа к диску, связанных с индексами, реализованными на диске. Факторы доступа к диску, как отмечает @silentbicycle, еще больше искажают его в пользу сбалансированного индекса дерева.

Answer 5

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

Answer 6

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

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

Тем не менее, выигрыш в производительности, если вы используете физическое местоположение на основе хеш-функции в его полном объеме, огромен.

Answer 7

Хазинг хорош, когда данные не увеличиваются, более технически, когда N / n постоянно. где N = Нет элементов и n = слотов хэша ..

Если это не так, хеширование не дает хорошего прироста производительности.

В базе данных, скорее всего, данные будут увеличиваться значительными темпами, поэтому использование хэша не является хорошей идеей.

и да, там тоже есть сортировка ...