time efficient key value store for fast lookup

Question

Let's state a collection of key/values.

Key is an unsigned integer (0 - 2^32-1). Hense there are comparable. Value is few bytes fixed size.

There are 4M items in the collection. Keys are not evenly spread in the key space i.e there is no way to predict hole size between two consecutive keys.

This collection is created once and never modify after that, even if not prohibited.

The aim is to lookup a value by its key. But if key is not found then the previous one (as in integer natural order) must be returned.

I'm looking for a data-structure that can be mmap on disk which would be reasonably space efficient but most importantly very time efficient for the lookup function.

There is no known pattern on how the keys are queried.

Answer 1

Make a table with 2^22 entries to lookup the highest 22 bits of the key. Each entry is responsible for one value on average (but may contain up to 1024).

Entry #i in the table, which is responsible for 0 to 1024 values with keys from 1024i to 1024i + 1023, contains the following: 1. The number of keys in that range. 2. If there are 0 keys, the value of the next lower available key. If there is 1 key, the lower 10 bit of the key in that range, and its value. If there are two or more keys, an index j into a second table.

In the second table, we store the lower 10 bit of the key, plus the value, for every key where there are two or more keys in the range from 1024i to 1024i + 1023. For values in the second table, we use binary search.

Answer 2

Since the data structure is only created once, you can simply use an array ordered by the key. Each element in the array contains the key-value pair. Sorting the array is O(n*log(n)), which will be fast for 4e6 items and only needs to be done once. You can then use binary search (which is O(log2(n) or ~22) on the array to find the key. If not found, simply return the prior element in the array.

This will be very fast and will fit even more easily in RAM because there are no pointers. It also has the advantage of being extremely simple and easy to write. If the data needs to be persisted, you just write the array to disk, use mmap if you want, etc.

Answer 3

The minimum possible size for such any such data structure is $\log_2{ 2^{32} \choose 4\times 10^6} \approx 4.6\times10^7$ bits, or around 5.5MB.

An array of 4 million 32-bit numbers is only 15.25MB. So even relatively space-inefficient data structures should fit comfortably in RAM.

Any rank/select dictionary will work. Briefly, given a set $S$ of values, we can define the operations as:

$$\hbox{rank}(x) = \left| \{ y \in S\ : y < x\} \right|$$ $$\hbox{select}(i) = \min \{ x : \hbox{rank}(x) = i \}$$

Intuitively, $\hbox{rank}(x)$ is the number of elements in the set less than x, and $\hbox{select}(i)$ is the ith smallest element in S.

As an example of a simple implementation, if you store the set as a sorted array of integers, then select is just an array lookup, and rank can be implemented with binary search.

Given those two queries, the value that you're looking for is $\hbox{select}(\hbox{rank}(x) - 1)$. However, it should be possible to take pretty much any rank/select data structure (e.g. these ones) and implement this query directly.

You may also want to consider some variant of a van Emde Boas tree. But to be honest, a B-tree (with careful implementation of the leaf nodes) might do the job.

Answer 4

If you have only 2^32 numbers, just make a lookup table on disk. If the number of value bytes (=n) is low enough, then just copy the values for the non existent keys from the last valid one. Otherwise introduce another indirection where you link from that lookup table to our list of 4M values.

You can calculate the access point for the value exactly: key * n Bytes. Lookup speed is O(1) for existing and non existing keys.

Disk consumption is 2^32 * n Bytes for value.