我试图用Big-O表示法来理解数据库索引的性能。如果不了解它，我会猜测：
这通常是正确的吗？查询主键给予性能会比O（1）更差吗？我特别关注SQLite，但我也想知道不同数据库之间的差异程度。
bq9c1y661#
大多数关系数据库将索引构造为B树。如果数据表有丛集索引，数据页面会储存为B型树状目录的分叶节点。实质上，丛集索引会变成数据表。对于没有聚簇索引的表，表的数据页存储在堆中。任何非聚簇索引都是B树，其中B树的叶节点标识堆中的特定页。最坏情况下B树的高度是O（log n），由于搜索依赖于高度，B树查找的运行时间如下（平均）时间复杂度O（logt n）其中t是最小化因子（每个节点必须具有至少 t-1个关键字和至多2t -1个关键字（例如，2t 个子节点））。我是这么理解的。当然，不同的数据库系统可能会使用不同的数据结构。当然，如果查询不使用索引，那么搜索就是对包含数据页的堆或B树的迭代。如果所使用的索引能够满足查询，则搜索成本会低一些;否则，需要旁视来获取存储器中的相应数据页。
v7pvogib2#
在一个简单的例子中，你可以把它看作是一个排序数组中的二分搜索，更准确地说，它取决于索引类型，但是一个b树搜索仍然是O（log n）。如果没有索引，那么，是的，它是O（N）。
epfja78i3#
如果选择要搜索的相同列，则
如果你需要从另一个“源”（索引交集，书签/键查找等）的信息，因为索引是非覆盖的，那么你可能有O（n + log n）或O（log n + log n + log n），因为多个索引命中+中间排序。如果统计数据显示您需要高百分比的行（例如不是非常有选择性的索引），那么索引可以被忽略，成为一个扫描= O（n）
js5cn81o4#
其他的答案给予了一个很好的起点;但是我只想补充一点，要得到O（1），主索引本身需要是基于哈希的（这通常不是默认的选择）;因此更常见是对数树（B树）。您是正确的，因为辅助索引通常具有相同的复杂性，但实际性能更差--这是因为索引和数据没有聚集，所以常数（磁盘寻道次数）更大。
hujrc8aj5#
这取决于您的查询是什么。
Column = Value
<
>
<=
>=
由于您主要对SQLite感兴趣，因此可能希望阅读它的Query Optimizer Overview，它更详细地解释了如何选择索引。
rxztt3cl6#
这是一个很好的问题。它值得一本书来写！这里有三个主要的东西
大多数数据库引擎默认使用B树索引，聚簇索引也不例外，这就是为什么当按主键搜索时，你应该预期复杂度为O（log N）。在this nice article中，您可以找到更多关于引擎盖下发生的事情的详细信息：
6条答案
按热度按时间bq9c1y661#
大多数关系数据库将索引构造为B树。
如果数据表有丛集索引，数据页面会储存为B型树状目录的分叶节点。实质上，丛集索引会变成数据表。
对于没有聚簇索引的表，表的数据页存储在堆中。任何非聚簇索引都是B树，其中B树的叶节点标识堆中的特定页。
最坏情况下B树的高度是O（log n），由于搜索依赖于高度，B树查找的运行时间如下（平均）
时间复杂度O（logt n）
其中t是最小化因子（每个节点必须具有至少 t-1个关键字和至多2t -1个关键字（例如，2t 个子节点））。
我是这么理解的。
当然，不同的数据库系统可能会使用不同的数据结构。
当然，如果查询不使用索引，那么搜索就是对包含数据页的堆或B树的迭代。
如果所使用的索引能够满足查询，则搜索成本会低一些;否则，需要旁视来获取存储器中的相应数据页。
v7pvogib2#
在一个简单的例子中，你可以把它看作是一个排序数组中的二分搜索，更准确地说，它取决于索引类型，但是一个b树搜索仍然是O（log n）。
如果没有索引，那么，是的，它是O（N）。
epfja78i3#
如果选择要搜索的相同列，则
如果你需要从另一个“源”（索引交集，书签/键查找等）的信息，因为索引是非覆盖的，那么你可能有O（n + log n）或O（log n + log n + log n），因为多个索引命中+中间排序。
如果统计数据显示您需要高百分比的行（例如不是非常有选择性的索引），那么索引可以被忽略，成为一个扫描= O（n）
js5cn81o4#
其他的答案给予了一个很好的起点;但是我只想补充一点，要得到O（1），主索引本身需要是基于哈希的（这通常不是默认的选择）;因此更常见是对数树（B树）。
您是正确的，因为辅助索引通常具有相同的复杂性，但实际性能更差--这是因为索引和数据没有聚集，所以常数（磁盘寻道次数）更大。
hujrc8aj5#
这取决于您的查询是什么。
Column = Value形式的条件允许使用基于散列的索引，其查找时间为O（1）。然而，许多数据库，包括SQLite，不支持它们。<，>，<=，>=）的条件可以利用有序索引，通常用二叉树实现，其具有O（log n）查找时间。由于您主要对SQLite感兴趣，因此可能希望阅读它的Query Optimizer Overview，它更详细地解释了如何选择索引。
rxztt3cl6#
这是一个很好的问题。它值得一本书来写！这里有三个主要的东西
**一般而言，O（1）**的复杂度适用于 * 散列索引 * 和数据库引擎该高速缓存中的数据。
大多数数据库引擎默认使用B树索引，聚簇索引也不例外，这就是为什么当按主键搜索时，你应该预期复杂度为O（log N）。
在this nice article中，您可以找到更多关于引擎盖下发生的事情的详细信息：