Redis压缩列表和跳表

Redis 的压缩列表（ziplist）和跳表（skiplist）是两种不同的数据结构，它们在 Redis 中被用于实现不同的功能。

压缩列表

实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段zlbytes、zltail和zllen，分别表示列表长度、列表尾的偏移量和列表中的entry个数；压缩列表在表尾还有一个zlend，表示列表结束。

0

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段zlbytes、zltail和zllen，分别表示列表长度、列表尾的偏移量和列表中的entry个数；压缩列表在表尾还有一个zlend，表示列表结束。

跳表（skiplist）

有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表，时间复杂度为O(N)。具体来说，跳表，在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示：

0

如果我们要在链表中查找33这个元素，只能从头开始遍历链表，查找6次，直到找到33为止。此时，复杂度是O(N)，查找效率很低。

为了提高查找速度，我们来增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素1作为一级索引，从第三、四个元素中抽取元素11作为一级索引。此时，我们只需要4次查找就能定位到元素33了。

如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取1、27、100作为二级索引，二级索引指向一级索引。这样，我们只需要3次查找，就能定位到元素33了。

可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时，跳表的查找复杂度就是O(logN)。

总之，压缩列表和跳表是两种不同的数据结构，它们在 Redis 中被用于实现不同的功能。压缩列表用于存储短的列表或集合，而跳表用于实现可以在对数时间内进行搜索、插入和删除操作的有序集合。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！