Redis底层数据结构,今日免费续餐!

1

跳跃表

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素,效率和平衡树媲美 ——查找、删除、添加等操作都可以在对数期望时间下完成,并且比起平衡树来说,跳跃表的实现要简单直观得多。

Redis 只在两个地方用到了跳跃表,一个是实现有序集合键,另外一个是在集群节点中用作内部数据结构。

Redis 的跳跃表 主要由两部分组成:zskiplist(链表)和zskiplistNode (节点)

typedef struct zskiplistNode{

//层

struct zskiplistLevel{

//前进指针

struct zskiplistNode *forward;

//跨度

unsigned int span;

} level[];

//后退指针

struct zskiplistNode *backward;

//分值

double score;

//成员对象

robj *obj;

}

1层:level 数组可以包含多个元素,每个元素都包含一个指向其他节点的指针。

2前进指针:用于指向表尾方向的前进指针

3跨度:用于记录两个节点之间的距离

4后退指针:用于从表尾向表头方向访问节点

5分值和成员:跳跃表中的所有节点都按分值从小到大排序。成员对象指向一个字符串,这个字符串对象保存着一个SDS值

typedef struct zskiplist {

//表头节点和表尾节点

structz skiplistNode *header,*tail;

//表中节点数量

unsigned long length;

//表中层数最大的节点的层数

int level;

}zskiplist;

header,tail分别指向跳跃表的头结点和尾节点。level 用于记录最大的层数,length 用于记录我们的节点数量。

总结:

跳跃表是有序集合的底层实现之一

主要有zskiplist 和zskiplistNode两个结构组成

每个跳跃表节点的层高都是1至32之间的随机数

在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的对象必须是唯一的

节点按照分值的大小从大到小排序,如果分值相同,则按成员对象大小排序

2

整数集合(Intest)

一个特殊的集合,里面存储的数据只能够是整数,并且数据量不能过大。

typedef struct intset{

//编码方式

uint32_t enconding;

// 集合包含的元素数量

uint32_t length;

//保存元素的数组

int8_t contents[];

}

1encoding:用于定义整数集合的编码方式

2length:用于记录整数集合中变量的数量

3contents:用于保存元素的数组,虽然我们在数据结构图中看到,intset将数组定义为int8_t,但实际上数组保存的元素类型取决于encoding

整数集合的升级

intset 在默认情况下会帮我们设定整数集合中的编码方式,但是当我们存入的整数不符合整数集合中的编码格式时,就需要使用到Redis 中的升级策略来解决。

Intset 中升级整数集合并添加新元素共分为三步进行:

1根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间

2将底层数组现有的所有元素都转换成新的编码格式,重新分配空间

3将新元素加入到底层数组中

总结:

整数集合是集合建的底层实现之一

整数集合的底层实现为数组,这个数组以有序,无重复的范式保存集合元素,在有需要时,程序会根据新添加的元素类型改变这个数组的类型

升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存

整数集合只支持升级操作,不支持降级操作

3

压缩列表

1zlbytes:用于记录整个压缩列表占用的内存字节数

2zltail:记录要列表尾节点距离压缩列表的起始地址有多少字节

3zllen:记录了压缩列表包含的节点数量。

4entryX:要说列表包含的各个节点

5zlend:用于标记压缩列表的末端

总结:

压缩列表是一种为了节约内存而开发的顺序型数据结构

压缩列表被用作列表键和哈希键的底层实现之一

压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值

添加新节点到压缩列表,可能会引发连锁更新操作。

祝您今日的用餐愉快,明天供应餐点为Redis持久化

程序员食堂

用了这么久了,

还没关注公众号吗。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180705G1R09D00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券