Class InterpolationSearchStrategy

  extended by voldemort.store.readonly.InterpolationSearchStrategy
All Implemented Interfaces:

public class InterpolationSearchStrategy
extends java.lang.Object
implements SearchStrategy

A search strategy that uses interpolation to jump to approximately the correct location in the index with as few comparisons as possible. This strategy depends entirely on the uniform distribution of the keys that is guaranteed by the md5 hash.

Constructor Summary
Method Summary
 int indexOf(java.nio.ByteBuffer index, byte[] key, int indexFileSize)
          Search for the key in the buffer.
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail


public InterpolationSearchStrategy()
Method Detail


public int indexOf(java.nio.ByteBuffer index,
                   byte[] key,
                   int indexFileSize)
Description copied from interface: SearchStrategy
Search for the key in the buffer.

Specified by:
indexOf in interface SearchStrategy
index - The index buffer
key - The key to search for
indexFileSize - The size of the index
The integer offset of the position offset, if the key is found, else -1

Jay Kreps, Roshan Sumbaly, Alex Feinberg, Bhupesh Bansal, Lei Gao, Chinmay Soman, Vinoth Chandar, Zhongjie Wu