跳表

引言 你是否好奇：为什么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选择跳表的理由： ...

引言 前面我们学习了Set（无序、唯一），今天要学习有序且唯一的ZSet（Sorted Set）。 想象一下这些场景： 🏆 游戏排行榜：按分数从高到低排序，实时更新 🔥 热搜榜：按热度值排序，展示TOP 10 ⏰ 延迟队列：按时间戳排序，到期自动执行 💰 按价格筛选：查询1000-5000元的商品 这些场景的共同特点是：需要排序、需要快速查询范围。ZSet正是为此而生，它是Redis中最强大、最复杂的数据类型。 一、ZSet的本质 1.1 什么是ZSet？ ZSet（Sorted Set）是一个按分数排序的有序集合： ZSet: { (member1, score1), (member2, score2), (member3, score3), ... } 特点： - 有序：按score从小到大排序 - 唯一：member不能重复 - 分数可重复：多个member可以有相同score - 支持范围查询：按score或按排名查询 示例： # 添加元素（member:score） 127.0.0.1:6379> ZADD leaderboard 100 "张三" 95 "李四" 92 "王五" (integer) 3 # 按分数从低到高查询 127.0.0.1:6379> ZRANGE leaderboard 0 -1 WITHSCORES 1) "王五" 2) "92" 3) "李四" 4) "95" 5) "张三" 6) "100" # 按分数从高到低查询 127.0.0.1:6379> ZREVRANGE leaderboard 0 -1 WITHSCORES 1) "张三" 2) "100" 3) "李四" 4) "95" 5) "王五" 6) "92" 1.2 ZSet vs Set 特性 Set ZSet 有序性 无序 有序（按score） 唯一性 元素唯一 元素唯一 分数 无 有 范围查询 不支持 支持 排名查询 不支持 支持 时间复杂度 O(1) O(log n) 适用场景 去重、标签 排行榜、范围查询 1.3 底层实现：跳表（Skiplist） ZSet底层使用**跳表（Skiplist）+ 哈希表（Hashtable）**实现： ...