Redis八种数据结构简介

Redis数据结构

Redis新旧版本中一共出现过八种数据结构，分别是SDS、双向链表、压缩列表、整数集合、哈希表、跳表、quicklist、listpack。

SDS

SDS是用于存储Redis中字符串的数据结构，Redis底层使用的语言是C语言，因此字符串也是C语言的字符串。然而C语言字符串存在一些问题。

1.获取长度时间复杂度为O(N)，因为C语言中没有预置的字符串数据类型，而是用一个以“/0”结尾的字符数组代替的，所以要获取字符串长度的话就需要遍历整个数组，数组长度越大消耗时间就越多。

2.无法存储二进制数据，因为C语言字符串就是以"/0"结尾的字符数组，所以如果存储二进制数据的话可能会含有/0的内容，会混淆数组结尾的/0。

3.存在缓冲区溢出的风险，因为C语言不像Java等语言有自己的自动内存管理机制（如Java的垃圾回收器），而是依靠程序员手动管理内存，因此字符数组在添加内容时就可能会导致缓冲区溢出的问题。

为了解决这些问题，Redis中的字符串在原来的基础上添加了三个元数据，分别是len、alloc、flags，分别代表长度、空间长度、SDS类型。具体来说，len记录了字符串的长度，这样在获取字符串长度的时候直接从这个字段获取就行，时间复杂度为O(1)，而且由于len表明了字符串的长度，因此字符串最后一位就不是必须使用“/0”结尾，所以可以存储二进制数据；

alloc则记录了字符串的空间大小，在修改字符串的时候首先会查看alloc大小是否满足，如果不满足的话会进行扩容（小于1MB翻倍，大于1MB增加1MB），这样就能避免缓冲区溢出的问题；

flags用来表示不用类型的SDS，一共有5种类型，分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。这五种类型的区别在于数据结构中的len和alloc成员变量的数据类型不同，因此字符串可以用来存放不同类型的数据而不是只能为原来的字符型。

链表

由于C语言中没有链表这一数据结构，所以Redis自己实现了一个双向链表的数据结构。对于每一个节点来说，拥有前置节点、后置节点、节点值三个属性，而链表在节点的基础上封装了头结点、尾结点、节点复制函数、节点释放函数、节点比较函数、链表节点数量等属性和方法。

对链表的属性和方法中可以看出，该链表对于获取节点的上/下一个节点、头/尾节点、节点数量等操作都非常快，而且链表节点中可以保存不同类型值。

但是也有缺陷，因为链表和数组不同，内存地址并不是连续的，所以不像数组那样可以充分利用CPU缓存加速访问；而且每添加一个节点都需要为其元数据等添加额外的内存，增加了内存的开销。

压缩列表

压缩列表相对于链表来说，内存地址是连续的，和数组一样可以充分地利用CPU缓存，提高了查询的速度，而且会针对不同长度的数据进行相应编码，这种方法能有效地节省内存开销。

在Redis中，List、Hash、Zset等数据类型在包含的元素数量较少的情况下才会使用到压缩列表存储数据。

除此之外，其他和列表不同的是，压缩列表在表头有几个默认字段，分别为zlbytes（列表占用内存的字节数）、zltail（列表尾部的偏移量，可以理解为列表的容量大小）、zllen（列表包含的节点数量）、zlend（列表的结束点）。这些字段能够帮助快速获取列表大小、高效访问尾元素、元素数量等。

压缩列表中的节点也有自己的元数据，分别为prevlen（前一个节点的长度）、encoding（当前节点的数据类型和长度）、data（当前节点的实际数据）。由此可以看出不同节点的空间大小会根据其实际的数据类型进行分配，节省了内存。

连锁更新问题：由于一个节点中有prevlen属性，记录上一个节点的大小，因此当插入节点的时候，如果插入节点的下一个节点中的prevlen长度不足以标明节点的大小的时候那么就需要更新下一个节点的大小，也就是增加其prevlen属性大小，进而也就改变了下一个节点的大小，以此类推也可能改变其他节点。

尽管压缩列表能够通过连续地址和类型分配节省内存，提供一些较为高效的数据操作，但是当其所包含的元素数量过多时，由于是一片连续的内存空间，就可能导致重新分配内存地址，导致性能下降。

哈希表

Redis中的哈希表是一个数组，每个元素指向哈希表节点，哈希表节点中除了值以外还有指向下一个哈希表节点的指针，形成单向链表，因此和Java中的hashmap类似，使用链表的结构存放hash冲突的元素。

不过这里的负载因子算法是哈希表中的节点数/哈希表大小，因此当负载因子大于等于1的时候就需要进行扩容（rehash）操作。

整数集合

当一个Set中只有整数值元素的时候就会使用整数集这个数据结构作为底层实现。

当将一个新元素添加进整数集合的时候并且这个元素的长度大于整数集合中的最大元素长度时就会触发整数集合的升级，一旦升级后就无法降级。由于添加新的元素才触发升级，所以这个机制能够节省内存资源。

跳表

Redis中唯一使用到了跳表的数据类型是Zset（Zset中使用到了跳表+哈希表两种数据结构），跳表这一数据结构能够实现范围查询。

链表查询元素效率很低，而跳表在链表的基础上实现了一种多层结构，简单来说就是按照一定的跨度（两个节点之间的距离）将原来的链表进行了分层，不同的跨度能够实现跳跃式的查询。因此，跳表中存在多级索引，占用的空间较大，但是查询效率得到提升。

quicklist

在Redis3.2后，list数据类型的底层实现由原来的双向链表或压缩列表改为了quicklist，解决了由于压缩列表无法存储大量数据的问题。

quicklist的结构和链表类似，但是将链表的每个元素改为设置一个压缩列表，并且控制每个链表节点中压缩列表的大小，这样就能利用压缩列表的优势同时避免了一个压缩列表存储大量数据的问题。

在quicklist中并不是所有元素都会进行压缩，在两端处有一些数据会频繁地进行操作（像lpush、rpush、lpop、rpop等操作都是直接访问两端节点数据），因此这部分数据可以不用进行压缩，以减少性能损耗，除此之外如果有的压缩列表中只有一个元素，那也不会为之创建一个压缩列表。

quicklist允许对数据进行压缩，原理是如果数据与之前的数据重复，则只会记录重复的位置和重复的长度。

listpack

虽然quicklist降低了连锁更新的概率和造成的影响，但是没有完全避免，因为数据结构中还是用了压缩列表，因此Redis在5.0后设计了一个新的数据结构listpack来替代压缩列表，在listpack中取消了prevlen字段，避免了因为更新而可能需要不断更新相邻节点的prevlen的隐患。

listpack头也有两个属性，分别为listpack总字节数和元素数量，在尾部有结尾标识。

每个listpack节点中有len，encoding，data三个字段，其中encoding定义元素的编码类型，data为实际存放的数据，len则是encoding+data的总长度。所以listpack节点没有记录前一个节点长度，而是只记录当前节点长度，所以向listpack中加入新元素的时候不会影响其他节点，进而避免了连锁更新问题。

由于取消了prevlen字段，listpack无法像压缩列表那样进行双向遍历，但是节省了内存，避免了连锁更新。