首先介绍redis底层实际存储数据的八种数据类型：
一、简单的动态字符串（SDS）
定义结构：
struct sdshdr{
int len; //记录buf数组使用的字节数量，也等于SDS保存字符的长度
int free； //记录buf数组中未使用的字节的数量
char buf[]; //字节数组，用于保存字符串
}
特性1：buf是一个字节数组，且遵循C字符串以'\0'结尾的特性，且保存'\0'的1字节空间不计入SDS的len使用空间内，所以对使用者透明。这样做最大的好处是可以重用一部分C字符串函数里面的函数
问题1：为什么不直接使用C字符串，而选择使用SDS这种结构存储字符？下面列举下SDS的优势：
（1）常数复杂度获取字符串长度：C字符串不能存储字符串长度，在获取字符串长度时需要对自身进行遍历，时间复杂度为N，而SDS只需要获取len属性就知道字符串长度
（2）杜绝缓存区溢出：在C字符串中进行数据拼接时，比如拼接两个字符串s1和s2，如果s1字符串没有足够的空间来容纳两个字符串，会导致溢出错误，但是SDS用于拼接的方法sdscat，它在拼接字符串前
会先检查给定的SDS空间是否足够，如果不够就先扩展SDS的空间
（3）减少修改字符串修改时带来的内存重分配次数：C字符串底层实现总是一个包含了N+1个字符长的数组，在增长字符串时需要通过内存重分配来扩展底层数组空间大小, 如果程序执行的是缩短字符串的操作，程序需要通过内存重分配来释放不需要使用的那一部分空间，否则会造成内存泄露，对于redis数据库这种对速度要求严苛，数据被频繁修改的场合，如果每次修改字符串都进行一次内存的重新分配，很显然是不可取的。针对这两个问题，SDS实现了空间预分配和惰性空间释放两种优化策略。
**** 空间预分配：对SDS进行修改后，SDS的api会检查使未使用的空间是否足够，如果足够，则如果SDS的长度小于未使用的空间，则无需进行内存重分配，否则，如果SDS需要的内存空间小于1M，那么会额外分配同样大小的空间作为未使用的字节大小，即len=free; 如果SDS需要的空间大于1M，那么程序会分配1MB的未使用空间。
**** 惰性空间释放：如果对SDS进行缩短操作，空出来的空间通过free属性记录而不直接释放，如果需要释放SDS的未使用空间，SDS也提供了相应的api。
（4）二进制安全：C字符串必须符合某种编码（比如ASCII码），并且除了字符串的末尾外，中间不能有空字符，否则程序只能读取第一个空字符串前的数据。这个限制使得C字符串只能保存文本文件，而SDS的api都是二进制安全的，也就是所有SDS API都会以处理二进制的方式来处理SDS存放在buf中的数据，程序不会对其中数据做任何限制、过滤或者假设，数据在写入时什么样，读取的时候就什么样。
二、链表结构
redis底层实现语言C是没有链表结构的，所以redis构建了自己的链表结构。链表的优点是方便重排，顺序访问，灵活调整长度。链表在redis中典型应用场景为列表键，列表键指的是列表的底层实现。当列表键包含较多元素或者包含元素较长时，列表键就会采用链表的形式储存数据。
链表结构要注意listNode结构，且redis的链表节点可以用来存储不同类型的结构。redis链表是无环结构，链表表头节点的prev指针和链表表尾节点的next指针都指向NULL
三、字典
1 概述：字典又称符号表，关联数组，映射，是一种保存键值对的抽象数据类型。字典作为一种常用的数据结构内置于很多高级编程语言中，但redis使用的C语言没有，因此redis构建了自己的字典实现。redis的数据库也是使用字典作为底层实现的。对数据库的增删查改操作也是基于字典操作之上。这里需要注意的是，当哈希键的键值对比较多或者键值对中的元素都是比较长的字符串时，redis就会使用字典作为哈希键的实现（哈希键就是我们的哈希表或者说时散列表，在python中，字典的底层实现是哈希表）
2 字典的实现
2.1哈希表
typedef struct dictht {
dictEntry **table; //哈希表数组，数组中每个元素都是指向dictEntry结构的指针，每个dictEntry均保存一个键值对，键值对除了保存键值外，还有next属性，指向另一个哈希表节点的指针，以此解决键冲突问题
unsigned long size;
unsigned long sizemask;
unsigned long used; //哈希表中节点数量
} dictht;
2.2 字典
typedef struct dict {
dictType *type; //类型特定函数，指向dicttype的指针，每个dicttype都保存了一簇用于键值对操作的函数，同时也包括了计算哈希值的函数
void *privdata; //传给特定函数的可选参数
dictht ht[2]; //两个哈希表组成的数组，一般情况下，字典只使用ht[0]哈希表，ht[1]只在rehash时使用
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;
这里有必要提下字典的哈希函数为 hash = dict->type->hashFunction 如果我们的key是k0的时候，key在字典的index的计算方法为：
index = hash(k0) & dict->ht[0或者1，具体看使用哪个hash表].sizemask
当字典被用作数据库的底层实现时，Redis 使用MurmurHash2算法来计算键的哈希值，该算法在输入的键很有规律时，算法仍能给出很好的随机分布性，且算法计算速度很快
2.3 解决键冲突
当有两个或者两个以上的键被分配到同一个index上面时，我们认为这些键发生了冲突，redis的哈希表使用链表来解决冲突，也就是多个被分配到同一索引的节点构成单向链表，链表中节点
通过next指针指向下一个节点
2.4哈希表的rehash
随着操作的不断执行，hash表中保存的键值对逐渐增加或者减少，为了让hash表的负载因子维持在一个合理的范围（这个接下来会讨论哈希表进行hash的条件），程序需要对哈希表进行相应的扩展
或者收缩，我们称这个过程为rehash过程，字典中的rehashidx和ptauserehash两个属性都表示rehash的状态。rehash分为一下几个步骤：
（1）为字典的h[1]哈希表分配空间，分配的空间大小取决于接下来要进行的操作和ht[0].used属性值。这点很好理解，如果执行的是扩展操作，那么h[1]分配的值为第一个大于等于ht[0].used*2的2的n次幂，
如果执行的是收缩操作，那么h[1]分配的值为第一个大于等于ht[0].used的2的n次幂。这里有一个问题，hash表大小为什么总是2的n次幂，我们的hash表的sizemask值为hash表大小（size）减1，由于dictht.size 的值为2的n次方，size-1（即sizemask）用二进制表示为0001111***11的形式，由于后n-1位为1，在与哈希函数计算出来的hash值做与操作时，会直接保留hash值的后n-1位。因此，在计算index
时速度快，index值可以保证不超过hash表的范围。
（2）在为ht[1]分配好了内存以后，将保存在ht[0]上的所有键值对rehash到ht[1]上，这里的rehash的意思是：重新计算键值对在ht[1]中的index值，然后将键值对放置到ht[1]指定位置上。
(3) 当ht[0]包含的所有键值对都迁移到ht[1]中后（这是个渐进的过程，所以也称为渐进式哈希, 这个之后会解释），ht[0]就变成了空表，释放ht[0], 将ht[1]置为ht[0], 在ht[1]处建立一个新的空白哈希表
接下来讨论哈希表在什么时候进行扩展或者收缩，之前提到负载因子计算方式为load_factor = ht[0].used/ht[0].size计算得到。
情况1：在哈希表的负载因子小于0.1的时候，程序自动对哈希表进行rehash收缩操作。
情况2：如果服务器（redis服务）目前没有执行BGSAVE命令（redis起redis子进程将数据库数据写入磁盘）或者BGREWRITEAOF命令时，当哈希表的负载因子大于等于1的时候，会进行rehash的扩展操作。
如果服务器执行了BGSAVE命令（redis起redis子进程将数据库数据写入磁盘）或者BGREWRITEAOF命令时，这个时候只有在负载因子大于等于5的时候才进行rehash操作，原因时执行以上命令时，大多数操作系统都采用写时复制技术（copy-on-write）来优化子进程的使用效率，所以这个时候尽量不要进行哈希表的扩展操作，避免不必要的内存写入操作导致操作系统写时复制。最大限度节约内存。关于写时复制参考链接：https://www.cnblogs.com/biyeymyhjob/archive/2012/07/20/2601655.html
2.5 渐进式哈希
rehash过程（将ht[0]键值对转移到ht[1]中）不是一次性集中完成，而是多次性、渐进式完成，这么做的原因是如果哈希表中键值对比较庞大的时候，比如几百上千万个键值对，如果服务器一次性完成rehash操作，可能会导致服务器在一段时间内停止服务。在渐进式的rehash过程中，rehash结束后会将字典的rehashidx属性置为-1。在rehash过程中，采用的是分而治之的方法，将rehash键值对所需要的工作拆分成单个键值对的添加，删除、查找和更新操作上。从而避免了rehash带来的庞大计算量。rehashidx的属性值代表的就是目前正在rehash的index。
在进行渐进式rehash期间，字典的删除，查找，更新操作会在两个哈希表中进行。但是如果是添加键值对的操作一律会保存到ht[1]表里面。这样可以保证ht[0]表只减不增，最终变成空表，rehash结束。
三 跳跃表
3.1 跳表（skiplist）
redis使用跳表作为有序集合的底层实现之一，这里要注意两点, 有序，跳表的查找时间复杂度为O(logn), 查找的原理有点像二分法。
跳表的节点定义为：
typedef struct zskiplistNode {
sds ele; //成员对象
double score; //分值，跳表中所有节点都是根据分值来进行排序, 如果分值一样的节点，节点顺序由成员对象决定
struct zskiplistNode *backward; //后退指针，从表尾到表头方向访问节点，每个节点只有一个后退指针，只能后退到前一个节点
struct zskiplistLevel {
struct zskiplistNode *forward; //前进指针，用于程序从表头到表尾方向访问跳表的节点，当碰到NULL时，程序知道已经到达了跳表的表尾
unsigned long span; //跨度，指向同一层级的下一节点的距离，注意，如果level[i].forward 指向的NULL，此时level[i].span为0。跨度不仅仅和遍历有关，通过跨度，可以快速计算节点所在的排名
} level[]; //层级列表，在每次创建一个节点的时候，程序都根据幂次定律随机生成的一个1-32的整数作为level数组大小，这个大小就是层的高度，高度越大，访问其他节点的速度就越快。
} zskiplistNode;
跳表的定义：
typedef struct zskiplist {
struct zskiplistNode *header, *tail; //表头和表尾节点
unsigned long length; //节点个数，在时间复杂度O(1)内获取跳表的长度
int level; //表中层数最大的节点的层数，不包括header指向的节点的层数，header节点为一个32层的level数组
} zskiplist;
由多个节点就可以组成一个跳跃表，但是通过zskiplist持有这些节点，更方便管理
四 整数集合 intset
当一个集合只包含整数值的元素，且集合元素不多时，redis会使用整数集合作为集合键的实现。整数集合的结构为：
typedef struct intset {
uint32_t encoding; //编码方式，代表contents数组中数的类型
uint32_t length; //整数集合包含的元素个数
int8_t contents[]; //各个项在数组中按照值的大小有序排列，且没有重复，虽然声明为int8_t，但真正类型取决于encoding属性的值
} intset;
4.1 整数集合的升级
整数集合的升级就是将contents数组中所有数字编码类型换成更大的数字编码，发生在往整数集合中添加整数，该整数不能用现有的编码方式表示。整数集合的升级分为三步：
（1）根据新元素的类型，扩展整数集合底层数组contents的大小，同时也要为新元素分配空间
（2）将底层数组中现有元素转换成新元素相同的类型，然后将转换之后的元素防止到正确的位置，确保底层数组的有序性不变
（3）将新元素添加到底层数组里，触发升级后，添加的元素要么大于所有现有元素，要么小于所有现有元素，因此新元素只可能放置在底层数组的开头或者结尾
升级机制的好处：
**** 灵活性高：
因为C是静态语言，我们通常不会将不同类型的数据放到同一个数组中，否则会报错。而使用整数集合，我们不需要担心这个，使用非常灵活
**** 节省内存：
如果需要一个数组同时保存int16_t, int32_t和int64_t三种类型的值，最简单的方法就是使用int64_t类型作为数组类型，这样会造成内存浪费的情况。而整数集合的做法是：如果你一直往集合中添加
int16_t的整数，整数集合的底层数组实现一直都是int16_t，这样避免了内存浪费。
重要提示：整数集合不支持降级操作
五 压缩列表 ziplist
当列表项要么就是小整数，要么就是长度比较短的字符串，那么redis就会使用压缩列表作为列表键的底层实现，此外压缩列表还是哈希键的底层实现之一。
压缩列表是Redis为了节省内存而开发的。是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
5.1 压缩列表的组成
前面说了，压缩列表是连续内存块组成的顺序型数据结构，压缩列表各个组成部分按顺序分别为：
**内存第一部分，zlbytes,类型uint32_t, 占用4字节** 记录整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配时（后面会讲到内存重分配机制）或者计算节点数量的时候使用
**zltail, uint32_t, 4字节** 记录压缩列表表尾节点到压缩列表起始地址有多少字节，其实也是一个偏移量，通过该参数能够很快确认表尾节点的地址
**zllen, uint16_t, 2字节** 记录压缩列表节点数量
**entryX, 列表节点的数据类型不定，大小不定**
**zlend, uint8_t，1字节** 标志位，特殊值0xFF,用于标记压缩列表的末端
5.2 压缩列表节点的组成
现在主要讲下entryX, X, 即压缩列表节点的构成：
每个压缩列表的节点由previous_entry_length、encoding、content组成
previous_entry_length：记录了上一个节点的长度，可以为1字节或者五字节，如果时五字节，最高位字节值为0xFE。通过该属性，程序可以根据当前节点的起始地址计算前一个节点的起始地址；
encoding: 记录了content属性保存数据的类型及长度，该属性可为一字节、二字节或者五字节长。属性值的高位分别为00，01，10，11。00代表一字节字节数组编码；
01代表两字节字节数组；11代表五字节字节数组，11代表整数编码。字节数组，整数的长度为除最高位两位外的值。
content: 节点保存的值，可以是字节数组或者整数。
5.3 连锁更新
每个节点previous_entry_length都存着上一个节点的长度，该属性为1-5字节。如果前一个节点长度小于254字节，那么此时当前节点previous_entry_length只占用一个字节。当前一个节点变大时，比如我们
在当前节点前插入一个大于254字节的节点，此时当前节点的previous_entry_length占用五个字节，而当前节点previous_entry_length属性仅长一个字节，此时程序会对压缩列表执行空间重分配操作。如果当前节点恰好大小位于[251,254]个字节之间，此时当前节点大小大于等于255个字节，下一节点的previous_entry_length也从1个字节变成5个字节，倘若接下来的所有节点都是[251,254]个字节之间,便会发生连锁反应，redis讲这种连续多次空间操作称为连锁更新。注意，删除节点也可能会造成连锁更新。
如果redis进行连锁跟新，需要进行n次空间重分配操作，每次空间重分配的最坏时间复杂度为O(n), 所以总的时间复杂度为O(n2)，这对性能影响比较大。但是要进行大规模的连锁更新的情况是不多见的，因为要满足连续多个节点长度位于[251,254]之间。一般情况如果进行连锁更新，且更新节点数不多，对redis性能不会造成很大影响。
六 redis的对象系统
前面讲到Redis用到的主要数据结构，比如简单动态字符串，链表，字典，压缩列表等。Redis并没有直接使用这些结构来实现键值对数据库，而是基于这些数据结构构建了一个对象系统，对象系统包含了字符串对象、列表对象、哈希对象、集合对象、有序集合对象这五类对象，每种对象都用到了至少一种我们前面介绍的数据结构。
Redis中的每一个对象都由一个redisObject结构表示：
typedef struct redisObject {
unsigned type:4; //类型：字符串对象、列表对象、哈希对象、集合对象、有序集合对象之一，标识着对象的类型
unsigned encoding:4; //编码：记录了对象使用了什么数据结构作为底层实现。每种对象都至少可以使用两种不同的编码方式，通过encoding来设置对象的编码，而不是为每个对象设定固定的编码方 式，极大提高了redis的灵活性和效率
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */ 记录对象最后一次被命令程序访问的时间。注意：如果用OBJECT IDLETIME （查询对象的空转时长）来访问该对象时，不会修改对象lru属性
int refcount; //引用计数，和redis内存回收机制有关，创建或者引用对象，引用计数加一，对象不再被一个程序引用时，引用计数减一，当引用计数为0时，对象所占用内存会被释放
void *ptr;
} robj;
注意：对于redis数据库保存的键值对来说，键总是一个字符串对象, 而值可以是字符串对象、列表对象、哈希对象、集合对象、有序集合对象中的一种，因此如果我们说一个键为列表键的时候，我们指的是这个数据库键所对应的值为列表对象。
标签：基本,字节,Rdis,redis,ht,列表,哈希,数据结构,节点 From： https://www.cnblogs.com/kevin-zsq/p/16836457.html