I need to be able to locate a missing element from a table with tens-of-millions of rows, and has a primary key of a BINARY(64) column (which is the input value to calculate from). These values are mostly inserted in order, but on occasion I want to reuse a previous value that was deleted. It's infeasible to modify the deleted records with a IsDeleted column, as sometimes a row is inserted that is many millions of values ahead of the currently existing rows. This means the sample data would look something like:

KeyCol : BINARY(64)
0x..000000000001
0x..000000000002
0x..FFFFFFFFFFFF

So inserting all the missing values between 0x000000000002 and 0xFFFFFFFFFFFF is infeasible, the amount of time and space used would be undesirable. Essentially, when I run the algorithm, I expect it to return 0x000000000003, which is the first opening.

I've come up with a binary-search algorithm in C#, which would query the database for each value at position i, and test if that value was expected. For context, my terrible algorithm: https://codereview.stackexchange.com/questions/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

This algorithm would run, for example, 26-27 SQL-queries on a table with 100,000,000 items. (That doesn't seem like a lot, but it's going to be occurring very frequently.) Currently, this table has approximately 50,000,000 rows in it, and performance is becoming noticeable.

My first alternative thought is to translate this to a stored-procedure, but that has it's own hurdles. (I have to write a BINARY(64) + BINARY(64) algorithm, as well as a slew of other things.) This would be painful, but not infeasible. I've also considered implementing the translation algorithm based on ROW_NUMBER, but I have a really bad gut feeling about this. (A BIGINT is not nearly big enough for these values.)

I'm up for other suggestions, as I really need this to be as quick as possible. For what it's worth the only column selected by the C# query is the KeyCol, the others are irrelevant for this portion.

Also, for what it's worth, the current query that fetches the appropriate record is along the lines of:

SELECT [KeyCol]
  FROM [Table]
  ORDER BY [KeyCol] ASC
  OFFSET <VALUE> ROWS FETCH FIRST 1 ROWS ONLY

Where <VALUE> is the index supplied by the algorithm. I also haven't had the BIGINT issue with OFFSET yet, but I will. (Only having 50,000,000 rows right now means that it never asks for an index above that value, but at some point it'll get above the BIGINT range.)

Some additional data:

• From deletions, the gap:sequential ratio is about 1:20;
• The last 35,000 rows in the table have values > BIGINT's maximum;