I need to be able to locate a missing element from an *obscenely large* table. The table in question has 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 performant 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.