我正在尝试根据 Big-O 表示法理解数据库索引的性能。在不太了解它的情况下，我猜想:
- 查询主键或唯一索引将为您提供 O(1) 查找时间。
- 查询非唯一索引也将给出 O(1) 时间，尽管“1”可能比唯一索引慢 (?)
- 在没有索引的列上查询将给出 O(N) 查找时间(全表扫描)。
这通常是正确的吗？查询主键的性能会比 O(1) 更差吗？我特别关心的是 SQLite，但我也有兴趣了解不同数据库之间的差异程度。
最佳答案
大多数关系数据库将索引结构化为 B 树。
如果表有聚簇索引，数据页存储为B树的叶节点。本质上，聚簇索引变成了表。
对于没有聚簇索引的表，表的数据页存储在堆中。任何非聚集索引都是 B 树，其中 B 树的叶节点标识堆中的特定页面。
B 树的最坏情况下的高度是 O(log n)，并且由于搜索依赖于高度，B 树查找的运行方式类似于(平均而言)
O(logt n)
其中 t 是最小化因子(每个节点必须至少有 t-1 个键，最多 2*t* -1 个键(例如，2*t* 个子节点)。
我是这么理解的。
当然，不同的数据库系统可能在底层使用不同的数据结构。
当然，如果查询不使用索引，则搜索是对包含数据页的堆或 B 树的迭代。
如果使用的索引可以满足查询，搜索会更便宜一些；否则，需要一个 lookaside 来获取内存中相应的数据页。
关于sql - 数据库索引及其 Big-O 表示法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4694574/