select - SELECT WHERE [主键] = [主键值] O(1) 吗？

Question

对于典型的现代 RDBMS，通过一个特定的主键查询与通过键查询哈希表一样快，是否正确？

或者是否有“实际工作”来遍历表并追踪主键值？即使有主键的自动索引，这似乎也是不可想象的浪费。

Answer 1

数据库操作涉及辅助内存单元（磁盘）的访问。实现效率重要的是减少块访问时间（而不是操作）。Select 查询的复杂性取决于做了什么样的优化。
因为您提到=了关键属性，所以对文件排序的关键属性进行相等比较（带有主索引），使用二进制搜索是有效的。（比内部搜索更有效）被使用。二进制搜索通常访问 log ₂ (Br) 块，其中 Br 是文件的块数。（这是经过计算的，您可能还需要访问额外的索引块）。

它还取决于索引实现的类型。如果它通过多级或 B、B ⁺实现，则访问时间可能会进一步减少，这取决于节点中的键数（这进一步取决于一个块中可以容纳多少记录）。

在启发式优化中，DBMS 系统通常将 MAX、MIN、AVG 等信息保存在表目录中。因此，如果信息可以从目录信息中导出，则查询执行时间可能是常数 O(1)。

阅读：第 19 章查询处理和优化算法

Answer 2

让我们以 InnoDB 存储引擎为例。所有 InnoDB 索引都是 B 树。B 树中最坏情况的搜索复杂度为 O(log n)。但是如果一个表几乎完全适合主内存，InnoDB 可以自动构建一个哈希索引。自适应哈希索引