在现代数据库中，如果我使用索引来访问一行，这将是 O(1) 复杂度。
但是如果我执行查询来选择另一列，它会是 O(1) 还是 O(n)？
数据库是否必须遍历所有行？
或者它是否为每列构建一个排序列表？
实际上，我认为基于索引的访问将是 O(log(n))，因为您仍然需要通过 B 树式组织向下搜索以获取记录。
要回答您的字面问题，是的，如果列上没有索引，数据库引擎将必须查看所有行。
在更有趣的按多列选择的情况下，无论有索引还是没有索引，情况都会变得更加复杂：如果查询优化器选择使用索引，那么它将首先根据索引选择行，然后应用过滤器与其余的限制。从而将第二次过滤操作从 O（行数）减少到 O（按索引选择的行数）。这两个数字之间的比率称为选择性，是选择使用哪个指标时的一个重要统计数据。
索引是按列计算的，因此如果您在未索引的列上使用 where 子句，它将执行所谓的表扫描，时间复杂度为 O(n)。
我不知道答案，但请记住，大 O 表示法只能指示任意大的数据集大小的性能。
例如，数据库性能的瓶颈通常是磁盘查找。因此，如果工作数据集可以保存在内存中，性能将大大提高。 Big-O 表示法不会告诉您有关此类优化的任何信息，因为它们仅与有限数据集相关。
B 树不会产生 O(logN)，即二叉树的复杂度。
B 树的组织方式使得每个节点都有一个完整的块，因此一旦找到一个节点，单个 I/O 操作就可以读取整个块。
每个节点的项目数 = 阻塞因子 (#records/block){bfr}，B 树优化搜索将产生 O(log bfr÷2 +1 N) I/O 操作，而不是 O(N ) 通过键查找记录的 I/O 操作。
你有索引。聚集索引在磁盘上进行物理排序，每个表只能有一个。非聚集索引是逻辑排序的，您可以拥有很多非聚集索引（也不要滥用它，它可能会减慢写入操作）。 如果您的列上没有索引，那么我相信这是很好的旧逐行方法。
不同的数据库有不同类型的索引、不同的执行计划和不同的实现。关系数据库的大部分代码都是搜索优化算法。你的问题没有单一的答案。当您想知道查询将如何执行时，您可以使用工具来可视化执行计划。
无索引的表，数据保存在无序结构上。当你想查找某些数据时，它会使用“扫描”来检查表格中从头到尾的所有数据。
情况1：查询没有索引的表，查询1条记录， SQL查询计划步骤：“表扫描”所有数据，O(N)
情况2：查询没有索引的表，查询很多条记录， SQL查询计划步骤：“表扫描”所有数据，O(N)
带有索引的表，数据将保存在B树结构上，当您要搜索1条数据（在索引列上）时，它将利用B树结构来查找数据。
情况3：查询有索引列的表，查询1条记录， SQL查询计划步骤：“索引查找”，O(LogN)
情况4：查询带有索引列的表，查询很多记录，
2 可能的话，SQL 查询优化器将利用“索引统计信息”来计算并确定哪个操作步骤使用起来更快。