深入理解redis之基本数据结构

本文是对redis系统中用到的基本数据结构的梳理

1.sds 字符串

redis 中字符串数据结构如下

struct sdshdr{
    int len; //已用长度
    int free; //未使用数据长度
    char buf[]; //数据指针
    
};

可以看到,在字符串的头部,记录了字符串对象当前
使用的长度以及剩余的空间大小。有了这个长度可以杜绝字符串的溢出，也能基于len和free字段做字符串空间的预分配。

2.链表

struct list{
    listNode* head;
    listNode * tail;
    int len;
    void *(*dup)(void *ptr);//节点复制函数
    void(*free)(void *prt); //节点释放函数
    void （*match）（void*ptr,void *key）//节点比对函数
    
    
}

双向链表的实现没有特别的地方，这里值得借鉴的是，把函数指针当做结构体成员，这个就是c语言编写面向对象程序的方法。

3.字典

字典数据结构示意图：

image

redis的字典结构底层是一个拉链法实现的哈希表。

值得注意的是一个字典结构里实际上有两个哈希表结构。目的是用来做rehash。

当哈希表中元素过多或过少时，就需要对原来这个哈希表做rehash操作。

rehash本质上是开一个新hash表,其空间是原先空间的指数倍放大或缩小。将原表上的每一个元素取出,重新hash并放入到新表中的过程。

如果一次性将表中所有元素都rehash掉，其代价较大,redis 这里采用的方式是，每次访问一个key时，将val = hash（key）上的所有元素rehash掉。

4.跳跃表

跳跃表在redis 中用于解决zset的排序问题。

跳跃表的平均时间复杂度O(logn)，其空间复杂度为O(n)。

image

跳跃表的原理见:
https://www.cnblogs.com/George1994/p/7635731.html

5.整数集合

整数集合是redis set 类型的底层的实现,当一个集合中只包含整数值元素，并且这个集合的元素数量不多时，redis就会用整数集合作为底层实现。

目的在于：节省内存

整数集合的数据结构如下：

struct intset {
    uint32_t encoding;//说明一个元素占多少空间。
    uint32_t length //元素个数;
    int8_t contents[];
};

可以看到，实际上就是一个整数数组。数组中的值从小到大排序。

如果添加的新元素类型比当前整数集合保存值的类型长时需要做升级处理。

升级步骤：

1. 扩展数组空间
2. 将已有元素扩展为新类型
3. 放入新元素

6.压缩列表

压缩列表是列表和哈希表的底层实现之一。
当列表/哈希表包含的对象较少，切对象是整数或者短字符串时，采用压缩列表作为底层实现。

压缩列表目的在于：节省内存

image