What is the time complexity for fetching a row from a MySQL database when searching on the primary key?

Question

I have a huge database and want fast data retrieval (search based only on the primary key). Is the time complexity for a database O(1) because it acts like a dictionary? (Since only one row will be fetched because i am doing the search only on the primary key)

Answer 1

Searching for one record in a primary key can be done in different ways, depending on what the Query Optimizer decides is most efficient. For a small table an index scan may be selected. For most tables, however, an index seek is more likely. This is a binary search.

The time complexity of a binary search is likely to be around O(log n).

Having retrieved a key from the index, getting the non-key fields of a single record will be O(1).