y initialized // version of the returned Node. return reinterpret_cast
(next_[n].Acquire_Load()); } //重设n层的next指针 void SetNext(int n, Node* x) { assert(n >= 0); // Use a 'release store' so that anybody who reads through this // pointer observes a fully initialized version of the inserted node. next_[n].Release_Store(x); } // No-barrier variants that can be safely used in a few locations. Node* NoBarrier_Next(int n) { assert(n >= 0); return reinterpret_cast
(next_[n].NoBarrier_Load()); } void NoBarrier_SetNext(int n, Node* x) { assert(n >= 0); next_[n].NoBarrier_Store(x); } private: // Array of length equal to the node height. next_[0] is lowest level link. // 本节点的n层后向的指针 port::AtomicPointer next_[1]; };
在memtable的实现中，我们看到skiplist的实例化版本是SkipList
template
typename SkipList
::Node* SkipList
::NewNode(const Key& key, int height) { char* mem = arena_->AllocateAligned( sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1)); return new (mem) Node(key); }
很多人可能之前就奇怪为什么每个节点的n层后向指针却是next_[1]，只有一个成员？因为节点的高度需要由一个随机算子产生，也就是说height对于每个节点是无法提前预知的，自然也就不能在node定义中确定next数组的大小，那么如何保证next数组足够用呢？newnode为我们展现了这样的一种奇技淫巧，实际上新节点在确定height后，向内存申请空间时，申请了一块sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1)大小的空间，确保next指针的空间足够，并用placement new为新node指定空间。
结构已经铺垫好，接下来我们就看看skiplist成员函数的实现吧。
//寻找关键字大于等于key值的最近节点，指针数组prev保存此节点每一层上访问的前一个节点。 template
typename SkipList
::Node* SkipList
::FindGreaterOrEqual(const Key& key, Node** prev) const { Node* x = head_; //首先获得跳表的最高层数，减一是数组next最大下标 int level = GetMaxHeight() - 1; //查找操作开始 while (true) { //跳表可以看成多层的链表，层数越高，链表的节点数越少，查找也就从高层数的链表开始 //如果key在本节点node之后，继续前进 //若果小于本节点node，把本节点的level层上的前节点指针记录进数组prev中，并跳向第一层的链表 //重复上述过程，直至来到最底层 Node* next = x->Next(level); if (KeyIsAfterNode(key, next)) { // Keep searching in this list x = next; } else { if (prev != NULL) prev[level] = x; if (level == 0) { return next; } else { // Switch to next list level--; } } } }
跳表实际上是类似一种多层的有序链表，高层的链表比底层的链表节点更少，在更高层的链表上能更快的遍历完整个链表，跳到更底层的链表更利于精确的定位，以上便是skiplist利用空间换取时间的方法精髓。想首先从跳表头结点的最高层开始遍历，key值大于节点key值，则前往同一层的下一个节点，否则跳到节点的低一层并记录上一层的最后访问的节点，直到来到第一层（最底层）。以下其他操作的分析均源于此。贴一张跳表的示意图，帮助理解
类似的函数还有FindLessThan，FindLast，大家自己理解理解。
其实FindGreaterOrEqual函数返回的前向节点指针数组是为了向跳表插入节点时用的，想想链表的插入操作，insert一个key时，首先新建一个node(key)，把node->next指向prev-next，再把prev->next指向node。跳表也是，只不过需要操作多个链表。skiplist::insert函数如下：
template
void SkipList
::Insert(const Key& key) { // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual() // here since Insert() is externally synchronized. Node* prev[kMaxHeight]; Node* x = FindGreaterOrEqual(key, prev); // Our data structure does not allow duplicate insertion assert(x == NULL || !Equal(key, x->key)); int height = RandomHeight(); if (height > GetMaxHeight()) { for (int i = GetMaxHeight(); i < height; i++) { prev[i] = head_; } max_height_.NoBarrier_Store(reinterpret_cast
(height)); } x = NewNode(key, height); for (int i = 0; i < height; i++) { x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i)); prev[i]->SetNext(i, x); } }
总结
好了，看了leveldb的skiplist和memtable，确实受益匪浅，不仅学习了skiplist的实现和memtable的封装，还认识了内存屏障以及如何在C++中插入汇编语句。但我觉得看leveldb最重要的还是学习人家的设计思路，说到底其实跳表的实现并不难，抛开性能上的差距，也许我也能实现，但如何真正做到面向对象，如何理解需求和设计出最简明的结构，如何让你的代码层次清楚，一目了然，这真的是一门大智慧。