Redis底层数据类型

pf666nb / 2023-07-14 / 原文

Redis底层基础数据类型

redis共有5种基本数据结构：string，List，Set，Hash，Zset

1.SDS的定义

struct sdshdr {
    //记录buf数组中已使用的字节量
    //等于SDS所保存字符串长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组,用于保存字符串
    char buf[];
};

1.2 SDS 与 C 字符串的区别

1.2.1 常数复杂度获取字符串长度

因为c字符串并不记录自身长度信息，所以为了获取一个c字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符串为止，这个操作的复杂度为O(N),和c字符串不同，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O(1)。

设置和更新SDS长度的工作是由SDS的API在执行时自动完成的，使用SDS无需进行任何手动修改长度的工作，通过使用SDS而不是C字符串，Redis将获取字符串长度所需要的复杂度从O(N)降低到O(1)，这确保了获取字符串长度的工作不会成为Redis性能的瓶颈。所以即使我们对一个非常长的字符串使用STRLEN命令，也不会对系统的性能造成任何的影响

1.2.2 杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外，c字符串不记录自身长度带来的另一个问题是容易造成缓存区溢出，与c字符串不同，SDS的空间分配策略完全杜绝了这种可能性，当SDS API 需要对SDS进行修改的时候，API会首先检查SDS的空间是否满足修改的要求，如果不满足会自动的扩展到所需要的大小，

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

c字符串总不记录自身长度，而是采用N+1个字符长度的数组，每次增长或者缩短一个c字符串，程序总要对保存这个c字符串的数组进行一次内衬重分配操作，通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

1.2.3.1 空间预分配

空间预分配用于优化SDS的字符串增长的操作，当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配必要的空间，还会为SDS分配额外的空间。额外空间的分配原则是

如果对SDS进行修改后，SDS的长度将小于1MB，那么程序分配和len属性一样的大小的未使用空间，实际空间将变为 2len+1的空间
如果对SDS进行修改后，SDS的长度大于1MB，那么程序将分配1MB的未使用空间，空间大小将为 N+1MB+1byte的空间

1.2.3.2 二进制安全

c 字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包括空字符，否则，最先被程序读入的空字符将会被认为是字符串的结尾，这些限制使得c字符串将只能保留文本数据，而不能保存图片，音频视频，压缩文件这样的二进制文件，为了确保redis可以适用于不同的场景，SDS的API都是二进制安全的，因为，SDS是使用len属性的值而不是空字符来判断字符串是否结尾，使用二进制安全的SDS，而不是c字符串，使得Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据，

1.2.3.3 兼容部分C字符函数

虽然SDS的API都是二进制安全的，但是他们一样遵循c字符串，以空字符结尾的惯例，这些API，总会将SDS保存的数据的末尾设置空字符串，这是为了让那些保存文本数据的SDS可以重用一部分<string.h>库定义的函数
。

1.2.4 总结

1.2.5 重点回顾

2.链表

链表在Redis中的应用非常的广泛，比如列表键的底层实现之一就是链表，当一个列表键包含了数量比较多的元素，
又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。
每个链表节点使用一个adlist.h/listNode结构来表示

typeder struct listNode {

    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
}

Rdis 的链表实现的特性可以总结如下

双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）
无环：表头节点的prev指针和表尾节点的next指针都指向Null，对链表的访问以NULL为终点
带表头指针和表尾指针，通过list结构的head指针和tail指针，程序获取表头节点和表尾节点的复杂度为O（1）
带链表长度计数器，程序使用list结构的len属性，来对list持有的链表节点进行计数，程序获取链表中节点数量多复杂度为O(1)。
多态：链表节点使用void 指针来保存节点值，并可以通过list结构的dup，free，match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。