Skip Lists – 跳表原论文解析

@创建时间 2022年08月17日 18:15:32
@更新时间 2023年04月07日 22:23:12

本文基于跳表作者William Pugh原论文进行原理解读和代码实现分析

跳表思想

跳表是有序链表存储数据的数据结构，其在链表上建立了多级索引。这些索引将链表划分为多个区间，同时索引指向自身划分的区间起点，用以加快范围查询：

1）高层索引节点数量少，划分区间数量少跨度大，排除大范围无效查询

2）低层索引节点数量多，划分区间数量多跨度小，搜索数量少，查询距离节点越近，精度更高

如图节点9建立了区间[9,21)、[9,17)、[9,12)的索引

查询操作

跳表查询时不断确定元素所在区间：同层之间从左到右；不同层之间从上到下、跨度由大到小。当区间长度为1，且左端点为不超过元素值的最大区间左端点时，到达正确查询区间

Search(list, searchKey)
    x := list→header
    for i := list→level downto 1 do                 // 从上到下确定元素所在区间
        while x→forward[i]→key < searchKey do
            x := x→forward[i]                       // 从左到右确定元素所在区间，并记录区间左端点
    x := x→forward[1]                               // 底层区间长度为1，左端点右侧节点不小于元素值
    if x→key = searchKey then return x→value        // 等于查询成功
    else return failure                             // 大于则元素不在跳表中

插入操作

①查询到正确区间插入元素
②更新待插元素左右侧节点的指针指向
③插入节点高于原跳表，需处理高层指针和全表高度

图为插入17时的查询路径和指针修改

Insert(list, searchKey, newValue)
    local update[1..MaxLevel]
    x := list→header
    for i := list→level downto 1 do
        while x→forward[i]→key < searchKey do
            x := x→forward[i]
        update[i] := x                              // 记录元素所在各区间的左端点，小于元素值
    x := x→forward[1]                               // 元素所在底层区间左端点右侧为正确位置
    if x→key = searchKey then x→value := newValue   // 已有待插节点仅更新值
    else                                            // 尚无待插节点则插入节点
        lvl := randomLevel()                        // 随机生成待插节点高度
        if lvl > list→level then                    // 新节点高于跳表，头节点高层应指向该节点
            for i := list→level + 1 to lvl do
                update[i] := list→header
            list→level := lvl
        x := makeNode(lvl, searchKey, value)
        for i := 1 to level do                      // 将新节点"挡入"最右节点和下一节点之间
            x→forward[i] := update[i]→forward[i]
            update[i]→forward[i] := x

删除操作

①查找删除元素所在位置
②"抽除"节点后应还原待删元素左右侧节点之间的指针指向
③唯一最高节点删除后应降低跳表高度为第二高节点高度

Delete(list, searchKey)
    local update[1..MaxLevel]
    x := list→header
    for i := list→level downto 1 do
        while x→forward[i]→key < searchKey do
            x := x→forward[i]
        update[i] := x                              // 记录元素所在各区间的左端点，小于元素值
    x := x→forward[1]                               // 指向待删节点所在位置
    if x→key = searchKey then                       // 待删节点仅当存在时处理
        for i := 1 to list→level do
            if update[i]→forward[i] ≠ x then break  // * 优化：无需处理唯一最高节点独属高度
            update[i]→forward[i] := x→forward[i]    // 还原删除元素左右侧节点的指针指向
        free(x)                                     // 释放删除节点内存
        while list→level > 1 and list→header→forward[list→level] = NIL do
            list→level := list→level – 1            // 降低跳表高度至当前最高节点高度

性能分析

增删查平均时间复杂度 $\scriptsize O(\log n)$
平均空间复杂度 $\scriptsize O(\frac{n}{1-p})$

为什么可以代替平衡查找树

跳表的性能接近于平衡查找树
跳表维护索引代价低于维护平衡操作代价
跳表的代码实现更简单，可读性可理解性更强

应用

Redis中排序集合zset底层实现

参考资料

W. Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, in CACM, 1990