CODEWITHSUNDEEP
sqlsql-serverselectindexingtime-complexity
Alex Dlikman
Alex Dlikman

Reputation: 61

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?

Upvotes: 4

Views: 1853

Answers (3)

Joe Ratzer
Joe Ratzer

Reputation: 18549

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.

Upvotes: 3

Martin Smith
Martin Smith

Reputation: 453348

SQL Server 2014 does allow hash indexes.

For tables declared as memory optimized only.

Upvotes: 2

wilx
wilx

Reputation: 18228

IIRC, some RDBMS engines have hash table indexes. That would AFAIK give you amortized constant time as you so desire. AFAICT, MS SQL Server does not have this feature.

Upvotes: 2

Related Questions