B-дерево против хеш-таблицы

В MySQL тип индекса - это b-дерево, и доступ к элементу в b-дереве осуществляется за логарифмическое амортизированное время O(log(n)).

С другой стороны, доступ к элементу в хеш-таблице находится в O(1).

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

Вы можете получить доступ к элементам только по их первичному ключу в хеш-таблице. Это быстрее, чем с древовидным алгоритмом ( O(1)вместоlog(n) ), но вы не можете выбирать диапазоны ( все, что находится между xиy ). Алгоритмы дерева поддерживают это, Log(n)тогда как хеш-индексы могут привести к полному сканированию таблицы O(n). Кроме того, постоянные накладные расходы на хеш-индексы обычно больше ( что не является фактором в тета-нотации, но все же существует ). Кроме того, древовидные алгоритмы обычно легче поддерживать, увеличивать вместе с данными, масштабировать и т. Д.

Индексы хеширования работают с заранее определенными размерами хешей, так что в итоге вы получаете несколько «корзин», в которых хранятся объекты. Эти объекты снова зацикливаются, чтобы действительно найти нужный внутри этого раздела.

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

Современные алгоритмы хэш-таблиц обычно масштабируются, но масштабирование может быть неэффективным.

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

Его называют РАШ - R eplication U NDER S calable Н озоления, и эти алгоритмы, таким образом , называют алгоритмы Раша.

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

Компромисс для древовидных алгоритмов невелик, и они подходят почти для каждого случая использования и поэтому используются по умолчанию.

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

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

Разница между использованием b-дерева и хеш-таблицы заключается в том, что первая позволяет использовать сравнения столбцов в выражениях, использующих операторы =,>,> =, <, <= или BETWEEN, а последняя используется только для сравнения на равенство , в которых используются операторы = или <=>.

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

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

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