My keys (to date) are usually floating point numbers which I format like %012.7f since these numbers will never exceed 9999.

Do you need 7 decimal places of accuracy? If your application could get by with 6, you could multiply your floats by 1e6 and store them as integers--which would probably reduce space and speed things up a lot whatever DB you use.

Yes, I do need all those decimal places sometimes. Using integers is a nice idea, though.

Yes, I do need all those decimal places sometimes.

Okay. There is always more than one way to skin a cat. Since you need 11 significant digits to store your 0 - 10,000 range with seven decimal places, and that's too big for an integer, partition the dataset.

If you split your floats into their integer and decimal parts, you can then scale the decimal part (multiply by 10e6) and the result fits easily into a 32-bit int. You can now store these packed in an array of strings of sorted packed ints:

@lookup = (
  "0000001/0000235/0002300/...", #(packed) 0.0000000 to 0.9999999
  "0000001/0004567/.../9999999", # 1.0000000 to 1.9999999
  ...
  "..."                          # 9999.0000000 to 9999.9999999
); # 10,000 elements
[download]

This requires 381MB per 100 million floats, allowing a typical 32-bit machine to store 500+ million in ram.

To lookup a range, you split the start value into its integer and scaled decimal parts and do a binary chop on the packed integers in the scalar indexed by the integer part. The initial bucket lookup subdivides the total number of floats into 10,000 sets making the binary search require best case (assuming 100 million evenly distributed data points), log2( 100e6/10e3 )=10 probes. Worst case, log2( 100e6 )=19 probes.

To put that into some perspective, it takes just over 5 seconds to locate and iterate 1 million "doubles" amongst 100 million:

C:\test>junk7 -N=100e6
min max: 1000.5 1100.5
1000103 values [1000.5 < N < 1100.5] located in 4.984375 seconds (0.00
+0005)/sec)
[download]

which is probably faster than you can locate the first one using most DBs. That average lookup time of 5 microseconds per element of the range, is remarkably consistant in my (unthorough and unscientific) testing.

C:\test>junk7 -N=100e6
min max: 1000.5 1100.5
1000103 values [1000.5 < N < 1100.5] located in 4.984375 seconds (0.00
+0005)/sec)

min max: 1 2
9999 values [1 < N < 2] located in 0.046875 seconds (0.000005)/sec)

min max: 9000.5 9000.75
2537 values [9000.5 < N < 9000.75] located in 0.011861 seconds (0.0000
+05)/sec)

min max: 9999.9 9999.9999999
965 values [9999.9 < N < 9999.9999999] located in 0.015625 seconds (0.
+000006)/sec)

min max: 9999.99999 9999.9999999

min max: 9998.99999 9998.9999999

min max: 9998.99999 9999.9999999
1 values [9998.99999 < N < 9999.9999999] located in 0.000000 seconds (
+0.000000)/sec)

min max: 0 1
9999 values [0 < N < 1] located in 0.046875 seconds (0.000005)/sec)

min max: 0.5 0.9999999
5002 values [0.5 < N < 0.9999999] located in 0.023772 seconds (0.00000
+5)/sec)

min max: 0.9 0.9999999
984 values [0.9 < N < 0.9999999] located in 0.000000 seconds (0.000000
+)/sec)

min max: 0 10000
99999990 values [0 < N < 10000] located in 519.562500 seconds (0.00000
+5)/sec)
min max: ^C
[download]

Let me know if you're interested in the POC code.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."