S03-X03 · 跳跃表与平衡树：Redis 为什么选跳表

既要有序，又要按区间取数，还要多线程同时改。跳表和平衡树都能做到，渐近复杂度都在 O(log n) 量级。Redis 的 ZSet 选跳表，LevelDB 的 memtable 选跳表，JDK 的 ConcurrentSkipListMap 也选跳表，TreeMap 却守着红黑树——差别不在复杂度，在实现常数、区间操作、并发可写性与指针开销。

1. 多层索引结构与查找路径

底层（level 0）是全量有序链表，越往上越稀疏。

L3  head ─────────────────► 42 ────────► NULL
L2  head ───────► 17 ──────► 42 ────────► NULL
L1  head ─► 9 ─► 17 ─► 25 ─► 42 ─► 55 ──► NULL
L0  head ─► 9 ─► 12 ─► 17 ─► 25 ─► 31 ─► 42 ─► 55 ─► NULL

查 31（能右移就右移，越界就降一层）：
L3 head→42  42 > 31，降层
L2 head→17  17 ≤ 31 右移；下一个 42 越界，降层
L1 17→25    25 ≤ 31 右移；下一个 42 越界，降层
L0 25→31    命中

每降一层，候选区间被压缩到上一层节点间距内，缩小倍率即升层概率 p 的倒数。访问节点数正比于层数，不随链表长度线性增长。

一句话选择：跳表把"平衡"从结构约束换成概率约束，代价是层数随机，收益是不用旋转。

2. 期望层数与随机化设计

抛硬币定层数，命中 p 就再升一层，直到失败或撞上限。

/* 生成新节点层数，p = 1/4，最高 32 层。值按 Redis 7 源码口径 */
#define ZSKIPLIST_MAXLEVEL 32   /* 上限，Redis 7 文档：可覆盖 2^32 个元素 */
#define ZSKIPLIST_P 0.25

int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P * RAND_MAX;
    int level = 1;
    while (random() < threshold)     /* 命中 1/4 就再升一层 */
        level += 1;
    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

层数 ≥ k 的概率是 p^(k-1)，故平均层数 1/(1-p)，这个值同时决定内存放大与查找期望步数。

`p`	平均层数	第 k 层占比	取舍
1/2	2	1/2^(k-1)	查找快，指针翻倍
1/4（Redis）	4/3	1/4^(k-1)	省空间，仍对数级
1/8	8/7	1/8^(k-1)	更省，降层多

随机化给的是"大概率平衡"：期望 1.33 层、期望 O(log n)；最坏情况（层数全为 1，退化成单链表）概率极低但非零。层数只由随机数决定、与 key 分布无关，没有一组恶意输入能构造出退化形态。32 层是硬上界，防无界膨胀，同时远超单机内存的元素规模。

3. Redis 的 ZSet 为什么用跳表而不是红黑树

ZSet 要的不只是有序：区间取、排名取、按排名算、逆序走、并发快速读。

需求	跳表做法	红黑树难点
`ZRANGEBYSCORE`	定位起点后沿 level 0 右扫，成本正比结果集	需中序后继或回溯
`ZREVRANGE`	`backward` 指针直接走	父指针或栈
`ZRANK`	forward 带 `span`，路径累加即得排名	需维护子树 size 并随旋转更新
无锁改造	只改局部指针 + CAS	旋转牵动祖父、兄弟、颜色位

/* Redis 7：有序集合的跳表结构 */
typedef struct zskiplistNode {
    sds ele;                        /* 成员；score 相同再比 ele */
    double score;                   /* 分值，排序主键 */
    struct zskiplistNode *backward; /* 只存 level 0，支撑逆序遍历 */
    struct zskiplistLevel {
        struct zskiplistNode *forward;  /* 本层前进指针 */
        unsigned long span;             /* 跨度：跨过多少节点，用于算排名 */
    } level[];                      /* 柔性数组，层数创建时随机定 */
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  /* header 含 MAXLEVEL 个空层 */
    unsigned long length;                 /* 节点数，不含 header */
    int level;                            /* 当前最大有效层数 */
} zskiplist;

span 让排名复用查找路径，不必第二套结构；backward 只存一份，逆序是 O(1) 步进。

一句话选择：需要"区间 + 排名 + 逆序 + 局部改动即可并发化"，跳表的实现常数低一档。

