首页 > 数据库 >Redis基础数据结构

Redis基础数据结构

时间：2024-02-29 21:46:00浏览次数：28  
标签：Redis 基础 ht 链表 哈希 字符串 数据结构 节点

简单动态字符串SDS

在Redis里面字符串随处可见
比如

//设置一个(key,value)为msg和hello world的键值对
set msg "hello world"

在这里,msg和hello world都是一个字符串.

Redis自己构建了一个名为SDS(Simple Dynamic String 简单动态字符串)的类,用于作为Redis底层字符串的默认实现,只有当打印日志之类的,仅仅将字符串作为字面量(也就是不会进行修改的字符串)使用时,才会使用C语言自带的String实现.

Redis的AOF缓冲区和输入缓冲区也都是用SDS来实现的.可以说SDS是Redis中最常用最基本的数据结构了.

SDS的定义

sds.h/sdshdr

结构部分定义 描述
int len SDS字符串当前的长度,也就是buf数组中已经使用的部分
int free buf数组中还未使用的部分长度
char[] buf 真正存储字符串数据的部分

SDS字符串与C语言字符串一样在存储上一空字符为结尾"/0",len属性并不算入空字符的长度,所以在分配空间的时候会自动为SDS字符串多分配一字节的空间.这样的好处是可以在一些时候复用C字符串的API

我们可以看到SDS相对于C字符串还多了len和free属性,那么这样有什么好处呢?

  • 我们接下来就根据SDS与C字符串的差异来讲解SDS定义的优势

SDS数据结构的优势

提高获取字符串长度的性能

通过记录len属性,在获取字符串长度的时候,SDS可以通过直接获取len属性来达到O(1)的复杂度,而C字符串需要遍历字符串直到遇到空字符,然后返回遍历的字符个数,这样时间复杂度就是O(N),所以len属性能够极大的提高STRLEN命令或是其他时候需要获取字符串长度的速度.

防止缓冲区溢出

通过记录SDS字符串的长度,在对SDS对象进行处理的时候,比如在原字符串后拼接,或是更新为一个长度大于原字符串的新字符串,如果是C语言字符串,没有为该字符串分配足够的空间,可能会发生修改到改字符串的空间之外,即溢出.

当对S1字符串末尾追加" Cluster"字符串:strcat(s1," Cluster")

就会造成对S1修改的内容溢出到S2的空间.这是我们不希望看到的.
而对SDS的执行追加操作如sdscat函数,函数内部会先检查给SDS字符串分配的空间是否足够这次操作,如果不够会先对空间进行扩容,然后再进行操作.

减少修改字符串时的内存的重分配次数

C字符串的字符数组长度是依托于字符串长度的,一般来说一个存储N个字符的C字符串,其字符数组的长度就为N+1.而要是对该C字符串做修改操作:

  • 如字符串追加操作: 需要先进行内存重分配,而后再执行操作,如果没有进行内存重分配可能会出现缓冲区溢出问题
  • 如字符串截取操作: 需要先进行内存重分配来释放不需要的空间,而后再执行操作,如果没有进行内存重分配会出现内存泄露问题.

内存重分配需要进行系统调用,所以算是一个比较消耗性能的操作,而Redis作为一个数据库,修改操作时常发生,性能上还有一定要求,我们当然想要尽可能的避免经常进行内存重分配,减少内存重分配的次数来提高性能.

那么SDS是怎么来解决这些问题并且减少内存重分配的次数的呢?

  • 别忘了我们在SDS的定义中还有个free属性用于记录当前字符数组中还未使用的部分,我们通过free属性可以解除存储字符串的字符数组长度与字符串长度之间关联关系.这样我们就可以让buf字符数组分配的空间实际上大于字符串的长度了.

