Level DB --- SkipList

class SkipList

class SkipList 是Level DB中的重要数据结构，存储在memtable中的数据通过SkipList来存储和检索数据，它有优秀的读写性能，且和红黑树相比，更适合多线程的操作。

SkipList 

SkipList还是一个比较简单的数据结构，它首先是一个List（链表），读写操作也和List相差不大。SkipList的复杂之处是每一个Node有一个高度的信息，带有这个高度信息的Node，可以看成一个Node Array [Height]，其中的Height小于或等于SkipList 的 Max Height，如图1所示。

                                                           图1. Max Height = 4 's SkipList

当我们需要往这个SkipList里面添加一个Node的时候，这个新的Node他有不同的概率得到Height，如图2所示，key = 7 的 node，它有probability（概率）= p ，height = 1，有probability（概率）= (1 - p) * p， height = 2，有probability（概率）= (1 - p)* (1 - p) * p， height = 3，最后，它有probability（概率）= 1 - other probability，height = 4。

图2. Max Height = 4 's SkipList insert key = 7

Level DB 中的实现

Level DB中实现了class SkipList，下面来梳理总结一下这个SkipList的一些特点。

原子操作

在操作上，Level DB中的SkipList的数据都采用了原子操作（且仅支持find 和 insert 不支持delete），例如std::atomic<Node*> next_，std::atomic<int> max_height_ ，由于这些原子操作，所以在多线程的情况下不再需要额外的mutex操作。

memory order

对于原子操作，memory order 是在多核处理器上，每一个CPU看到的不同的上下文的表征。在SkipList里面对于单纯的原子互斥操作使用了std::memory_order_relaxed。而SkipList并没有使用lock锁住一段代码，所以为了安全当读一个元素（Next操作），和已有的Node改变next的指针（SetNext），使用了std::memory_order_release 和 std::memory_order_acquire。也就是在读的时候要考虑到写的前序上下文都已经完成。