skiplist原理深入浅出

1月 21, 2019 |

redis的hash实现没有使用红黑数, 而是采用了skiplist, 将学习中的理解整理出来备忘,如果能帮助到其他人就更好了。
这个主题最好的文档还是William Pugh 博士的论文,直接baidu "skip list pdf"就能搜索到,当然也可以从我分享的链接中下载
skipList的基本原理就是每个节点不仅有指向下一个节点的指针, 还维护了k个额外的指针。第k个指针指向(ahead翻译为后继,希望大家能接受)后继第k个节点,比如当前为第5个节点,那么第3个指针就指向第8个节点(也就是当前节点的第3个后继节点)

skip List的示例:


1、什么是level k节点 
含有key 个ahead(后继)指针的节点
2、每个节点要维护多少个额外后继指针?
采用抛硬币的方式,抛一次硬币指针的个数加1, 重复抛硬币直到某次结果为反面。伪代码见论文中的randomLevel() 函数
3、header指针要维护多少个指针呢 
当前链表的level最大为多少,那么header就维护多少个指针

4、查找如何遍历   
先沿最大的ahead 指针向后继查找,如果ahead[k] <searchKey, 将ahead[k]作为当前节点继续查找,否则检查ahead[k-1],直到k=1或者当前节点的key==查找的key
比如为了查找key=25, 那么遍历的路径为6->25

5、新增时额外的向前指针如何维护 
调用随机数产生器产生level ,根据key, 查找到待插入的位置,同时update[]记录链表中其他节点需要指向当前节点指针,修改指针时,当前节点的ahead[i]=update[i],update[i]指向当前节点
比如上图中   为了插入17,先遍历链表找到待插入的位置为12之后, 那么update[2]=节点9的ahead[2], update[1]=节点12的ahead[1], 将节点17的ahead[2]=update[2], ahead[1]=update[1];   upate[2]=节点17, upate[1]=节点17

6、删除节点时额外指针维护 
先根据key,查找到对应节点的位置,同时update[]数组记录链表的其他节点指向当前节点的情况, 当前节点删除后需要将update[i]更新为当前节点的ahead[i]
针对上图   为了删除key=17的节点,先遍历链表找到key=17节点位置, 并记录update[2]=节点key=9的ahead[2], update[1]=节点key=12的ahead[1]; 修改指针时,节点9的ahead[2]=节点17的ahead[2], 节点12的ahead[1]=节点17的ahead[1];

Posted in: 面试加油站

Comments are closed.