sqldatabaselanguage-agnosticbig-o

Database query time complexity

In modern databases, if I use an index to access a row, 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?

Solution

  • 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.