Skip List——跳表，一个高效的索引技术-白红宇

Skip List——跳表，一个高效的索引技术

阅读量：6187 次

发布时间：2019-06-21

本文共 12344 字，大约阅读时间需要 41 分钟。

对于一个查询任务，如果不能开辟连续空间进而采样二分查找进行处理的话，通常各种树，各种碉堡的更高级的数据结构就会被提出，用来快速进行数据查询。

在这里，我无意显示自己的高人一等或是弱智一面，但是对于常见的数据结构，用于动态处理一组数据的索引构建工作，采样的多个数据结构都面临一个复杂编程过程，程序难以调试，算法难以理解的问题，而跳表——可以在满足O(LogN)的查询复杂度的前提下，十分简单的完成数据查询。

通常对于动态数据的搜索，红黑树等平衡二叉树，通过模拟二分搜索过程，可以达到一个查询代价为O( log N)的结果，而编程过程相当容易的链表，查询代价确是惊人的O(N)，所以一个简单的思路就出现了，通过对链表进行修改，使其能够通过空间上增加节点数据而获得时间上缩短查询时间——这就是跳表的思想。

跳表是由William Pugh发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在该论文中详细解释了跳表的数据结构和插入删除操作。

William Pugh是University of Maryland, College 大学的一名教授。

在MIT的算法导论公开课上，Erik Demaine给出了一个很有创意而且很容易理解的例子——地铁系统。

如果一个城市中，地铁有快车和慢车，快车能够快速的从一个站到达另一个站，而中间并不停，慢车就想普通的链表一样，每个站都要停（很有我经常坐的7374次列车的风范）。这样，首先通过快车到达目的地的附近，然后通过慢车倒车，到达目的地，这就是skiplist如何进行搜索的原理。

因为我们计算机并不需要考虑动车的调度问题，所以如果感觉快车线路不够快，可以再搭建超级快车线路，超级无敌快车线路，超级无敌风火轮快车线路，火箭快车线路，，，，，

只要我们能够良好的在c++中管理这些指针（这正是我的代码的问题），我们就可以得到一个最优的乘车线路设计结果。

下面给出一个完整的跳表的图示：

如果我们刚刚进入沈阳市，这时候我们位于点e，而想要去21号站台，作为高富帅的你们，肯定不会在乎车费这些毛毛雨的问题，所以选择地铁一号线，坐到6号站下车（一号线太贵了，沈阳只修了一站）。

我们知道目的地21号站在6号站的前面，所以从6号站下车的你们，选择二号线继续前行，一口气坐到25号站（baidu的地图应用此时只能在你坐过站的时候提醒你）。所以，我们回到6号站，坐三号线。。。（有钱也不是这么花的啊）

从三号线（沈阳的三号线现在还没有影子呢）出发，一路经过9号站，17号站，又到了25号站（现在一定会对baidu地图的开发人员进行意念上的人身攻击了），在一通纠结之后，回到17号站。

这时候baidu地图提示我们，17号站之下就是公交了，如果在坐公交的过程中，一直到25号站都没有到达目的地，这时候只能说明你拿了过期地图。。。不过我们经过两站公交之后，成功到达21号站。

进入沈阳我们投了9个钢镚，才成功到达21号站台，似乎在进入沈阳之后直接坐公交才花8块钱，还能省一个钢镚去买中街大果。。。。。。不过，skiplist是一个统计学上的最优结果，例子如果这个网络是整个中国，这就完全不同了。

上面写的都是如何搜索，但是搜索在一个数据结构中是最简单的操作，增删这两个操作才是最为让我们关注的，而这才是skiplist的精髓所在，通过一个概率为50%的过程判断一个节点是否提高到上一个层次上，通过理论分析，我们可以得到一个惊人的结论——O(logN)的期望查询代价。

代价分析：

这个过程很容易理解，但是它真的能够为我们提供一个O(logN)的期望查询代价的数据结构吗？

对于一个长度为N的链表，由于我们按照0.5的概率进行节点的向上升级，则上一层的节点数目的期望就是N/2，更高一层的节点数目期望是N/4，以此类推，则整个链的高度的期望就是logN。

和各种树的查询结构一样，跳表的查询代价分析也是与跳表的高度相关的，假如两个链，长度分别是L(1)和L(2)，则对于一个查询的最大代价就是：

