redis数据结构和数据类型

1.动态字符串SIMPLE DYNAMIC STRING(SDS)

观察上图中的SDS结构，头部包含字符串长度和分配的空间，可以以O（1）的时间复杂度计算出字符串长度，并且有了字符串长度后可以无视c语言的字符串缺陷（\0作为结尾标识，容易被误判），可以动态扩容以及二进制安全。

2.intset

intset是一个集合，用于存储整形数据，由于是set所以满足元素唯一性，在不需要扩容的情况下，插入新元素时，底层采用二分法进行查找插入位置，效率为Ologn。

intset支持动态扩容，如果插入的元素大小大于当前编码ecoding设计大小，那么就会进行inset升级，具体见下述流程。

当插入一个比int16大得元素，那么就涉及到了整体的扩容，但这种情况会造成相当大得空间浪费。

具体过程是：假设目前的编码是int16，那么就升级为int32（如果int32能够装下新插入的数据，如果不够就继续升级），然后按照排列的倒叙对所有数据进行移动，最后再插入新元素。因为新加入的元素所需容量比剩余元素都大，并且所有元素都是int整形，那么新插入的元素一定是最大的，所以存储在末尾。

intSet 是一个set，本身得元素必须是唯一的，为了保证整体数据的有序性，所以在插入元素的时候需要进行判断：

判断方式即对传入数据的值进行查找，如果没有查找到，那么就插入，否则直接返回（有相同元素）。这个特性使得在当set集合中存储的元素是整数时，并且插入数据不超过set中默认设置的intset最大值时，intset作为set数据类型的数据结构，否则dict会作为set的数据结构。

查找的过程使用二分查找，根据intset存储的整形数据的value进行查找插入位置，用于保证intset的有序性。

3.dict

3.1Dict的数据结构

dict数据结构会创建一个dictht表示字典的hashtable，里面有一个指向entry数组的指针、size数组大小、sizemask使用与运算“&”进行取余、used表示已有entry的数量。

需要注意，这里的dictEntry是一个键值对。

后续的set就是使用dict进行实现的，不过将dictEntry设置为了0。

3.2Dict的扩容

dict这个数据结构存储了两张表，一张表用于存储所有的entry的指针，一张表用于rehash。

rehash的原因在于dict需要进行扩容，最初的大小为size，如果此时used（即已存储的entry数量）已经大于size的值了（即负载因子>1），那么此时就会考虑dict的扩容，前提是后台不忙碌的情况，当负载因子>5之后，dict不管后台是否有处理过程，都会进行扩容。

此时会根据used的数量，找到离used最近的2^n，比如现在的used为5，那么扩容的size就为8，会在等待执行rehash的表创建相应的存储容量，再将原本数据复制到新表中，最后将原表置空，从而完成扩容。

3.3Dict的收缩

如果负载因子<0.1，就会触发收缩，如果当前size<4那么会将另一张等待rehash的空表大小置为4，否则，根据size找到离size最近的2^n来进行扩容，最后将源数据复制到新表，将原数据表置为rehash辅助表。

3.4总结

dict的数据结构包含两张dictht表，记为ht(0)与ht(1)，ht(0)用于存储当前数据，ht(1)用于rehash辅助来扩容与收缩。ht(0)与ht(1)会反复翻转，来实现扩容与收缩。扩容与收缩都是根据负载因子来判断的，最终都会找到离size最近的2^n作为新的存储容量。

最后需要了解一个细节，rehash不是一次性转移整张表，而是批量处理部分数据内容，因为数据量大的情况下，处理时间会很长

4.ZipList

4.1数据结构

ziplist的头部会保存整个链表的长度、尾指针以及entry的数量，ziplist用于节省存储空间

ziplist节省空间的原因在于不会存储指针，entry中会记录上一个节点的entry大小、entry中自身节点大小与编码方式以及自身数据，这样会比存指针和数据节省更多空间。这里的entry就是指一个节点。

同时entry中存储的内容content是可变长的，所以不会因为等长如intset浪费掉空间。

又由于ziplist中每个entry有上个节点的大小，所以可以通过地址计算进行顺序以及逆序遍历（顺序遍历通过当前entry起始地址加上本节点的大小计算下个节点的起始地址、逆序遍历通过当前entry的起始地址-上个节点大小）

4.2连锁更新问题

ziplist如果本节点的内容进行更新，假设现在使得后一个节点记录的前一个节点的长度从1字节变为了5字节，也就是说当前节点的更新导致了下个节点的更新（因为后一个节点记录了前一个节点的长度，而当前一个节点的长度大于254字节，就会使得后一个字节的前一个节点大小从1字节升级为5字节）。

在极端情况下就会出现一个节点更新，导致连锁反应，后续节点都进行更新，更新需要使用到内核态，涉及到内核态与用户态的切换，进行内存分配，资源开销很大。

5.quicklist

quicklist的创建就是为了解决ziplist的自身问题，比如ziplist需要连续的存储空间，那么当数据量很大时，内存分配很大的连续空间的难度会很高，所以为了解决这个问题，将ziplist拆分为多段，使用一个辅助节点来连接对应的ziplist段，每个辅助节点都有一个pre指针与next指针还有一个zip指针。

这个辅助接点就是quicklist节点。

整个数据结构称为quicklist。

quicklist可以对每个ziplist进行压缩，一般而言对中间节点进行压缩，因为查询是通过头节点与尾节点进行查询的。

6.SkipList

总结：跳表就是一个多指针链表，会在链表之间建立新的指针来增加遍历的跨度，根据score的大小来具体判断使用哪个跨度对应的指针，从而加速查找速度。

在redis中最多支持32级跳表

Redis 的跳表主要应用在 有序集合（ZSet） 的底层实现中（配合哈希表），它通过如下结构来维持元素的顺序：

