文档介绍：printk(KERN_DEBUG,"Hello World");
Redis内部数据结构详解之压缩链表(ziplist)
分类: Redis 2013-12-20 22:36 155人阅读评论(0) 收藏举报
redisziplist
。
Redis中压缩链表ziplist数据结构与API相关文件是:, , 。
一、ziplist的构成
<zlbytes><zltail><zllen><entry><entry><zlend>
<zlbytes>是一个4字节无符号整数,用来存储整个ziplist占用的字节数;
<zltail>是一个4字节无符号整数,用来存储ziplist最后一个节点的相对于ziplist首地
址偏移量;
<zllen>是一个2字节无符号整数,存储ziplist中节点的数目,最大值为(2^16 - 2),当
zllen大于最大值时,需要遍历整个ziplist才能获取ziplist节点的数目;
<entry>ziplist存储的节点,各个节点的字节数根据内容而定;
<zlend>是一个1字节无符号整数,值为255(11111111),作为ziplist的结尾符
二、ziplist宏模块
宏名称作用
ZIPLIST_BYTES(zl) 获取zlbytes值
ZIPLIST_TAIL_OFFSET(zl) 获取zltail值
ZIPLIST_LENGTH(zl) 获取zllen值
ZIPLIST_HEADER_SIZE 获取ziplist header的长度,固定为10个字节
ZIPLIST_ENTRY_HEAD(zl) 获取ziplist第一个entry的首地址
ZIPLIST_ENTRY_TAIL(zl) 获取ziplist最后一个entry的首地址
ZIPLIST_ENTRY_END(zl) 获取ziplist的末端,即zlend首地址
三、ziplist典型结构分布图
图中相关域以及宏的解析见上面的分析。
四、entry结构解析
prev_entry_bytes_length:
表示上个节点所占的字节数,即上个节点的长度,如果需要跳到上个节点,而已知道当前节
点的首地址p,上个节点的首地址prev = p-prev_entry_bytes_length
根据编码方式的不同,prev_entry_bytes_length可能占1 bytes或5 bytes:
1
1 bytes:如果上个节点的长度小于254,那么就只需要1个字节;
5 bytes:如果上个节点的长度大于等于254,那么就将第一个字节设为254(1111
1110),然后接下来的4个字节保存实际的长度值;
encoding与length:
ziplist的编码类型分为字符串、整数
encoding的前两个比特位用来判断编码类型是字符串或整数:
00, 01, 10表示contents中保存着字符串
11表示contents中保存着整数
字符串的具体编码方式:(_:预留,a:实际的二进制数)
编码编码长度 contents中的值
00aaaaaa 1 bytes 长度[0,63]个字节的字符串
01aaaaaa bbbbbbbb 2 bytes 长度[64,16383]个字节的字符串
01______ aaaaaaaa bbbbbbbb 5 bytes 长度[16384,2^32-1]个字节的字符串
dddddddd
11开头的整型编码方式:
编码编码长度 contents中的值
1100 0000 1 bytes int16_t类型整数
1101 0000 1 bytes int32_t类型整数
1110 0000 1 bytes int64_t类型整数
1111 0000 1 bytes 24 bit 有符号整数
1111 1110 1 bytes 8 bit 有符号整数
1111 xxxx 1 bytes 4 bit 无符号整数,[0,12]
解释一下1111 xxxx编码:1111 xxxx 首先最小值应该是0001(0000已经被占用),最大值应
该是1101(1110与111 1均已经被占用),因此,可被编码的值实际上只能是 1 至 13,由于还
需要减1,所以实际只能编码[0,12],至于减1的理由,我的理解是方便编码0。
五、zlentry数据结构
typedef struct zlentry {