为什么 MySQL 在 MyISAM 或 InnoDB 上没有哈希索引？

Question

我有一个只选择相等的应用程序，我想我应该在 btree 索引上使用哈希索引。令我沮丧的是，MyISAM 或 InnoDB 不支持哈希索引。那是怎么回事？

Answer 1

许多数据库不支持基于散列索引可言。

为了使哈希表高效，您需要知道可能存在的行数，否则基本哈希表将太大（许多空条目，浪费空间和潜在的磁盘 IO）或太小意味着经常使用间接（可能是多级间接，或者更糟糕的是，如果哈希实现是单级的，你最终可能会在相当数量的记录上执行线性搜索）在这一点上，事情可能没有基于树的效率更高无论如何索引。

所以为了普遍有用（即通常比替代方案更好），索引需要偶尔随着数据增长（和收缩）而重建，这可能会增加大量的间歇性开销。这通常适用于基于内存的表，因为重建可能会非常快（因为数据总是在 RAM 中并且在任何情况下都不可能很大），但是在磁盘上重建大型索引是一个非常繁重的操作（并且 IIRC mySQL 不支持实时索引重建，因此在操作期间持有表锁）。

因此，在内存表中使用哈希索引，因为它们通常具有更好的性能，但基于磁盘的表不支持它们，因为它们可能会损害性能而不是奖励。当然，没有什么可以阻止哈希索引可用于基于磁盘的表，毫无疑问，某些数据库确实支持该功能，但据推测它们并未在 ISAM/InnoDB 表中实现，因为维护人员不认为该功能值得添加（因为在少数情况下，要编写和维护的额外代码不值得，因为它会产生显着差异）。也许如果您强烈反对，您可以与他们交谈并为该功能的实现提供一个很好的案例。

如果您正在索引大字符串，那么实现您自己的伪哈希索引（通过存储值的哈希值以及实际值，并索引具有列的索引）可能会起作用，但这对于大字符串（其中计算哈希值并通过该值搜索树索引总是可能比使用较大的值搜索树索引进行比较要快，并且使用的额外存储不会很重要）所以在实现之前做一些性能分析这在生产中。

Answer 2

这里有一些有趣的事情：

根据MySQL 5.0 Certification Study Guide一书，第 433 页，第 29.5.1 节

MEMORY 引擎默认使用 HASH 索引算法。

为了笑，我尝试在 MySQL 5.5.12 中使用 HASH 创建一个 InnoDB 表和一个带有主键的 MyISAM 表

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存储引擎可容纳该散列索引。

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)

有些人建议按照“高性能 MySQL：优化、备份、复制和更多”一书的第 102-105 页中的想法来模拟哈希算法。

第 105 页具有我喜欢的这种快速而肮脏的算法：

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

在任何表中为此创建一列并索引此值。

试一试 ！！！

Answer 3

在相关说明中，您可能会发现 PostgreSQL 文档中关于索引类型的讨论很有趣。它不再出现在最近版本的文档中（由于后续的优化，我接受了它），但是 MySQL 的外卖可能是相似的（以及哈希索引仅用于堆表的原因）：

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

注意：测试表明 PostgreSQL 的哈希索引的性能并不比 B 树索引好，哈希索引的索引大小和构建时间要差得多。此外，哈希索引操作目前没有 WAL 日志记录，因此在数据库崩溃后可能需要使用 REINDEX 重建哈希索引。由于这些原因，目前不鼓励使用哈希索引。同样，与 GiST 索引的等效操作相比，R 树索引似乎没有任何性能优势。与哈希索引一样，它们不是 WAL 记录的，可能需要在数据库崩溃后重新索引。虽然哈希索引的问题最终可能会得到修复，但 R-tree 索引类型很可能会在未来的版本中停用。鼓励用户将使用 R-tree 索引的应用程序迁移到 GiST 索引。

同样，它是特定于 PostgreSQL 的（过时版本），但它应该暗示“自然”索引类型不一定会产生最佳性能。