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

В MySQL тип индекса - это b-дерево, а доступ к элементу в b-дереве - в логарифмическом амортизированном времени. >.

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

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

75 голосов | спросил JohnJohnGa 5 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 05 Sep 2011 13:43:17 +0400 2011, 13:43:17

4 ответа


0

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

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

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

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

  

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

     

Это называется RUSH - R эпликация U и S , которую можно H озолить и эти алгоритмы, таким образом, называются алгоритмами RUSH.

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

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

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

ответил The Surrican 5 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 05 Sep 2011 13:58:30 +0400 2011, 13:58:30
0

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

Разница между использованием b-дерева и хеш-таблицы заключается в том, что первая позволяет использовать сравнения столбцов в выражениях, которые используют =, & gt ;,> =, & lt ;, & lt ; = или операторы МЕЖДУ, в то время как последний используется только для сравнений на равенство , которые используют = или <=> операторы.

ответил lmiguelvargasf 20 Mayam16 2016, 00:23:03
0

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

ответил Emil Vikström 5 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 05 Sep 2011 13:48:12 +0400 2011, 13:48:12
0

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

ответил Jonathan Weatherhead 5 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowMon, 05 Sep 2011 13:48:53 +0400 2011, 13:48:53

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132