mysql - 在 HASH 索引上使用 PRIMARY KEY 插入表的时间复杂度

Question

刚刚发现MEMORY表中HASH索引列的PRIMARY KEY本身就是HASH索引，如下所示:

mysql> CREATE TABLE `test_memory` (
    -> `id` int(11) NOT NULL AUTO_INCREMENT,
    -> PRIMARY KEY (`id`),
    -> KEY `id` (`id`) USING HASH
    -> ) ENGINE=MEMORY DEFAULT CHARSET=latin1;
Query OK, 0 rows affected (0.10 sec)

mysql> SHOW INDEXES FROM test_memory;
+-------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table       | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| test_memory |          0 | PRIMARY  |            1 | id          | NULL      |           0 |     NULL | NULL   |      | HASH       |         |               |
| test_memory |          1 | id       |            1 | id          | NULL      |           0 |     NULL | NULL   |      | HASH       |         |               |
+-------------+------------+----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
2 rows in set (0.00 sec)

然后我想知道:因为 PRIMARY KEY 必须检查其列中新条目的唯一性，这是否意味着插入到 test_memory 是 O(n) 时间，而不是 O(log n) 时间(在具有 BTREE PRIMARY KEY 的表的情况下？

Answer 1

哈希结构可以在 O(1) 时间内识别哈希桶中的非冲突——理论上比 b 树更快。哈希不是 O(n)，除非“n”是单个 key 中的位数(通常是指记录数)。

冲突是个问题，因为您必须测试哈希桶中的每个值。这取决于底层实现。有时，使用列表；有时是树；有时是另一种哈希级别。在任何情况下，如果您合理地假设哈希表永远不会有超过 x 个冲突，那么复杂度就是 O(x) == O(1)。

因此，哈希可以比 b 树更快。也就是说，当 B 树大于可用内存时，它们可以更好地扩展并且更易于管理。