dm vdo: implement the delta index

The delta index is a space and memory efficient alternative to a hashtable.
Instead of storing the entire key for each entry, the entries are sorted by
key and only the difference between adjacent keys (the delta) is stored.
If the keys are evenly distributed, the size of the deltas follows an
exponential distribution, and the deltas can use a Huffman code to take up
even less space.

This structure allows the index to use many fewer bytes per entry than a
traditional hash table, but it is slightly more expensive to look up
entries, because a request must read and sum every entry in a list of
deltas in order to find a given record. The delta index reduces this lookup
cost by splitting its key space into many sub-lists, each starting at a
fixed key value, so that each individual list is short.

Co-developed-by: J. corwin Coburn <[email protected]>
Signed-off-by: J. corwin Coburn <[email protected]>
Co-developed-by: Michael Sclafani <[email protected]>
Signed-off-by: Michael Sclafani <[email protected]>
Co-developed-by: Thomas Jaskiewicz <[email protected]>
Signed-off-by: Thomas Jaskiewicz <[email protected]>
Signed-off-by: Matthew Sakai <[email protected]>
Signed-off-by: Mike Snitzer <[email protected]>

0 files changed, 0 insertions, 0 deletions