详细介绍了Redis的基础数据结构： dict、ziplist和quicklist。
此前我们学习了常见的Reids数据类型，这些数据类型都需要底层的数据结构的支持，现在我们来看看Redis常见的底层数据结构：dict、ziplist、quicklist。
文章目录1 Redis dict1.1缩放条件1.2渐进读刷新操作2 Redis ziplist2.1 ziplist结构2.2入口结构3 Redis quicklist
1就绪诊断
dict就是“字典”的意思，它是Redis中的一种使用的非常多的底层的数据结构，除了hash会使用字段之外，整个 Redis 数据库的所有 key 和 value 也组成了一个全局字典dict，还有带过期时间的 key 也是一个字典expires(存储在 RedisDb 数据结构中)。
Redis 中的字典相当于 JDK1.7中的 HashMap的内部实现也差不多，通过“数组链表”的链地址法解决部分散列冲突，同时这种结构吸收了两种不同的数据结构的优点。
和JDK1.7中的hashmap不同的是，Reids的字典结构内部包含两个hashtable变量，通常情况下只有一个hashtable有值，另一个为空表，但是在字典扩容缩容时，需要分配新的hashtable，并且使用了一种叫做渐进式搬迁(rehash)的机制来提高dict的缩放效率，这时候两个hashtable分别存储旧的和新的 hashtable，待搬迁结束后，旧的将被删除，新的 hashtable 取而代之。
1.1缩放条件正常情况下，当 hash 表中元素的个数等于数组的长度时，就会开始扩容，扩容的新数组是原数组大小的2倍。不过如果 Redis 正在做 BGSAVE或者BGREWRITEAOF(持久化)，为了减少内存占用，Redis 尽量不去扩容，但是如果 hash 表非常满了，达到了数组长度的 5 倍了，这个时候就会强制扩容。
当 hash 表因为元素逐渐被删除变得越来越稀疏时，Redis 会对 hash 表进行缩容来减少hash表的第一维数组空间占用。所用的条件是：元素个数低于数组长度的10%，缩容不会考虑 Redis 是否在做 bgsave。
1.2渐进式rehash操作在扩容和收缩的时候，如果哈希字典中有很多元素，一次性将这些键从ht0（正在使用的hashtable）全部rehash到ht1（另一个空的hashtable）的话，由于Redis是单线程模型，那么可能会导致服务器在一段时间内停止服务。所以，采用渐进式rehash的方式，数据的迁移并不是一步完成的，因此dict内部还有一个rehashidx属性用来控制rehash，默认置为-1。
为ht[1]分配空间，使词典同时具有ht[0]和ht[1]哈希表。 将rehashindex的值设置为0将正式开始rehash工作。 在rehash过程中，每当对词典执行添加/删除/更改操作时，程序除了执行指定的操作外，还会自动将ht[0]哈希表的rehash索引上的所有键值与rehash到ht[1]相关联，使其与1 持续执行字典操作时，最终ht[0]的所有键值对都从rehash设置为ht[1]，rehashindex的值设置为-1，表示rehash操作已结束。 将ht[1]设置为ht[0]，在ht[1]中创建新的空表，为以下刷新做准备：渐进式rehash采用的是一种分而治之的方式，它以bucket(桶)为基本单位进行渐进式的数据迁移，每步完成一个bucket的迁移，直至所有数据迁移完毕。这种方式将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。
在渐进式rehash的过程中，如果有删除、修改、查询操作，则会在两个哈希表ht[0]和ht[1]上进行，先操作ht[0]，如果没找到，再操作ht[1]，则新增的数据则会被保存在ht[1]中，ht[0]中包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。
2 redisziplist http://www.Sina.com /
ziplist又名压缩列表，见其名知其意，这种数据结构就比较节省内存空间，Redis中对于list（3.2版本之前）、hash、zset类型的数据，如果元素较少，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来存储。
ziplist的节省空间是相较于数组而言的，ziplist和数组一样同样采用一整块连续的空间来存储数据，数组在实际存储时，每一个元素所占的实际大小是一样的，并且是以最大的元素的大小为准，这样就能进行快速的根据索引访问，而ziplist则允许每一个entry节点（对于数组中的元素）所占的实际大小不同，另外，节点之间没有存储前驱和后继的指针，以此节约空间。
ziplist支持正序或者倒序的遍历，往ziplist里插入一个entry 时间复杂度 平均:O(n),最坏:O(n²)，从ziplist里删除一个entry 时间复杂度 平均:O(n), 最坏:O(n²)。最坏为O(n²)是因为Redis连锁更新导致的，但这种情况出现的概率不高。
ziplist和数组类似，删除和添加节点都可能涉及到其他节点位置的移动，因此只适用于元素数据量较少，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串的情况。
2.1 ziplist结构Redis的ziplist采用一系列特殊编码的连续内存块，一个压缩列表出了在头部包含一些整体信息之外，剩下的部分可以包含任意多个节点(entry)。
整体结构如下：
zlbytes：32位无符号整数，表示ziplist的整体长度（字节)。在对ziplist重新分配内存或者计算zlend的位置时有用。zltail：32位无符号整数，最后一个节点距离头部的偏移量，通过该偏移量程序无需遍历整个ziplist即可确定尾节点的地址，在反向遍历ziplist或者pop尾部节点的时候很有用。zllen：16位无符号整数，ziplist的节点（entry）个数。当小于值小于65535时，该值时准确的，等于65535（16位的最大值）时，需要遍历整个链表才能得到真实节点数量。entry：ziplist中的数据节点，长度不固定，自己的长度保存在每一个entry节点内部。zlend：8位无符号整数固定值为0xFF，用于标记ziplist的结尾。 2.2 entry结构ziplist的entry用于存储正数或者字符串（字节数组），且每个节点的长度都是不一样的，因此节点的长度只能由这个节点自己来保存，Redis的ziplist中，entry由三部分构成：
previous_entry_length：8bit或者40bit，用于记录上一个节点的长度（字节），为了方便反向遍历ziplist。encoding：当前节点数据的编码规则，即data属性的数据类型以及长度。content：当前节点的值，可以是数字或字符串（字节数组）。previous_entry_length用于记录上一个节点的长度（字节），为了方便反向遍历ziplist，其本身的长度可能是8bit或者40bit。
如果前一节点的长度小于254字节，那么prevlengh属性的长度为1字节，前一节点的长度就保存在这一个字节里面，这样更加节约内存。如果前一节点的长度大于等于254字节，那么prevlengh属性的总长度为5字节，第一字节被固定设置为0xFE（十进制值254），而之后的四个字节则用于保存前一节点的长度。第二种情况下，第一个字节254而不用255（0xFF）是因为255是zlend的值，它用于判断ziplist是否到达尾部。content表示当前节点的值，可以是数字或字符串（字节数组），encoding 表示当前节点数据的编码规则，即data属性的数据类型以及长度，其中encoding其中高2位用来区分整数节点和字符串节点（高2位为11时是整数节点），根据值的类型不同，一共有九种编码类型。
字节数组的encoding类型3种，encoding有8位、16位、40位三种长度，context的长度也是变化的：
encoding长度encoding格式content格式8bit高两位固定00，后6位表示字节数组的长度长度小于等于63(2^6-1)字节的字节数组16bit高两位固定01，后14位表示字节数组的长度。长度小于等于16383(2^14-1)字节的字节数组40bit高两位固定10，后38位表示字节数组的长度。长度小于等于4294967295(2^32-1)字节的字节数组整数值的encoding类型6种，固定长度8位，高两位固定11，表示整数，因此需要后两位来表示不同的整数类型。整数类型的content的长度虽然也是可变的，但固定范围内的整数长度一样，也就是说content长度只有固定的几种。
encoding长度encoding格式content格式1bit1111xxxx，后四位用来表示content。4bit长的无符号整数，即介于0至12之间，没有content字段，在encoding中存储。111111108bit，有符号整数。1100000016bit，有符号整数。1111000024bit，有符号整数。1101000032bit，有符号整数。1110000064bit，有符号整数。 3 Redis quicklistRedis 的list在3.2版本之前在元素较少时实际上是采用ziplist结构，当链表entry数据超过512、或单个value 长度超过64，底层就会转化成linkedlist编码，而Redis3.2及其之后则采用quicklist结构代替ziplist和linkedlist。
ziplist存储在一段连续的内存上，所以存储和查找效率很高，顺序IO访问。但是，它不利于修改操作，插入和删除操作需要频繁的申请和释放内存。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，适用于存储整数和短字符串。
双向链表linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个prev 和 next指针（64 位操作系统占用 8 个字节）；其次，双向链表的各个节点是单独的内存块，地址不连续，随机IO访问，节点多了容易产生内存碎片，影响内存管理效率。
quickList将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。
首先quickList就是一个标准的双向链表的配置，有head 和tail节点，每个节点是一个quicklistNode节点，包含prev和next指针，内部还包含一个ziplist，使用ziplist来保存数据，而ziplist实际上含有多个entry节点，保存着数据。相当与一个quicklistNode节点保存的是一片数据，而不再是一个数据。
quickList将二者的优点结合起来，在宏观上是一个双向链表结构，插入、删除quicklistNode节点的成本很低，不需要移动其他节点的位置，而在微观上，每一个quicklistNode节点又是一个个的ziplist，内部包含多个数据，ziplist内存连续，减少了内存碎片，同时由于每一个ziplist不是很大（大小可以配置），因此插入和删除操作不会进行大量的数据移动。
相关文章：
https://redis.io/topics/data-typeshttps://redis.io/topics/data-types-intro如有需要交流，或者文章有误，请直接留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！