sql - 数据库查询时间复杂度

Question

我对数据库很陌生，所以如果这是一个愚蠢的问题，请原谅我。

在现代数据库中，如果我使用索引来访问一行，我相信这将是 O(1) 复杂度。但是，如果我进行查询以选择另一列，它将是 O(1) 还是 O(n)？数据库是否必须遍历所有行，还是为每一列构建一个排序列表？

score 38 · Accepted Answer

实际上，我认为基于索引的访问将是 O(log(n))，因为您仍将通过 B-Tree-esque 组织向下搜索以获取您的记录。

score 13 · Accepted Answer

要回答您的字面问题，是的，如果列上没有索引，数据库引擎将不得不查看所有行。

在通过多列选择的更有趣的情况下，无论有无索引，情况变得更加复杂：如果查询优化器选择使用索引，那么它将首先根据索引选择行，然后应用过滤器剩余的约束。从而将第二次过滤操作从 O（行数）减少到 O（按索引选择的行数）。这两个数字之间的比率称为选择性，是选择使用哪个指标时的重要统计数据。

score 4 · Accepted Answer

索引是每列的，因此如果您在未索引的列上使用 where 子句，它将执行所谓的表扫描，即 O(n)。

score 4 · Accepted Answer

我不知道答案，但请记住，大 O 表示法只为您提供任意大的数据集大小的性能指示。

例如，数据库性能的瓶颈通常是磁盘寻道。因此，如果可以将工作数据集保存在内存中，性能会大大提高。Big-O 符号不会告诉您有关此类优化的任何信息，因为它们仅与有限数据集相关。

score 3 · Accepted Answer

B-trees 不会产生 O(logN)，这是二叉树的复杂度。

B-Tree 的组织方式是每个节点都有一个完整的块，因此一旦找到一个节点，单个 I/O 操作就可以读取整个块。

每个节点的项目数 = 阻塞因子 (#records/block){bfr}，B-Tree 优化搜索将产生 O(log _{bfr÷2 +1} N) I/O 操作而不是 O(N) I/ O 按键查找记录的操作。

score 0 · Accepted Answer

你有索引。聚集索引在磁盘上进行物理排序，每个表只能有一个。非聚集索引是按逻辑排序的，你可以有很多（小心不要滥用它，它可能会减慢写入操作）。如果您的列上没有索引，那么我相信这是好的旧的逐行方法。

score 0 · Accepted Answer

不同的数据库有不同类型的索引、不同的执行计划和不同的实现。关系数据库的大部分代码都在搜索优化算法中。你的问题没有一个单一的答案。当您想知道查询将如何执行时，可以使用工具来可视化执行计划。

score 0 · Accepted Answer

没有索引的表，数据保存在无序结构上。当您要搜索某些数据时，它会使用“扫描”来检查表格上从头到尾的所有数据。

案例1：无索引查询表，查询1条记录，SQL查询计划步骤：“表扫描”所有数据，O(N)

案例2：无索引查询表，查询多条记录，SQL查询计划步骤：“表扫描”所有数据，O(N)

带索引的表，数据会保存在 B-tree 结构中，当你要搜索 1 个数据（在索引列上）时，它会利用 B-tree 结构来查找数据。

案例 3：在索引列上查询表，查询 1 条记录，SQL 查询计划步骤：“index seek”，O(LogN)

案例4：查询带有索引列的表，查询多条记录，

2 可能的情况下，SQL 查询优化器将利用“索引统计”来计算并确定使用哪个操作步骤更快。

8 回答 8