В чем разница между индексированием btree и rtree?

36

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

  1. BTREE
  2. RTREE
  3. HASH

Исследуя это, я нашел некоторую информацию, которая была в значительной степени над моей головой, поэтому я ищу практическую информацию о том, в чем разница между ними и / или почему вы должны выбрать одно из другого.

Кроме того, я никогда раньше не выбирал тип хранилища, поэтому я предполагаю, что MySQL выбирает тип хранилища по умолчанию (BTREE?)


источник

Ответы:

51

BTree

BTree (фактически B * Tree) - это эффективная упорядоченная карта ключ-значение. Смысл:

  • учитывая ключ, индекс BTree может быстро найти запись,
  • BTree можно сканировать по порядку.
  • также легко получить все ключи (и записи) в пределах диапазона.

например, «все события с 9:00 до 17:00», «фамилии, начинающиеся с« R »»

RTree

RTree - это spatial indexозначает, что он может быстро идентифицировать closeзначения в 2 или более измерениях. Он используется в географических базах данных для запросов, таких как:

все точки в пределах X метров от (x, y)

гашиш

Хэш является неупорядоченной картой ключ-значение. Это даже более эффективно, чем BTree: O(1)вместо O(log n).

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

Как примечание, первоначально MySQL разрешал хеш-индексы только для MEMORYтаблиц; но я не уверен, что это изменилось за эти годы.

Хавьер
источник
MySQL поддерживает Rtrees?
Pacerier
2
да, они называются SPATIAL INDEX ( dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html )
Хавьер
Круто, спасибо =) Есть ли другие структуры помимо этих 3, или запланированные структуры в ближайшем будущем?
Пейсер
Таблицы памяти также поддерживают индексы btree
Amareswar
@ Амаресвар, верно. Возможно, мой ответ можно прочитать обоими способами, но я имел в виду, что индексы HASH разрешены только для таблиц MEMORY, а не для «обычных» таблиц.
Хавьер