解除了该关联关系,我们就可以使用俩个策略来减少内存重分配次数了

  • 空间预分配: 在SDS字符串扩展操作时候,空间不足需要内存重分配时,不仅为buf分配该字符串需要的空间,还会分配额外的空间,这样进行增长操作时,会先检查当前SDS中预留分配的空间是否足够,如果足够,就能够使用之前额外分配的空间,而不是一律再进行内存重分配了.就能够减少字符串扩展操作时发生的内存重分配次数了.
    额外分配的空间大小也有对应的分配策略,我们可以来了解一下:
    • 如果修改之后len值小于1MB(也就是1024Byte),那么就会总共分配俩倍len属性的大小(额外分配len值大小的未使用空间).也就是分配之后,len属性的大小和free属性大小一致,如果我们有一个13大小的SDS字符串,在这个字符串末尾追加2字节的数据,那么内存重分配后的buf数组空间就会为:(13+2)*2+1(空字符所占1字节)=31
    • 如果修改之后len值大于等于1MB,那么就会额外分配1MB的未使用空间.如果我们有一个修改之后为30MB的SDS字符串,那么就会为其分配30MB+1MB=31MB的空间来使用.
  • 空间惰性释放: 在对SDS字符串进行缩减等会让字符串减少占用空间操作时,并不会直接进行内存重分配,而是先将减少的空间大小用free属性记录下来,在之后进行字符串扩展操作的时候可以进行利用.当然,当你担心这些空间造成浪费,可以使用sdsfree函数来进行释放对应的SDS字符串空闲空间.

二进制安全

有时候可能Redis数据库会被用来存放图片、音频等二进制数据而不是单纯是文本数据.但是C字符串需要使用空字符来控制字符串的结束,要是某个二进制数据规范是用空字符作分隔呢?或者需要使用到空字符的类型.而SDS字符串就支持这种场景,因为SDS字符串使用len来判断字符串的结束,而不是空字符,也不会对存入Redis的数据作过滤或是处理,存入的时候什么样,取出来的时候也就是什么样.这让Redis支持各种二进制数据的处理.

兼容部分C字符串的函数

因为SDS字符串buf字符数组还是与C字符串有一样的规范(比如以空字符结尾,并且会为空字符多分配一个空间),所以可以利用一些C语言<string.h>的库,就比如strcat,strcasecmp等.

链表

链表也是Redis中常用的数据结构,因为C语言没有内置的链表实现,所以Redis也就自己实现了.
我们通过链表可以将一个键对应多个值,当一个键对应了许多的值或是一些值的长度较长,Redis就会选择链表作为列表的实现(否则采用zipList压缩链表,这个数据结构后面会说).

127.0.0.1:6379> LPUSH integers 0 1 2
(integer) 3
127.0.0.1:6379> LLEN integers
(integer) 3
127.0.0.1:6379> LRANGE integers 0 2
1) "2"
2) "1"
3) "0"

链表的定义

这里链表的定义包括链表的定义和链表节点的定义,我们先来说链表节点的定义:
adlist.h/listNode

结构部分定义 描述
prev 指向前一个节点
next 指向后一个节点
value 当前节点的值

可以看到每个节点都有prev和next指针,多个节点相互链接组成了一个双向链表.

为了方便管理这些节点,Redis设计者又设计了list,统一管理这个链表中的节点:

adlist.h/list

结构部分定义 描述
head 指向该链表的头节点
tail 指向该链表的尾节点
len 记录该链表中有几个节点
dup 节点值复制函数
free 节点值释放函数
match 用于比较节点是否与给定值匹配的函数

可以注意到,其head节点的prev是NULL,而tail节点的next也是NULL,所以Redis的链表是一个无环链表.

字典

字典是一种用于保存键值对(key-value)的数据结构,也被称为MAP.
C语言中没有对其进行实现,所以Redis实现了字典数据结构.
在Redis中,数据库底层实现就是使用字典来实现的.对于数据库的各种增删改查操作也就是基于字典来操作的:

//数据库会在字典中创建一个key为msg,而value为hello world的键值对
set msg "hello world"
OK
get msg
"hello world"

