Redis里头List怎么读，结构层面来聊聊它的实现细节

不是一种数据结构，而是两种的“组合拳”

首先最核心的一点是，Redis的List并不是由单一的一种数据结构实现的，它会根据当前List存储的数据量、元素的大小等因素，在两种不同的内部编码之间自动切换，这两种编码分别是：ziplist（压缩列表） 和 linkedlist（快速链表），这个设计思想在Redis的开发者们写的书和博客里（Redis设计与实现》）被反复强调,就是为了在内存使用和性能之间取得一个最佳的平衡。

当List还“小”的时候：ziplist（压缩列表）

你可以把ziplist想象成一个非常紧凑的“数组”，但它和普通数组不一样，它是为了节省内存而设计的“特殊数组”。

1. 它的长相：ziplist是一大块连续的内存空间，这块内存里，一个挨着一个地存放着List里的所有元素，比如你执行 LPUSH mylist "Hello" "World"，World”和“Hello”这两个字符串就会紧挨着被塞进这块内存。
2. 怎么节省内存的：普通链表每个节点除了存数据，还要存指向前一个和后一个节点的指针，这些指针本身就要占不少内存，而ziplist完全不要这些指针，因为它靠“偏移量”来寻找下一个元素，每个元素记录了自己占用了多少字节，下一个元素只要把自己的位置加上这个长度，就能找到下一个元素的起始位置，这就好像一排紧挨着的房子，你知道第一间房子的门牌号是1，并且知道每间房子有多宽,你就能轻松找到第N间房子。
3. 代价是什么：这种紧凑带来的问题是，修改操作的代价很高，比如你想在List中间插入一个新元素，那么这个新元素后面的所有元素都需要在内存里“集体向后移动”，腾出空位，如果这个List很大，这个移动操作就会很慢，删除操作也是同理,需要把后面的元素向前移动来填补空缺。
4. 什么时候用：Redis非常聪明，它只在小数据量的时候使用ziplist，具体什么时候算“小”呢？这可以在Redis的配置文件里设置，主要是两个条件：
   • list-max-ziplist-entries：List中元素的个数超过这个值（默认512个）,就会转换。
   • list-max-ziplist-value：List中任何一个元素的值的长度超过这个字节数（默认64字节），就会转换。 只要满足其中一个条件,Redis就会把这个List的底层实现从ziplist转换成linkedlist。

当List“长大”后：linkedlist（快速链表）

这里的linkedlist也不是我们教科书上那种简单的双向链表，Redis对它做了优化，称之为quicklist（快速链表），这个结构是在后续版本中引入的，目的是为了在保留链表修改效率高的优点的同时,尽量减少内存碎片和指针占用的额外空间。

1. 它的长相：quicklist可以理解为是“由多个ziplist连接起来组成的一个双向链表”，也就是说，每个quicklist的节点（node）,本身就是一个小的ziplist。
2. 为什么这么设计：这个设计非常巧妙，它结合了两种结构的优点。
   • 从链表的角度看：因为整体是链表结构，所以在中间插入或删除一个元素时，通常只需要改动一两个节点（小ziplist）内部的指针，而不用像纯ziplist那样大规模移动数据,这保证了修改操作的效率。
   • 从ziplist的角度看：每个节点内部又是一小块连续的ziplist，这意味着在一小段数据范围内，内存依然是紧凑的，减少了普通链表中每个元素都需要两个指针带来的内存开销，多个小ziplist也比一个大ziplist更灵活,避免了在中间修改时巨大的内存拷贝成本。
3. 可以控制的小ziplist：Redis同样允许你配置每个小ziplist的大小（通过list-max-ziplist-size参数），让你可以根据实际应用场景（是偏向于节省内存还是偏向于操作性能）进行微调。

总结一下

当我们谈论Redis的List时，不能把它当成一个静态的东西，它更像一个“智能”的容器：

• 在数据量小、元素体积也小的“童年时期”，它采用ziplist的形式，像个节俭的管家，把东西整整齐齐地码放好,极力节省每一分内存。
• 当它长大成人，数据变多或元素变大后，它就切换为quicklist形态，像一个高效的物流分拣系统，它把货物（数据）分装在许多个小箱子（ziplist）里，再用链条把这些箱子连接起来，这样，既保持了整体结构的灵活性（便于增删改）,又在每个小箱子内部保持了高效的内存使用。

这个动态切换、混合使用的策略，正是Redis能在保证高性能的同时，又非常节省内存的关键设计哲学之一，你通过OBJECT ENCODING yourlistkey这个命令，就可以亲眼看到你的List当前正在使用哪种内部编码,非常直观。