前言
在之前的文章中我们有提及string类型是通过底层的SDS(简单动态字符串)实现的，那么其他呢？
除了String类型外，list,set,sorted set,hash这四种都有两种底层实现结构，通常情况我们称这四种类型为集合类型，特点是一个键对应了一个集合的数据:
list由双向链表和压缩列表实现
hash由压缩列表和哈希表实现
sorted set由跳表和压缩列表实现
set 由整数数组和哈希表实现
思考
·1.压缩列表在查找和更新的时间复杂度方面没有很大的优势，为什么redis要把他作为底层数据结构?
2.集合数据的操作效率
List
list由双向链表和压缩列表实现
ziplist（压缩链表）
阅读src/ziplist.h和src/ziplist.c我们惊奇的发现一件事情:
redis竟没有提供一个结构体保存压缩列表的信息，而是提供了一组宏来定义每个成员的地址
压缩列表是一系列特殊编码的连续内存块组成的顺序序列数据结构，可以包含任意多个节点(entry)，每一个节点可以保存一个字节数组或者一个整数值。
ziplist示意图
这个数据结构是不是乍一看很像数组，每一个元素entry保存了一个数据，和数组不同的是表头有三个字段:
1.zlbytes标识整个压缩列表长度
2.zltail标识列表的偏移量,表尾点entryN距离压缩列表起始地址的字节数
3.zllen标识列表中entry个数
列表表尾还有一个zlend标识结束
那么我们就可以快速定位第一个元素（zlbytes-10）和最后一个元素(zlbytes-1)了
ziplist元素节点
ziplist的每个节点由3个部分组成：
1.prevlen表示前一个节点的长度
2.encoding表示节点的编码格式
3.entry-data:压缩后的数据
小结
zpilist格式
<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
zlbytes：ziplist占总字节数
zltail：最后一个元素的偏移量，相当于ziplist的尾指针。
zllen：entry元素个数
zlend ：ziplist结束标志位
entry：ziplist的各个节点
ziplist的entry 的格式：
<prevlen> <encoding><len> <entry-data>
prevlen ：前一个元素的长度，相当于节点保存前一个元素的指针。
encoding： 记录了当前节点保存的数据的类型以及当前节点长度，相当于节点保存后一个元素的指针。
len:自身长度
entry-data ：经过压缩后的数据
quicklist（双向链表/快速链表）
quciklist结构实现
typedef struct quicklist {
//头尾指针
quicklistNode *head;
quicklistNode *tail;
// ziplist中的entry节点计数器
unsigned long count;
//quicklist中的quicklistNode节点计数器
unsigned long len;
//保存ziplist的大小
int fill : 16;
//保存压缩程度值
unsigned int compress : 16;
} quicklist;
其中节点实现
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
//不设置压缩数据参数recompress时指向一个ziplist结构
//设置压缩数据参数recompress指向quicklistLZF结构
unsigned char *zl;
//压缩列表ziplist的总长度
unsigned int sz;
//ziplist中包的节点数
unsigned int count : 16;
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;
我们阅读结构体发现虽然是quicklist但却出现了很多关于ziplist的身影
首先ziplist的插入和删除操作时间复杂度非常高(参考数组需要重新生成一个ziplist来作为更新后的list)，当一个list非常大的且更新平凡就会带来非常大的开销。
所谓的quicklist就是把ziplist和普通的双向链表解和，每个双向节点保存一个ziplist，每个ziplist中存一批list数据，这样可以避免大量链表指针操作带来的内存开销(即化整为零思想)
小结
Redis对外暴露的list数据结构，其底层实现所依赖的内部数据结构就是quicklist。quicklist就是一个块状的双向压缩链表。
考虑到双向链表在保存大量数据时需要更多额外内存保存指针并容易产生大量内存碎片，以及ziplist的插入删除的高时间复杂度，两个数据结构的缺陷会导致在数据量很大或插入删除操作频繁的极端情况时，性能极其低下。
Redis为了避免数据结构在极端情况下的低性能，将双向链表和ziplist综合起来，成为了较双向链表及ziplist性能更加稳定的quicklist
思考
1.压缩列表在查找和更新的时间复杂度方面没有很大的优势，为什么redis要把他作为底层数据结构?
list底层使用压缩列表本质上是将所有元素紧挨着存储，能节省空间避免内存碎片（内存空间不是硬盘空间是很昂贵的）
skiplist(跳表)
有序列表查找元素，只能遍历查找，于是就出现了跳表
struct skipList{
int lenth; //元素个数
skipListNode* head; //跳表头节点
}skiplist;
skiplist节点结构体
struct skipListNode{
//下一个链表指针
skipListNode* levelnext[3];
//当前层数
int currentlevel;
int totallevel;
int value;
}
也就是说跳表在链表的基础上增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位
其中索引可以持续累加
整数数组
整数数组是集合的底层实现之一，当一个集合只包含整数元素且数量不多，就会用该方式实现
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
思考
2.集合数据的操作效率
- 单元素操作是基础
- 范围操作非常耗时
- 统计操作通常高效
- 例外情况只有几个
单元素操作指对单个数据实现增删改查，这些操作的时间复杂度由集合采用的数据结构决定
范围操作指遍历操作，返回所有数据(像链表实现需要遍历整个)
统计操作指对个数的记录(当集合类型使用压缩列表和双向链表，整数数组时，这类数据结构都有专门的指针记录个数)
例外情况指某些数据结构的特殊记录，如压缩列表和双向链表都会记录表头和表尾对于其的LPOP等时间复杂度都是O(1)的(通过偏移量直接记录位置)
网友评论