Redis的哈希键也是使用字典来实现的:

127.0.0.1:6379> hset hashKey name "zhang" age 15
(integer) 2
127.0.0.1:6379> hgetAll hashKey
1) "name"
2) "zhang"
3) "age"
4) "15"
127.0.0.1:6379> hget hashKey name
"zhang"
127.0.0.1:6379> hget hashKey age
"15"
127.0.0.1:6379>

Redis字典的实现使用哈希表的思想来进行设计.

字典的定义

字典的定义也同样被分为字典,哈希表与哈希表节点:
dict.h/dictht

定义部分结构 描述
**table 哈希表数组,数组中的每一项指向一个dictEntry对象
size 哈希表大小
sizemark 用于哈希值计算,一般来说等于size-1
used 哈希表节点个数

dict.h/dictEntry

定义部分结构 定义部分子结构 描述
key 键值对的键
v val 值,指针类型
tu64 值,uint64类型
ts64 值,int64类型
next 指向下一个哈希表节点,构成一个链表

union的概念和结构体类似,不过是互斥的,union中的多个变量公用同一块内存,也就是说v这个属性可以是一个指针,也可以是一个uint64的整数,或是一个int64的整数.

因为有时候不同的键值对,其哈希值是相同的,会被分到相同的位置上(也就是键冲突),这个时候就通过next指针来构成一个链表.

字典结构的定义:
dict.h/dict

定义部分结构 描述
type 一个指向dictType的指针,字典类型,说是叫字典类型,其实该结构体中只是定义了一些字典的公用方法
privdata 私有数据,也就是在执行dictType中的共用方法时的一些可选参数
ht[2] 存储了俩个dictht哈希表,在rehash阶段的时候使用,当不在rehash阶段的时候只会有ht[0]被使用,ht[1]中的哈希表dictht中的dictEntry会为NULL
refreshidx rehash索引,当不在rehash阶段的时候值为-1

dict.h/dictType

