数据库索引及其Big-O符号表示法

Question

40

我试图理解数据库索引在大O符号表示法方面的性能。在不了解太多的情况下，我猜测：

这个概括正确吗？在主键上查询会比O（1）的性能更差吗？我的具体关注点是SQLite，但我很想知道这在不同数据库之间的差异程度。

- Michael Low

6个回答

11

索引查询（无论是否唯一）通常是O（log n）。简单地说，您可以将其视为在排序数组中执行二进制搜索类似。更准确地说，这取决于索引类型。但是，例如B树搜索仍然是O（log n）。

如果没有索引，则确实为O（N）。

- Mark Wilkins

5

如果你选择搜索相同的列，那么：

- 主键或唯一键的搜索复杂度是O(log n)：它是一种b-tree搜索 - 非唯一索引的搜索复杂度也是O(log n) + 一点点：它是一种b-tree搜索 - 没有索引 = O(N)

如果你需要来自另一个“源”（索引交集、书签/键查找等）的信息，因为索引不是覆盖的，那么由于多个索引命中和中间排序，可能会出现O(n+log n)或O(log n+log n+log n)的情况。

如果统计数据显示你需要高比例的行（例如非常不可选择的索引），那么索引可能会被忽略并变成扫描= O(n)。

- gbn

4

其他答案已经给出了一个很好的起点；但我想补充的是，要达到O(1)，主索引本身需要基于哈希（这通常不是默认选择）；因此更常见的是对数时间复杂度（B树）。

您说的二级索引通常具有相同的复杂度，但实际性能更差--这是因为索引和数据没有聚集在一起，所以常数（磁盘寻道次数）更大。

- StaxMan

3

这取决于您的查询是什么。

由于您主要关注SQLite，您可能需要阅读其查询优化器概述，其中更详细地解释了如何选择索引。

- dan04

1

这是一个很好的问题。它值得写一本书！这里有三个主要因素：

通常情况下，O(1)的复杂度适用于哈希索引和数据库引擎缓存中的数据。大多数数据库引擎默认使用B-Tree索引，聚集索引也不例外。因此，当按主键搜索时，您应该预期复杂度为O(log N)。

在这篇好文章中，您可以找到更多关于内部运作的细节：

- Johnny Svarog

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicholas Carey · Accepted Answer

大多数关系型数据库将索引构造为B-trees（即B树）。

如果一个表有聚集索引，那么数据页将作为B-tree的叶节点存储。实际上，聚集索引就成了整个表。

对于没有聚集索引的表，表中的数据页将按堆积方式存储。任何非聚集索引都是B-trees，其中B-tree的叶节点标识着堆积中的特定页面。

B-tree的最坏情况高度为O(log n)，由于搜索取决于高度，因此B-tree查找大体上运行在

O(log_t n)

的时间复杂度，其中t是最小化因子(每个节点必须至少有t-1个键，最多有2*t* -1个键(例如2*t*个子节点)。

这是我理解的方式。

当然，不同的数据库系统可能会使用不同的数据结构。

如果查询不使用索引，则搜索是迭代遍历包含数据页的堆或B-tree。

如果使用的索引可以满足查询条件，则搜索会更快；否则，需要查找相应的数据页以从内存中获取数据。