Временная сложность вставки в таблицу с первичным ключом индекса HASH

Question

Я только что узнал, что первичные ключи HASH индексированных столбцов в таблицах ПАМЯТИ сами индексов 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) 

I» m интересно, тогда: поскольку ПЕРВИЧНЫЕ КЛЮЧИ должны проверить уникальность новых записей в своей колонке, означает ли это, что вставка в test_memory находится в O(n) времени, а не O(log n) раз в случае таблицы с БРИТИЧЕСКИМ ПЕРВИЧНЫМ КЛЮЧОМ?

Answer 1

Хэш-структура может идентифицировать неконфликты в хэш-кодах в O (1) время - теоретически быстрее, чем b-дерево. Хэши не O (n), если только «n» не является числом бит в одном ключе (обычно это относится к числу записей).

Столкновения - проблема, потому что вы должны проверить каждое значение в хэш-ведре. Это зависит от базовой реализации. Иногда используются списки; иногда деревья; иногда другой уровень хеширования. В любом случае, если вы сделаете разумным предположение, что в хеш-таблице никогда не было больше х-коллизий, тогда сложность O (x) == O (1).

По этой причине хеши могут быть быстрее, чем b-деревья. Тем не менее, b-деревья лучше масштабируются и легче управлять, когда они больше доступной памяти.