/* 定义了字典操作的公共方法，类似于adlist.h文件中list的定义，将对节点的公共操作方法统一定义。搞不明白为什么要命名为dictType */
typedef struct dictType {
    /* hash方法，根据关键字计算哈希值 */
    unsigned int (*hashFunction)(const void *key);
    /* 复制key */
    void *(*keyDup)(void *privdata, const void *key);
    /* 复制value */
    void *(*valDup)(void *privdata, const void *obj);
    /* 关键字比较方法 */
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    /* 销毁key */
    void (*keyDestructor)(void *privdata, void *key);
    /* 销毁value */
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

我们可以看到Redis的字典使用了四种数据结构来构成,这四种数据结构的关系是这样的:

哈希算法

我们说过Redis的字典是通过哈希表的设计思想来设计的,那么它也有相应的哈希算法,根据key来算出对应的哈希值与索引值,来在对应位置新增节点或是寻找节点.

//先使用dictType结构体中的函数hashFunction来计算key值对应的hash值,使用的是MurmurHash2算法.
hash = dict->type->hashFunction(key);
//与哈希表的sizemark做与运算
//会根据情况来选择ht[0]还是ht[1],这个和rehash有关系,我们等会介绍
index = hash & dict->ht[x]->sizemark;

根据以上的步骤就能获取到一个索引值.

键冲突

有时候不同键值计算出的哈希值可能会相同,那这样就会导致不同键可能被添加到相同的哈希表的相同索引位置上.我们称这种情况为键冲突.
Redis字典采用链地址法来解决这种问题,当有不同的键值对映射到相同的索引位置上时,会使用dictEntry的next属性来将这些键值对连接成一个链表.

为了效率考虑,Redis总会将新节点放在链表的头结点位置,这样能够保证当获取新节点时的时间复杂度为O(1).

rehash

为了保持字典的负载因子保持在一个合理的范围,在一些情况下会程序会对字典进行扩展/收缩操作.

负载因子:哈希表中节点的个数/哈希表大小
load_factory = dict->ht[0]->used / dict->ht[0]->size

那么在哪些情况下会进行扩展和收缩操作呢?

  • 扩展这要根据程序是否在执行BGSAVE(用于后台异步保存当前数据库的数据到磁盘)或是BGREWRITEAOF(用于异步执行一个 AOF（AppendOnly File） 文件重写操作,重写会创建一个当前 AOF 文件的体积优化版本)命令来决定:
    • 在执行这些命令: 负载因子大于等于5
    • 不在执行这些命令: 负载因子大于等于1
  • 当负载因子小于0.1时进行收缩

因为在执行这些命令的时,操作系统会采取写时复制的优化技术,为了节约内存,尽量减少在这些时候进行扩展操作.

既然我们已经说了字典的负载因子,即什么时候字典会进行扩展和收缩,那么字典是如何进行扩展和收缩操作的呢?

  • 这就到这一部分的重点了,我们之前在介绍dict的定义的时候,说过ht[2],rehashidx属性,都需要为rehash阶段服务.
    而这个rehash阶段,就是来进行字典的扩展或是收缩操作的.我们接下来就来看一下rehash的步骤

rehash(重新散列)的步骤

  1. 先为ht[1]分配空间.
    • 如果是扩展操作,则分配的空间大小为:2ⁿ>=ht[0].used * 2
    • 如果是收缩操作,则分配的空间大小为:2ⁿ>=ht[0].used
  2. 将保存在ht[0]上的键值对根据ht[1]的属性重新计算哈希值和索引值(这也就是rehash),增加到ht[1]的哈希表中.
  3. 当ht[0]的键值对都被迁移到ht[1]的哈希表中后,将ht[0]的哈希表释放掉,然后再将ht[0]指针指向ht[1]的哈希表.再为ht[1]创建一个新的空的哈希表.为下一次refresh做准备.
步骤 状态
初始化
步骤1
步骤2
步骤3

渐进式Refresh

等下? 我们前面似乎说过dict字典中还有一个字段refreshIdx也是为refresh阶段服务的,但是为什么上面步骤里没有提及这个属性呢?

  • 在上面的步骤2,将ht[0]哈希表中的键值对迁移到ht[1]哈希表的操作似乎是一次性的,但是其实Redis在做这一步是渐进的.
    如果这个字典有几千万,几百万个键值对,甚至更多时,如果一次性就将所有的键值对迁移过去,庞大的计算量可能会造成一段时间内Redis停止服务.
    我们肯定是希望避免出现这种情况的.

那接下来就来介绍下渐进式Refresh的具体步骤

  1. 当为ht[1]分配完空间后,为dict的refreshidx属性分配为0,代表refresh阶段正式开始.
  2. 在refresh阶段中,每次对字典进行增,删,改,查操作时,不止会执行指定的操作,还会将ht[0]位于refreshidx位置的所有键值对重新计算散列值并迁移到ht[1]中.当refresh完成后,refreshidx值自增1
  3. 随着字典的操作,ht[0]上的键值对都会慢慢被迁移到ht[1]中,当ht[0]中的键值对都迁移到ht[1]后,Redis会将dict的refreshidx属性赋值为-1,接下来就和上面说的一样了,将ht[0]释放,ht[0]指向ht[1]的哈希表,然后再重新为ht[1]分配个空的哈希表.

当然,在渐进式Refresh阶段,是不能在ht[0]哈希表中新增新的键值对的,新增操作都会在ht[1]去执行,当对该字典进行查询的时候也会先进行查询ht[0]的哈希表中,如果没有再去ht[1]中寻找.

跳跃表

跳表是一种有序的顺序结构,通过在节点中的多个映射其他节点的指针来达到快速查询到相应大小节点的能力.
跳表支持平均O(logN),最坏O(N)的时间复杂度,还可以根据顺序性操作批处理节点.

可以认为一般来说节点中更高层的指针会指向链表中更后面的节点(也就是更大的节点),所以可以从节点的上层指针开始寻找,如果该指针指向的比所要寻找的大,就再从低一层指针去寻找,依此往复,寻找某个数的复杂度就从有效降低了,能够节省不少比较次数.
在使用Redis的有序集合时,如果集合中的字符串比较长,或者集合中的元素比较多,那么就会采用跳表作为有序集合的实现.

//增加一个键为score 而值为有序集合的键值对
127.0.0.1:6379> ZADD score 50 zhangsan 60 lisi 30 wangwu
(integer) 3
//可以看到这个集合中的数据都是根据分值来从大到小排序的
127.0.0.1:6379> ZRANGE score 0 2
1) "wangwu"
2) "zhangsan"
3) "lisi"
127.0.0.1:6379> ZRANGE score 0 2 WITHSCORES
1) "wangwu"
2) "30"
3) "zhangsan"
4) "50"
5) "lisi"
6) "60"