4. 跳表 / 平衡树 / B+ 树三方对照

维度	跳表	平衡树	B+ 树
范围查询	定位后顺链表扫	需中序后继，跨子树跳	叶子链扫，最优
实现复杂度	低，只改邻居指针	高，旋转 + 颜色位	中高，分裂合并
缓存友好	一般，节点随机	差，树高跳动	好，整块读
并发友好	好，改动局部	差，常需整树锁	中，页级闩
常数因子	多走 `1/p` 倍节点，每步极简	节点少但每步重	节点最少，代价在 IO
有序遍历	优，仅 level 0	中，需遍历状态	优
外存适用	差，随机 IO	差	专为磁盘设计

内存里比实现与并发，磁盘上比 IO 次数。

5. LevelDB / RocksDB memtable 中的角色

写路径：写 WAL 保不丢 → 写 memtable（内存有序表）→ 满了冻结成 immutable memtable → 后台刷成 SST → 读时按 memtable、immutable、各层 SST 依次查。memtable 要三者兼得：内存可控、写入无全局锁、能顺序导出。

/* LevelDB 风格 memtable 插入：无需平衡，只做指针接驳（伪代码） */
Node* prev[kMaxHeight];                /* 每层直接前驱 */
FindGreaterOrEqual(key, prev);         /* 从最高层向下定位 */
int height = RandomHeight();           /* kBranching = 4 → p = 1/4 */
if (height > GetMaxHeight()) {
  for (int i = GetMaxHeight(); i < height; i++)
    prev[i] = head_;                   /* 前驱即头节点 */
  max_height_.store(height, relaxed);
}
Node* x = NewNode(key, height);        /* arena 分配，避免逐次 malloc */
for (int i = 0; i < height; i++) {
  x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
  prev[i]->SetNext(i, x);              /* 只接指针，不改动已有节点形态 */
}

RocksDB 做成可选项：默认 SkiplistMemTable，另有 HashSkipListMemTable（前缀分桶）、VectorMemTable（批量导入）；allow_concurrent_memtable_write 靠"只改局部指针"支持多线程并发插入。

一句话选择：memtable 要"无锁写 + 顺序导出"，跳表两样都给，B+ 树两样都不给。

6. 复杂度与空间开销

操作	期望	最坏	说明
查找（含区间起点）	O(log n)	O(n)	最坏来自层数极端退化
插入 / 删除	O(log n)	O(n)	定层数 + 接指针，不动结构
按排名取数	O(log n)	O(n)	靠 `span` 累加
空间	期望 O(n)	O(n · MAXLEVEL)	上限存在，期望由 `p` 定

指针开销只讲公式：每节点期望层数 1/(1-p)，forward 指针数 ≈ n × 1/(1-p)，另加 n 个 backward、n × (score + ele 指针 + SDS 头) 与对齐损耗。p = 1/4 时系数约 1.33 + 1；对照红黑树固定 2 子指针 + 1 颜色位，不随机。估完按实测核对，公式只判量级。

7. 并发跳表的做法

难点只有一个：新节点要同时进入多层，每层都是"读前驱 next → 写自己 next → CAS 前驱 next"，中途被打断就会被看到半成品。对策：节点先完整造好再发布；每层独立 CAS，失败整轮重试；删除先逻辑标记让查找跳过，再事后摘链。

// 无锁插入骨架（思路对齐 ConcurrentSkipListMap，非其源码）
Node[] preds = new Node[level], succs = new Node[level];
Node node = new Node(key, value, level);      // 1) 先完整构建，再发布

for (;;) {
    findPredecessors(key, preds, succs);      // 2) 找各层前驱/后继
    boolean linked = true;
    for (int i = 0; i < level; i++) {         // 3) 自底向上逐层接驳
        node.next[i] = succs[i];
        if (!preds[i].casNext(succs[i], node)) {  // 前驱变了，整轮重试
            linked = false;
            break;
        }
    }
    if (linked) return node;
    // level 0 一接上即可达；上层缺失只影响速度，不影响正确性
}

红黑树插入触发旋转时要原子地改父指针、子指针和颜色位，这是多变量的联合不变式：用锁省事，用 CAS 得先设计"标记 + 协助完成"协议。跳表把问题降级成若干次独立的单指针 CAS。

