《Redis设计与实现》[第一部分]数据结构与对象-C源码阅读（二）
4、跳跃表
跳跃表支持平均O（logN）、最坏O(N)复杂度的结点查找，还可以通过顺序性操作来批量处理结点。 在大部份情况下，跳跃表的效力可以和平衡树相媲美，由于跳跃表的实现比平衡树来得更加简单，所以很多程序都使用跳跃表代替平衡树。 Redis使用跳跃表作为有序集合键的底层实现之1，如果有1个有序集合包括的元素数量比较多，或有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表作为有序集合键的底层实现。 Redis只在两个地方用到了跳跃表，1个是实现有序集合键，另外一个是在集群结点中用作内部数据结构 数据结构源码Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义： /*
* 跳跃表节点
*/
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;zskiplistNode结构包括以下属性：
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header,*tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;zskiplist结构用于保存跳跃表结点的相干信息，如结点数量，指向表头结点和表尾结点的指针等：
表头结点和其他结点的构造是1样的：表头结点也有后退指针、分值和成员对象，不过表头结点的这些属性都不会被用到。 5、整数集合
整数集合（intset）是集合键的底层实现之1，当1个集合只包括整数值元素，并且这个集合的元素数量不多时，Redis就使用整数集合作为集合键的底层实现。 数据结构源码typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包括的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t或int64_t的整数值，并且保证集合中不会出现重复元素。
整数集合的升级策略当将1个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。 升级整数集合并添加新元素共分为3步进行：
由于每次向整数集合添加新元素都可能会引发升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(N) 引发升级的新元素长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要末大于所有现有元素，要末小于所有现有元素：
整数集合的升级策略有两个好处：
整数集合不支持降级操作，1旦对数组升级，编码就会1直保持升级后的状态。 6、紧缩列表
紧缩列表（ziplist）是列表键和哈希键的底层实现之1。当1个列表键只包括少许列表项，且每一个列表项要末是小整数值，要末是长度比较短的字符串，那末Redis就会是1紧缩列表来做列表键的底层实现 紧缩列表是Redis为了节俭内存开发的，是由1系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。1个紧缩列表可以包括任意多个结点（Entry），每一个结点保存1个字节数组或1个整数值。 数据结构源码
/*
空白 ziplist 示例图
area |<---- ziplist header ---->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 1 byte
+---------+--------+-------+-----------+
component | zlbytes | zltail | zllen | zlend |
| | | | |
value | 1011 | 1010 | 0 | 1111 1111 |
+---------+--------+-------+-----------+
^
|
ZIPLIST_ENTRY_HEAD
&
address ZIPLIST_ENTRY_TAIL
&
ZIPLIST_ENTRY_END
非空 ziplist 示例图
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
*/
/*
* 保存 ziplist 节点信息的结构
*/
typedef struct zlentry {
// prevrawlen ：前置节点的长度
// prevrawlensize ：编码 prevrawlen 所需的字节大小
unsigned int prevrawlensize,prevrawlen;
// len ：当前节点值的长度
// lensize ：编码 len 所需的字节大小
unsigned int lensize,len;
// 当前节点 header 的大小
// 等于 prevrawlensize + lensize
unsigned int headersize;
// 当前节点值所使用的编码类型
unsigned char encoding;
// 指向当前节点的指针
unsigned char *p;
} zlentry;每一个紧缩列表结点可以保存1个字节数组或1个整数值，其中，字节数组可以是以下3种长度的其中1种：
整数值则可以是以下中的1种：
每一个紧缩列表结点都由previous_entry_length、encoding、content3个部份：
连锁更新紧缩列表的添加新节点操作和删除结点操作都可能会引发连锁更新： 连锁更新在最坏情况下需要对紧缩列表履行N次空间重分配操作，而每次空间重分配的最坏复杂度为O（N），所以连锁更新的最坏复杂度为O(N^2) 虽然连锁更新的复杂度较高，但它真正造成性能问题的可能性不大：
7、对象
Redis基于以上数据结构创建了1个对象系统，这个系统包括字符串对象、列表对象、哈希对象、集合对象和有序集合对象这5种类型的对象，每种对象都用到了最少1种以上数据结构。 使用对象的好处：
数据结构源码Redis使用对象来表示数据库中的键和值，数据库中新创建1个键值对时，最少会创建两个对象：键对象，用作键值对的键，值对象，用作键值对的值 typedef struct redisObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 对象最后1次被访问的时间，用于计算对象的空转时长
// 当服务器占用的内存数超过了maxmemory选项设置的上限时，空转时长高的那部份键会优先被服务器释放，从而回收内存
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 援用计数
int refcount;
// 指向实际值的指针
void *ptr;
} robj;Redis中的每一个对象都由1个redisObject结构表示，该结构中的type属性、encoding属性和ptr属性与保存数据相关：
通过encoding设定对象所使用的编码，使得Redis可以根据不同的使用处景为1个对象设置不同的编码，从而优化对象在某1场景下的效力 字符串对象的编码转换字符串对象的编码可以是int、raw或embstr。 如果1个字符串对象保存的是long类型的整数值，那末字符串对象会将整数值保存在字符串对象结构的ptr属性里（将void*转换成long），并将字符串对象的编码设置为int。 如果字符串对象保存的是1个字符串值，并且这个字符串值的长度小于等于32字节，那末字符串对象将使用embstr编码的方式来保存这个字符串值。 可以用long double类型表示的浮点数在Redis中也是作为字符串值保存的。 对int编码的字符串对象，如果我们向对象履行了1些命令，使对象保存的不再是整数，而是1个字符串值，那末字符串对象的编码将从int变成raw。 embstr编码的字符串对象实际上是只读的。对embstr编码的字符串对象履行任何修改命令时，程序会先将对象的编码从embstr转换成raw，然后再履行修改命令。所以，embstr编码的字符串对象在履行修改命令后，总会变成1个raw编码的字符串对象 列表对象的编码转换列表对象的编码可以是ziplist或Linkedlist。 ziplist编码的列表对象使用紧缩列表作为底层实现，每一个紧缩列表结点（Entry）保存了1个列表元素。 Linkedlist编码的列表对象使用双端链表作为底层实现，每一个双端链表结点（Node）保存1个字符串对象，而每一个字符串对象保存1个列表元素。 当列表对象同时满足以下两个条件时，列表对象使用ziplist编码：
否则使用linkedlist编码。 哈希对象的编码转换哈希对象的编码可以是ziplist或hashtable。 ziplist编码的哈希对象使用紧缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存键的紧缩列表结点推入到紧缩列表表尾，然后再将保存值的紧缩列表结点推入到紧缩列表表尾：
hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每一个键值对都使用1个字典键值对来保存：
当哈希对象同时满足以下两个条件时，哈希对象使用ziplist编码：
否则需要使用hashtable编码。 集合对象的编码转换集合对象的编码可以是intset或hashtable。 intset编码的集合对象使用整数集合作为底层实现，集合对象包括的所有元素都被保存在整数集合里。 hashtable编码的集合对象使用字典作为底层实现，字典的每一个键都是1个字符串对象，每一个字符串对象包括1个集合元素，而字典的值则全部被设置为null. 当满足以下两个条件时，使用intset编码：
否则使用hashtable编码。 有序集合对象的编码转换有序集合的编码可以是ziplist或skiplist。 ziplist编码的有序集合对象使用紧缩列表作为底层实现，每一个集合元素使用两个紧挨在1起的紧缩列表结点保存，第1个结点保存元素的成员（member），第2个元素则保存元素的分值（score）。 紧缩列表内的集合元素按分值从小到大进行排序，分值较小的元素靠近表头的方向，分值较大靠近表尾。 skiplist编码的有序集合对象使用zset结构作为底层实现，1个zset结构同时包括1个字典和1个跳跃表： /*
* 有序集合
*/
typedef struct zset {
// 字典，键为成员，值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表，按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 和范围操作
zskiplist *zsl;
} zset;有序集合每一个元素的成员都是1个字符串对象，而每一个元素的分值都是1个double类型的浮点数。 虽然zset结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来同享相同元素的成员和分值，所以同时使用跳跃表和字典保存集合元素，不会产生重复成员和分值，不会因此浪费额外内存。 满足以下两个条件时，对象使用ziplist编码：
否则有序集合对象使用skiplist编码。 类型检查与命令多态Redis中用于操作键的命令可分为两种类型：
在履行1个类型特定的命令之前，Redis会先检查输入键的类型是不是正确，然后再决定是不是履行给定的命令。 类型特定命令的类型检查是通过redisObject结构的type属性来实现的：
Redis还会根据对象的编码方式，选择正确的命令实现代码来履行命令。 内存回收与对象同享Redis通过援用计数技术实现内存回收机制。 对象的援用计数信息会随着对象的使用状态而不断变化：
基于援用计数的对象同享机制使Redis更节俭内存。 Redis的同享对象包括字符串键，和那些在数据结构中嵌套了字符串对象的对象（linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象，zset编码的有序集合对象）也能够使用这些同享对象。 Redis只对包括整数值的字符串对象进行同享。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