跳表的定义

跳表的定义由zskiplist结构与zskiplistNode组成
redis.h/zskiplist

typedef struct zskiplist{
  struct zskiplistNode *header,*tail;
  unsigned long length;
  int level;
}
结构部分定义 描述
header 指向跳表的头结点
tail 指向跳表的尾节点
level 记录跳表的层级(除了表头节点)
length 记录跳跃表中节点的数量 (除了表头结点)

可以看到zskiplist的结构还是较为清晰简单的,为什么level和length中都不包括表头节点呢?因为Redis的跳表中表头节点并不用于存储数据,并且还拥有层数有32层(),而是主要作为快速访问其他节点的指针结点来使用.

redis.h/zskiplistNode

typedef struct zskiplistNode{
  //层
  struct zskiplistLevel {
    //前进指针,每个结点的数个层,各自都拥有自己的前进指针,这个指针会指向表尾方向的结点.
    struct zskiplistNode *forward;
    //跨度
    unsigned int span;
  } level[];
  // 后退指针
  struct zskiplistNode *backward;
  // 分值
  double score;
  // 成员对象
  robj *obj;
} zskiplistNode;

层

层: 在生成某个跳跃表节点的时候,会根据幂次定律算法从1~32范围内取一个随机值作为该节点level数组的大小(也就是该节点的层数),而节点对应层数的指针会与附近有相同层数的指针相连.我们可以如图5-1,o1所在节点的L1,L2指针指向o2节点,而L3因为o2节点没有相同层数,而o3有,所以o1节点的L3层指针就直接连接到o3节点.

幂次定律是什么?为什么随机取层数需要根据这个定律呢?

  • 幂次定律: 表示在发生的时候,小部分事件的发生占据了大部分发生的频率.

看了是不是很迷糊? 我们可以先来看Redis具体取随机数的代码:

//获取一个随机值作为跳跃表节点层数,zskiplistNode结构level数组的长度
int zslRandomLevel (void) {
  //层数初始值
  int level = 1;
  //与0xFFFF(即1111111111111111)做与运算,只保留最低位2个字节的属性,取值范围会是0~65535
  // ZSKIPLIST_P是一个常数,这里为0.25
  // 所以level每次循环+1的概率为0.25
  while( (random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF) ){
     level+=1;
  }
  return (level < ZSKIPLIST_MAX_LEVEL) ? level : ZSKIPLIST_MAX_LEVEL ;
}

这样会让生成新跳跃表节点时,不会经常出现层数非常高的节点.能够保持跳跃表中的所有节点拥有的平均层数在一个较低的数值上.就不会导致经常出现层数高的节点,进一步减少高层数的比较次数.

幂次定律参考:https://blog.csdn.net/men_wen/article/details/70040026

跨度

