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_(){      
        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=;i<level;++i)
            node->next[i]=NULL;//表頭中初始的下一節點均為NULL
        return node;
    }
           

經過構造函數構造的表頭如下：

連結清單的增、删、查、改中，查找操作是最核心的，其他操作均是建立在查找的基礎上的

1）查找元素

Node* Find(KeyType  Key) const{
        Node *node=head_;
        for(int i=level_-;i>=;--i){//從最大高度開始查找
            while(node->next[i]!=NULL&&node->next[i]->KeyValue.first<Key)
                node=node->next[i];//當下一節點值比目标小時，直接往後查找，否則從下一層開始查找
        }
        node=node->next[];
        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_-;i>=;--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[];
        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=;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_-;i>=;--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=;i<newlevel;++i){//與一般節點的插入類似，要對每一高度的節點更新插入
            node->next[i]=update[i]->next[i];
            update[i]->next[i]=node;
        }
           

這樣就将元素插入到SkipList中了