欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

redis支持的数据结构

程序员文章站 2022-03-10 18:33:08
redis支持的数据结构个人读书笔记简单动态字符串 (String)链表(list)字典跳跃表整数集合压缩列表对象sds(简单动态字符串)定义://记录buf数组中已使用字节的数量int len//记录buf数组中未使用字节的数量int free//字节数组 用于保存字符串char buf []使用sds的好处是:1.方便获取当前字符串的长度2.杜绝缓冲区溢出3.减少字符串修改带来的内存重分配次数.修改之后......

redis支持的数据结构

个人读书笔记

  • 简单动态字符串 (String)
  • 链表(list)
  • 字典
  • 跳跃表
  • 整数集合
  • 压缩列表
  • 对象

 

 

 

 

  1. sds(简单动态字符串)

定义:

//记录buf数组中已使用字节的数量

int len

//记录buf数组中未使用字节的数量

int free

//字节数组 用于保存字符串

char buf []

 

使用sds的好处是:1.方便获取当前字符串的长度

2.杜绝缓冲区溢出

3.减少字符串修改带来的内存重分配次数.修改之后的空间,预分配的字空间大小和已 使用的空间大小相等.但是最大为1M.

4.二进制安全.redis api读进去的是一系列二进制

 

 

 

2.链表

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过只能删节点来灵活的调整链表的长度.

redis支持的数据结构

redis支持的数据结构

3.字典

字典又称为符号表.,关联数组活映射(map),是一中用于保存键值对的抽象数据结构.

字典的底层是由哈希表实现的,一个哈希表里面可以有很多个哈希表节点,而每个哈希表节点就保存了字典表中的一个键值对.

1.1.哈希表

结构定义:

table:哈希表数组.数组中的每个元素都是一个指向dictEntry结构的指针,每个dictEntry结构保存着一个键值对

size:哈希表大小

sizemask:哈希表掩码,用于计算索引值.总是等于size-1

used:该哈希表已有节点的数量

redis支持的数据结构

 

1.2.哈希表节点

哈希表节点使用dictEntry结构表示,每个dictEntry结构都保存着一个键值对;

定义:

key:键

v:值

dictEntry *next :指向下个哈希表节点的指针,形成链表

redis支持的数据结构

 

 

1.3.字典(dict)

redis中的字典由dict结构表示

dict{

type:类型特定函数

privdata:私有数据

ht[2]:哈希表

trehashidx:rehash索引.当rehash不在进行时,值为-1.

}

ht是一个包含两个项的数组,数组中的每个项都是一个dictht哈希表,一般情况下,字典只是用ht[0]哈希表,ht[1]哈希表指挥对ht[0]哈希表进行rehash时使用

rehashidx,记录了rehash目前的进度.

 

3.解决哈希冲突

当有两个或两个以上的键分配到了同一个索引上面,我们就称这些键触发了hash冲突.

redis使用链地址法解决冲突。每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单项链表,被分配到同一个索引上的多个节点可以使用这个单向链表连接起来,这就解决了键冲突的问题。(个人感觉和map差不多)

1.4.rehash

随着操作的不断执行,哈希表保存的键值会逐渐的增多或者减少,程序需要对哈希表的大下进行相应的扩展或者收缩。这些需要rehash来完成。

rehash的步骤:

1.为ht[1]分配空间,空间的大小取决于执行的操作以及ht[0]当前包含的键值对的数量(即ht[0].user属性的值)

  • 如果执行的是扩展操作,那么ht[1]的大小为 第一个大于等于ht[0].user*2的2的那次方
  • 如果是收缩,那么ht[1]的大小为第一个大于等于ht[0].user的2的n次方

2.将保存保存在ht[0]的值全部rehash到ht[1]上,rehash是指重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的制定位置上。

3.当ht[0]全部放置到ht[1]上,就要释放ht[0]的空间,将ht[1]置为ht[0],并在ht[1]新建一个空白的哈希表,为下一次rehash做准备。

 

 

哈希表的宽展与收缩触发因素:

 

1)服务器目前没有执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于 等于1.

2)服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于5

哈希表的负载因子通过公式计算

load_factor=ht[0].user/ht[0].size

3)当哈希表的负载因子小于0.1,会自动执行收缩。

1.5渐进式rehash

rehash不是一次性完成的,二十分多次,渐进式地将ht0里面的键值对rehash到ht1.在此期间rehashidx记录迁移的结果

在rehash期间,字典的delete,update,find等操作会在两个哈希表上进行。

而增加只会在ht1上执行。

redis支持的数据结构

5 跳跃表(skiplist)

跳跃表是一种有序的数据结构,它通过在节点中维持多个指向其他节点的指针,草那个人达到快速访问节点的目的。

跳跃表主要用在有序集合键。

redis支持的数据结构

redis支持的数据结构

6整数集合

 

7 压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度较短的字符串,那么redis就会使用压缩列表来做列表键的底层实现。

同时如果哈希表的哈希键也是少量的,且每个键值对的键和值要么就是小整数值,要么就是长度较短的字符串,那么哈希键的底层实现也是压缩列表。

 

压缩列表节点的构成

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

redis支持的数据结构

redis支持的数据结构

 

 

 

本文地址:https://blog.csdn.net/zhangshng/article/details/110949967

相关标签: redis 数据结构