数据库查询时间复杂度

问题描述 投票:0回答:8

在现代数据库中,如果我使用索引来访问一行,这将是 O(1) 复杂度。

但是如果我执行查询来选择另一列,它会是 O(1) 还是 O(n)?

数据库是否必须遍历所有行?

或者它是否为每列构建一个排序列表?

sql database language-agnostic big-o
8个回答
40
投票

实际上,我认为基于索引的访问将是 O(log(n)),因为您仍然需要通过 B 树式组织向下搜索以获取记录。


13
投票

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

在更有趣的按多列选择的情况下,无论有索引还是没有索引,情况都会变得更加复杂:如果查询优化器选择使用索引,那么它将首先根据索引选择行,然后应用过滤器与其余的限制。从而将第二次过滤操作从 O(行数)减少到 O(按索引选择的行数)。这两个数字之间的比率称为选择性,是选择使用哪个指标时的一个重要统计数据。


4
投票

索引是按列计算的,因此如果您在未索引的列上使用 where 子句,它将执行所谓的表扫描,时间复杂度为 O(n)。


4
投票

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

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


3
投票

B 树不会产生 O(logN),即二叉树的复杂度。

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

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


0
投票

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


0
投票

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


0
投票

无索引的表,数据保存在无序结构上。当你想查找某些数据时,它会使用“扫描”来检查表格中从头到尾的所有数据。

情况1:查询没有索引的表,查询1条记录, SQL查询计划步骤:“表扫描”所有数据,O(N)

情况2:查询没有索引的表,查询很多条记录, SQL查询计划步骤:“表扫描”所有数据,O(N)

带有索引的表,数据将保存在B树结构上,当您要搜索1条数据(在索引列上)时,它将利用B树结构来查找数据。

情况3:查询有索引列的表,查询1条记录, SQL查询计划步骤:“索引查找”,O(LogN)

情况4:查询带有索引列的表,查询很多记录,

2 可能的话,SQL 查询优化器将利用“索引统计信息”来计算并确定哪个操作步骤使用起来更快。

  • (a) SQL 查询计划步骤:“索引扫描”,O(N)
  • (b) SQL 查询计划步骤: “索引查找”,O(R LogN) [R 表示记录数]
© www.soinside.com 2019 - 2024. All rights reserved.