Redis学习，QuickList vs 跳表 区别

先给定调：两者都是「优化普通链表」的结构，但用途完全不一样——QuickList解决“内存浪费+操作卡顿”，跳表解决“查找太慢”，记住这句话，看完直接分清。

1. QuickList：普通链表的「内存省+不卡顿」优化版

先想两个痛点，小白也能懂：

• 普通双向链表：每个元素都带2个指针（前后指向），内存浪费多，而且元素散落在内存各处，CPU读取慢；

• 纯Ziplist（紧凑列表）：所有元素挤在一块连续内存，内存超省，但元素多了之后，插入/删除要挪动一整块内存，巨卡。

QuickList的核心操作：把大的Ziplist切成一个个小Ziplist，再用双向链表串起来，相当于“分袋装东西”。

大白话特点（小白重点记）：

• 不用记复杂算法，它没有索引，查找还是“挨个遍历”，但比普通链表快（因为小Ziplist是连续内存，CPU一次能读一堆）；

• 主打「头尾操作快」（比如往开头加元素、往结尾删元素），适合做队列、栈（Redis的List底层就是它）；

• 不要求元素有序，怎么存都可以，核心是“省内存、不卡顿”。

极简结构（文字版，一眼懂）：

双向链表 → 小Ziplist1（元素1-10） → 小Ziplist2（元素11-20） → 小Ziplist3（元素21-30）

2. 跳表：普通链表的「查找加速器」（链表版二分）

痛点：普通链表找元素，只能从头一个个挪，比如找第1000个元素，要挪1000次，太慢。

跳表的核心操作：给有序链表建“多层索引”，相当于给链表修了“高架桥”，不用一步步挪，能大步跳着找。

大白话特点（小白重点记）：

• 必须有序！无序的话，索引没用（就像高架桥没路标，没法跳）；

• 查找逻辑和二分一样：从最高层索引开始跳，跳不过去就降一层，直到找到目标（比如找第1000个元素，可能只需要跳10次）；

• 插入、删除也快：先靠索引快速找到位置，再改指针（不用挪内存），整体速度和红黑树差不多，但实现更简单；

• 高层索引靠“抛硬币”随机建（50%概率往上建一层），不用复杂操作，天然平衡。

极简结构（文字版，一眼懂）：

层3（高架桥）：1 → 100 → 1000
层2（主干道）：1 → 10 → 50 → 100 → 500 → 1000
层1（小路）：1 → 5 → 10 → ... → 1000
底层（原始链表）：所有元素依次排列

3. 两者核心区别（一句话分清）

• 用途不同：QuickList管“省内存、不卡顿”，主打头尾操作；跳表管“快速查找”，主打有序查询、范围查询；

• 索引不同：QuickList无索引，只能挨个遍历；跳表有多层索引，能跳着找；

• 有序性：QuickList可无序，跳表必须有序；

• 速度：QuickList头尾操作O(1)，查找O(n)；跳表查找、插入、删除都是O(logn)。