leveldb中的memtable只是一个封装类，它的底层实现是一个跳表。跳表是一种基于随机数的平衡数据结构，其他的平衡数据结构还有红黑树、AVL树，但跳表的原理比它们简单很多。跳表有点像链表，只不过每个节点是多层结构，通过在每个节点中增加向前的指针提高查找效率。如下图:
在/leveldb/db文件夹下有跳表的实现skiplist.h和跳表的测试程序skiplist_test.cc。
template
class SkipList {
可以看出leveldb的skiplist是一个模板类，key是跳表每个节点存储的信息类，跳表是一个顺序结构，comparator是跳表key的比较器。
成员变量：
private: //设定的跳表最大层数，新增节点的随机层数不能大于此值 enum { kMaxHeight = 12 }; // Immutable after construction //key的比较器 Comparator const compare_; //内存池 Arena* const arena_; // Arena used for allocations of nodes //跳表的头结点 Node* const head_; // Modified only by Insert(). Read racily by readers, but stale // values are ok. // 跳表的最大层数，不包括head节点，head节点的key为0，小于任何key，层数为kmaxheight=12 // AtomicPointer是leveldb定义的一个原子指针，它的读取和写入都设立了内存屏障，保证读取的值是即时的、最新的 // 这里直接将int型转化为指针保存，因为不会对其取地址，所以可行，值得借鉴 port::AtomicPointer max_height_; // Height of the entire list
成员函数有：
// Insert key into the list. void Insert(const Key& key); // Returns true iff an entry that compares equal to key is in the list. bool Contains(const Key& key) const; Node* NewNode(const Key& key, int height); int RandomHeight(); bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); } // Return true if key is greater than the data stored in "n" bool KeyIsAfterNode(const Key& key, Node* n) const; // Return the earliest node that comes at or after key. // Return NULL if there is no such node. // // If prev is non-NULL, fills prev[level] with pointer to previous // node at "level" for every level in [0..max_height_-1]. Node* FindGreaterOrEqual(const Key& key, Node** prev) const; // Return the latest node with a key < key. // Return head_ if there is no such node. Node* FindLessThan(const Key& key) const; // Return the last node in the list. // Return head_ if list is empty. Node* FindLast() const;
相信你们可以看懂这些函数功能的注释。
节点和迭代器：
skiplist的节点Node和迭代器Iterator都是以嵌套类定义在类skiplist中的
class Iterator { public: // Initialize an iterator over the specified list. // The returned iterator is not valid. explicit Iterator(const SkipList* list); // Returns true iff the iterator is positioned at a valid node. bool Valid() const; // Returns the key at the current position. // REQUIRES: Valid() const Key& key() const; // Advances to the next position. // REQUIRES: Valid() void Next(); // Advances to the previous position. // REQUIRES: Valid() void Prev(); // Advance to the first entry with a key >= target void Seek(const Key& target); // Position at the first entry in list. // Final state of iterator is Valid() iff list is not empty. void SeekToFirst(); // Position at the last entry in list. // Final state of iterator is Valid() iff list is not empty. void SeekToLast(); private: const SkipList* list_; Node* node_; // Intentionally copyable };
迭代器只有一个list指针（保存所指skiplist的指针）和node指针（所指的节点）。迭代器主要操作有前进，后退，定位头结点，尾节点，封装了list和node的操作。比如：
template
inline void SkipList
::Iterator::Next() { assert(Valid()); node_ = node_->Next(0); } template
inline void SkipList
::Iterator::Prev() { // Instead of using explicit "prev" links, we just search for the // last node that falls before key. assert(Valid()); node_ = list_->FindLessThan(node_->key); if (node_ == list_->head_) { node_ = NULL; } }
注意next操作时沿节点最低层的指针前进的，实际上prev也是，这样保证可以遍历skiplist每个节点。实际上跳表的多层指针结构为了提高查询的效率。
下面来看看节点node的定义：
template
struct SkipList
::Node { explicit Node(const Key& k) : key(k) { } //所携带的数据，memtable中为我们指明了实例化版本是char* key Key const key; // Accessors/mutators for links. Wrapped in methods so we can // add the appropriate barriers as necessary. //返回本节点第n层的下一个节点指针 Node* Next(int n) { assert(n >= 0); // Use an 'acquire load' so that we observe a full