1.跳跃表
是一种有序的数据结构,支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点
在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树要来的更为简单,
redis使用跳跃表作为有序集合键的底层实现之一,如果有序集合包含的元素较多,或者元素是较长的字符串时使用跳表.
跳表的实现原理:由redis.h/zskiplistNode和redis.h/zskiplist定义
struct zskiplistNode{
struct zskiplistLevel{
struct zskiplistNode *forward; //前进指针
unsigend int span; //跨度
}level[];
struct zskiplistNode *backward; // 后退指针
double score; // 分值
robj *obj; // 成员对象
}zskiplistNode;
结构解析:
1.层:跳跃表的节点的level数组可以包含多个元素,每个元素都包含一个指向其他节点的指针,程序可以通过这些层来加快访问其他节点的速度,一般来说层的数量越多,访问其他节点的速度就越快,每次创建一个新的跳跃表节点的时候程序就根据幂次定律(越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个就是其高度.
2.前进指针:
每个层都有一个指向表尾方向的前进指针,用于从表头向表尾访问节点,遍历跳跃表中所有节点的路径.
1)迭代程序首先访问跳跃表的第一个节点,从
3.跨度:层的跨度用于记录两个节点之间的距离:(两个节点之间的跨度越大,两者相距就越远)(指向null的所有前进指针跨度为0,)(
4.后退指针:用于从表尾向表头访问,每次只能后退至前一个节点.
5.分值和成员
节点的分值是一个double类型的浮点数,跳跃表中的所有节点都按分值从小到大进行排序.节点的成员对象是一个指针,它指向一个字符串对象,字符串对象保存着一个SDS;在同一个跳表中,各个节点保存的成员对象必须是唯一的,但多个节点保存的分值是可以相同的.分值相同的节点将按照成员对象在字典序中的大小进行排序.
多个跳跃表节点就可以组成一个跳跃表
struct zskiplist{
struct zskiplistNode *head,*tail;
unsigned long length;
int level;
}zskiplist
2.整数集合
整数集合是集合键的底层实现之一,还是那两个条件((～ o ～)~zZ
(元素量,和元素是字符串的长度过长);
整数集合用于保存整数值的集合抽象数据结构,并且保证集合中不会出现重复元素.在intset.h/intset中
struct intset{
uint32_t encoding;//编码方式
uint32_t length;//元素数量
int8_t contents[];//保存元素的数组
}intset;
contents数组是整数集合的底层实现,
如果encoding属性的值为INTSET_ENC_INT16 那么contexts就是一个int16_t类型的数组.
升级
当我们将一个新元素添加到整数集合里面,并且新元素的类型比整数集合的所有元素的类型都要长时,整数集合要升级,
升级:分为三步1)根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间,
2)将底层数组现有元素转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上.而且有序性不变.
3)将新元素添加到底层数组 总而言之就是换成新的类型,空间扩大
其好处为:提升整数集合的灵活性,尽可能的节约内存
5. 压缩列表
是列表键和哈希键的底层实现之一,当一个列表键只包含少量列表项,并且每个列表项要么是小整数值,要么就是长度比较短的字符串,那么redis使用压缩列表来做列表键的底层实现
压缩列表(如其名字)为了节省空间而开发的,一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数值,zlbytes,zltail,zllen,entryX,zlend
每个压缩列表节点可以保存一个字节数组或者一个整数值,其中,字节数组可以是以下三种长度的其中一种
长度小于等于63(2的六次方-1)字节的字节数组
长度小于等于16383(2的十四次方-1)字节的字节数组
长度小于等于4294967295(2的三十二次方-1)字节的数组
而整数值可以是六种以下之一 4位长,1字节,3字节,int16_t int32_t int64_t
previous_entry_length
节点属性以字节为单位,记录了压缩列表中前一个节点的长度,可以是1字节或者5字节
encoding属性记录了节点的content属性所保存的数据类型及长度,
content属性保存节点的值,节点值可以是一个字节数组或者整数,值得类型和长度由节点的encoding属性决定,
6.对象
redis并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,每种对象都是用到了至少一种我们前面所介绍的数据结构.
好处: 针对不同的使用场景,为对象设置多种不同的数据结构实现,优化使用场景,除此以外还实现了基于引用计数技术的内存回收机制(java CMS的gc)
对象的类型和编码:redis使用对象表示键值对,每次在数据库中设置键值对时,至少创建两个对象(可能有其他集合还有创建多个对象),一个键对象,一个值对象.每个对象由一个redisObject结构表示,结构如下:
struct redisObject {
unsigned type:4; //类型
unsigned encoding:4;//编码
void *ptr; //指向底层实现的数据结构指针
//
}robj;
type属性记录了对象的类型,这个属性的值可以是常量(redis的五种类型)的其中一个 可以使用type查看对象的类型.
ptr指向对象的底层数据结构,这些数据结构类型由对象的encoding属性决定,
对于设置编码:
字符串对象:编码是int,raw,embstr.例如:set number 100886; number的对象类型:(type:REDIS_STRING encoding:REDIS_ENCODING_INT ptr:"int的值")
例如: set story "LONG, jia jun long";
ptr: SDS类型(sdshdr free:0 len:18 buf:LONG, jia jun long 结合SDS结构的存储)
对于string类型,当字符串值长度小于等于32时使用类型为embstr的方式来保存字符串值得问题.
列表对象:编码可以是ziplist(压缩列表) linkedlist(链表)
rpush number 1 "three" 5
什么时间使用ziplist编码两个条件:
1)列表对象保存的所有字符串元素的长度都小于64字节:
2)列表对象保存的元素数量小于512个:不能满足这两个条件的使用linkedlist编码
哈希对象:编码可以是ziplist 或者 hashtable.
ziplist实现哈希对象,将保存了键的压缩列表节点推入到压缩列表表尾,然后将保存了值得压缩列表节点推入到压缩列表表尾,(保存了同一键值对的节点总是在一起的)
例如:HSET pro name "Tom"; HSET pro age 25;HSET pro career "Programmer"
hashtable编码的哈希对象的实现:每一个键值对都是使用一个字典键值对来保存(详情请见字典的数据类型的实现),
两者编码转换:使用ziplist 1)哈希对象保存的所有键值对的键和值的字符串长度都小于64字节2)哈希对象保存的键值对数量小于512个 (反之使用hashtable).
集合对象:编码可以是intest或者hashtable
intset整数集合,集合对象包含所有的元素都保存在整数集合里面,
编码转换: 当集合对象保存的所有元素都是整数值,集合对象的元素数量不超过512个满足这两个条件使用intset编码,否则使用hashtable
有序集合对象:编码可以是ziplist或者skiplist
发表回复