参考资料:《Redis设计与实现 第二版》;
本篇笔记按照书里的脉络,将知识点分为四个部分。其中第一部分数据结构与对象分为上中下篇,上篇包括:SDS、链表和字典;中篇包括跳跃表、整数集合和压缩列表;下篇为对象;
上篇的链接:https://www.cnblogs.com/dlhjw/p/15569578.html
跳跃表的定义,在redis.h/zskiplist
结构里:
typedef struct zskiplist { //表头节点和表尾节点 structz skiplistNode *header, *tail; //表中节点的数量(不包括表头指针) unsigned long length; //表中层数最大的节点的层数(不包括表头指针) int level; } zskiplist;
跳跃表节点的定义,在redis.h/zskiplistNode
结构里:
typedef struct zskiplistNode{ //后退指针 struct zskiplistNode *backwars; //分值 double score; //成员对象 robj *obj; //层 struct zskiplistLevel{ //前进指针 struct zskiplistNode *forward; //跨度 unsigned int apan; } level[]; } askiplistNode;
L1
、L2
、L3
等来标记节点的各个层,每个层有前进指针和跨度;
rank
有关。查找某个节点时,将沿途层相加,得到排位;BW
字样的为后退指针;1.0
、2.0
、3.0
为分值,分值从小到大排列;
o1
、o2
、o3
等是成员对象,成员对象必须唯一;level
为5是因为o3对象有5层,为该跳跃表中最大层;函数 | 作用 | 时间复杂度 |
---|---|---|
zslCreate | 创建一个新的跳跃表 | O(1) |
zslFree | 释放给定跳跃表,以及表中包含的所有节点 | O(N),N为跳跃表的长度 |
zslInsert | 将包含给定成员和分值的新节点添加到跳跃表中 | 平均O(logN),最坏O(N),N为跳跃表长度 |
zslDelete | 删除跳跃表中包含给定成员和分值的节点 | 平均O(logN),最坏O(N),N为跳跃表长度 |
zslGetRank | 返回包含给定成员和分值的节点在跳跃表中的排位 | 平均O(logN),最坏O(N),N为跳跃表长度 |
zslGetElementByRank | 返回包含给定成员和分值的节点在跳跃表中的排位 | 平均O(logN) ,最坏O(N),N为跳跃表长度 |
zslIsInRange | 给定一个分值范围(range),比如0到15,20到28,诸如此类,如果给定的分值范围包含在跳跃表的分值范围内,返回1,否则返回0 | O(1),基于通过跳跃表的表头节点和表尾节点的分值得到范围 |
zslFirstInRange | 给定一个分值范围,返回跳跃表中第一个符合这个范围的节点 | 平均O(logN),最坏O(N),N为跳跃表长度 |
zslLastInRange | 给定一个分值范围,返回跳跃表中最后一个符合这个范围的节点 | 平均O(logN),最坏O(N),N为跳跃表长度 |
zslDeleteRangeByScore | 给定一个分值范围,删除跳跃表中所有在这个范围之内的节点 | O(N),N为被删除节点数量 |
zslDeleteRangeByRank | 给定一个排位范围,删除跳跃表中所有在这个范围之内的节点 | O(N),N为被删除节点数量 |
整数集合的定义,在intset.h/intset
结构中:
typedef struct intset{ //编码方式 uint32_t encoding; //集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[]; } intset;
contents
声明为 int8_t 类型的数组,但数组的真正类型取决于encoding
属性的值;encoding值 | contents值 | 范围 |
---|---|---|
INTSET_ENC_INT16 | int16_t | -32768~32768 |
INTSET_ENC_INT32 | int32_t | -2147483648~2147483647 |
INTSET_ENC_INT64 | int64_t | -9223372036854775808~9223372036854775807 |
函数 | 作用 | 时间复杂度 |
---|---|---|
intsetNew | 创建一个新的整数集合 | O(1) |
intsetAdd | 将给定元素添加到整数集合里面 | O(N) |
intsetRemove | 从整数集合中移除给定元素 | O(N) |
intsetFind | 检查给定值是否存在于集合 | O(logN),整数集合有序排列,可以用二分查找法 |
intsetRandom | 从整数集合中随机返回一个元素 | O(1) |
intsetGet | 取出底层数组在给定索引上的元素 | O(1) |
intsetLen | 返回整数集合包含的元素个数 | O(1) |
intsetBlobLen | 返回整数集合咱用的内存字节数 | O(1) |
节点的定义在ziplist.c/zlentry
结构里:
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;
prevrawlen
的值获得前置节点的首地址,可以由此实现从尾到头的遍历;*p
指向一个content
,保存节点的值,值的类型和长度由encoding
决定;encoding
的属性(下划线表示留空,abcdx代表实际二进制数据):prevrawlen
属性,用于记录前一个节点的长度,前一个节点的长度变化会影响prevrawlen
属性的长度取值(使用1个字节存储前一个节点的长度还是5个);函数 | 作用 | 时间复杂度 |
---|---|---|
ziplistNew | 创建一个新的压缩列表 | O(1) |
ziplistPush | 创建一个包含给定值的新节点,并将这个新节点添加到压缩列表的表头或表尾 | 平均O(N),最坏O(N2) |
ziplistInsert | 将包含给定值的新节点插入到给定节点之后 | 平均O(N),最坏O(N2) |
ziplistIndex | 返回压缩列表给定索引上的节点 | O(N) |
ziplistFind | 在压缩列表中查找并返回包含了给定值的节点 | 当保存的是字节数字时为O(N2),整数时为O(N) |
ziplistNext | 返回给定节点的下一个节点 | O(1) |
ziplistPrev | 返回给定节点的前一个节点 | O(1) |
ziplistGet | 获取给顶节点说保存的值 | O(1) |
ziplistDelete | 从压缩列表中删除给定的节点 | 平均O(N),最坏O(N2) |
ziplistDeleteRange | 删除压缩列表在给定索引上的连续多个节点 | 平均O(N),最坏O(N2) |
ziplistBlobLen | 返回压缩列表目前占用的内存字节数 | O(1) |
ziplistLen | 返回压缩列表目前包含的节点数量 | 节点数量小于65535时为O(1),大于65535时为O(N) |