Ordered Key-Value Stores deal with bytes. What database or program does not? Let's try again: bytes are exposed in an OKVS public interface. Yes, you read that correctly! When you want it, you can dive as low-level as bytes. There is even some occurrences where you need to perfect the representation of objects in the database deeper at the bit level.
Key and value
An Ordered Key-Value Store is also a key-value store. An OKVS will first and foremost associate a key with value. That is to say, if you know a key, you can retrieve the associated value. Does it ring a bell? Yes! This is called a dictionary or mapping or even associative array.
A key is unique
Like in a key-value store, Ordered Key-Value Store can only associate a key to a single value.
Keys are ordered
Unlike a hash map, an OKVS is ordered: it is a sorted container. This is the most important concept to understand, grok and remember. An immediate consequence of the ordered nature of the key space, is that given a key, it makes sense to query for the previous key or the next key given the invariant that the previous key will be smaller and the next key will be bigger.
Range and Prefix
This is an immediate consequence of the ordered nature of OKVS. It possible to retrieve all keys that are between two bytes: a range. There is a specific kind of range called prefix. A range of prefix or prefix range is all the keys that starts with a given key.
It is a generalization of the alphabetical order of the natural language dictionaries. It is the default ordering used when comparing keys that will determine their position in the key space. In an OKVS, keys and values are sequence of bytes where a byte is a positive integer at most 255. Imagine two finite byte sequences , and :
There is three cases:
If it means the sequence is made of less bytes, but it does not mean that is smaller. In a natural language dictionary, the word "zebra" is smaller in length than "elephant" but "zebra" is at the end of the dictionary, and appears after "elephant". One take away: it is not the length of a key that dictate its position in the key space. To determine the order, it is required to compare every element of the byte sequence in pairs picking one from and one from in the order they appear. If there is an index such as:
Then and have a common prefix. Then is smaller than if and only if
Packing and unpacking
A bijection, bijective function, one-to-one correspondence, or invertible function, that allows to represent basic objects e.g. string, integer, float, and composition of those inside containers e.g. tuple, list, arrays or vectors as bytes. This is also called serialization. One of the most popular textual serialization format is JSON.
Lexicographic packing is a reversible algorithm that represent objects as bytes while preserving their natural ordering. Let's consider the set of all possible objects in a program, is a totally ordered set, a function is a lexicographic packing function if it is reversible:
And if preserve the total order: