跳表是通过构建分层概率指针网络，将链表查找从o(n)优化至平均o(log n)，其核心为随机层数机制与自顶向下跳跃查找，实现比红黑树更简洁、并发更友好的有序集合。

跳表不是给链表加“一层”索引，而是构建一个分层的、概率驱动的指针网络，让查找从“一步步爬”变成“跨步跳”。它的本质是用可控的额外空间，把链表的 O(n) 查找拉到平均 O(log n)，且实现远比红黑树直观。

多层链表结构：每层都是下一层的“快车道”

最底层（Level 0）是完整的有序单链表，存所有数据节点，比如 1 → 3 → 5 → 7 → 9 → 12 → 17 → 19 → 21 → 25。往上每一层都是稀疏索引： - Level 1 可能只连 1 → 6 → 9 → 17 → 21 - Level 2 进一步精简为 1 → 9 → 21 - Level 3（顶层）可能只有 1 → 21 层级越高，跨度越大，但不强制等距或固定比例；实际中靠随机化生成层数来维持整体平衡。

随机层数机制：避免结构僵化的核心设计

如果每插入一个节点都严格按“每两个节点升一级”，删除时就得频繁重排索引，退化成 O(n)。跳表用概率方式解决： - 每个新节点独立掷硬币（比如 p = 0.5），决定它出现在几层 - 层数为 1 的概率是 50%，为 2 是 25%，为 3 是 12.5%…… - Redis 中最大层数设为 64，但绝大多数节点只在前几层出现 这样既保持了高层索引的稀疏性，又让插入/删除只需局部修改，不牵动全局。

查找过程：自顶向下，边跳边降

查目标值 x 时，不从底层开始扫，而是： - 从最高层头节点出发，沿该层向右走，直到下一个节点 > x，就停下 - 向下落到低一层，从当前节点继续向右找 - 重复直到 Level 0，再做一次精确比对 例如查 21：先在 Level 2 从 1 跳到 9，再跳到 21；发现 21 存在，直接命中。整个过程跳过了中间大量无关节点。

为什么它比平衡树更实用？

跳表的优势不在理论极限，而在工程友好性： - 插入时不用旋转、染色、递归回溯，只需按概率生成层数 + 更新沿途 forward 指针 - 天然支持范围查询（比如 zrange 10 20），遍历某一层就能拿到连续区间 - 多线程场景下，可对不同层加细粒度锁，比树结构更容易并发优化 Redis 选它而非红黑树，正是看重这点——简单、稳定、易维护，且性能不打折扣。