从 SQL 表中选择 O(1)

Question

我正在寻找通过 O(1) 运行选择查询的方法。
我可以通过主键 SELECT 的方式创建索引，时间复杂度为 O(1) 吗？

Answer 1

聚集主键在 SQL Server 中被组织为 b+ 树。

聚集键不是基于哈希的索引，这是O(1)所必需的。

我相信树搜索是 O(log n)。

所以不，你不能

这样创建索引，通过主键进行SELECT将花费O(1) 时间复杂度

毫无价值的是，虽然基于哈希的索引可以更快地进行基于相等的查找，但它们不如树索引灵活。

例如，树算法允许范围运算符。此外，树算法应该能够更快地维护、增长和缩小。

Answer 2

IIRC，一些 RDBMS 引擎具有哈希表索引。 AFAIK 会给你摊销 如您所愿的恒定时间。 AFAICT，MS SQL Server 没有此功能。

Answer 3

SQL Server 2014 确实允许哈希索引。

仅适用于声明为内存优化的表。