MemTable

There are some basic knowledge of skiplist structure which you need to learn before reading remaining.There is a nice blog about skiplist:

http://ticki.github.io/blog/skip-lists-done-right/

0. Implementation of SkipList

0.0. SkipList

The Node of SkipList is defined as below:

struct Node {
    Key const key;  //!< The key of K/V pair (user data)
    // the SkipList Column, next_[0] is the lowest list item
    std::atomic<Node*> next_[1];
}

0.1. InlineSkipList

The Node of InlineSkipList is defined as below:

struct Node {
    // the next_[0] is the lowest list item, next_[-1] is higher one
    // the next_+1 point to the value of key
    std::atomic<Node*> next_[0];
}

The Node of InlineSkipList are defined not very property, so you must do reinterpret_cast to access value of key.But there are two optimization while the Key are pointer in SkipList:

1. Less memory consumption for one Key pointer.
2. Less cache missing for better locality memory.

1. Implementation of MemTable

1.0. HashSkipListRep

Each bucket of the HashMap contains pointer to one SkipList (InlineSkipList in fact).

1.1. HashLinkListRep

Each bucket of HashMap contains pointer to LinkList (for smaller count) or SkipList (for bigger count).

1.2. SkipListRep

SkipListRep store K/V by single SkipList.

1.3. VectorRep

VectorRep store K/V by single vector.