Database query time complexity

Question

I'm pretty new to databases, so forgive me if this is a silly question.

In modern databases, if I use an index to access a row, I believe this will be O(1) complexity. But if I do a query to select another column, will it be O(1) or O(n)? Does the database have to iterate through all the rows, or does it build a sorted list for each column?

Answer 1

Actually, I think access based on an index will be O(log(n)), because you'll still be searching down through a B-Tree-esque organization to get to your record.

Answer 2

To answer your literal question, yes if there is no index on a column, the database engine will have to look at all rows.

In the more interesting case of selecting by multiple columns, both with and without index, the situation becomes more complex: If the Query Optimizer chooses to use the index, then it'll first select rows based on the index and then apply a filter with the remaining constraints. Thus reducing the second filtering operation from O(number of rows) to O(number of selected rows by index). The ratio between these two number is called selectivity and an important statistic when choosing which index to use.