我们有时候需要获取有序集合中某个成员在链表之中的位置,而ZSET(有序集合)也提供了一个ZRANK命令来获取对应成员的排位,那我们可以想想,跳跃表中如何获取到一个节点在链表之中的排位呢?

  • 可以直接遍历跳跃表的时候记录下遍历的次数来作为排位吗?不可以的,因为跳跃表是从高层节点先进行遍历的,高层大多数时候都可以使用少于O(N)的时间复杂度来完成寻找,这样做就会导致得到的排位比实际上的排位少.
    那我们就只能在层中记录下该层指针到下一个节点的跨度了(也就是经过了几个节点),这样在获取对应节点的排位时,只需要在遍历寻找该节点的时候对跨度进行累加即可.

跨度: 对应zskiplistNode->level[x].span用于表示该节点层数到下一个相同层数节点的距离,可以通过该属性来记录下寻找到的节点在链表之中的排位.

后退指针

zskiplistNode->backward
给跳跃表提供从后向前遍历的能力.不过跳表并没有维护从后向前遍历的层,所以只能从zskiplist->tail寻找到尾节点,然后一个个来遍历,直到遇到为NULL的后退指针.

成员对象与分值

成员对象:一个robj对象指针,指向一个字符串对象,保存着一个SDS值
分值:是一个double类型的值,跳跃表中的节点都会根据该值从小到大进行排序

成员对象在该跳表中是不可重复的,但是分值是可以重复的.

整数集合

当一个集合键中,集合元素不多,并且这些元素都是整数.
那么程序就会选择整数集合来作为集合键的实现.

127.0.0.1:6379> SADD numbers 0 1 2 3 4 5
(integer) 6
127.0.0.1:6379> OBJECT ENCODING numbers
"intset"

整数集合中保证出现的元素不会重复,并且集合中的元素按照从小到大排列.按照从小到大排列的好处就是可以在向集合之中插入元素的时候,可以直接根据大小来,查询到该元素的位置,并且判断该元素在集合中存不存在,而不用每次花费O(N)的时间去遍历查询.

整数集合的定义

intset.h/intset

typeof struct intset{
  //编码方式
  uint32_t encoding;
  //集合中元素的个数,也就是length的长度
  uint32_t length;
  //存放集合元素的数组,按照从小到大的顺序来存放元素
  int8_t contents[];
}

我们这里比较要关注的就是encoding属性相关的内容:
虽然结构体这将contents数组定义为int8_t类型(即使没有进行过升级,编码方式初始值也是为int16_t类型的),但实际上contents数组的类型取决于encoding字段.
如果encoding字段的取值为INTSET_ENC_INT16,那么contents数组的底层类型即为int16_t

intset具有自动升级的功能: 即在添加元素时,当前encoding指定的类型不够存放对应元素,会自动将encoding的取值以及contents数组的类型升级到能够存放该元素的整数.
我们接下来就来了解一下升级的过程.

不过要注意一下,intset并不会单独的为某一个元素设置单独的类型
比如:即使这个集合中只有一个元素需要int64_t的类型才能存储,而其他只需要int16_t类型,但还是会为集合中的每一个元素分配int64_t的空间来使用.

升级

当在向intset中添加元素的时,程序会判断当前的编码方式是否足够存储下对应元素,是否比现在的contents数组类型要长.
如果出现这种情况,则需要先对intset进行升级编码方式,然后再进行添加操作.

我们接下来就来了解一下升级的具体步骤:

  1. 根据新元素的类型来扩展intset底层数组的大小,并且为新元素分配好空间
  2. 将原本contents中的原元素转换成新的类型,然后将其迁移到正确的位置上,并保证集合内元素的有序性.
  3. 将新元素添加到底层数组中.

