select - SELECT WHERE [primary key] = [primary key value] O(1)？

Question

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

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

Answer 1

数据库操作涉及到二级内存单元(Disk)的访问。而实现效率重要的是减少块访问时间(而不是操作)。 Select 查询的复杂性取决于所做的优化类型。
因为你提到了=在关键属性上，对文件排序的关键属性进行相等比较(使用 primary index )，二进制搜索是有效的。(比内部搜索更有效)被使用。二分查找通常访问 log2(Br) 块，其中 Br 是文件的块数。 (这是经过计算的，您可能还需要访问额外的索引块)。

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

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

阅读:第19章Algorithms for Query Processing and Optimization