36

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?

1
  • I'm no expert, but I notice that you haven't stated which database engine you're using. Unless there's anything in the standard requiring certain time complexity you can't rely on that cross implementations. The answers below all seem to assume that it's implemented in a specific way (which the standard might not require). It also goes the other way - unless the standard forbids it (which would be silly) searches for other columns could be faster as well.
    – skyking
    Commented Nov 22, 2021 at 9:43

8 Answers 8

40

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.

1
  • 11
    Except for a hash index, where it is O(bucket-chain-length) Commented Apr 7, 2009 at 21:55
13

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.

0
4

Indexes are per column, so if you use a where clause on a un-indexed column it will do a so called tablescan which is O(n).

4

I don't know the answer, but keep in mind that big-O notation only gives you an indication of performance for data-set sizes which are arbitrarily large.

For example, the bottleneck for database performance is typically disk seeks. Therefore, performance is greatly increased if the working data-set can be kept in memory. Big-O notation won't tell you anything about such optimizations, because they are only relevant for finite data-sets.

3

B-trees do not yield O(logN), that is the complexity of a binary tree.

A B-Tree is organised such that it has an entire block per node, thus once a node is found a single I/O operation can read an entire block.

With the number of items per node = blocking factor (#records/block){bfr}, a B-Tree optimized search will yield O(log bfr÷2 +1 N) I/O operations instead of O(N) I/O operations seeking a record by key.

2
  • Sorry if I ask you out of the blue, but is there a book that you could suggest me where I could find such kind of informatioin?
    – jackb
    Commented Feb 13, 2015 at 14:13
  • 12
    Keep in mind that O(log_k n) = O(log n / log k) = O(log n) for any constant k, so technically, B-Tree lookups do take O(log n) time. They are, however, a lot faster than binary trees, but only by a constant factor.
    – cfstras
    Commented Feb 25, 2015 at 15:04
0

You have indexes. Clustered indexes are physically sorted on the disk, you can have only one per table. Unclustered indexes are logically sorted and you can have many of those (careful not to abuse it either, it might slow down write actions). If there is no index on your column then I believe it's the good old row by row method.

0

There are different types of indexes, different execution plans and different implementations for different databases. Most of the code of relations database is in search-optimising algorithms. There is not a single answer to your question. You can use a tool to visualise the execution plan when you want to know how a query is going to be executed.

3
  • true, but still a good approximation (and what he's looking for) is: O(log(n)) when indexed and O(n) when not
    – Javier
    Commented Apr 7, 2009 at 22:27
  • That's true, but indexes are not always the most limiting factor in queries. In some cases you might not notice the difference between using an index or not.
    – Paco
    Commented Apr 7, 2009 at 22:49
  • @Paco : which is the best tool to visualise the execution plan?
    – Mzq
    Commented Jun 4, 2012 at 2:16
0

Table without index, data save on non-order structure. When you want to search for some data, it would use the "Scan" to go check through all the data from start till end on the table.

Case 1: query table without index, query 1 record, SQL query plan step: "table scan" all data, O(N)

Case 2: query table without index, query many records, SQL query plan step: "table scan" all data, O(N)

Table with index, data will save on B-tree structure, which when you want to search for 1 data (on the indexed column), it would make use of the B-tree structure to find the data.

Case 3: query table with on indexed column, query 1 record, SQL query plan step: "index seek", O(LogN)

Case 4: query table with on indexed column, query many record,

2 possible, the SQL Query Optimizer will made use of the "index statistics" to compute and determine which action step is faster to be use.

  • (a) SQL query plan step: "index Scan", O(N)
  • (b) SQL query plan step: "index seek", O(R LogN) [R for number of records]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.