跳表SkipList：为什么Redis选择它而不是红黑树？
引言 你是否好奇：为什么Redis的有序集合（ZSet）能在O(logN)时间内完成插入、删除、查找和范围查询？为什么Redis选择跳表（SkipList）而不是更常见的红黑树或AVL树？ 今天我们深入剖析跳表的设计思想和实现细节，理解这个优雅而高效的数据结构。 一、从问题出发：有序集合的需求 1.1 ZSet的典型操作 # 添加元素（带分数） 127.0.0.1:6379> ZADD ranking 95 "张三" 88 "李四" 92 "王五" (integer) 3 # 按分数范围查询 127.0.0.1:6379> ZRANGEBYSCORE ranking 90 100 1) "王五" # 92分 2) "张三" # 95分 # 查询排名 127.0.0.1:6379> ZRANK ranking "李四" (integer) 0 # 第0名（分数最低） # 删除元素 127.0.0.1:6379> ZREM ranking "李四" (integer) 1 1.2 性能需求 操作 时间复杂度要求 插入元素 O(logN) 删除元素 O(logN) 查找元素 O(logN) 范围查询 O(logN + M)，M为结果数量 获取排名 O(logN) 1.3 候选数据结构 数据结构 插入/删除/查找 范围查询 实现复杂度 内存占用 有序数组 O(N) O(logN + M) 简单 低 平衡二叉树（AVL/红黑树） O(logN) O(logN + M) 复杂 中 B树/B+树 O(logN) O(logN + M) 复杂 中 跳表（SkipList） O(logN) O(logN + M) 简单 中 Redis选择跳表的理由： ...