O（1）是否可以访问数据库行？

Question

我有一个使用自动增量字段（ID）作为主键的表。该表只附加，不会删除行。表格被设计为具有恒定的行大小。因此，我期望O（1）访问时间使用任何值作为ID，因为很容易计算在文件中查找的确切位置（ID * row_size），但不幸的是情况并非如此。

我使用的SQL Server。
它甚至有可能吗？

由于

Answer 1

我想这对你很重要的事情是性能。 数据库使用索引来访问写在磁盘上的记录。

通常这与B +树索引，它们是登录完成 _b n其中b对于内部节点通常是100和200之间（优化块大小，见ref）

这仍然严格地说对数性能，但是如果记录数量相当多，比如说有几百万，那么叶节点可以在3到4个步骤内完成，并且还有查询计划，会话启动，锁定等所有开销（反正你会如果你需要多用户，符合ACID标准的数据管理系统）肯定是出于所有可以与恒定时间相比的实际原因。

Answer 2

因此，我期望具有O（1）访问使用任何值作为ID 时间，因为它是 容易计算精确的位置，以寻求在文件 （ID * row_size）

啊。不。自动增量不 - 即使没有删除 - 保证没有漏洞。孔=通过索引查找。 Ergo：你的假设是错误的。

Answer 3

好消息是，一个索引读取是O（日志（N）），其对于n值很大变得相当接近O（1）。这就是说，在这种情况下，O符号不是很有用，实际的时间安排更加平庸。

Answer 4

即使它是可以直接解决行，查询仍然要经过客户端和服务器协议栈，并开展各种查询和内存分配才可以给你想要的结果。看起来你正在期待一些甚至不实际的事情。这里真正的问题是什么？ SQL Server对你来说不够快吗？如果是这样，你可以使用许多选项来提高性能，但直接在文件中寻找地址不是其中的一个。

Answer 5

不可能的。 SQL Server根据键值和索引值将数据组织成树状结构;数据库意义上的“索引”更像是参考书的索引，而不像数组或列表等索引数据结构。充其量，在搜索索引值时可以获得对数性能（PK通常被视为索引）。最坏情况是对非索引列的表扫描，它是线性的。在数据库变得非常大之前，针对精心设计的表进行精心设计的查询的查找时间与通过网络或甚至命名管道发送它所需的时间相比将变得苍白。