Redis zset的数据接口:SkipList(跳表)的原理及实现
1.数据结构
1.1 简介
跳表（skiplist）是一个查询/插入/删除 复杂度o(lgn)的数据结构。在查询上跟平衡树的复杂度一致，因此是替代平衡树的方案。在redis的zset，leveldb都有应用。发现这个算法也解决了我一个问题。各种平衡树在工业界是广泛应用，帮助我们快速查找，插入数据，但其思想的复杂也让大家不是那么容易接触。当时想直接对有序链表进行二分搜索，那岂不是很容易做到相同复杂度且容易理解，不过链表并不能像数组随机访问，只能从头一个个遍历。跳表为节点设置了快速访问的指针，不同在一个个遍历，可以跨越节点进行访问，这也是跳表的名字的含义。
上面就是跳表的引子，下图就是它的数据结构
1.2 跳表如何构建
当插入一个数据时，随机获得这个节点的高度，没错，就是随机！每涨一层的概率为p，这个认为设置，一般为0.25或者0.5,这样层数越高的节点就越少（这种结构跟平衡树有点像）。
1.3 如何搜索
如上图所示，我们检索19这个值，遍历路径如下图所示
可以看到高层级的节点相当于一个快速通道，让搜索进行了节点的跳跃，而不是一个个的遍历。
2.编码实现
基于java我实现了一个具有增删查的跳表: https://github.com/yangzhenkun/learn/blob/master/src/main/java/com/yasin/algorithm/SkipList.java
2.1 搜索
搜索实现按照上面的思路，从顶层往下遍历，每层之间就是普通链表遍历。
public T get(Integer key) {SkipNode cur = head;for (int l = maxLevel - 1; l >= 0; l--) {if (cur.forward[l] == null) {continue;}while (cur.forward[l] != null && key > cur.forward[l].key) {cur = cur.forward[l];}if (cur.forward[l] != null && key == cur.forward[l].key) {return (T) cur.forward[l].value;}}return null;}
2.2 插入
插入的思路是要找到插入的点，并且在遍历的同时，记录下需要更新层数 快速通道指针的地方，在最后进行处理。
例如插入17，并且在17节点随机获得层数是2.这样节点9的第2层（从下往上数）需要指向新的节点17，12的第1层也要指向17。可以看出需要更新的就是每一层最后遍历过的节点。
public boolean set(int key, T value) {SkipNode newNode = initNode(key, value);int newNodeMaxLevel = newNode.forward.length;SkipNode cur = head;SkipNode[] update = new SkipNode[newNodeMaxLevel];//记录更新的节点/*** 遍历找到插入的节点，并记录下需要更新层指针的节点*/for (int l = maxLevel - 1; l >= 0; l--) {if (cur.forward[l] == null) {if (l < newNodeMaxLevel) {update[l] = cur;}continue;}while (cur.forward[l] != null && key > cur.forward[l].key) {cur = cur.forward[l];}if (cur.forward[l] != null && key == cur.forward[l].key) {return false;}if (l < newNodeMaxLevel) {update[l] = cur;}}/*** 执行插入更新操作*/for (int l = newNodeMaxLevel - 1; l >= 0; l--) {newNode.forward[l] = update[l].forward[l];update[l].forward[l] = newNode;}return true;}
2.3 删除
对get和set方法了解后，删除方法的实现已经没有理解的压力了。同理需要记录下搜索的过程中每一层最后遍历的节点。在找到删除节点后，把每一层中指向删除节点的 指针指向被删除节点每层的后续指针。
public boolean remove(int key) {SkipNode cur = head;SkipNode[] update = new SkipNode[maxLevel];//因为不知道被删除的节点有几层，所以需要把全部的层数记录下来SkipNode delete = null;/*** 遍历找到要删除的节点，并记录下需要更新层指针的节点*/for (int l = maxLevel - 1; l >= 0; l--) {if (cur.forward[l] == null) {continue;}while (cur.forward[l] != null && key > cur.forward[l].key) {cur = cur.forward[l];}if (cur.forward[l] != null && key == cur.forward[l].key) {delete = cur.forward[l];update[l] = cur;}}if (delete == null) {return false;}/*** 更新指针*/for (int l = delete.forward.length - 1; l >= 0; l--) {update[l].forward[l] = delete.forward[l];delete.forward[l] = null;//help gc}return true;}
3.原理证明
3.1 最大层级证明
把最底层的链表叫做level0，最大层数包括最底层
在数据结构小节中已经说到最大层级为
证明方式论文也提到
文中一开始也提到一种情况，16个节点，level1可能是9个，level2 3个，level3 3个，level14 1个。如果我们从第14层开始搜索，有很多无效的工作，因为顶层太过稀疏。文中提到最顶层应该是1/p个节点。
很容易得到每一层的节点数
这样就能推导出
这样就得到了最大层数
3.2复杂度证明
文中也对查找的复杂度进行了证明，我截取了部分图，可以去原文查看
这里利用递推的思想来进行了证明。
文中基于搜索路径回溯的方式进行了证明，往上和左进行遍历。假设当前位置在第i层，要访问的值为x，i到x之间的层数是k层。用c(k)表式遍历k层访问到x的步数。在回溯的任何一个节点的移动中，都如下图所示。当我们处于情况a的时候，我们下一步一定是情况b或者c。情况c的概率为什么是p呢？因为基于当前层，下一层有该节点的概率为p。那么情况b自然就是1-p。这样就得出递推公式
C(k)=(1-p)(1+C(k))+p(1+C(k-1))
同时C(0)=0
便可归纳出 搜索k层需要的步数为: c(k)=k/p
我们一次遍历最大层数上面已经推导出，带入步数公式得到一次搜索的步数
因为p是概率常数，一般为1/4或者1/2，这样复杂度就是O(lgn)级