请解释跳表的结构与复杂度,以及相比红黑树在 Redis 场景下的优势。
跳表:多层有序链表,底层包含全部元素,上层是下层的"快速通道"索引;节点以随机概率(Redis 中每层晋升概率 1/4,最高 32 层)决定层高。查找/插入/删除均 O(logN)(从顶层往下逐层缩小范围),范围查询沿底层链表顺序走。
相比红黑树:
相比 B+ 树:B+ 树为磁盘页设计(减少 IO),而 Redis 全内存、无 IO 压力;跳表实现更轻。
补充:ZSet 元素少时(≤128 且元素短)实际用 listpack 存储,跳表只在数据量上来后启用——"小数据走压缩编码"是 Redis 的通用设计。
题目与答案就在本页;收藏、批注和错题重练在应用内