跳表与索引

• 跳表节点结构（score、member、level 数组、span、backward）
• backward 指针用于逆序/倒序遍历
• zslRandomLevel 的 p 参数选择

Redis ZSET 的跳表节点包含 score（排序键）、member（成员）、level 数组（每层 forward 指针和 forward 跨过的节点数 span）、backward 指针（指向同一层前驱，用于逆序 range 查询和便于删除）。分数相同按 member 字典序比较。backward 指针使 Redis 能方便地倒序遍历（ZREVRANGE）和定位前驱。zslRandomLevel 按概率 p 决定是否提升层数：Redis 用 p=1/4（约 25%），使期望层数约 1/(1-p)=4/3，节点层数小、内存省，同时保证查找 O(log n)；p=1/2 则层级更密、查找更快但内存翻倍。p=1/4 是内存与速度的折中。

span 字段让 Redis 能 O(1) 计算排名（rank）；backward 支撑逆序操作。p=1/4 降低平均层数（内存），因为 Redis 里跳表主要用于有序集合，内存开销敏感，而 p=1/2 多用于理论最简模型。zslRandomLevel 上限 32 层。

• 逐层下降的搜索路径
• 插入时随机确定层数并更新前驱
• 删除时更新所有层的前驱指针

查找：从最高层头节点开始，逐层向右移动（当前层下一个节点值 ≤ 目标则右移），该层不能右移则降到下一层，最终在底层找到或确认不存在。插入：先按查找路径找到各层的前驱，随机生成新节点层数（按几何分布），更新各层前驱的 forward 指针指向新节点，并更新 span。删除：找到各层前驱，把各层指向被删节点的 forward 指针跳过它，更新 span。节点层数随机化决定节点出现在哪些层，从而决定搜索路径经过哪些层；层数越高，跳过越远，查找越快。

搜索路径是"每层尽量右移、再下降"的贪心，层数随机化保证期望 O(log n)。插入/删除都要维护所有受影响层的指针，前驱数组存各层前驱。随机层数越高，跨越的节点越多，路径越短。

• 搜索路径的层数与步数分析
• 期望 O(log n) 的证明
• Chernoff bound 的高概率界

跳表节点层数按几何分布，期望层数 1/(1-p)。最大层数约为 O(log_{1/p} n)。搜索路径从顶层开始，每层向右移动若干步再下降。按"反向"分析：从目标节点向上回溯，每层经过的节点数期望为常数，因此总步数期望 = 层数 × 常数 = O(log n)。更严格地，设每层步数期望为常数，总期望步数 O(log n)。高概率界：用 Chernoff bound 证明某层节点数不超过 O(log n) 的概率为 1-1/n^c，从而搜索路径长度高概率为 O(log n)。推导基于每层节点数的二项分布（每个节点独立以概率 p 进入上一层），Chernoff 界给出偏离期望的对数界。

期望 O(log n) 由"层数期望 + 每层常数步"得出；高概率界用层数上的二项分布 + Chernoff 界，说明路径长度几乎不会超过 O(log n)。这使跳表在概率上达到平衡 BST 的查找性能。

• 范围查询的比较
• 实现复杂度差异
• 并发友好性

跳表与红黑树都支持 O(log n) 查找/插入/删除。范围查询：跳表本质是多层有序链表，底层是有序链表，范围查询可直接沿底层链表线性扫描，实现简单、缓存友好；红黑树范围查询需要中序遍历，实现较复杂。实现复杂度：跳表实现简单（无需维护旋转/颜色），红黑树实现复杂（旋转、变色、case 分析）。并发友好性：跳表易做无锁并发（lock-free 跳表，如 ConcurrentSkipListMap），因为它用局部指针 CAS 更新；红黑树并发更新涉及全局旋转，难做无锁。因此跳表在范围查询、实现、并发上都更友好，用内存略多换实现简单。

跳表以"额外层指针 + 随机化"换取实现简单与并发友好，底层有序链表天然支持范围查询；红黑树保证最坏 O(log n) 但实现复杂、并发难。工程上（如 Java 并发容器）倾向跳表。

• 跳表支持范围查询、哈希支持 O(1) 点查
• 哈希无法有序遍历
• Redis 哈希 + 跳表互补

