SELECT WHERE [主键] = [主键值] O(​​1)吗? [英] Is SELECT WHERE [primary key] = [primary key value] O(1)?

问题描述

是否可以期望，对于典型的现代RDBMS，通过一个特定的主键进行查询与通过键查询哈希表一样快?

Is it right to expect that, for the typical modern RDBMS, querying by one specific primary key is as fast as querying a hashtable by key?

还是进行了实际工作"来遍历表并追踪主键值?即使有主键的自动索引，这似乎也是浪费.

Or is there "actual work" done to traverse the table and track down the primary key value? That seems unthinkably wasteful, even if there are automatic indexes for primary keys.

推荐答案

数据库操作涉及对辅助存储单元(磁盘)的访问.实现效率重要的是减少块访问时间(而非操作). Select查询的复杂性取决于完成哪种优化.
因为您在键属性上提到了=，所以对文件排序所在的键属性进行了相等比较(带有

Database operation involves access of secondary memory unit (Disk). And to achieve efficiency important is to reduce block access time(not operations). Complexity of Select query depends on what kind of optimization done.
Because you mentioned = on key attribute, an equality comparison on key attribute on which the file is ordered(with a primary index), Binary Search is efficient.(which is more efficient then inner search) are used. A binary search usually access log₂(Br) block, where Br is number of block a file. (this is wrought calculation you may need to access extra block for indexes also).

这也取决于索引实现的类型.如果通过多级或B，B ⁺ 实现，则访问时间可能会进一步减少，具体取决于节点中的键数是多少(这进一步取决于一个块中可以容纳多少条记录).

It also depends on type of index implementation. If its implemented through multilevel or B, B⁺ then access time may be further reduce depends on what is number of keys in a node (that further depends how many record can be accommodate in a block).

通常，在启发式优化中，DBMS系统将MAX，MIN，AVG和其他类型的信息存储在表目录中.因此，如果可以从目录信息中得出信息，则查询执行时间可以为常数O(1).

In heuristic type of optimization generally DBMS system keeps store MAX, MIN, AVG and other kind of information in table catalogs. So if information can be derived from catalog information query execution time may be constant O(1).

阅读:第19章 查看全文