Redis源码分析-底层数据结构盘点 (2)

跳表节点结构体除了维护保存的关键字外还保存下一个链表节点指针levelnext和当前层数currentlevel。可以看见,下一个链表节点指针是一个大小为3的数组.

数组中的元素指向该节点在某一层的下一个节点。

譬如示意图中的14节点,它的level[0]指向23,level[1]指向34,level[2]指向50。当需要降层查询时,只需要将clevel-1即可。这样便实现了跳表的基本查询逻辑。

而跳表的插入删除逻辑,在经过O(logn)复杂度查找到待删除节点或插入位置后,经过O(1)的时间复杂度即可完成。

 

5.跳表索引更新

 

下面考虑这样的问题

如果我往例子中的跳表插入24、25、26、27,那么在14-34之间元素就会新增加4个,那么如果我在这之间继续插入更多元素,但又不更新索引,那么随着插入元素的增加,跳表的查询效率将会退化成O(n)。

其实,这就像二叉排序树的失衡问题,平衡二叉树通过额外的翻转操作来维护树的左右平衡来确保它的效率,在跳表中,这个额外的操作就是更新索引,那么,跳表是怎么更新索引的呢?

在redis 中是通过一个随机函数,来决定将这个结点插入到哪几层索引中,比如随机函数生成了值K,那么我就将这个结点添加到第一级的到第K级的索引中,以此来避免复杂度的退化。

 

最后补充一点,redis中的 跳表实际上是双向的,并且保存头尾指针,支持双向遍历。

 

四、ziplist(压缩链表)

 

1.ziplist介绍

 

ziplist是经过特殊编码的方式压缩的集合

redis中,当list和hash元素较少并且数值较小时,使用ziplist实现,因为在数据量小的时候ziplist的查询效率接近于O(1),与hash效率相似,ziplist是一整块连续内存,实质是个数组,不利于插入删除和查找。删除节点时,将节点之后的所有节点前移。由于节点保存前一个节点的长度(可能一个字节,可能4个字节),如果删除某节点后导致之后的节点长度发生变化,需要级联更新之后的各个节点长度,直到不用更新长度的节点为止。

ziplist唯一的优势:以字节为单位,通过压缩变长编码的方式节省大量存储空间,当需要使用时,数据可以从磁盘中快速导入内存中处理,而数据在内存中的操作速度是极快的,通过节省存储空间的方式节省了时间。

 

2.ziplist数据结构

 

我们先看一个普通数组arr[100]的空间利用情况

struct Node{

 int value1;

    long value2;

}arr[100];

arr数组内存2个变量value1、value2,分别是int及long类型,分别占用4个字节和8个字节,当我们存储小数值时,就会导致内存的浪费,如arr[0].value1=100,实际上100仅使用了1个字节,但是却占用了4个字节。

而ziplisl就是redis为充分利用存储空间所设计的数据结构,实际上就是一个字节数组。

char ziplist[];

所有类型的数据,包括long、int、指针类型、字符串类型,在存入ziplist时都会先被压缩编码。

 

3.ziplist.两个问题

 

问:由于保存进ziplist的元素都会被压缩编码,ziplist中每个节点所占的字节数并不是固定的,那么ziplist能否用链表来存储呢?

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzwdyj.html