又是如何扩展的呢?什么叫迁移到正确的位置上呢?新元素是添加到什么位置的?
我们可以来想象一下升级进行中时内存中的分布:

  • 当一开始还未进行升级时:

  • 随后这个intset插入了一个65535的新整数,进行计算存储该整数所需的编码方式,我们计算为INTSET_ENC_INT32,很明显当前的编码方式INTSET_ENC_INT16是比它小的,所以我们需要进行升级

  • 现在正式进入升级环节:先对当前intset的encoding和length进行更新,然后进行内存空间扩展:

  • 再根据新的编码方式将原本数组上的整数都迁移到正确的位置:
    因为这里65535的位置是在数组末尾的,所以数组原元素只需要向后移动16位即可(这样每个数就占32位,符合INTSET_ENC_INT32的编码方式了),当然,是从最后一个整数3开始先进行迁移的,防止覆盖掉其他整数,迁移后为:

  • 到这一步,我们就只需要将新的整数赋值到96~127位的位置即可,即完成了整个升级并添加新元素的流程

我们有一个疑问,新元素是添加到什么位置的?我们可以想象,会引起数组进行升级操作的,只有当前编码方式存放不下的数,要么就是当前集合中最大的,要么就是当前集合中最小的.所以要么就是首部,要么就是尾部了.当添加到首部的时候,只需要将数组原元素多向后迁移一个元素的位置即可~

有了升级操作了之后,我们使用整数集合能够更加节约内存,提升灵活性,不需要考虑存入整数的大小,在有需要的时候,可以自动升级编码方式.不需要过早去定义占用空间大的数据类型,导致浪费空间.

虽然有升级操作,但是INTSET是没有降级操作的,比如我们上面举的例子,升级成了INTSET_ENC_INT32,他即使后面删除掉65535这个元素,依旧还是INTSET_ENC_INT32编码方式,而不会去降级为INTSET_ENC_INT16.

压缩列表

压缩链表是为了节约Redis的内存而提出的,是列表键或是哈希键的实现之一.
当列表键的值都是一些值较小的整数或是长度较短的字符串并且列表的长度较短时,Redis就会采用压缩链表作为列表键的实现.
当哈希键的键和值都是较小的整数或者长度短的字符串,就会采用压缩链表来作为列表键的实现.

当然,在Redis3.2版本后,又有了另一种数据结构quickList,他结合了链表和压缩链表的优点,这个我们之后再说~

压缩链表的定义


其中entryX列表节点部分又有其构成:
一个节点可以存储一个字节数组又或者是一个整数.

部分结构定义 描述
previous_entry_length 记录了压缩列表中当前节点的前一个节点的长度
encoding 记录了节点中content保存的内容数据类型与长度
content 节点中实际保存的内容
  • previous_entry_length: 为压缩链表提供从表尾节点向表头方向遍历的功能.该属性的值一般有俩种情况:
    • 前一个节点的长度<254字节时:直接用一个字节来表示前一个节点的长度
    • 前一个节点长度>=254字节时: 第一个字节值为0xFE(十进制为254),然后用后面四个字节来存储前一个节点的长度.
  • encoding: 记录了该结点的content的长度以及存储的内容类型,前俩位表示存储内容类型,后面表示长度,取值有以下几种:
  • content: 保存了该结点具体存储的内容,比如整数值或是字符数组~

连锁更新

我们可以根据上面给出的定义可以知道,节点之间需要维护previous_entry_length属性来保证压缩确保从后向前遍历的能力.
而列表节点部分,previous_entry_length属性会根据前一个结点的长度而为其分配不同大小的空间来存储.
所以我们可以知道,当一个节点的长度从小于254扩展到大于254时(也有可能是在某个节点前插入了一个长度大于254的节点),如果该结点的后一个结点原本只使用一个字节来存储previous_entry_length属性,就会对压缩链表进行内存重分配,给后一个结点的previous_entry_length分配5个字节的空间来存储前一个结点的长度.
这是乐观情况下,不会进行太多的内存重分配,那么要是多个连续的节点,其previous_entry_length都是1字节,并且这些节点的总长度都为250~253字节呢?这个时候在它们前面出现了一个节点长度超过254节点,造成连锁效应,就会造成大量的节点长度大于254,需要进行很多次的内存重分配来让每一个节点的previous_entry_length空间足够存储前一个节点的长度.
听起来是不是很可怕?
但其实这种情况还是比较少见的,因为大部分情况下,很少有很多个连续节点的长度刚好在250~253字节,而且即使出现连锁更新,只要这样的节点不多,少量的内存重分配并不是很影响效率.

