Redis跳表skiplist实现原理面试背景Redis的ZSet有序集合底层就是跳表哈希表哈希表负责去重跳表负责排序、范围查询。1. 原始痛点有序链表普通单向有序链表插入、删除方便查找元素必须从头挨个遍历时间复杂度 O(n)范围查询很慢。跳表的核心思想给有序链表建立多层“索引”空间换时间。2. 跳表原理最底层第0层是完整的有序原始链表保存全部真实数据节点按score从小到大排序。上层是索引层每隔部分节点向上提取节点建成高层索引高层索引节点不存完整数据起到“快速导航”作用。查找流程从最高层索引开始向后找如果下一个节点比目标大就下沉到下一层继续查找逐层缩小范围直到第0层找到目标。类比地铁底层是每一站都停的慢车上层索引是大站快车。想找某个站先坐快车快速接近再下到慢车精确找。3. Redis跳表的关键特性层数随机生成节点新增的时候通过随机算法决定这个节点最高到第几层不是均匀间隔。最大层数默认 32 层。概率每往上一层概率 1/2。这样整体期望层高 logn。查询、插入、删除平均时间复杂度O(log n)。双向链表Redis实现的是双向跳表节点有back后退指针支持反向遍历所以zrevrange倒序查询效率很高。zset同时维护两个结构skiplist按score排序做范围查询、排行榜dict哈希表key存membervalue存scoreO(1)判断元素是否存在、获取score完成去重。4. 插入流程随机确定新节点层数从最高层往下遍历记录每一层需要修改的前驱节点在每一层链表把新节点插入对应位置更新双向指针。删除同理先找到各层前驱节点每层摘除该节点。5. 和平衡树对比面试加分跳表实现简单范围查询强随机层数不需要复杂旋转内存略高。Redis适合。AVL、红黑树平衡维护需要旋转代码复杂单点查找优秀。总结跳表在有序链表基础上建立多层随机索引空间换时间把查找从O(n)降到O(logn)Redis zset的跳表是双向跳表层数随机最高32层搭配dict哈希表一起工作支持排序、范围、反向遍历。口述简短版跳表本质就是给有序链表建多层索引。最底层是完整有序链表上层是索引节点。查找从最高层开始目标太大就下沉下一层快速缩小查找范围。Redis zset用双向跳表节点层数随机生成时间复杂度O(logn)同时搭配哈希表做去重很适合排行榜、范围查询。