Почему MySQL не имеет хеш-индексов на MyISAM или InnoDB?

У меня есть приложение, которое будет выбирать только на равенство, и я думаю, что я должен использовать хеш-индекс над индексом btree. К моему великому сожалению, хеш-индексы не поддерживаются в MyISAM или InnoDB. Что с этим?

Многие базы данных вообще не поддерживают индексы на основе хеша .

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

Таким образом, чтобы быть в целом полезным (то есть, как правило, лучше, чем альтернативный), индекс должен время от времени перестраиваться по мере роста (и сокращения) данных, что может привести к значительным периодическим издержкам. Это обычно хорошо для таблиц на основе памяти, поскольку перестройка, вероятно, будет довольно быстрой (поскольку данные всегда будут в ОЗУ и вряд ли будут большими в любом случае), но перестройка большого индекса на диске очень тяжелая операция (и IIRC mySQL не поддерживает перестроения живого индекса, поэтому удерживает блокировку таблицы во время операции).

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

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

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

http://www.postgresql.org/docs/8.1/static/indexes-types.html

Примечание. Тестирование показало, что хеш-индексы PostgreSQL работают не лучше, чем индексы B-дерева, а размер и время построения хеш-индексов намного хуже. Более того, операции с хеш-индексами в настоящее время не регистрируются в WAL, поэтому, возможно, потребуется перестроить хеш-индексы с помощью REINDEX после сбоя базы данных. По этим причинам использование хеш-индекса в настоящее время не рекомендуется. Точно так же индексы R-дерева, похоже, не имеют каких-либо преимуществ в производительности по сравнению с эквивалентными операциями индексов GiST. Как и хеш-индексы, они не регистрируются в WAL и могут нуждаться в переиндексации после сбоя базы данных. Хотя проблемы с хэш-индексами могут быть со временем устранены, вполне вероятно, что тип индекса R-дерева будет удален в будущем выпуске. Пользователям рекомендуется перенести приложения, использующие индексы R-дерева, на индексы GiST.

Опять же, это (устаревшая версия) специфичная для PostgreSQL, но она должна намекать на то, что «естественный» тип индекса не обязательно даст оптимальную производительность.

Вот кое-что интересное:

Согласно книге MySQL 5.0 Certification Study Guide , стр. 433, раздел 29.5.1

Движок MEMORY по умолчанию использует алгоритм индексации HASH.

Для смеха я попытался создать таблицу InnoDB и таблицу MyISAM с первичным ключом, используя HASH в MySQL 5.5.12.

mysql> use test
Database changed
mysql> create table rolando (num int not null, primary key (num) using hash);
Query OK, 0 rows affected (0.11 sec)

mysql> show create table rolando\G
*************************** 1. row ***************************
       Table: rolando
Create Table: CREATE TABLE `rolando` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> create table rolando2 (num int not null, primary key (num) using hash) engine=MyISAM;
Query OK, 0 rows affected (0.05 sec)

mysql> show create table rolando2\G
*************************** 1. row ***************************
       Table: rolando2
Create Table: CREATE TABLE `rolando2` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`) USING HASH
) ENGINE=MyISAM DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

MySQL не жаловался.

ОБНОВИТЬ

Плохие новости !!! Я использовал SHOW INDEXES FROM. Это говорит, что индекс BTREE.

CREATE INDEX Синтаксис MySQL Страница утверждает , что только ПАМЯТЬ и двигатели хранения NDB может вместить HASH INDEX.

mysql> show indexes from rolando;
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table   | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+---------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> show indexes from rolando2;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando2 |          0 | PRIMARY  |            1 | num         | A         |           0 |     NULL | NULL   |      | BTREE      |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

mysql> create table rolando3 (num int not null, primary key (num)) ENGINE=MEMORY;
Query OK, 0 rows affected (0.03 sec)

mysql> show create table rolando3\G
*************************** 1. row ***************************
       Table: rolando3
Create Table: CREATE TABLE `rolando3` (
  `num` int(11) NOT NULL,
  PRIMARY KEY (`num`)
) ENGINE=MEMORY DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

mysql> show indexes from rolando3;
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table    | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| rolando3 |          0 | PRIMARY  |            1 | num         | NULL      |           0 |     NULL | NULL   |      | HASH       |         |               |
+----------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

Некоторые люди предложили следовать идее на страницах 102-105 книги « Высокопроизводительный MySQL: оптимизация, резервное копирование, репликация и многое другое » для эмуляции алгоритма хеширования.

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

SELECT CONV(RIGHT(MD5('whatever value you want'),16),16,10) AS HASH64;

Создайте столбец для этого в любой таблице и индексируйте это значение.

Попробуйте!

BTree не намного медленнее, чем Hash для поиска в одной строке. Так как BTree предоставляет очень эффективные запросы диапазона, зачем беспокоиться о чем-то кроме BTree.

MySQL отлично справляется с кэшированием блоков BTree, поэтому запросы на основе BTree редко требуют ввода-вывода, что является самым большим потребителем времени в любом запросе.