标签：Redis,基础,ht,链表,哈希,字符串,数据结构,节点
From： https://www.cnblogs.com/youjunhui/p/18018708

相关文章

  • JAVA基础：java的参数传递机制
    基本类型的参数传递：    关键点：传的只是值传递，值传递：传输的是实参存储的值的副本  引用类型的参数传递：传递的是地址，是对象   ......
  • web前端基础
    软件架构体系：C/S:client/Server客户端/服务端QQ,酷狗,爱奇艺,王者荣耀等3D游戏B/S:browser/Server浏览器/服务端百度/淘宝/京东/网页版的爱奇艺/基于web前端技术实现的一些手机APP[例如：百度地图、喜马拉雅、消消乐、斗地主]web前端技术其是基于浏览器实现客户端的一套......
  • Day00----Web前端基础
    1，什么是Web前端技术？Web前端技术是基于浏览器实现客户端的一套综合技术，包括了HTML,CSS,Javascript等。UI客户端技术是基于UI模块实现客户端的一种UI模块＋打包模块，包括了Pygame，pyqt5,Tkinter,wxPython,PyGUI等结合pyinstaller.2，发展历史Linux-->90年-->GUNLinux美苏冷战（2极争......
  • JAVA基础：方法案例
    方法设计技巧：  packagecom.itheima.Method;publicclassMethod3{publicstaticvoidmain(String[]args){System.out.println(sum(10));pan(5);}publicstaticintsum(intn){intsum=0;for(inti=1;i<=......
  • JAVA基础：方法的其他形式 方法使用需要注意的常见问题
                方法使用需要注意的常见问题 packagecom.itheima.Method;publicclassMethod2{publicstaticvoidprinthelloworld1(){System.out.println("helloworld！");}publicstaticvoidmain(String[]args){......
  • Java基础语法
    注释注释不参与编译和运行修改注释颜色  关键字被Java赋予了特定含义的英文单词，所以关键字不能被我们使用字面量 标识符数据类型Scanner键盘录入......
  • Redis使用方法
    Widows版下载Windows版安装包 Redis-x64-3.2.100，由于Redis是绿色软件，解压后即可使用。我放在c盘programfiles中。 使用命令行开启Redis服务 在Redis-x64-3.2.100文件夹内，地址栏输入cmd，弹出命令行窗口，输入redis-server.exeredis.windows.conf，即可开启服务。可见本服务......
  • java基础
    目录java入门知识：一、开发环境二、关系三、变量四、标识符一、标识符命名的规则二、标识符命名规范1、标识符的命名规则：2、标识符的命名规范：3、变量的声明格式，变量的赋值格式，变量的三要素，变量应该注意几点4、java基本数据类型有哪些？5、java程序的开发步骤是什么？五、运算符一、算术......
  • MWC 2024丨中国电信柯瑞文：建设云网融合的新型数字基础设施
    2月27日，世界互联网大会在2024世界移动通信大会（MWC2024）期间举办“算力网络”专题论坛。中国电信董事长柯瑞文作题为《建设云网融合的新型数字基础设施》的主旨演讲，分享了中国电信在云网一体、云智一体、天地一体等领域持续开展科技创新，推动以云网融合为核心特征的数字信息基础设施......
  • 黑马python基础课的一些题
    1，打印5行小星星思路：可以用1个星星乘以行数；还可以循环嵌套，外层循环控制行数，内层循环控制每一行应该输出多少个小星星，比如，第一行输出1个，第二行输出2个，内层循环可以当成列，只不过这个列要和行对应，就是如果是第二行，那小星星就不能超过2列，即列数小于等于行数。代码：1row=12wh......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99