redis数据结构的底层实现

redis数据结构的底层实现

redis中的数据结构

Redis支持五种数据类型：string（字符串）、hash（散列）、list

（列表）、set（无序集）和zset（有序集）o

String

HashTables

LinkedLists

Sets

SortedSets

在spike项目中,我使用了redis的Set和Hash结构:

String:一个key对应一个string,是Redis最基本的数据类型。

（bytes的abase框架只实现了redis的字符串数据结构，所以如果

我们要存储复杂的数据结构，只能将其转成json格式的字符串进行

存储）

list:一个键对应一个字符串列表。底层使用双向链表实现。它支

持双向链表支持的许多操作。

•Hash:

•Set:比如一个Set的实例：A-{,a','b',P},A是集合的key,a,'b'和'c是集合的member。无序、无重复元素。

•SortedSet:在set的基础上加上一f^score,sets面的数据是有序的。

redis数据结构底层实现

string

使用一种叫简单动态字符串（SDS）的数据类型来实现。

*保存字符串对象的结构

v

structsdshdr{

intlen;//buf中已占用空间的长度

intfree;//buf中剩余可用空间的长度

charbuf[];//数据空间

SDS相对于C字符串的优势:

SDS保存字符串的长度，而C字符串不保存长度，需要遍历整个数

组（直到找到''0'）才能得到字符串的长度。

修改SDS时，检查给定的SDS空间是否足够。如果没有，则首

先扩展SDS空间以防止缓冲区溢出。C字符串不检查字符串空间

是否足够，调用某些函数（如strcat字符串拼接函数）时容易造成缓

冲区溢出。

SDS预分配空间的机制可以减少为字符串重新分配空间的次数。

list

使用双向链表来实现。

hash

hash结构里其实是一个字典，有许多的键值对（类似于python的

diet类型）。

redis的哈希表是一个dictht结构体：

typedefstructdictht{

dictEntry**table

unsignedlongsize;〃的希表大

unsignedlongsizemask;//居希表大〃播行，用于计算索引值

unsignedlongused;〃该哈希表已有节点的数量

dietdictht

哈希表节点的结构体如下:

typeofstructdictEntry

void"key;//键

union{//不同键对应的值的类型可能不同,使用unton来处理这个问题

void*val;

uint64__tu64;

int64_ts64;

}

structdictEntry*next;

解决哈希冲突的方法之一是zipper方法。

为了将哈希表的负载因子保持在合理的范围内，需要对哈希表的大小

进行扩展或收缩，这称为rehasho字典中一共有两个哈希表diettht

结构，ht[O]用于存储键值对,ht[l]用于rehash时临时存储数据。

通常，它指向的哈希表是空的，需要扩展或收缩。Ht[0]的哈希表

为其分配了空间。

比如扩展哈希表就是为ht[l]分配一个ht⑼的两倍大的空间，然后通

过rehash将ht[O]的所有数据迁移到ht[l],最后释放ht[O]]，使

ht[l]变为ht[O],并为ht[l]分配一个空的哈希表。类似于缩小哈

希表。

渐进式rehash:redis并没有专门找时间一次执行rehash,而是

逐步进行。在rehash期间，它不会影响对ht[O]的外部访问。修

改字典时需要将对应的数据同步到ht[l]o，当所有数据传输完成后,

rehash结束。

set

set可以用intset或者字典实现。

intset

只有当数据全是整数值，而且数量少于512个时，才使用intset,

intset是一个由整数组成的有序集合，可以进行二分查找。

typ«

encoding

"2

ptr

zset

zset中的每个元素都包含数据本身和相应的分数。

经典例子：一个zset的key是"math",代表数学课的成绩，然后

这个key里面可以插入很多数据。输入数据时，每次都需要输入姓名

和对应的等级。那么名称就是数据本身，分数就是它的分数。

zset本身的数据是不允许重复的，但是score是允许重复的。

zset的底层实现原理：

数据少的时候使用Ziplist:ziplist占用连续内存，每个元素以

(data+score)的形式连续存储，按照score从小到大排序。为了节省

ziplist中的内存，每个元素占用的空间可以不同。对于大数据(long

long),使用更多的字节来存储，对于小数据(short),使用更少

的字节来存储。因此，在搜索时，需要按W页序遍历。ziplist节省内

存，但搜索效率低。

当数据很多时，使用字典+跳过表：

使用字典根据数据查找分数，使用跳表根据分数查找数据(查找效率

高)。

理论上，搜索、插入、删除和迭代输出有序序列的操作也可以由红黑

树完成，时间复杂度与跳表相同。

redis使用跳过表而不是红黑树的原因：

按区间查找数据的操作，红黑树的效率不如跳表的高。跳过链表可

以以O(logn)时间复杂度定位区间的起始点，然后在原链表中按顺序

向后查询。

与红黑树相比，跳表还具有代码实现更容易、可读性更好、不易出错、

更灵活的优点。

插入和删除时，跳过表只需要调整几个节点，而红黑树需要颜色重绘

和旋转，成本高。

跳表插入删除过程

跳过列表是基于一个有序的单链表构造的。通过建立索引，提高了

搜索效率，空间换来了时间。查找方法是从最上面的链表开始逐层

往下杳找，最后在最下面的链表中找到对应的节点：

插入：逐层查找位置，然后插入到最底层的链表中。请注意，需要保

持索引和原始链表之间的大小平衡。如果底层节点大量增加，索引也

会相应增加，避免两个索引之间节点过多的情况，降低搜索效率。同

样，当底层节点大大减少时，索引也相应减少。

删除如果该节点也出现在索引中，那么除了删除原链表中的节点外,

索引中的节点也应该被删除。

跳表查找的时间复杂度为O(log(n))。索引占用的空间复杂度为0(n)。

时间复杂度：时间复杂度;索引的层数*索引每层遍历的元素个数。

先看索引层数，假设每绘制两个节点作为上一级索引的节点，最高一

级索引有个节点，那么索引层数为

3Iog2(n)o

然后看每一层遍历了多少元素。首先最高层最多可以遍历3个节点,

然后可以往下走。同样，第二层也最多可以遍历三个节点，然后就可

以往下走。取平均值后，可以认为每层遍历2个节点。

因此，时间复杂度类似地,如果对每个节