Zif*_*fre 22 sql database language-agnostic big-o
我对数据库很陌生,所以如果这是一个愚蠢的问题,请原谅我.
在现代数据库中,如果我使用索引访问行,我相信这将是O(1)复杂性.但是,如果我执行查询以选择另一列,它将是O(1)还是O(n)？数据库是否必须遍历所有行,还是为每列构建排序列表？
要回答您的文字问题,是的,如果列上没有索引,则数据库引擎必须查看所有行.
在使用和不使用索引的多列选择的更有趣的情况下,情况变得更复杂:如果查询优化器选择使用索引,那么它将首先根据索引选择行,然后应用过滤器剩下的约束.从而将第二过滤操作从O(行数)减少到O(按索引选择的行数).在选择使用哪个索引时,这两个数字之间的比率称为选择性和重要统计量.