跳表原理笔记

课程地址

跳表是一种基于随机化的有序数据结构，它提出是为了赋予有序单链表以 O(logn) 的快速查找和插入的能力

创建

首先在头部创建一个 sentinel 节点，然后在 L1 层采用“抛硬币”的方式来决定 L0 层的指针是否增长到 L1 层

例如上图中，L0 层的节点2，10，11，13，20，26 都增长到了 L1 层。继续采用抛硬币的方式，来决定 L1 层的指针是否增长到 L2 层

例如上图中，L1 层的节点2，13，26 都增长到了 L2 层。继续采用抛硬币的方式，来决定 L2 层的指针是否增长到 L3 层

例如上图中，L2 层的节点 13 增长到了 L3 层。至此我们停止层数增长，层数一般定为 logn 层

所以 L0 层保存了原始数据，逐个串联。L1 层平均每次跳过 1 个，L2 层平均每次跳过 2 个，L3 层平均每次跳过 4 个

跳跃相当于快速通道，使我们得以快速确定查找的元素是否在当前区间中

查找

首先查找 key = 13，从 L3 层开始查找，第一个节点的值就是 13，直接找到了

然后查找 key = 8，从 L3 出发，第一个节点的值是 13，大于 8，则从 Sentinel 向下走一层到 L2

从 L2 的 Sentinel 出发，第一个节点的值是 2，小于 8，则继续向后走一步，下一个节点的值是 13，大于 8，则从 L2 的第一个节点（2）向下走一层到 L1

从 L1 的第一个节点（2）出发，下一个节点的值是 10，大于 8，则从 L1 的第一个节点（2）向下走一层到 L0

从 L0 的第一个节点（2）出发，下一个节点的值是8，则找到了

然后查找 key = 20，从 L3 的 Sentinel 出发，下一个节点的值是 13，小于 20，因为 13 节点已经是最后一个节点，不能再往后走，所以向下走一层到 L2

从 L2 的第二个节点（13）出发，下一个节点的值是 26，大于 13，则向下走一层到 L1 层

从 L1 层的第 4 个节点出发，下一个节点的值是 20，则找到了

最后一个查找的例子是查找 key = 21，从 L3 的 Sentinel 出发，下一个节点的值是 13，小于 21，因为 13 节点已经是最后一个节点，所以向下走一层到 L2

从 L2 的第二个节点（13）出发，下一个节点的值是 26，大于 13，则向下走一层到 L1 层

从 L1 层的第 4 个节点出发，下一个节点的值是 20，小于 21，则向后走一步到 26，大于 21，则从 20 向下走一步到达 L0 层

从 L0 层的第 7 个节点（20）出发，下一个节点的值是 22，已经大于 21，因为 L0 已经是最底层，所以 20 和 22 之间没有其他节点，故 key = 21 不存在

新增

首先需要确定新节点的插入位置，这个过程跟查找是一致的，上图中红色箭头就表示新节点需要插入到这个范围内

同时使用一张哈希表记录下每个红色箭头的起点（指针）

接下来创建一个新节点，它的指针域采用“抛硬币”的方式决定是否向上层增长：如果正面朝上就增加一层，如果反面朝上就终止这个过程，那么新节点的高度会以指数的方式快速收敛。例如上图中，新节点 9 就是抛了 2 次硬币都正面朝上，第三次反面朝上

最后，借助表中记录的指针，将新的节点插入到跳表中

跳表 vs B+树