跳表及其简单实现
跳表原理
理解跳表
跳表 (Skip List) 是由 William Pugh 发明的一种查找数据结构，支持对数据的快速查找，插入和删除。
下图是一个简单的有序单链表，单链表的特性就是每个元素存放下一个元素的引用。
想快速找到上图链表中的 10 这个元素，只能从头开始遍历链表，直到找到我们需要找的元素，查找路径：1、3、4、5、7、8、9、10，这样的查找效率很低，平均时间复杂度很高O(n)。
那有没有办法提高链表的查找速度呢？如下图所示，我们从链表中每两个元素抽出来，加一级索引，一级索引指向了原始链表，即：通过一级索引 7 的down指针可以找到原始链表的 7 。
从第一级索引开始找，查找路径变为：1、4、7、9、10，提高了查找效率。
那如果加二级索引呢？如下图所示，查找路径：1、7、9、10。找 10 的效率更高了。
这就是跳表的思想，用“空间换时间”，通过给链表建立索引，提高了查找的效率。
假如有序单链表现在有1万个元素，分别是 0~9999。现在我们建了很多级索引，最高级的索引，就两个元素 0、5000，次高级索引四个元素 0、2500、5000、7500，依次类推，当我们查找 7890 这个元素时，查找路径为 0、5000、7500 ... 7890，通过最高级索引直接跳过了5000个元素，次高层索引直接跳过了2500个元素，从而使得链表能够实现二分查找。由此可以看出，当元素数量较多时，索引提高的效率比较大，近似于二分查找。
时间复杂度
先来求跳表的索引高度。如下图所示，假设每两个结点会抽出一个结点作为上一级索引的结点，原始的链表有n个元素，则一级索引有n/2 个元素、二级索引有 n/4 个元素、k级索引就有 n/2k个元素。最高级索引一般有2个元素，即：最高级索引 h 满足 2 = n/2h，即 h = log2n - 1，最高级索引 h 为索引层的高度加上原始数据一层，跳表的总高度 h = log2n。
图中所示，现在到达第 k 级索引，我们发现要查找的元素 x 比 y 大比 z 小，所以，我们需要从 y 处下降到 k-1 级索引继续查找，k-1级索引中比 y 大比 z 小的只有一个 w，所以在 k-1 级索引中，我们遍历的元素最多就是 y、w、z，发现 x 比 w大比 z 小之后，再下降到 k-2 级索引。所以，k-2 级索引最多遍历的元素为 w、u、z。
其实每级索引都是类似的道理，每级索引中都是两个结点抽出一个结点作为上一级索引的结点。 现在我们得出结论：当每级索引都是两个结点抽出一个结点作为上一级索引的结点时，每一层最多遍历3个结点。
跳表的索引高度 h = log2n，且每层索引最多遍历 3 个元素。所以跳表中查找一个元素的时间复杂度为 O(3*logn)，省略常数即：O(logn)。
空间复杂度
假如原始链表包含 n 个元素，则一级索引元素个数为 n/2、二级索引元素个数为 n/4、三级索引元素个数为 n/8 以此类推。所以，索引节点的总和是：n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n-2，空间复杂度是 O(n)。
如下图所示：如果每三个结点抽一个结点做为索引，索引总和数就是 n/3 + n/9 + n/27 + … + 9 + 3 + 1= n/2，减少了一半。所以我们可以通过较少索引数来减少空间复杂度，但是相应的肯定会造成查找效率有一定下降，我们可以根据我们的应用场景来控制这个阈值，看我们更注重时间还是空间。
插入数据
如下图所示，要插入数据6，整个过程类似于查找6，整个的查找路径为 1、1、1、4、4、5。查找到第底层原始链表的元素 5 时，发现 5 小于 6 但是后继节点 7 大于 6，所以应该把 6 插入到 5 之后 7 之前。整个时间复杂度为查找元素的时间复杂度 O(logn)。
但是，假如一直往原始列表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从 O(logn) 退化为 O(n)。
为了解决这个问题，跳表通过 概率化的多层索引 来平衡性能和复杂度。
假如，我们在第一级索引中，随机选取n/2个元素，当原始链表中元素数量足够大，且抽取足够随机的话，我们得到的索引是均匀。
如果随机选 n/2 个元素做为一级索引、随机选 n/4 个元素做为二级索引、随机选 n/8 个元素做为三级索引，依次类推，一直到最顶层索引。这里每层索引的元素个数已经确定，且每层索引元素选取的足够随机，所以可以通过索引来提升跳表的查找效率。
在代码实现上，可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推，就能满足我们上面的条件。现在我们就需要一个概率算法帮我们把控这个 1/2、1/4、1/8 ... ，当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。下面开始讲解这个概率算法代码如何实现。
我们可以实现一个 randomLevel() 方法，该方法会随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），且该方法有 1/2 的概率返回 1、1/4 的概率返回 2、1/8的概率返回 3，以此类推。
- randomLevel() 方法返回 1 表示当前插入的该元素不需要建索引，只需要存储数据到原始链表即可（概率 1/2）
- randomLevel() 方法返回 2 表示当前插入的该元素需要建一级索引（概率 1/4）
- randomLevel() 方法返回 3 表示当前插入的该元素需要建二级索引（概率 1/8）
- randomLevel() 方法返回 4 表示当前插入的该元素需要建三级索引（概率 1/16）
- 。。。以此类推
过程大概理解了，再通过一个例子描述一下跳表插入数据的全流程。现在我们要插入数据 6 到跳表中，首先 randomLevel() 返回 3，表示需要建二级索引，即：一级索引和二级索引需要增加元素 6。该跳表目前最高三级索引，首先找到三级索引的 1，发现 6 比 1大比 13小，所以，从 1 下沉到二级索引。
下沉到二级索引后，发现 6 比 1 大比 7 小，此时需要在二级索引中 1 和 7 之间加一个元素6 ，并从元素 1 继续下沉到一级索引。
下沉到一级索引后，发现 6 比 1 大比 4 大，所以往后查找，发现 6 比 4 大比 7 小，此时需要在一级索引中 4 和 7 之间加一个元素 6 ，并把二级索引的 6 指向 一级索引的 6，最后，从元素 4 继续下沉到原始链表。
下沉到原始链表后，就比较简单了，发现 4、5 比 6小，7比6大，所以将6插入到 5 和 7 之间即可，整个插入过程结束。
整个插入过程的路径与查找元素路径类似， 每层索引中插入元素的时间复杂度 O(1)，所以整个插入的时间复杂度是 O(logn)。
删除数据
跳表删除数据时，要把索引中对应节点也要删掉。如下图所示，如果要删除元素 9，需要把原始链表中的 9 和第一级索引的 9 都删除掉。
跳表中，每一层索引其实都是一个有序的单链表，单链表删除元素的时间复杂度为 O(1)，索引层数为 logn 表示最多需要删除 logn 个元素，所以删除元素的总时间包含 查找元素的时间 加 删除 logn个元素的时间 为 O(logn) + O(logn) = 2 O(logn)，忽略常数部分，删除元素的时间复杂度为 O(logn)。
源码分析和简单实现
Redies源码
Redis的ZSET通过跳表（Skip List）实现有序元素的快速操作，以下是其核心实现机制
跳表节点（zskiplistNode）
每个节点包含以下关键信息：
typedef struct zskiplistNode {
sds ele; // 存储的元素（例如 "user:123"）
double score; // 排序分数（例如 95.5）
struct zskiplistNode *backward; // 后退指针（双向链表）
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned long span; // 跨度（到下一个节点的距离）
} level[]; // 柔性数组，表示节点的层级
} zskiplistNode;- level[]：每个节点的层级数随机生成（例如节点A有3层，节点B有1层）。
- span：记录从当前节点到下一个节点跨越了多少个节点，用于快速计算排名（如
ZRANK命令）。
跳表结构（zskiplist）
typedef struct zskiplist {
struct zskiplistNode *header, *tail; // 头尾节点
unsigned long length; // 元素总数
int level; // 当前最大层数
} zskiplist;- header：头节点不存储实际数据，作为各层查找的起点。
- tail：指向最底层链表的最后一个节点，便于反向遍历。
跳表插入
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
// 1. 查找插入位置，记录各层前驱节点
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
rank[i] = (i == zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele, ele) < 0)))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x; // 记录每层的前驱节点
}
// 2. 生成新节点的随机层数
level = zslRandomLevel();
if (level > zsl->level) {
// 若新层数超过当前最大层，初始化更高层的前驱为头节点
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
// 3. 创建新节点并插入到各层链表
x = zslCreateNode(level, score, ele);
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
// 更新跨度
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
// 4. 更新未触及的高层的跨度
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
// 5. 维护后退指针和跳表属性
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}- rank：在插入操作中，
rank[i]记录 从header到第i层的前驱节点（update[i]）所经过的总节点数。帮助计算新节点插入后各层的span值。 level[i].span：从当前节点到该层下一个节点之间跨越的节点数（不包括当前节点，包括下一个节点）。用于快速计算某个节点的排名（ZRANK）或逆排名（ZREVRANK）。
假设现有跳表如下（按 score 排序）：
Level 2: header -> [node1(score=10)] ------------------------> NULL
Level 1: header -> [node1(score=10)] --------> [node3(score=30)] -> NULL
Level 0: header -> [node1(score=10)] -> [node2(score=20)] -> [node3(score=30)] -> NULL 现在要插入一个新节点 node4(score=25)，其随机层数为 2。
查找插入位置
从最高层（Level 2）开始，逐层向下查找插入位置：
- Level 2：
- 头节点的
forward指向node1(score=10)。 node1的score=10<25，继续向右。node1的forward为NULL，无法继续，记录前驱节点为 header。
- 头节点的
- Level 1：
- 头节点的
forward指向node1(score=10)。 node1的forward指向node3(score=30)，30 > 25，停止，记录前驱节点为 node1。
- 头节点的
- Level 0：
node1的forward指向node2(score=20)，20 < 25，继续向右。node2的forward指向node3(score=30)，30 > 25，停止，记录前驱节点为 node2。
最终记录各层前驱节点：
update[2] = header
update[1] = node1
update[0] = node2生成新节点的层数
通过 zslRandomLevel() 随机生成层数（假设为2）：
int zslRandomLevel() {
int level = 1;
// 每次有 25% 的概率增加层数
while ((rand() % 0xFFFF) < (0.25 * 0xFFFF)) level++;
return (level < 32) ? level : 32;
}调整指针和跨度
将新节点 node4(score=25) 插入各层链表：
- Level 1：
node1的forward原本指向node3，现在改为指向node4。node4的forward指向node3。- 更新跨度：
node1到node4的跨度 = 原跨度（从node1到node3的跨度） - 已走过的节点数。node4到node3的跨度 = 剩余跨度。
- Level 0：
node2的forward原本指向node3，现在改为指向node4。node4的forward指向node3。
插入后的跳表结构：
Level 2: header -> [node1(score=10)] ------------------------> NULL
Level 1: header -> [node1(score=10)] --------> [node4(score=25)] -> [node3(score=30)] -> NULL
Level 0: header -> [node1(score=10)] -> [node2(score=20)] -> [node4(score=25)] -> [node3(score=30)] -> NULL简单实现
Golang完成1206. 设计跳表 - 力扣（LeetCode），实现简单跳表
const (
maxLevel = 32 // 定义跳表的最大层数，限制跳表的最高可能层级，避免无限制增长
probability = 0.25 // 层数生成的概率因子，决定新节点层级增加的概率，采用 1/4 的概率提升层级
)
type Node struct {
val int // 节点存储的整数值
next []*Node // 每个层级对应的下一个节点指针数组，允许在不同层级上进行快速跳转
}
type Skiplist struct {
head *Node // 跳表的头节点，所有层级的链表都从这里开始
level int // 当前跳表的最高层数，动态变化以适应插入和删除操作
rand *rand.Rand // 用于生成随机数的随机数生成器，确保层级生成的随机性
update []*Node // 预分配用于插入/删除操作的更新数组，存储各层级的前驱节点，减少内存分配次数
}
// 构造函数，初始化跳表
func Constructor() Skiplist {
source := rand.NewSource(time.Now().UnixNano()) // 使用当前时间作为随机种子，确保随机性
return Skiplist{
head: &Node{next: make([]*Node, maxLevel)}, // 初始化头节点的 next 数组，大小为最大层级，初始化时均为 nil
level: 1, // 初始层数为 1，随着时间推移和插入操作可能增加
rand: rand.New(source), // 初始化随机数生成器
update: make([]*Node, maxLevel), // 预分配最大层级大小的更新数组，避免频繁分配
}
}
// 随机生成节点的层级，概率递减
func (sl *Skiplist) randomLevel() int {
level := 1
for sl.rand.Intn(4) == 0 && level < maxLevel { // 使用整数运算模拟概率，当随机数为 0（概率 1/4）时提升层级
level++ // 层级逐步累加，但不超过最大层级
}
return level
}
// 搜索目标值是否存在
func (sl *Skiplist) Search(target int) bool {
curr := sl.head // 从头节点开始搜索
for i := sl.level - 1; i >= 0; i-- { // 从最高层开始逐层向下搜索
for curr.next[i] != nil && curr.next[i].val < target { // 向后移动到第一个大于或等于 target 的节点
curr = curr.next[i]
}
if curr.next[i] != nil && curr.next[i].val == target { // 如果找到目标值，立即返回 true
return true
}
}
return false // 搜索完所有层级仍未找到目标值
}
// 插入一个新值到跳表
func (sl *Skiplist) Add(num int) {
curr := sl.head
// 重置 update 数组为当前各层的前驱节点
for i := sl.level - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].val < num { // 找到插入位置的前驱节点
curr = curr.next[i]
}
sl.update[i] = curr // 保存当前层的前驱节点到 update 数组
}
level := sl.randomLevel() // 根据概率生成新节点的层级
if level > sl.level { // 如果新节点的层级超过当前最高层级
// 扩展 update 数组以覆盖新增的高层级，初始化为头节点
for i := sl.level; i < level; i++ {
sl.update[i] = sl.head
}
sl.level = level // 更新跳表的最高层级
}
// 创建新节点，并初始化其 next 指针数组
newNode := &Node{
val: num,
next: make([]*Node, level),
}
// 将新节点插入到各层的合适位置
for i := 0; i < level; i++ {
newNode.next[i] = sl.update[i].next[i] // 新节点的 next 指向原前驱的 next
sl.update[i].next[i] = newNode // 更新前驱的 next 指向新节点
}
}
// 从跳表中删除一个值
func (sl *Skiplist) Erase(num int) bool {
curr := sl.head
var target *Node // 用于存储待删除的节点
// 查找待删除节点的前驱节点，并保存到 update 数组
for i := sl.level - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].val < num { // 找到前驱节点
curr = curr.next[i]
}
sl.update[i] = curr // 保存前驱节点
}
// 检查最低层是否存在目标节点
if curr.next[0] != nil && curr.next[0].val == num {
target = curr.next[0] // 获取目标节点
} else {
return false // 目标值不存在，返回 false
}
// 更新各层的指针，跳过目标节点
for i := 0; i < sl.level; i++ {
if sl.update[i].next[i] != target { // 如果当前层的后继不是目标节点，停止更新
break
}
sl.update[i].next[i] = target.next[i] // 更新前驱的 next 指针，跳过目标节点
}
// 快速调整有效层级
for sl.level > 1 && sl.head.next[sl.level-1] == nil { // 如果最高层的下一个节点为空，减少层级
sl.level--
}
return true
}总结
有意思的跳表，LevelDB 以及RocksDB内部的 MemTable 都是使用了跳表，可以多看看这些源码学习一下跳表的多种应用~
Comments NOTHING