Redis 第一部分 “数据结构与对象”
简单动态字符串
Redis 构建了一种名为 简单动态字符串（simple dynamic string，SDS）的抽象类型，并将 SDS用作 Redis 的默认字符串表示。
如果Redis 在数据库中创建一个新的键值对，那么键值对的 键是一个字符串对象，对象的底层实现是一个保存着字符串的SDS。
Reids这么做的原因有多个：
1.C语言中字符串并不记录自身长度信息，照成程序必须遍历整个字符串。SDS 在 len 属性中记录了它本身的长度，这使Reids 获取字符串长度所需的复杂度从 O(N) 降到了 O(1)，确保获取字符串不会成为Redis 的性能瓶颈。
2.C字符串不记录自身长度带来另外一个问题就是容易造成缓冲区溢出。SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：对SDS进行修改时，API会先检查 SDS 的空间是否满足修改所需的要求，如果不满足，API会自动修改所需的大小。
3.C字符串的底层总是一个N+1个字符长的数组，所以每次增长或缩短一个C字符串，程序都要对保存这个C字符串的数组进行一次内存重分配操作。
4.C字符串中的字符必须符合某种编码，处理字符串的末尾之外，字符串不能包含空字符串。这些限制使C字符串只能保存文本数据，而不能保存图片，音频，视频这样的二进制数据。SDS 的 API 都是二进制安全的。所以Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据。
5.SDS 兼容部分 C 字符串函数，虽然 SDS的API 是二进制安全的，但是它依旧遵循 C 字符串以空字符串结尾的惯例。这是为了重用<string.h>/strcasecmp 函数，这样 Redis 会避免部分的函数重写。
链表
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。
因为 Redis 使用 C语言编写，但又因为 C 语言并没有内置这种数据结构，所以Redis 自己实现链表。
1.Redis 是一个双向链表，但是无环，表头的 prev 和 表尾的 next 指向 NULL。
2.Redis 的链表包含表头指针和表尾指针，可以将获取头尾节点复杂度降低为 O(1)
3.Redis链表包含长度计数器，可以使用 list 结构的 len 属性对持有的链表节点进行计数，复杂度为O(1)
4.Redis 链表使用 void* 指针来保存节点值，所以链表可以用于保存各种不同类型的值。
字典
在字典中，一个键（key）可以和一个值（value）进行关联，这些关联的键和值称之为键值对。
字典在 Redis 中应用相当广泛，比如Redis 的数据库就是使用字典来作为底层实现的，对数据库的操作都是基于对字典的操作之上。
字典还是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希键的底层实现。
键冲突
当有两个或者以上数量的键被分配到了哈希表数组的同一个索引上时，称之为键冲突。
Redis 的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这样就解决了键冲突的问题。
rehash
当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或收缩。
这个操作不是一次性完成的，为了避免程序在一瞬间执行大量操作造成程序暂停，rehash过程是渐进式完成的。
跳跃表
跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
Redis 使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis 就会使用跳跃表作为有序集合键的底层实现。
Redis 只在两个地方用到了跳跃表：
1.实现有序集合键。
2.集群节点中用作内部数据结构。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
整数集合
整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。
contents 数组是整数集合的底层实现：整数集合的每个元素都是他的一个数组项，各个项在数组中按照值的大小从小到大有序排列，并且数组不包含任何重复项。
升级（upgrade）
每当我们要将一个新元素添加到整数集合里面。并且新元素的类型比整数集合现有所有元素类型都要长时，整数集合需要进行 升级（upgrade）然后才能将新元素添加到整数集合里面。
1.根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2.将底层数组现有的所有元素都转换成与新元素相同类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
3.将新元素添加到底层数组里面。
整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。
压缩列表
压缩列表是列表键和哈希键的底层实现之一。当一个列表键或者哈希键只包含少量列表项，并且每个列表项要么是小整数值，要么就是长度比较短的字符串，那么Redis 就会使用压缩列表来做底层实现。
压缩列表是 Redis 为了节约内存而开发的，是由一系列特数编码的连续内存块组成的顺序形数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或一个整数值。
压缩列表可以包含多个节点，每个节点可以保存一个字节数组或整数值。
对象
Redis 基于简单字符串，双端链表，字典，压缩列表，整数集合等数据结构，创建了一个对象系统，这个系统包含：字符串对象，列表对象，哈希对象，集合对象和有序集合对象这五种类型对象。
我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
Redis 对象系统实现了基于引用计数技术的内存回收机制，当程序不在使用某个对象的时候，这个对象所占用的内存就会被自动释放。Redis 还通过引用计数技术实现了对象共享机制，它可以让多个数据库键共享同一对象来节约内存。
Redis 使用对象来表示键和值，每创建一个新的键值对时，Redis 至少创建两个对象，一个对象用作键值对的键，另一个对象用作键值对的值。
对于Redis 来说，键总是一个字符串对象，而值可以是Redis 任意一种对象。
内存回收
Redis 在自己的对象系统中构建了一个引用计数技术实现内存回收机制，程序可以通过跟踪对象的引用技术信息，在适当的时候自动释放对象并进行内存回收。
对象的整个生命周期可以划分为：创建对象，操作对象，释放对象三个阶段。
对象共享
Redis 中让多个键共享同一值需要两步操作：
1.将数据库键的值指针指向一个现有的值对象
2.将被共享的值对象的引用技术增一
共享对象机制对于节约内存非常有帮助，数据库中保存的相同值对象越多，对象共享机制就能节约越多的内存。
这些共享对象不只有字符串键可以使用，在数据结构中嵌套了字符串对象的对象都可以使用共享对象。
受到CPU时间的限制，Redis 值对包含整数值的字符串对象进行共享。
Redis 会共享值为 0 到 9999 的字符串对象。
学习资料
《Redis 设计与实现》