Skip to main content

Redis的ZSet底层是怎么实现的？

作者：程序员马丁

在线博客：https://open8gu.com

note

大话面试，技术同学面试必备的八股文小册，以精彩回答应对深度问题，助力你在面试中拿个offer。

回答话术​

1. 压缩列表​

在数据量比较小的时候，Redis 会使用压缩列表作为实现方式。具体条件如下：

  • 当元素数量小于 zset-max-ziplist-entries 时（默认为 128）。
  • 当每个元素大小都小于zset-max-ziplist-value 时（默认为 64 字节）。

压缩列表是一种类似于数组的数据结构，以一段连续的内存空间存储数据。每个节点都占用相邻一小段内存，节点之间通过内存偏移量而非指针记录相对位置。这种结构能以最少内存保存尽可能多的数据。不过，由于压缩列表结构的特殊性，对某个节点的修改可能会导致后续节点的级联更新。因此，Redis 在未来计划采用紧凑列表替代压缩列表。

具体参照：✅ Redis 的压缩列表是什么？

2. 跳表+字典​

另一种实现方式是跳表+字典，这种实现用于处理较大的数据集。在这种实现方式中，Redis 使用跳表的节点保存指向 member 的指针和 score，同时又使用了字典保存 member 和 score 之间的对应关系，以便同时实现高效的随机查找和范围查找。

回到跳表本身，它是一种多级链表数据结构，它通过额外的索引层实现快速查找，使查找和插入操作的复杂度为 O(logN)。跳表的层数会影响操作的效率，因此 Redis 使用了一种随机算法来生成节点的层高，从而保证索引层节点密度从底层到顶层逐渐减少。

相对于具有相似查找效率的二叉树，跳表占用的内存更少，对范围操作的支持更好，修改的代价更小，并实现更简单。

具体参照：✅ Redis 的跳表是什么？

Table of Contents