【Redis】数据结构（中）----ZipList(压缩列表)

文章目录

ZipList(压缩列表)
- 概念
- `ZipList`的结构
- `Entry`的内部结构
- - `previous_entry_length`
  - `Encoding`
  - - 存储字符串
    - 存储整数
  - `content`
- `ZipList`会存在的问题
- - 查询中间数据
  - 连锁更新
总结

ZipList(压缩列表)

概念

ZipList是一种特殊的"双端链表",由一系列特殊编码的连续内存块组成(所以本质上并不是链表,但是具有链表的特性).可以在任意一段进行压入/弹出操作,并且该操作的时间复杂度为O(1).

`ZipList`的结构

在这里插入图片描述
各属性含义:

这里我们看到,entry长度是不定的,也就是说,每个entry节点的大小并不是统一的,而是根据数据的大小来进行动态变化,这也是ZipList可以节省空间的关键

那么这里会引入一个问题:ZipList是如何进行寻址的呢?
这与entry的内部结构有关系.

`Entry`的内部结构

在这里插入图片描述

previous_entry_length:前一个节点的长度,占1个或者5个字节
- 如果前一个节点的长度小于254个字节,那么就采用1个字节来保存这个长度值
- 如果前一个节点的长度大于254个字节,那么就采用5个字节来保存这个长度值,并且第一个字节为0xfe,后四个字节才是真实的长数据
encoding:编码属性,记录当前content的数据类型(字符串还是整数)以及长度,占用1个,2个或者5个字节
contents:负责保存节点的数据,可以是字符串或者整数

Entry为什么这么设计:
这样设计,保证了正序遍历和逆序遍历.
正序遍历:正序遍历比较容易理解,因为ZipList是连续的内存空间,所以此处只需要从第一个entry起始地址开始,不断移动指针,便可以遍历完整个ZipList.
逆序遍历:

previous_entry_length和encoding都采用小端字节序来进行存储的.

小端字节序:低位字节在前,高位字节在后.例如:数值0x1234,采用小端字节序来进行存储时,实际的存储值为0x3412.

`previous_entry_length`

previous_entry_length:记录前一个节点的长度.

此时我们要存储字符串"ab"时,前面没有节点,所以此处为0,转换为16进制,就应该为0x00.

`Encoding`

Encoding:编码属性,记录当前content的数据类型(字符串还是整数)以及长度,占用1个,2个或者5个字节

存储字符串

首先是存储字符串的表示方式:
如果encoding是以00,01,10开头,则证明content是字符串

00:表示encoding的长度为1字节
01:表示encoding的长度为2字节
10:表示encoding的长度为5字节,且第1个字节不表示长度

例如还是存储"ab",此时"ab"占2字节,所以entry只需要占1字节即可,所以二进制形式应该表示为00000010,转化为16进制,表示为0x02

存储整数

如果encoding是以11开始,则证明content是整数,且encoding固定只占用1个字节
在这里插入图片描述
这里我们需要关注最后一种存储方式1111****,这里适用于比较小的整数,比如存储2,这时并不需要将数据内容存放到content中,只需要存储到encoding中即可,此时的encoding表示为11110011.转化为16进制,表示为0xf3,这样做的目的也是为了节省内存空间.

`content`

此处便是存储数据的位置,比较简单,比如"ab",此处转化为16进制数据后,可以得到:0x61和0x62.

综上所述:ZipList使用场景非常广泛,原因是:ZipList在节省内存方面作出了很多努力.
但ZipList只能做到正序遍历和倒序遍历,所以如果查询的内容位于中间,这就会带来数据遍历效率低的问题.也就是说:ZipList的数据查询和链表是一样的,只不过在节省空间方面,ZipList会更加优良

`ZipList`会存在的问题

查询中间数据

我们了解到,ZipList相当于一个具有连续内存空间的双向链表,那么就会具有双向链表中存在的中间数据遍历效率低的问题,因为ZipList并不能直接进行

连锁更新

ZipList某种特殊情况下产生的连续空间扩展操作称之为连锁更新

现在,假设我们有N个连续的,长度为250~253字节之间的entry,因此entry的previous_entry_length属性用1个字节即可表示,如下图所示:
在这里插入图片描述
此时,如果我们在第一个节点前面加上一个260字节长度的entry此时,之前的第一个entry中的pre_entry_length就需要从占用1字节变为占用5字节,此时后续的entry均需要发生这样的改变.这样就带来了连锁更新的情况
在这里插入图片描述
但是,连锁更新的情况,在Redis当中,并没有进行解决,原因是这种特殊情况是比较罕见的,需要同时满足:要有连续的,N个字节数在250~253之间长度的entry.