SELECT WHERE [主键] = [主键值] O（1）？

对于典型的现代关系型数据库管理系统，通过一个特定的主键进行查询的速度与通过关键字查询哈希表一样快是否正确？SELECT WHERE [主键] = [主键值] O（1）？

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

2013-03-31 S. Valmont

它应该很快，但不一定是O（1）。许多数据库索引是树结构，而不是哈希表。 – Barmar

听起来像你正在考虑通过主键上的自动索引进行树搜索。这将是O（log n）。这会令人失望。没有什么个人，但我希望你错了！ –

阅读[第19章]（http://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC8QFjAA&url=http%3A%2F%2Fwww.aabu.edu .jo％2Ftool％2Fcourse_file％2Flec_notes％2F901331_Fundamentals_of_Database_Systems％2C_6th_Edition_％280136086209％29.pdf＆EI = Lj9ZUaHoEIjmrAeHn4C4CQ＆USG = AFQjCNGr81mTvpcjSnSPei0hWXIAsJCOfQ＆BVM = bv.44442042，d.bmk）算法查询处理和优化 –

数据库操作涉及访问辅助内存单元（磁盘）。而实现效率的重要是减少块访问时间（而不是操作）。 Select查询的复杂性取决于完成的优化类型。
由于您在关键属性上提到了=，因此对文件排序的关键属性（与primary index）进行了相等比较，二进制搜索是有效的（这比内搜索更有效）。二进制搜索通常访问日志_{（Br）块，其中Br是块文件的编号。（这是锻造计算，您可能还需要访问额外的索引块）。}

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

在启发式优化中，通常DBMS系统会在表格目录中存储MAX，MIN，AVG和其他类型的信息。所以如果可以从目录信息派生信息查询执行时间可能是恒定的O（1）。

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

来源

2013-03-31 09:13:52

实际上可以在读取数据库访问结构，存储结构和查询优化后进行回答。 –

让我们InnoDB存储引擎。所有的InnoDB索引都是B树。 B树中最坏情况下的搜索复杂度为O（log n）。但是，如果一张表几乎完全适合主内存，InnoDB可以自动构建一个散列索引。 Adaptive Hash Indexes

来源

2013-03-31 09:18:53

SELECT WHERE [主键] = [主键值] O（​​1）？

回答

相关问题

SELECT WHERE [主键] = [主键值] O（1）？