Redis Data Structure

书接上回,面试破防有感中，我遭遇了面试官的夺命连环问，其中让我最久久不能平息的莫过于“你了解Redis数据结构的底层实现吗？”。遥记曾多次看到过类似文章，但总是用各种理由推脱，没仔细研究，这才在面试上吃了大亏。为了弥补面试的遗憾，我花了些时间，研究了Redis的数据结构底层实现。

Redis的数据存储

讨论Redis底层的几种数据结构前，我们需要先了解到Redis是如何阻止其中五花八门的数据类型的。

redisDb中存储有两个hash表，用于存储我们存于其中的键值对，其中一个正常使用，另一个用于rehash。

哈希表中的每一项对应一个键值对，其中键为String对象，而Value则可能是五种基础数据对象中的一种，所以使用void*指针，满足多态需求。而在value对象与实际使用的底层数据结构间，也利用了这种多态。

Simple Dynamic String

Redis使用C进行开发，而C是没有提供String类型的，仅有一些基于Char*的库操作函数，一般仅满足文本编辑。但在Redis中，String指的不仅仅是狭义上的文本，而是泛指一切可二进制序列化的文本文件。于是，Redis自己设计了SDS数据类型，用于字符串处理。

其中len字段记载已存储字符串长度，alloc则表示buf中可以存储的最大长度,flags用于表示len与alloc的长度(uint5-uint32)，用于压缩头部。

双向链表

双向链表是一种十分泛用的数据结构了。

其中head与tail对头尾进行索引，len记载数量。

压缩列表

双向列表作为列表，使用的是离散的内存空间，往往难以进行CPU缓存优化，同时，头部与大量的指针也占据了不少空间。因此，基于双向链表，又改进出了压缩链表。

压缩链表是一种类数组结构，起始处的几个字段记载了压缩列表所需的元数据——字节数量、尾部偏移、节点数量。之后，连续的entry保存了列表所需数据。

分析entry结构，包含prevlen、encoding与data三个字段，分别表示前一个节点的长度、编码方式和数据。

为什么要保存前一个节点的数据呢？因为压缩列表采用的是尾遍历的方式，从最后一个节点开始，减去prevlen，即可获取前一个节点的初始地址。

压缩列表虽然节省空间，但是带来了一个比较大的问题：连锁更新。

当我们在首个元素前——尾遍历的最后一个元素后插入元素后，需要更新前一个元素的prevlen字段，而这个prevlen字段的长度是自适应的（即按照表示长度的大小变化滋生大小，如int8能表示到255，但是需要int16才能表示256），如果前一个元素过大，后一个元素的prevlen装不下，就将导致后一个元素的prevlen需要变大，导致后续节点的连锁反应。

ListPack与QuickList

ListPack与QuickList是对压缩链表的改进。

Quicklist结合了双向列表与压缩列表，在可能产生连锁更新时，插入一个新的双向链表节点，并将元素放入新的节点中的压缩列表中。

ListPack的解决方案更为高明，不采用尾部遍历，而采用正向遍历，保存自身长度，指针偏移自身长度后得到下一个元素，完美地避开了连锁更新地问题。

整数集合

相较于其他数据结构，整数集合看起来就非常简洁。

其头部包含元素个数、元素长度与元素内容三个字段，其中元素内容按下排列。

在元素较小时，使用int8类型编码，而当存入较大元素是，则进行整体升级，原地扩展更大空间，并将原元素升级到较大类型存入。但是不支持向下转型。

跳表

跳表是一种媲美红黑树的数据结构，通过巧妙地设置索引比例与层数，我们可以获得如平衡树般的查找效率，且由于其底层有序，相较于一般平衡树，还支持范围查询。

具体内容可以查看这篇博客

Redis中的跳表，除了元素内容外，还存在一个可重复的权重属性，故虽然跳表使用Score（权重）作为索引，但查询时也需要比较元素内容。

注意：虽然五种类型与底层实现间存在多种可替换实现，但Zset是同时使用了Listpack与跳表，其中，Listpack进行哈希查找，而跳表实现范围遍历。