Search code examples
sqldatabaserdbmsdevelopment-environment

Can we access a record in SQL table using primary key in O(1) time?

I want to know that while finding a record using the primary key does RDBMS takes O(1) time or not?

Solution

  • No. In all databases that I know of, the primary key index is a B-tree index. Finding a particular element in such an index is an O(log n) operation, not O(1).

    Note that for the sizes of databases, O(log n) is pretty close to O(1). After all, the log of one billion is only about 30 (base 2).