time efficient key value store for fast lookup
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.