哈希索引（如 Redis 的 dict）支持 O(1) 精确点查，但不支持范围查询、无法有序遍历。跳表底层是有序链表，支持范围查询（ZRANGE）、排名、有序遍历，但点查是 O(log n)。因此：只做精确点查选哈希，需要范围/有序操作用跳表。Redis 中两者互补：ZSET 同时用 dict（存 member→score，O(1) 查分数）和跳表（存 score 有序结构，支持范围操作），dict 加速点查、跳表加速范围与排名，充分发挥各自优势。

Redis 的哈希表提供 O(1) 的 member→score 映射和按 member 更新，跳表提供有序的 score 索引支持范围查询。二者结合覆盖"点查 + 范围"两种访问模式，是哈希与有序索引互补的典型设计。

• 层数的几何分布 P(level=i)
• 期望指针数（每节点期望 1/(1-p)）
• 总空间 O(n/(1-p))

跳表节点层数按几何分布：P(level=i) = p^(i-1)(1-p)，即节点至少 i 层的概率为 p^(i-1)。期望层数 = Σ i·p^(i-1)(1-p) = 1/(1-p)，即每个节点期望指针数也是 1/(1-p)（每层一个 forward 指针）。n 个节点的总期望指针数 = n/(1-p)，总空间 O(n/(1-p))。p=1/2 时每节点约 2 个指针，空间 O(2n)；p=1/4 时约 4/3 个指针，空间更省。时间复杂度期望 O(log n) 由层数期望与每层常数步得出。

几何分布是"持续以概率 p 提升、否则停止"，P(level=i) 即前 i-1 次成功、第 i 次失败。期望指针数 1/(1-p) 决定空间；p 越小指针越少、内存越省，但层数少、查找略慢。p 是空间与速度的权衡参数。

• 层数随机化（几何分布）
• 期望层数 1/(1-p)
• 最大层数 O(log_{1/p} n)

跳表插入时随机生成节点层数：从 1 开始，每层以概率 p 继续提升，否则停，即层数服从几何分布 P(level)=p^(level-1)(1-p)。期望层数 = Σ i·p^(i-1)(1-p) = 1/(1-p)，是常数。对于 n 个节点，某一层节点数期望为 n·p^(level-1)，层数达到 k 的节点数期望为 n·p^(k-1)。要使最大层数足够高覆盖 n 个节点，令 n·p^(k-1)≈1，得 k≈log_{1/p} n，即最大层数 O(log_{1/p} n)。因此搜索路径层数期望 O(log n)。

几何分布的平均层数是常数，但为了快速跳过，需要"某些节点"有较高层，最大层数要达到 O(log n)，这样从顶向下搜索才能跨越多个节点。期望层数恒定 + 最大层数对数，共同支撑 O(log n) 查找。

• 实现复杂度对比
• 范围查询与并发
• Redis 选择跳表的原因

跳表与红黑树查找/插入/删除都是 O(log n)。实现复杂度：跳表简单（随机层数 + 多层链表），红黑树复杂（旋转、变色、多 case）。范围查询：跳表底层是有序链表，范围查询直接线性扫描，实现简单；红黑树需中序遍历。并发友好性：跳表易做无锁并发（指针局部 CAS），红黑树难。Redis 选择跳表而非红黑树的原因：实现简单易维护、范围查询（ZRANGE/ZREVRANGE）效果好、内存开销可接受，且无需像红黑树那样维护复杂平衡。虽然红黑树最坏 O(log n) 有保证，但跳表概率上已足够且更实用。

Redis 的 ZSET 需要频繁的范围查询和排名操作，跳表天然支持；实现简单降低维护成本；并发（虽然 Redis 单线程）和无锁扩展也受益。跳表以略微增加的内存换取实现简单与范围查询便利。

• 几何分布的概率质量函数
• 期望层数推导（调和级数）
• 最大层数推导

跳表生成层数时，从第 1 层开始，每层以概率 p 提升，得到 level 的分布为 P(level=i)=p^(i-1)(1-p)，i≥1。期望层数 E[level] = Σ_{i≥1} i·p^(i-1)(1-p) = 1/(1-p)（几何分布的期望）。最大层数：n 个节点中层数 ≥ k 的期望个数为 n·p^(k-1)，令其约等于 1，得 k ≈ log_{1/p}(n)+1，故最大层数 O(log_{1/p} n)。p=1/2 时最大层数约 O(log2 n)，p=1/4 时约 O(log4 n)（层更少）。

