✅ZSet为什么在数据量少的时候用ZipList,而在数据量大的时候转成SkipList?

✅ZSet为什么在数据量少的时候用ZipList,而在数据量大的时候转成SkipList?

典型回答

✅Redis中的Zset是怎么实现的?

通过上文我们知道,在 Redis 中,ZSet在特定条件下会使用ZipList作为其内部表示。这通常发生在有序集合较小的时候**,默认情况下,当元素数量少于128,每个元素的长度都小于64字节的时候,使用ZipList(ListPack),否则,使用SkipList!**

Redis 之所以在数据量少的时候使用ZipList(包括后来的ListPack),而在数据量大时转成SkipList(跳表),是出于 内存优化性能考量 的双重目的。

内存对比

首先ZipList是一个压缩的数据结构,它的每个元素都是连续存储的(和数组有点像),因此内存的使用非常紧凑。与其他数据结构相比,ZipList在小规模数据存储时显著减少了内存占用。

而在内存方面,SkipList 相比于 ZipList 内存开销要大得多,因为它是通过多个链表层级来实现的,每个元素需要额外的指针来维护层级结构。

那么按理说,ZipList的内存占用要比Skip要小的,所以他更适合用来存储数据,所以ZSet会使用ZipList,那为啥不全都用,而只有在数据量小的额时候采用呢?

这就涉及到ZipList的一个缺点了。

性能对比

前面说过了ZipList 是一个紧凑的线性结构,所以如果在 ZipList 中查找一个元素时,可能需要遍历整个列表,同理插入和删除操作也是线性的。所以它的插入、删除和查找操作的时间复杂度通常是 O(N)。


而SkipList 采用多级索引结构,它的查找、插入、删除操作的时间复杂度是 O(log N),远远优于 ZipList 的 O(N)。

总结

所以,ZipList的存储更节省空间,而SkipList的操作性能会更好。

所以,对于少量数据,ZipList更好,因为它的内存开销很小,而且性能也可以接受(N越小,logN和N的差别更小)。但是当数据量大到一定程度时,SkipList的 O(log N) 性能会显著优于ZipList 的 O(N) 性能,尤其是涉及到范围查询和顺序遍历时。


所以,默认情况下,当元素数量少于128,每个元素的长度都小于64字节的时候,ZSet使用ZipList(ListPack),否则,使用SkipList!