Redis底层数据结构

数据操作效率

在 String 类型，查找到哈希桶就能直接对 value 增删改查，它的实际复杂度就是哈希表的时间复杂度 O(1)。而集合类型中找到哈希桶后还要在集合中进行下一步操作。

集合操作效率受哪些因素影响？

• 首先和集合底层数据结构有关，使用哈希表实现的集合比链表实现的集合访问效率更高
• 其次和操作本身执行特点有关，读写一个元素显而易见比读写所有元素效率高

集合的底层数据结构

集合类型的底层数据结构主要有 5 种：整数数组，双向链表、哈希表、压缩列表和跳表。

之前介绍过哈希表，整数数组和双向链表的操作特征都是顺序读写，即通过数组下标或链表指针逐个元素访问，操作时间复杂的 O(N)，操作效率比较低。

压缩列表

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

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。在查找其他元素时，只能逐个访问，时间复杂度 O(N)

跳表

有序链表只能逐个查找元素，效率很低，为了优化查询效率，出现了跳表。

跳表就是在链表的基础上增加多级索引，通过索引位置的快速跳转，实现数据的快速定位。当数据量很大时，跳表的查找时间复杂度是 O(logN)

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

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

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

以下是各个数据结构的时间复杂度：

总结

今天我们学习了 Redis 集合类型的底层数据结构。Redis 能快速操作键值对，一方面是在 String、Hash 和 Set 中广泛使用时间复杂度 O(1) 的哈希表，另一方面 SortedSet 使用时间复杂度 O(logN) 的跳表。但是在范围操作要遍历底层数据结构的时候时间复杂度是 O(N)。优化方法可以用其他命令代替，比如 SCAN，减少耗时。