每个元素按照 score（分数）从小到大排列；
插入时按照 score 插入合适的位置；
查询时可以快速跳跃查找，比如范围查找、排名查找、按顺序遍历等。

7.RedisObject

8.String数据类型

string数据类型的基本编码方式是RAW，redisobject与SDS是分块存储的，而当SDS的大小小于44字节时，此时RAW编码会更改为EMBSTR。

如果存储的字符串是整数类型，并且在long范围以下，那么会在内存中创建一个空间用于存储整形数据，然后将指针指向该空间即可。这种编码方式是INT编码

9.list数据类型

list数据结构底层实现使用了quicklist，lpush和rpush对应双端队列得队首与队尾，lpop与rpop同理。

10.set数据类型

set结构底层实现使用的是dict数据结构，dict数据结构存储得是一个entry，也就是一个键值对。在set应用dict作为数据结构时，会将键值对中的值置为NULL

当存储的值都为整数，并且存储的数据量没有超过set中设置的最大值时，使用的数据结构是intset

，否则使用dict

11.zset数据类型

zset这个数据类型存储的内容是一个键值对，键存储对应的value，而值存储score。

zset的特性要求键值存储、唯一键、可排序的特性。

所以对应的数据结构，满足键值存储的就只有dict字典。但是dict实际上是一个hash表，无法进行排序在zset中进行键值查询。

而跳表本身包含score，在zset中用于范围查询和排序功能。

所以zset选择将数据分别存储在skipList和dict中，使用dict来进行查询键值对，使用skipList来进行排序。

当zset中的数据量较少，单个数据的大小也较小，具体小于某个预设值时，为了节省空间，zset会转换为一张ziplist压缩表，ziplist本身不支持排序功能，但是其占用空间小，并且存储的数据少，相应查询时间也不会太长。相当于是一种时间换空间的策略，但是由于数据量少，这个时间的增长可以接收。

ziplist存储的entry只能包含一个内容，所以在zset中，两个连续的entry会分别存储value和score

12.hash数据类型

底层就是使用dict，完全适配，没什么好说的。

13.redis数据结构以及对应的数据类型总结

redis数据结构有SDS，这是redis自带一种字符串存储结构，其避免了c语言的字符串问题，同时支持空间的动态扩充，能以O（1）时间复杂度读取字符串长度以及具有二进制安全；

有intset，这是一种相对灵活的整形数组，所有元素存储大小都是相同的，如果某个元素大于当前存储元素的最大空间，那么intset会进行动态升级。在intset中会在头部记录存储的数据数量、尾部指针、当前的数据存储空间大小（8、16、32）。支持存储空间动态扩张、插入有序、底层使用了二分法来插入数据，所以元素是有序的，读取速度快，缺点是需要连续的存储空间，并且伴随相当一部分的空间浪费；

有dict字典，这是一个典型的哈希表，通过hash code得到散列值，再将散列值与掩码进行与运算得到具体的存储位置。与经典哈希不同的点就在于使用与运算进行装填。dict包含两张ht，一张ht用于存放数据，一张ht用于rehash进行扩容与紧缩。扩容与紧缩都是根据负载因子来进行的，当负载因子大于1并且无后台操作时，或者负载因子大于5时，进行扩容，当负载因子<0.1时进行紧缩。扩容与紧缩都是找当前离size最近的2^n来作为新的size，比如原本size为5，现在就取8；

有zipList压缩链表，压缩链表特点是每个节点包含上一个节点的长度以及自身长度，可以看作是一个可变长的列表，虽然不支持随机访问，但是支持顺序、逆序访问。由于没有使用指针，并且每个数据内容都装满了存储空间（除了存储的辅助信息外），存储的密度非常高，基本不会出现空间浪费。缺点是需要申请连续的存储空间，当所需连续空间较大时，操作系统难以分配所需空间，同时还有可能出现连锁更新，即一个节点扩容，导致下个节点的encoding部分增大，刚好又引起下下一个节点的encoding部分增大，从而出现连锁反应；

quicklist快速链表，快速链表就是使用辅助接点将ziplist穿起来，并且辅助结点有pre behind、zip三个指针。quicklist解决了ziplist的问题，使得一个很长的数据内容能够切成多篇进行存储。quicklist是list数据类型的底层实现。同时quicklist能够将ziplist的中间部分进行压缩，因为list数据类型基本只会对队首与队尾进行操作，通过压缩中间部分内容可以节省存储空间；

skiplist跳表，跳表可以看作是一个多指针链表，链表中不同的节点间建立指针来加快查询速度，跳表的查询速度基本与红黑树相当。并且在跳表中维护了一个score值，根据score值来进行查询，所以跳表的数值是有序的。目前学到的数据结构中，就skiplist和intset是有序的，intset底层使用二分查找实现有序插入，而skiplist根据score来进行有序插入；

redisobject，所有redis数据存储的顶层封装就是redisobject，包含对应的数据编码方式，数据指针等。

在数据类型中学习了String、list、set、zset、hash

String使用SDS进行存储，没什么好说的；

list使用quicklist实现，quicklist通过多个辅助节点和多个ziplist组合而成，将中间ziplist进行压缩，留下首尾节点（可以调整首尾节点的数量），可见list结构不支持顺序检索、但是存储密度大、只需对首尾进行操作；

set集合底层使用dict字典数据结构，数据包含多个内容，比如Sadd text 01,02,03，这里就插入01、02、03三个数，显然01、02、03数据的结构不是一个键值对，所以使用dict时会保留键，而将值置空；

zset底层使用跳表和dict数据结构实现，跳表用于根据score进行范围查询，通过key查value(对应score)就需要使用到dict。同时需要注意zset的键唯一性是由dict实现的；

最后hash由dict实现没什么好说的。