几何分布刻画"成功次数"：连续提升 i-1 次后停止。期望 1/(1-p) 是常数，说明平均节点层数不大；但要保证高节点的存在以维持快速查找，最大层数需达到对数级。二者结合给定期望 O(log n) 查找。

• span 字段的含义与累加
• rank 查询的 O(log n) 过程
• member 反向查找（借助 dict）

Redis 跳表节点的 level 数组里，每个 forward 指针记录 span（该指针跨过的节点数）。查找排名（rank）时，从最高层头节点出发，沿搜索路径累计每层右移的 span，到达目标节点时累计值即该节点的排名（rank），O(log n)。反向查找：member → score 的查找不在跳表里做（跳表按 score 排序，无法按 member 直接定位），而是借助哈希表 dict（member→score），O(1)。若需在跳表中按 member 反向定位，需遍历，代价 O(n)，所以 Redis 用 dict 支持 member 到 score/rank 的反向映射。

span 使排名查询无需遍历底层，沿路径累加 span 即得 rank。member 反向查找之所以用 dict，是因为跳表只按 score 有序，member 无索引；dict 提供 O(1) 的 member→score 映射，配合跳表实现完整功能。

• 贪心搜索的正确性
• 层间下降的指针不变量
• 不变量保证不漏目标

跳表查找从最高层头节点开始，每层向右移动直到下一个节点值大于目标（或到末尾），然后下降一层重复。这个贪心不会错过目标，因为维护的不变量是：当前节点 x 满足 x.val ≤ 目标，且 x 所在层的下一个节点（forward）值 > 目标。每层内向左不超过目标，下降一层后继续从 x 出发，底层最终会定位到目标节点或恰好小于它的前驱。由于底层是有序链表，逐层收窄的区间最终收敛到目标，故不会遗漏。

不变量"当前节点 ≤ 目标 < 当前节点在该层的后继"保证每层都卡在目标左侧，下降后区间逐步收窄，最终在底层找到目标或其前驱。贪心正确性由该不变量在每层下降时保持而保证。

• 删除时找各层前驱
• 更新各层 forward 指针与 span
• 与插入的对称性

删除节点时，先沿查找路径记录各层前驱（update 数组），然后从第 1 层到被删节点所在的最高层，把每个前驱的 forward 指针从被删节点改为其下一个节点，并更新 span（被删层 span 减 1 或按定义调整）。对于被删节点未出现的层，前驱的 forward 不变但 span 需减 1（因为底层跨过的节点数减少）。删除后可能需要调整头节点层数（若最高层空）。删除过程与插入对称：插入是"在各层前驱后插入新节点、更新 span 加 1"，删除是"从各层前驱后移除节点、更新 span 减 1"，两者都基于 update 数组维护各层指针。

遍历时记录各层前驱是关键，删除时逐层把 forward 跳到被删节点的后继。与插入对称：插入在各层前驱后连上新节点，删除在各层前驱后跳过被删节点。边界（最高层、头节点）需特殊处理。

• 期望指针数 1/(1-p) 的推导
• p=1/2 时每节点 2 个指针
• p=1/4 与 p=1/2 的取舍

每节点层数期望 1/(1-p)，每层一个 forward 指针，故期望指针数 = 1/(1-p)。当 p=1/2 时，期望指针数 = 1/(1-1/2)=2，即每节点平均约 2 个指针，总空间约 2n 个指针。p=1/2 层级密集、查找更快（每层步数少），但内存翻倍；p=1/4 时期望指针数 1/(1-1/4)=4/3≈1.33，内存更省，但层数少、查找略慢。取舍：内存敏感（如 Redis）用 p=1/4，追求速度或理论简单用 p=1/2。p 越小指针越少、越省内存，但查找路径略长。

期望指针数随 p 增大而增大（p=1/2 时 2，p=1/4 时 4/3），是 p 的增函数。p=1/2 是经典理论选择（每节点 2 指针推导最简单），p=1/4 是工程折中。空间与速度的权衡通过 p 调节。

• 跳表与 B+Tree 的空间复杂度
• 缓存表现与实现复杂度
• 内存数据库场景的取舍

