leveldb之SkipList的简单实现

1、Skiplist

SkipList是链表的变形，它在链表的基础上给每个元素增加了一个高度，且每个元素的高度是一个随机值，因此SkipList是一种随机化的数据结构。SkipList增、删查、改的效率都非常高，是一种典型的以空间换时间的存储方式。

常规的链表如下：

而相同元素对应的SkipList结构如下：

由上可知，当要在链表中查找某个元素时，必须从链表头一个一个遍历，而在SkipList中查找某个元素时，查找却是跳跃的，因此将其称为SkipList。
如要查找元素25时，对于单链表，要遍历到第9个节点才能找到。而对于Skiplist，只需要经过2次比较即可（表头到元素6再到25），效率非常高。
当查找的效率高了之后，插入、删除、修改的效率自然也就变高了

2、Skiplist中的节点

SkipList中的每个节点，都包含有一个值和一个数组，其中数组元素的个数即为当前节点的高度，数组中对应位置的元素存储的是指向同一高度的下一节点的指针（如next[0]指向level 0的下一节点，next[3]指向level 3的下一节点），因此数组可用一个二级指针表示。

template<typename KeyType,typename DataType,typename Comparator>
struct SkipListNode{
    std::pair<KeyType,DataType> KeyValue;//Leveldb是一个K-V存储系统，因此节点元素值包括Key和Value两部分
    SkipListNode **next;//一个二级指针，指向一个包含level个节点的数组
};

3、SkipList的实现

SkipList类中的成员变量只包含了当前链表的最大高度和表头

template<typename KeyType,typename DataType,typename Comparator> class SkipList{
public:
    typedef SkipListNode<KeyType,DataType,Comparator> Node;

    SkipList():level_(0){      
        head_ = CreateNode(std::make_pair(KeyType(), DataType()), MAXLEVEL);  
    }
    ~SkipList();

    bool Insert(const std::pair<KeyType,DataType>& value);  
    Node* Find(KeyType&  Key) const;
    bool Remove(KeyType& Key);
    int GetLevel() const{
        return level_;
    }
private:
    Node* CreateNode(std::pair<KeyType,DataType> key,int level);
    void DestroyNode(Node *node);

    int level_;//SKipList中节点的最大高度
    Node *head_;//表头元素
};

SkipList在构造函数中调用CreateNode()得到表头节点，表头首先会初始化系统规定的最大高度个数组元素，假设最大高度为4

Node* CreateNode(std::pair<KeyType,DataType> value,int level){
        Node *node=new Node();
        node->KeyValue=value;
        node->next=new Node*[level];
        for(int i=0;i<level;++i)
            node->next[i]=NULL;//表头中初始的下一节点均为NULL
        return node;
    }

经过构造函数构造的表头如下：

链表的增、删、查、改中，查找操作是最核心的，其他操作均是建立在查找的基础上的
1）查找元素

    Node* Find(KeyType  Key) const{
        Node *node=head_;
        for(int i=level_-1;i>=0;--i){//从最大高度开始查找
            while(node->next[i]!=NULL&&node->next[i]->KeyValue.first<Key)
                node=node->next[i];//当下一节点值比目标小时，直接往后查找，否则从下一层开始查找
        }
        node=node->next[0];
        if(node==NULL||node->KeyValue.first!=Key)   return NULL;
        else    return node;
    }

2）插入元素

bool Insert(const std::pair<KeyType,DataType>& value){
        Node *node=head_;
        Node *update[MAXLEVEL];
        //SkipList中最核心的部分，找到要增、删、查、改的元素的每一个直接前驱，存储在update[]中，在后面的修改中会用到。当链表为空时，全为head_
        for(int i=level_-1;i>=0;--i){   //当level_到达规定的最大高度时，i从0到level_-1，即i=0~3
            while(node->next[i]!=NULL&&node->next[i]->KeyValue.first<value.first)
                node=node->next[i];
            update[i]=node;
        }

        node=node->next[0];
        if(node!=NULL&&node->KeyValue.first==value.first)   return false;//若已存在于要插入元素的Key值相等的，则不插入直接返回

        int newlevel=getRandomLevel();//随机产生要插入元素的高度
        if(level_<newlevel){//当新的高度大于原来链表中的最大高度时，说明此时从level_到newlevel高度均为空，还没有初始值
            for(int i=level_;i<newlevel;++i)
                update[i]=head_;//则说明新节点从level_到newlevel的直接前驱都只会是head_，将其存放在update[]中
            level_=newlevel;//更新此时链表的最大高度
        }

        node=CreateNode(value,newlevel);//创建新节点
        for(int i=0;i<newlevel;++i){//然后将新节点插入到SkipList中，基本操作与链表相似，只不过节点的不同高度的直接前驱都不同
            node->next[i]=update[i]->next[i];
            update[i]->next[i]=node;
        }
        return true;
    }

以要插入元素17为例（假设其他元素都已经存在），此时的level_=4

for(int i=level_-1;i>=0;--i){   //当level_到达规定的最大高度时，i从0到level_-1，即i=0~3
            while(node->next[i]!=NULL&&node->next[i]->KeyValue.first<value.first)
                node=node->next[i];
            update[i]=node;
        }

得到后面要更新的节点update： update[3]=6,update[2]=6,update[1]=9,update[0]=12
同时newlevel=2

for(int i=0;i<newlevel;++i){//与一般节点的插入类似，要对每一高度的节点更新插入
            node->next[i]=update[i]->next[i];
            update[i]->next[i]=node;
        }

这样就将元素插入到SkipList中了