  In-memory data management systems, such as key-value stores, have become an
essential infrastructure in today's big-data processing and cloud computing.
They rely on efficient index structures to access data. While unordered
indexes, such as hash tables, can perform point search with O(1) time, they
cannot be used in many scenarios where range queries must be supported. Many
ordered indexes, such as B+ tree and skip list, have a O(log N) lookup cost,
where N is number of keys in an index. For an ordered index hosting billions of
keys, it may take more than 30 key-comparisons in a lookup, which is an order
of magnitude more expensive than that on a hash table. With availability of
large memory and fast network in today's data centers, this O(log N) time is
taking a heavy toll on applications that rely on ordered indexes.
  In this paper we introduce a new ordered index structure, named Wormhole,
that takes O(log L) worst-case time for looking up a key with a length of L.
The low cost is achieved by simultaneously leveraging strengths of three
indexing structures, namely hash table, prefix tree, and B+ tree, to
orchestrate a single fast ordered index. Wormhole's range operations can be
performed by a linear scan of a list after an initial lookup. This improvement
of access efficiency does not come at a price of compromised space efficiency.
Instead, Wormhole's index space is comparable to those of B+ tree and skip
list. Experiment results show that Wormhole outperforms skip list, B+ tree,
ART, and Masstree by up to 8.4x, 4.9x, 4.3x, and 6.6x in terms of key lookup
throughput, respectively.