COST = L(2) + L(2)/L(1）

COST = L(3) + L(3)/L(2) + L(2)/L(1)

对于更长的链都采用相同的代价分析，这样就可以明显看出，当这些量都相同的时候，COST获得最小值。

对于一个跳表，存在k个链，则他的最小查询代价是K*[N^(1/K)]

之前的代价是一个查询的最大查询代价，而得到的 K*[N^(1/K)] 是这个最大代价的最小值，但是通过摊还分析，这个代价可以作为整个平均代价进行处理，可以认为一个查询的平均代价是K*[N^(1/K)]。将K的值带入其中，最终得到代价的表达式。

这样，对于跳表这个结构，查询时间代价是O（logN），具体为2logN。所有表的节点数目为N+logN，其中新加入的索引大小为logN。

查询过程：

对于一个查询值value，我们从链的最高层开始进行查找，在代码中就是BEGIN节点。

1.在链L中一直向前走，直到这个节点为value或是NULL或是这个节点的值超过value。

2.如果节点值为value，向下搜索直到最低一层。返回这个节点；不然，进入3.

3.向前返回一个节点，进入下一层链L，如果链L存在，回到1继续探测——其中探测范围为上一层向下传递的两个节点的elem值；如果不存在，返回NULL。

插入过程：

skiplist是一个对排序的表进行处理的结构，每个节点插入的时候，插入最低一层，然后找出一个硬币来获得50%的概率，0表示不采取任何行动，1表示将这个节点向上提高一层，如果提高一层之后再次抛硬币，直到得到一个0才停止。。。。

如果想要插入一个值value，插入过程如下：

1.首先在已有跳表中进行查询，如果这个点存在，就放弃插入操作，如果不存在，创建新节点，并且返回应该插入的节点（这个过程的代码很难与查询过程完美对接，怎么整都有问题，降低重复代码这个过程任重而道远啊）。

2.将节点插入，然后加入一个随机过程，以0.5的概率将这个节点向上提高一层，过程直到停止提高操作。

3.提高如果新建一层链，更新BEGIN。

删除操作：

对于一个节点只value，想要删除这个节点的对象。

1.用search过程找到这个节点，对于返回值处理。

2.向上搜索获得最高层。

3.依次删除各个层上的节点，如果删除导致层数改变，更新BEGIN。

可以看出除了插入过程显得与众不同之外，其他的各个方面都与常见的链表操作相同，所以我们可以通过上述的分析写出一个简单的跳表的实现。

View Code

1 #include 
      
         2 #include 
       
          3 using namespace std;  4 #define MINELEM -2147483648  5 class Node;  6 class Node{  7 public:  8     friend void print();  9     Node* getForward(){
    return forward;} 10     Node* getBackward(){
    return backward;} 11     Node* getUplevel(){
    return uplevel;} 12     Node* getDownlevel(){
    return downlevel;} 13  14     void setForward(Node *obj){forward = obj;} 15     void setBackward(Node *obj){backward = obj;} 16     void setUplevel(Node *obj){uplevel = obj;} 17     void setDownlevel(Node *obj){downlevel = obj;} 18  19     void setLevel(int a){level = a;} 20     int getLevel()const{
    return level;} 21     int getElem()const{
    return elem;} 22     Node():forward(NULL),backward(NULL),uplevel(NULL),downlevel(NULL),elem(0){} 23     Node(int a):forward(NULL),backward(NULL),uplevel(NULL),downlevel(NULL),elem(a){} 24     Node(const Node &obj):forward(obj.forward),backward(obj.backward),uplevel(obj.uplevel),downlevel(obj.downlevel){ 25         elem = obj.getElem(); 26     } 27     Node(Node *forward_ptr,Node *backward_ptr,Node *uplevel_ptr,Node *downlevel_ptr,int value){ 28         forward = forward_ptr; 29         backward = backward_ptr; 30         uplevel = uplevel_ptr; 31         downlevel = downlevel_ptr; 32         elem = value; 33     } 34     Node& operator=(const Node &obj){ 35         forward = obj.forward; 36         backward = obj.backward; 37         uplevel = obj.uplevel; 38         downlevel = obj.downlevel; 39         elem = obj.getElem(); 40         level = obj.getElem(); 41         return* this;  42     } 43 private: 44     Node *forward,*backward,*uplevel,*downlevel; 45     int elem; 46     int level; 47 }; 48 static Node *START = new Node(NULL,NULL,NULL,NULL,MINELEM); 49 static Node *BEGIN = START; 50 Node* Levelup(Node &obj){ 51     Node *p = &obj; 52     Node *new_obj = new Node(obj);     53     obj.setUplevel(new_obj); 54     new_obj->setDownlevel(&obj); 55     while((p->getElem())!= (START->getElem())){ 56         p = p->getBackward(); 57     }//find the next level up position 58     if(p->getUplevel() == NULL) 59     { 60         Node *q = new Node(*START); 61         q->setDownlevel(p); 62         p->setUplevel(q); 63         q->setUplevel(NULL); 64         BEGIN = q; 65         new_obj->setBackward(q); 66         q->setForward(new_obj); 67         new_obj->setUplevel(NULL); 68         new_obj->setForward(NULL); 69         return new_obj; 70     } 71     else{ 72         p = obj.getBackward(); 73         new_obj->setUplevel(NULL); 74         while(p->getUplevel() == NULL) 75             p = p->getBackward(); 76         p = p->getUplevel(); 77         Node *q = p->getForward(); 78         new_obj->setBackward(p); 79         p->setForward(new_obj); 80         new_obj->setForward(q); 81         if(q != NULL){ 82             q->setBackward(new_obj); 83         } 84         return new_obj; 85     } 86 } 87 Node* Search(int value){ 88     Node *p = START,*q = BEGIN; 89     while(q->getDownlevel()!=NULL){ 90         p = q; 91         while(p->getForward()!=NULL && p->getElem()
        
         getForward(); 93         } 94         if(p->getElem() == value){ 95             while(p->getDownlevel()!=NULL) 96                 p = p->getDownlevel(); 97             return p; 98         } 99         else {100             q = p->getDownlevel()->getBackward();101         }102         //search the next level103     }//serach part return the former object!104     if(q->getDownlevel() != NULL){105         if(p->getForward() != NULL){106             q = p->getBackward()->getDownlevel();107             while(q->getElem()!=p->getElem()){108                 if(q->getElem() == value)109                     return q;110                 else q = q->getForward();111             }112         }113         else {114             p = p->getDownlevel();115             while(p!=NULL){116                 if(p->getElem() == value)117                     return p;118                 else p = p->getForward();119             }120         }121     }//there are many level122     else {123         while(p!=NULL){124             if(p->getElem() == value)125                 return p;126             else p = p->getForward();127         }128     }//there only one level129     return NULL;130 }131 int Insert(int value){132     Node *p = START,*q = BEGIN;133     if(Search(value) == NULL){134         Node *obj = new Node(value);135         while(q!=NULL){136             p = q;137             while(p->getForward()!=NULL){138                 if(obj->getElem()>p->getElem())139                 {140                     p = p->getForward();141                 }//end if142                 else break;143             }144             if(p->getBackward()==NULL)145                 break;146             if(p->getBackward()->getDownlevel() != NULL)147                 q = p->getBackward()->getDownlevel();148             else break;149             //search the next level150         }//serach part return the former object!151         if(p->getElem() == START->getElem())152             q = p->getForward();153         else {154             q = p;155             p = p->getBackward();156         }157         if(q!=NULL){158             if(q->getElem()>value){159                 q->setBackward(obj);160                 p->setForward(obj);161                 obj->setBackward(p);162                 obj->setForward(q);163             }164             else {165                 q->setForward(obj);166                 obj->setBackward(q);167             }168         }169         else {170             p->setForward(obj);171             obj->setBackward(p);172         }173         int r = rand();174         Node *temp = obj;175         while(r%2 == 0){176             temp = Levelup(*temp);177             r = rand();178         }179         return 1;180     }//end if value do not exist181     else {182         return 0;183     }184 }185 int Delete(int value){186     Node *temp = Search(value);187     if(temp == NULL)return -1;188     else{189         Node *p = temp;190         while(p->getUplevel()!=NULL)p = p->getUplevel();191         while(p != NULL){192             if(p->getBackward()->getElem() == START->getElem() && p->getForward()==NULL){193                 Node *q;194                 if(p->getBackward()->getDownlevel()!=NULL){195                     p->getBackward()->getDownlevel()->setUplevel(NULL);196                     q= p->getDownlevel();197                 }198                 if(BEGIN != START){199                     BEGIN = p->getBackward()->getDownlevel();200                     delete p->getBackward();                201                     delete p;202                     p = q;203                 }204                 else{205                     BEGIN->setForward(NULL);206                     START->setForward(NULL);207                     delete p;208                     p = NULL;209                 }//there only one node exist210             }//end if, 211             else {212                 if(p->getForward() != NULL)213                     p->getForward()->setBackward(p->getBackward());214                 p->getBackward()->setForward(p->getForward());215                 Node *q = p->getDownlevel();216                 delete p;217                 p = q;218             }219         }220     }221 }222 void print(){223     cout<<"PRINT!"<
         
          getElem()<<"    ";227         p = p->forward;228     }229     cout<
          
           uplevel;231     q = p;232     while(p!=NULL){233         if(q != NULL){234             cout<
           
            getElem()<<" ";235 q = q->getForward();236 }237 Node *t = START->getForward();238 while(q != NULL){239 Node *temp = q->getBackward(); 240 while(t->getElem()!=q->getElem()){241 cout<<" ";242 t = t->getForward();243 }244 cout<
            
             getElem();245 q = q->getForward();246 }247 p = p->uplevel;248 q = p;249 cout<
             
              >i;256 while(i--){ 257 print();258 Insert(i);259 }260 char c;261 cout<<"i--Insert d--Delete"<
              
               >c>>i){264 switch(c){265 case 'd':266 cout<
               
                <