3

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?

Alex Dlikman
  • 51
  • 5
  • 1
    Big-O on a sql select? – Joe Ratzer Dec 09 '13 at 12:10
  • possible duplicate of [SQL Server Hash Indexes](http://stackoverflow.com/questions/318219/sql-server-hash-indexes) – wilx Dec 09 '13 at 12:16
  • @wilx That "duplicate" is based on a misunderstanding that the `CHECKSUM` function creates a hash index (it doesn't) and is from 2008. The next version of SQL Server (Or current version for early adopters such as this very site) *does* support hash indexes. – Martin Smith Feb 28 '14 at 14:22

3 Answers3

2

A clustered primary key is organised as a b-tree.

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

I believe b-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?

Joe Ratzer
  • 18,176
  • 3
  • 37
  • 51
  • 1
    It seems like there should be a way to search by id (primary key) in O(1) time. At least when all the table fields of fixed number of bytes. It would essentially be function the same as an array, simply calculating `address + offset` to directly `load` the row. No indexes (tree or hash-based) needed. – ZMitton Mar 21 '20 at 18:38
1

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.

wilx
  • 17,697
  • 6
  • 59
  • 114
1

SQL Server 2014 does allow hash indexes.

For tables declared as memory optimized only.

Martin Smith
  • 438,706
  • 87
  • 741
  • 845