redis数据结构--压缩列表
2019-05-19 本文已影响0人
MontyOak
压缩列表是列表和哈希的底层实现之一。当列表中元素较少，且元素为小整数或短字符串的时候，redis使用压缩列表作为列表的底层实现。当哈希里包含少量键值对，且键值均为小整数或者短字符串的时候，redis使用压缩列表作为底层实现。
压缩列表为了节省内存而设计，是连续数据结构。由以下几个部分组成：
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4byte | 记录整个列表的内存占用字节数，内存重新分配或者计算zlend的时候使用 |
| zltail | uint32_t | 4byte | 记录表尾相对于起始位置的偏移量，方便快速访问表尾 |
| zllen | uint16_t | 2byte | 记录节点总数，当节点总数大于uint16_max(65535)时，需要遍历节点才能知道节点总数 |
| entryX | 列表节点 | 不定 | 用于存放实际的节点数据 |
| zlend | uint8_t | 1byte | 特殊值0xFF，标记列表结束 |
压缩列表节点由previous_entry_length，encoding，content三部分组成。
其中content可以保存一个字节数组或者整数值，字节数组可以是：
- 长度小于等于63(2^6 - 1)的字节数组；
- 长度小于等于16383(2^14 - 1)的字节数组；
- 长度小于等于4294967295(2^32 - 1)的字节数组；
整数则是以下一种： - 4位长，在0到12之间的整数；
- 1字节长有符号整数；
- 3字节长有符号整数；
- int16_t，int32_t，int64_t
previous_entry_length是长度为1或5的整数，记录前一个节点的完整长度。encoding记录content的数据类型及其长度。
可以看出，由于previous_entry_length长度不确定，因而导致节点长度不确定，在发生节点插入或者删除的时候，可能会出现多个节点连锁更新的情况。
