So you have 64-bit integer keys and 64-bit integer values, and you need to store these key-value pairs such that you get good lookups from key to list of values and from value to list of keys?
How often are you updating? What is reading from this data structure? What's the query structure?
If you're adding lots of records often, I'd go for a B+tree. There's also a trie (and a B-trie), if your keys share lots of common prefixes.
If you are making consecutive queries, then you'd do well to take advantage of what pages are in L1 and L2 cache, but if you're randomly picking things, that's less important.
What we have is 32 bit integers (or anything really) that we store using bit vectors (which are implemented as 64 bit integers).
These structures are read only. I believe that there is some work on making updatable Wavelet trees but I think that this would be very expensive.
Reads are primarily Seeks (maybe 70%) I think, but Access is also important - so the order must also be encoded.
Storing keys and values is expensive in terms of memory (storing everything twice) so what we are trying to do is to manipulate the data such that we can do these operations quickly while using the minimum number of bits.
How often are you updating? What is reading from this data structure? What's the query structure?
If you're adding lots of records often, I'd go for a B+tree. There's also a trie (and a B-trie), if your keys share lots of common prefixes.
If you are making consecutive queries, then you'd do well to take advantage of what pages are in L1 and L2 cache, but if you're randomly picking things, that's less important.