Por que o MySQL não possui índices de hash no MyISAM ou InnoDB?

Eu tenho um aplicativo que selecionará apenas igualdade e acho que devo usar um índice de hash sobre um índice de btree. Para minha surpresa, os índices de hash não são suportados no MyISAM ou InnoDB. O que há com isso?

Muitos bancos de dados não suportam índices com base de hash em tudo .

Para que uma tabela de hash seja eficiente, você precisa saber o número de linhas que provavelmente estarão presentes, caso contrário, a tabela de hash base será muito grande (muitas entradas vazias, desperdiçando espaço e potencialmente E / S de disco) ou muito pequena, o que significa que a indireção é frequentemente usada (possivelmente vários níveis de indireção, ou pior ainda, se a implementação do hash for de nível único, você pode acabar realizando uma pesquisa linear em um número razoável de registros); nesse ponto, as coisas provavelmente não são mais eficientes do que uma árvore baseada índice de qualquer maneira.

Portanto, para ser geralmente útil (ou seja, geralmente melhor que a alternativa), o índice precisa ser reconstruído ocasionalmente à medida que os dados aumentam (e diminuem), o que poderia adicionar uma sobrecarga intermitente significativa. Isso geralmente é bom com tabelas baseadas em memória, pois a reconstrução provavelmente será muito rápida (como os dados sempre estarão na RAM e provavelmente não serão enormes em qualquer caso), mas a reconstrução de um grande índice no disco é uma operação muito pesada (e o IIRC mySQL não suporta reconstruções de índice ao vivo, portanto mantém um bloqueio de tabela durante a operação).

Portanto, os índices de hash são usados ​​nas tabelas de memória, pois geralmente apresentam melhores desempenhos, mas as tabelas baseadas em disco não as suportam, pois podem prejudicar o desempenho e não um bônus. Não há nada a índices hash deixar de ser disponibilizado para tabelas baseadas em disco, é claro, sem dúvida alguns bancos de dados fazem suporta o recurso, mas provavelmente eles não são implementados em ISAM / tabelas InnoDB como os mantenedores não consideram o valor recurso adicionando (como o código extra para escrever e manter não vale o benefício nessas poucas circunstâncias em que faz uma diferença significativa). Talvez, se você discordar, possa conversar com eles e defender a implementação do recurso.

Se você estiver indexando cadeias grandes, a implementação de seu próprio índice pseudo-hash (armazenando uma mistura do valor e do valor real e a indexação que possui coluna) pode funcionar, mas isso é definitivamente mais eficiente para cadeias grandes (onde calcular o valor do hash e pesquisar no índice da árvore por esse valor sempre será mais rápido do que apenas pesquisar no índice da árvore usando os valores maiores para comparação e o armazenamento extra usado não será significativo); faça algumas análises de desempenho antes de implementar isso em produção.

Em uma nota relacionada, você pode achar interessante a discussão sobre tipos de índice nos documentos do PostgreSQL. Ele não está mais presente nas versões recentes dos documentos (devido a otimizações subseqüentes, pelo menos), mas a solução pode ser semelhante para o MySQL (e a razão pela qual os índices de hash são usados ​​apenas para tabelas de heap):

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

Nota: O teste mostrou que os índices de hash do PostgreSQL não apresentam desempenho melhor que os índices da árvore B, e o tamanho do índice e o tempo de construção dos índices de hash são muito piores. Além disso, as operações de índice de hash não estão atualmente registradas no WAL, portanto, os índices de hash podem precisar ser reconstruídos com o REINDEX após uma falha no banco de dados. Por esses motivos, o uso do índice de hash é atualmente desencorajado. Da mesma forma, os índices da árvore R não parecem ter vantagens de desempenho em comparação com as operações equivalentes dos índices GiST. Como índices de hash, eles não são registrados no WAL e podem precisar ser reindexados após uma falha no banco de dados. Embora os problemas com os índices de hash possam ser corrigidos eventualmente, é provável que o tipo de índice da árvore R seja retirado em uma versão futura. Os usuários são incentivados a migrar aplicativos que usam índices da árvore R para índices do GiST.

Novamente, é (versão obsoleta) específica do PostgreSQL, mas deve sugerir que o tipo de índice "natural" não necessariamente trará desempenho ideal.

Aqui está algo interessante:

De acordo com o livro Guia de Estudo da Certificação MySQL 5.0 , Página 433, Seção 29.5.1

O mecanismo MEMORY usa o HASH por algoritmo de indexação padrão.

Para rir, tentei criar uma tabela InnoDB e uma tabela MyISAM com uma chave primária usando HASH no 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)

O MySQL não reclamou.

ATUALIZAR

Más notícias !!! Eu usei SHOW INDEXES FROM. Diz que o índice é BTREE.

A página MySQL da sintaxe CREATE INDEX afirma que apenas os mecanismos de armazenamento MEMORY e NDB podem acomodar o 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)

Algumas pessoas sugeriram seguir a idéia nas páginas 102-105 do livro " MySQL de alto desempenho: otimizações, backups, replicação e muito mais " para emular o algoritmo de hash.

A página 105 apresenta esse algoritmo rápido e sujo que eu gosto:

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

Crie uma coluna para isso em qualquer tabela e indexe esse valor.

De uma chance !!!

O BTree não é muito mais lento que o Hash para pesquisa de linha única. Como o BTree fornece consultas de intervalo muito eficientes, por que se preocupar com algo que não seja o BTree?

O MySQL faz um trabalho muito bom de armazenar em cache os blocos BTree, portanto, uma consulta baseada em BTree raramente precisa fazer E / S, que é o maior consumidor de tempo em qualquer consulta.