跳表空间 O(n log n)（期望 O(n) 指针），B+Tree 空间 O(n) 但节点按层组织。跳表在内存数据库（Redis、LevelDB MemTable）中优于 B+Tree 的原因：1）实现简单，无需 B+Tree 复杂的节点分裂/合并与页管理；2）在内存中，指针跳转比缓存块读取更自然，B+Tree 的块缓存优势在磁盘上明显、在内存中多基于指针；3）跳表易于并发与无锁实现，适合内存 KV；4）查找/插入 O(log n) 已足够，且插入无需维护分裂。LevelDB 的 MemTable 用跳表正因为实现简单、O(log n) 且适合内存有序结构。

B+Tree 的优势在磁盘场景（高扇出、缓存块、减少 IO），内存中跳表的指针结构更简单、更易实现无锁并发。内存数据库把数据放内存，跳表的实现简单与并发优势超过 B+Tree 的块缓存优势。

• hand-over-hand locking 的串行锁传递
• lock-free CAS 与 ABA 问题
• RCU 读优化与适用场景

per-node lock coupling（hand-over-hand locking）：搜索时逐节点加锁、释放上一个节点后锁下一个，保证区间不被并发修改，简单但锁开销大、并发度低，适合写多读少的场景。乐观锁（lock-free with CAS）：用 CAS 原子更新指针，无锁读，写操作冲突时重试，并发度高，但需要处理 ABA 问题（节点被复用导致指针值相同而状态改变），可用标记指针/版本号/延迟回收解决，适合高并发读多写多。RCU（Read-Copy-Update）：读操作不加锁、直接读共享结构，写操作复制后修改再原子发布，老版本待无读者后再回收，适合读远多于写、且读路径不能阻塞的场景（如内核、网络转发）。读优化把读开销降到最低。

三种策略权衡锁粒度与并发度：hand-over-hand 锁简单但串行；CAS 无锁并发高但实现复杂且有 ABA；RCU 极致读优化但写需复制、回收延迟。按读写比例和延迟要求选择。ABA 是并发跳表（尤其无锁）的核心难点，需标记/回收机制解决。

• MemTable 选跳表的原因
• 写放大与读放大权衡
• immutable 快照与 Iterator pin

LevelDB/RocksDB 的 MemTable 用跳表，因为：内存有序结构需要支持范围查询、插入 O(log n)，跳表实现简单、并发友好（LevelDB 用锁保护，RocksDB 用无锁跳表支持并发写）。写操作先进 MemTable（内存），写放大低（不立即落盘）；读操作先查 MemTable 再查磁盘 SStable，读放大由 LSM 分层控制。immutable 快照机制：MemTable 写满后转为 immutable MemTable，通过 Iterator pin 固定迭代器引用，保证迭代期间结构不被 GC/回收，同时支持并发迭代。对比 B+Tree memtable：B+Tree 查询/扫描也 O(log n)，但实现复杂、需处理分裂，且内存里 B+Tree 的块缓存优势不明显；跳表实现简单、易做并发与 immutable，故 LSM 的 MemTable 普遍选跳表。

MemTable 是内存缓冲，跳表提供有序 + 简单实现 + 并发的结合。写放大主要由磁盘合并（compaction）决定，MemTable 用跳表不减写放大，但保证内存有序。immutable 快照 + Iterator pin 让只读快照与并发写共存。B+Tree 更适合磁盘持久存储，内存 MemTable 用跳表更合适。

• B+Tree 适合磁盘、跳表适合内存
• 实现复杂度与并发
• LSM MemTable 选跳表的原因

B+Tree 是磁盘数据库的主流索引：高扇出、节点按页存储、缓存友好，减少磁盘 IO，适合持久化。跳表是内存索引：实现简单、支持范围查询、易并发无锁，但指针多、缓存不友好，不适合磁盘。LSM 的 MemTable 是内存中的有序缓冲，选跳表而非 B+Tree：1）内存中跳表实现简单，无需 B+Tree 的页分裂/合并；2）跳表易做无锁并发与 immutable 快照；3）MemTable 不是磁盘结构，不依赖 B+Tree 的块缓存优势；4）跳表 O(log n) 范围查询已满足。B+Tree 用于磁盘的 SStable/持久索引，MemTable 用跳表，两者各司其职。

B+Tree 的优势来自磁盘页面（减少 IO、缓存块），内存中无此需求；跳表的简单与并发优势在内存凸显。LSM 把"内存有序缓冲（跳表）+ 磁盘有序文件（B+Tree/SSTable）"结合，MemTable 选跳表是"内存用简单结构、磁盘用块友好结构"的合理分工。