Is the runtime of checking for duplicate primary keys in SQL Server O(n)?

I was curious and I couldn't find too much info on this. Is it also O(n) for checking for duplicates among primary keys?

Is it the same for most other SQL databases?

Is there a place that lists this info?

A primary key in SQL Server is always backed by an index (in fact, a B-tree for non-Hekaton tables). An index allows for O(log N) lookup (and duplicate checking).

In practice it's hard to measure the difference to O(1) behavior even if you aim at it. The upper index levels tend to be cached and the tree is very flat. The maximum tree level in SQL Server is 15 levels (you need to load the index pages with ~900 byte keys for that to force minimum fanout).

Each index row must be 807 bytes in size to fit at most 9 of them on a page. Then, the index size on level L is 8079^L. L starts at 1. L == 15 => 8079^15/10^12 = 166154 TB. Maximum database size: 524,272 TB. So the maximum level is 15.

StackExchange Database Administrators Q#80025, answer score: 7