Redis（Remote Dictionary Service远程字典服务）
参考：
图解redis五种数据结构底层实现(动图哦)
Redis(1)——5种基本数据结构
目录
1. Redis的五种存储类型
1.1 String字符串
字符串是redis中最简单的数据结构，其内部表示就是一个字符数组。
SDS动态字符串（simple dynamic string）
Redis中所有场景中出现的字符串，基本都是由SDS来实现的：包括字符串类型的key、字符串类型的值。
在C语言中，字符串可以用’\0’结尾的char数组标示。这种简单的字符串表示，在大多数情况下都能满足要求，但是不能高效的计算length和append数据。所以Redis自己实现了SDS（简单动态字符串）的抽象类型。
- free:还剩多少空间
- len:字符串长度
- buf:存放的字符数组
空间预分配
字符串类型的内部结构采用 预分配冗余空间 的方式来减少内存的频繁分配。内部为当前字符串分配的实际空间capacity一般要高于实际字符串长度。
当字符串长度小于1MB时，扩容都是加倍；长度超出1MB，一次只会多扩1MB的空间。
1.2 List列表
Redis的列表相当于Java语言中的LinkedList，它是一个 双向链表 而不是数组。这意味着list的插入和删除操作非常快，但索引定位很慢。
数据结构：由List和ListNode两个数据结构构成
List部分
- head：指向具体双向链表的头
- tail：指向具体双向链表的尾
- len：双向链表的长度
ListNode部分
- 前驱pre
- 后继next
使用场景
Redis的列表结构常用来做异步队列使用：将需要延后处理的任务结构体序列化成字符串，塞进Redis列表，另一个线程从这个列表中轮询数据进行处理。
1.2.1 ZipList压缩列表
使用LinkedList结构链表的附加空间太高，prex和next指针就要占去16个字节，另外每个节点的内存单独分配，会加剧内存的碎片化。
为了节约内存，使用一种ZipList压缩列表的存储方式。
在列表元素较少的情况下，会使用一块连续的内存存储，这个结构是 压缩列表ZipList。它将所有的元素紧挨着存储，分配的是一块连续的内存。当数据量比较多的时候使用LinkedList。
ZipList结构
- zlbytes：整个压缩列表占用字节数
- zltail_offset：最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
- zllength：元素个数
- Entries：元素列表内容，依次紧凑存储
- zlend：标志压缩列表结束，恒为0xFF
其中每一个Entry结构
- prevlen：前一个entry的字节长度
用于倒着遍历压缩列表时，用这个字段快速定位到下一个元素位置。 - encoding：元素类型编码
- content：元素内容
ZipList增加元素
因为ZipList是紧凑存储没有冗余空间，意味着插入一个元素就要调用realloc扩展内存，可能会分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有地址上进行扩展。
所以其不适合存储大型字符串、存储的元素也不宜过多。
1.2.1 QuickList快速链表
Redis的早期版本使用的是LinkedList和ZipList两种结构相结合的方式，在新版本中对列表的数据结构进行了改造，使用QuickList代替了LinkedList和ZipList。
QuickList将LinkedList按段切分，每一段使用ZipList让存储紧凑，多个ZipList之间使用双向指针串接起来。
ZipList长度
每一个ZipList长度为8KB，超出这个字节数就会灵气一个ZipList，这个长度是可配置的。
压缩深度
为了支持快速的push/pop操作，QuickList的首尾两个ZipList不压缩，此时压缩深度为1。
如果压缩深度为2，表示QuickList的收尾两个ZipList不压缩。QuickList的默认压缩深度为0。这个深度也是可配置的。
1.3 Hash字典
Redis的哈希对象的底层存储可以使用ZipList和HashTable。当hash对象可以同时满足一下两个条件时，哈希对象使用ziplist编码。当前超出以下条件，也会由ZipList结构转换为HashTable结构。
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512个
1.3.1 ZipList字典结构
与上述List结构中ZipList存储的结构是相同的，在存储内容上，每个Entry依次存储Key、Value。
1.3.2 HashTable字典结构
Redis中的字典相当于Java中的HashMap，是无序字典，内部存储了很多键值对。实现结构上和HashMap也是类似的，都是 “数组+链表” 结构，当hash数组位置碰撞时，就会将碰撞的元素使用链表串接起来。不同的是，Redis中的Hash字典的值只能是字符串。
实际上字典结构中含有两个HashTable，通常情况下字典中的两个HashTable只有一个是有值的。
渐进式reHash
大字典的扩容是比较耗时的，需要申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下边，这是一个O(n)级别的操作，作为单线程的Redis很难承受这样耗时的过程，所以Redis使用渐进式reHash小步搬迁。
在字典扩容缩容时，需要分配新的HashTable，然后进行渐进式搬迁。这时两个HashTable存储的分别是旧的HashTable和新的HashTable，待搬迁结束后，旧的HashTable被删除，新的HashTable取而代之。
1.4 Set集合
Redis的集合相当于Java中的HashSet，它内部的键值对是无序的、唯一的。
其内部实现相当于一个特殊的Hash字典，字典中所有的Value都是NULL。
1.5 ZSet有序列表
ZSet可能是Redis提供的最有特色的数据结构，它2类似于Java的SortedSet和HashMap的结合体。一方面它是一个Set，保证了内部value的唯一性；另一方面它可以给每个value赋予一个score，代表这个value的排序权重。
其内部实现是一种叫做 “跳跃列表” 的数据结构。
SlipList跳跃列表
跳表结构比较复杂，先简单介绍其原理
想象你是一家创业公司的老板，刚开始只有几个人，大家都平起平坐。后来随着公司的发展，人数越来越多，团队沟通成本逐渐增加，渐渐地引入了组长制，对团队进行划分，于是有一些人又是员工又有组长的身份。
再后来，公司规模进一步扩大，公司需要再进入一个层级：部门。于是每个部门又会从组长中推举一位选出部长。
跳跃表就类似于这样的机制，最下面一层所有的元素都会串起来，都是员工，然后每隔几个元素就会挑选出一个代表，再把这几个代表使用另外一级指针串起来。然后再在这些代表里面挑出二级代表，再串起来。最终形成了一个金字塔的结构。
跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。
从图中可以看到， 跳跃表主要由以下部分构成：
- 表头（head）：负责维护跳跃表的节点指针。
- 跳跃表节点：保存着元素值，以及多个层。
- 层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
- 表尾：全部由 NULL 组成，表示跳跃表的末尾。
跳表工作流程
跳表之所以跳跃，是因为其内部元素可能"身兼数职"，一个元素可以同时处于不同的层级，可以快速在不同层次之间进行"跳跃"。
元素定位
定位元素时，先在顶层进行定位，然后下潜到下一级定位，直到找到目标位置。
- 从header的最高层开始遍历，找到第一个节点，即最后一个比我小的元素（Node_7）
- 然后从这个节点开始降一层，继续向前遍历找到第二个节点（Node_19）
- 一直降到最底层（Node_23）
新元素的层级
跳跃列表采取一个随机策略来决定新元素可以兼职到第几层。
首先其位于第0层的概率肯定是100%，而兼职到L1层只有50%的概率，到L2层有25%的概率，以此类推，一直到最顶层。列表中元素越多，能够深入的层次就越深，元素能进入到顶层的可能性就越大。
跳表层数上限是32，最大的元素容量（即Level0层）有2的64次方个。根据这个随机算法，当level[0]有2的64次方个节点时能达到32层。