跳表原理的简单介绍
跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。
下面来研究一下跳表的核心思想：
先从链表开始，如果是一个简单的链表，那么我们知道在链表中查找一个元素I的话，需要将整个链表遍历一次。
如果是说链表是排序的，并且节点中还存储了指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。
跳表的数据存储模型
我们定义：
如果一个基点存在k个向前的指针的话，那么陈该节点是k层的节点。
一个跳表的层MaxLevel义为跳表中所有节点中最大的层数。
下面给出一个完整的跳表的图示：
那么我们该如何将该数据结构使用二进制存储呢？通过上面的跳表的很容易设计这样的数据结构：
定义每个节点类型：
// 这里仅仅是一个指针
typedef struct nodeStructure *node;
typedef struct nodeStructure
{
keyType key; // key值
valueType value; // value值
// 向前指针数组，根据该节点层数的
// 不同指向不同大小的数组，指向的是不同层的后面节点
node forward[1];
};
我们在来看看leveldb中跳表节点的定义：
template<typename Key, class Comparator>
struct SkipList<Key,Comparator>::Node {
explicit Node(const Key& k) : key(k) { }
Key const key;
Node* Next(int n) {
return reinterpret_cast<Node*>(next_[n].Acquire_Load());
}
void SetNext(int n, Node* x) {
next_[n].Release_Store(x);
}
Node* NoBarrier_Next(int n) {
return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
}
void NoBarrier_SetNext(int n, Node* x) {
next_[n].NoBarrier_Store(x);
}
private:
port::AtomicPointer next_[];
}
总体上与我们上面所说的存储模型结构一样，只不过这里的next_用了AtomicPointer ，关于AtomicPointer 请参考前面写的博客，主要起到同步的作用。Next的函数是为了读取第n层的下一个节点，而SetNext则是设置第n层的下一个节点是谁。
再来看下leveldb跳表的定义：
class SkipList {
private:
struct Node;
private:
enum { kMaxHeight = };//跳表最高多少层
Comparator const compare_;//比较节点key大小的
Arena* const arena_; //为节点分配空间用的
Node* const head_; //指向表头
// Modified only by Insert(). Read racily by readers, but stale
// values are ok.
port::AtomicPointer max_height_; //目前跳表最高多少层
Random rnd_; //用来生成每个节点层数的随机数生成器
...
}
跳表的代码实现分析
template<typename Key, class Comparator>
SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)
: compare_(cmp),
arena_(arena),
head_(NewNode( , kMaxHeight)),//头部节点初始化为具有最高层数的节点
max_height_(reinterpret_cast<void*>()),//但当前跳表高度初始化为1，就是只有最下面一层
rnd_() {
for (int i = ; i < kMaxHeight; i++) {
head_->SetNext(i, NULL);
}
}
template<typename Key, class Comparator>
typename SkipList<Key,Comparator>::Node*
SkipList<Key,Comparator>::NewNode(const Key& key, int height) {
char* mem = arena_->AllocateAligned(
sizeof(Node) + sizeof(port::AtomicPointer) * (height - ));
//这种分配方式很有特色
return new (mem) Node(key);
}
插入操作
template<typename Key, class Comparator>
void SkipList<Key,Comparator>::Insert(const Key& key) {
Node* prev[kMaxHeight];
//从最高层往下依次寻找各层大于或等于key的节点，并把各层前一个节点保存在prev中便于插入
Node* x = FindGreaterOrEqual(key, prev);
//随机生成几点层数，RandomHeight保证不会超过跳表规定的最高层kMaxHeight
int height = RandomHeight();
if (height > GetMaxHeight()) {
//把大于原来跳表高度的层的prev节点设为头，最后更新跳表高度
for (int i = GetMaxHeight(); i < height; i++) {
prev[i] = head_;
}
max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
}
x = NewNode(key, height);
for (int i = ; i < height; i++) {
// NoBarrier_SetNext() suffices since we will add a barrier when
// we publish a pointer to "x" in prev[i].
//更新各层，将新节点插入
x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
//这里使用了内存屏障，保证了下面这条setnext一定在上面那个setnext后发生，
//想想如果后面这个先发生会发生什么，先将prev的下一个节点设为了newNode，但
//newNode此时的next为null，无法继续读后面的节点，所以一定是先修改了newNode
//的next后在把newNode插入prev。
prev[i]->SetNext(i, x);
}
｝
因为leveldb的跳表是作为memtable使用的，上层只有插入没有删除操作，因为上层的删除操作其实也就是插入操作而以，所以这里就不分析delete操作，其实原理与insert差不多。
其他操作也比较简单，就不分析了。
跳表的迭代器
class Iterator
{
public:
explicit Iterator(const SkipList* list);
bool Valid() const;
const Key& key() const; //返回迭代器所处位置节点的值
void Next();
void Prev();
void Seek(const Key& target);
void SeekToFirst();//到跳表头
void SeekToLast();//到尾
private:
const SkipList* list_;//迭代器所迭代的跳表
Node* node_;//当前迭代器所处位置的节点
}
实现也比较简单，看名字就知道啥意思了。
template<typename Key, class Comparator>
inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {
node_ = list_->FindGreaterOrEqual(target, NULL);
}
seek就是在跳表中找到第一个key大于或等于target的元素。