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

Question

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

Answer

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

Accepted Answer

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

Advertisement

Answer