一句话选择：单线程两者都行；要无锁并发改，跳表成本低到不是一个量级。

8. Java 里有没有现成跳表

有，JDK 6 起就在 java.util.concurrent 里。"Java 没有跳表"是错误印象。

类	结构	并发语义	适用面
`ConcurrentSkipListMap`	跳表 + CAS 链接	无锁读、CAS 写；迭代器弱一致；`size()` 非常量时间	有序映射、区间取数
`ConcurrentSkipListSet`	内包一个 `ConcurrentSkipListMap`	同上	有序去重集合
`TreeMap`	红黑树	非线程安全；迭代器快速失败	单线程，API 最全
`ConcurrentHashMap`	桶数组（桶内树化）	无锁读 + 节点级 CAS	纯查找，整体不有序

import java.util.concurrent.ConcurrentSkipListMap;

public class ZSetLike {
    public static void main(String[] args) {
        // 天然按 key 有序，范围查询与并发写入可以同时存在
        ConcurrentSkipListMap<Long, String> zset = new ConcurrentSkipListMap<>();
        zset.put(100L, "user:9");
        zset.put(25L, "user:17");
        zset.put(42L, "user:31");

        System.out.println(zset.firstKey());   // 25：最小 score
        // 模拟 ZRANGEBYSCORE：闭区间 [30, 90]
        System.out.println(zset.subMap(30L, true, 90L, true));  // {42=user:31}

        // 模拟 ZRANK：前面有几个键就是 0 基排名；O(n)，别进热路径
        System.out.println(zset.headMap(42L).size());

        // 逆序视图是视图不是拷贝，底层仍是同一张跳表
        System.out.println(zset.descendingMap().firstKey());    // 100
    }
}

TreeMap 迭代器快速失败，并发改直接抛异常；ConcurrentSkipListMap 迭代器弱一致，新增可能看不到但不会崩，且不接受 null。

9. 常见坑

坑	表现	纠正
以为跳表一定比树快	单点查找没变快	复杂度同级，赢在区间与并发
忽略内存放大	内存涨超预期	被提升节点各带一层指针，先估后测
当缓存结构用	想做 LRU/TTL，越写越乱	它是有序索引，不是淘汰策略
以为随机化可复现	用固定种子对齐线上分布	随机源不同即不同，跨版本更难
层级上限不当	太小索引失效，太大白吃内存	按 `log_{1/p}(n)` 加余量
把排名当 O(1)	热路径调 `headMap(k).size()`	Java 侧无 `span` 字段，只能遍历

10. 排错：五类典型现象

现象	可能原因	处理
`ZRANGEBYSCORE` 慢，`ZSCORE` 快	结果集本身大	`LIMIT` 收窄或收紧区间
`ZRANK` 比预期慢	路径长，`span` 累加多	查高频写是否打散了层结构
内存远超元素大小之和	每层指针 + SDS 头 + 对齐	按 `1/(1-p)` 估后实测；看是否越过 `listpack` 阈值
并发插入丢元素或死循环	节点未造完就发布	先造好再发布，每层失败整轮重试
遍历崩或抛异常	快速失败迭代器	换 `ConcurrentSkipListMap`

11. 边界：什么情况本就该用别的结构

场景	更合适	理由
纯点查不要顺序	哈希表	有序维护白付
要严格最坏 O(log n)	平衡树	跳表只有期望保证
数据远超内存	B+ 树	外存比 IO 次数
元素只有几十个	数组 + 二分	索引常数开销不划算
只要前缀分桶	`HashSkipListMemTable`	省掉前缀比较
写多读少	`VectorMemTable`	不在线有序就不建索引
排名查询频繁	Redis `ZSet`	Java 侧无 `span`

一句话选择：有序 + 区间 + 并发写 → 跳表；外存 + 高扇出 → B+ 树；纯点查 → 哈希。

12. 自测

"能右移就右移、越界就降层"为什么是对数级而非线性级？
p = 1/4 时节点平均几层？与内存放大什么关系？
随机化只保证"大概率平衡"，为什么反而更抗最坏输入？
ZRANK 凭什么 O(log n) 出排名？依赖哪个字段，Java 侧有对应物吗？
memtable 不做成平衡树，改无锁写入时省掉了什么？
TreeMap 与 ConcurrentSkipListMap 的迭代器在并发修改下行为差在哪？