What is the best way to index lookups on a 2D array of integers that is boundless in x and y?

Question

Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer).

What is the best way to index these points in order to have an optimised lookup on an arbitrary (x,y) coordinate? Is an O(1) lookup solution possible?

Answer 1

You could have a table with 3 columns: XCoord, YCoord, and Value. The PK would be on XCoord and YCoord which would give lookups as fast as possible. Also, since it is the PK there would only be one read: no need to look up the index and then go read the data page: the index is the data page.

I'm not sure how you calculate an O number for SQL lookups, but if you keep the index stats up to date and defrag it regularly, this is as close to O(1) as you're going to get.