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

Ответ 1

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

Ответ 2

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

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

SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000

или

SELECT * FROM MyTable ORDER BY x

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

Ответ 3

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

SELECT * FROM MyTable WHERE Val BETWEEN 10000 AND 12000

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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