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

Question

刚刚发现MEMORYtable中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) 时间在 table 与 BTREE PRIMARY KEY 的情况下？

Answer 1

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

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

出于这个原因，散列可以比 b 树更快。也就是说，当 B 树大于可用内存时，它们可以更好地扩展并且更易于管理。

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

Time complexity of inserting into table with PRIMARY KEY on HASH index

mysql

hash

time-complexity

unique-index