sqlsql-serverselectindexingtime-complexity

Select by O(1) from SQL table

I looking for way to run select query by O(1).
Can I create index in this way that SELECT by primary key will take O (1) time complexity?

Solution

  • A clustered primary key is organized as a b+ tree in SQL Server.

    The clustered key is not a hash-based index, which is required for O(1).

    I believe tree searches are O(log n).

    So no, you can't

    create an index in this way that SELECT by primary key will take O (1) time complexity

    It is worth nothing that while a hash-based index would be quicker to do a look-up based on equality, they are less flexible than tree indexes.

    For example, tree algorithms allow range operators. Also, a tree algorithm should be quicker to maintain, grow, and shrink.