众所周知redis是由C语言实现的，包含有五种数据结构，跟别是string、list、set、hash以及sort_set，最近学习了一些关于redis底层的结构设计。
redis的SDS结构，是对C语言的string结构进行了一层封装，除了包括有基本的char[]数组buf之外，还包括有一个int类型的len（buf数组中已占用的字节数量），以及一个int类型的free（buf数组中未使用的字节数量）。
a、获取字符串长度非常频繁，可以常数复杂度获取，提高读取效率；
b、在字符串反复set过程中，长度容易变化，如果len不满足新长度时会进行扩展，不会出现长度溢出；
在长度增加时，首先会根绝len判断长度是否足够，如果不足时，则会进行扩展操作；
扩展并不是直接将buf扩展到指定长度，当长度len小于1MB时，扩展为len的两倍，即扩展后len=目标长度，且free也=目标长度；
当长度1>1MB时，会是的len=目标长度，free=1MB，即预留1MB的空间。
效果：这种预分配策略，SDS可以将连续增长N次字符串所需要的内存重分配次数，从必定N次降低为最多N次。
当SDS长度需要缩短时，程序不会立即使内存缩短，而是使用free属性将这些空间预留下来，等待接下来的使用，即不会释放内存。
效果：避免了缩短字符串带来的内存重新分配，并为将来可能的增长操作做了预留。
所有的SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其进行任何限制或者过滤，数据写入时是什么样，读取就是什么样，保证了存储数据时的安全性。
虽然SDS API是二进制安全的，但是SDS依然可以复用String类型的一些库定义的函数。
链表在redis中的应用非常广泛，比如列表键的底层实现之一就是链表，此外发布与订阅、慢查询、监视器等功能也用到了链表。
每个链表节点（ListNode）包括了一个前置节点，一个后置节点，以及节点所对应的值，所以redis链表是双端链表；
redis的链表结构，包括了一个表头节点、一个表尾节点、链表包含的节点数量，此外还提供了节点值复制函数、节点值释放函数以及节点值对比函数三个基础方法。
因为每个链表的表头节点的前置节点和表尾的后置节点都指向NULL，所以redis的链表是一个无环链表。
字典在redis中的应用也很广泛，包括了数据库和哈希键等。
每个字典带有两个哈希表，一个平常使用，一个在rehash时使用。
字典结构类似于Java的HashMap，使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会链接为一个单向链表。
在对哈希表进行扩展或者收缩操作时，程序会将现有哈希表包含的所有键值对rehash到新的哈希表里，并且rehash过程不是一次性完成的，而是当涉及到这个键值对时才写入新的哈希表，是一个渐进式的过程。
跳跃表时一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的，其节点查找平均O(logN)，最坏O(N)的复杂度。
跳跃表时有续集合（sort_set）的底层实现之一，其由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
每个跳跃表节点的层高，都是1至32的随机数。（随机是因为无论怎么算法设计，都不能完全符合实际最优情况）
跳跃表中的节点按照分值大小进行排序，不同节点可以包含相同的分值，但是每个节点的对象必须是不相同的，当分值相同时，节点按照对象成员的大小排序。
关于跳表查询的原理，这里列了一张图表示，查找55时，只需要两次查询即可，查找46时，首先会在L3层查找两次，再在L2层查找2次，最后在L1层查找1次，共五次可以查到46。
这里展示了结合redis数据结构表示的跳表结构。
整数集合是set的底层实现之一，当集合全是整数且集合大小小于一定阈值时，集合底层使用整数集合来实现；
整数集合的底层实现是数组，这个数组以有序、无重复的方式保存集合元素；
整数集合元素的类型为int_16，int_32和int_64，集合具体使用哪种类型视集合中最大的那个元素而定，当新插入的元素类型比之前数组中的类型范围要大时，数组会进行升级操作。如数组之前是int_32，新插入的数据大于int_32的范围，即会将数组升级为int_64类型的数组，然后再将新元素插入。
数组集合只支持升级操作，不支持降级操作。
压缩列表是list和hash的底层实现之一，是一种为了节约内存而开发的顺序型数据结构；
压缩列表由zlbytes，zltail，zllen，entryX，alend组成；
其中entryX代表存储的信息，可以包含多个节点，每个节点由previous_entry_length（前节点的长度，用于向前回溯），encoding（节点的数据类型和长度），content（节点值）组成，可以保存一个字节数组或者整数值；
添加新的节点（插入到entryX列表的最前端），或者从压缩列表中删除节点，由于previous_entry_length的长度可能会变化，其都有可能引发连锁更新操作，导致所有的entryX节点都发生变化，但是发生几率不太高。
redis中每个键值对的键和值都是一个对象，其共有string、list、hash、set和sort_set五种类型的对象，每种类型的对象都至少有两种或以上的编码方式，不同的编码方式可以再不同的场景优化对象的使用效率；
a、如果保存的是整数值，并且可以用long类型保存，则使用long类型保存；
b、如果保存的是一个字符串值，则使用SDS来保存；
a、如果list对象保存的所有字符串元素长度都小于64字节，且元素数量小于512个，则使用压缩列表的方式保存；
b、其余情况都使用链表保存。
a、如果hash对象的所有键和值的字符串长度都小于64字节，且保存的键值对数量小于512个，则使用压缩列表的方式保存；
b、其余情况使用字典来保存。
a、如果集合对象保存的所有元素都是整数，且元素数量不超过512个，则使用整数集合的方式来保存；
b、其余情况使用字典来保存，只使用字典键值对中的键，值都被置为null。
a、如果保存的元素成员长度都小于64，且数量小于128个，则使用压缩列表的方式来保存；
b、其余情况使用跳表来保存。
各种对象类型，底层的实现方式的阈值，都可以通过redis的配置来实现调整。
redis服务器在执行某些命令前，先会检查给定的键的类型能否执行该命令；
redis对象系统带有引用计数机制实现的内存回收，当一个对象不再被使用时，该对象所占用的内存就会被自动释放；
redis会共享值为0-9999的字符串对象，类似于Java中的共享常量；
对象会记录自己最后一次被访问的时间，这个时间可以用于计算对象的空转时间，用于内存耗尽时的淘汰。
