redis支持的数据结构

redis支持的数据结构

个人读书笔记

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

 

 

 

 

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

定义:

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

int len

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

int free

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

char buf []

 

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

2.杜绝缓冲区溢出

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

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

 

 

 

2.链表

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

3.字典

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

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

1.1.哈希表

结构定义:

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

size:哈希表大小

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

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

 

1.2.哈希表节点

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

定义:

key:键

v:值

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

 

 

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上执行。

5 跳跃表（skiplist）

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

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

6整数集合

 

7 压缩列表

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

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

 

压缩列表节点的构成

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

 

 

 

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