阅读 35

redis-简单动态字符串(sds)和链表的底层实现

一、简单动态字符串(simple dynamic string,SDS)

1.SDS的定义

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

2.SDS的优点

  • 获取自身长度为O(1),直接取len字段。
  • 杜绝缓冲区溢出,当SDS的API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改的所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用SDS既不需要手动修改SDS的空间大小,也不会出现前面所说的缓冲区溢出问题。
  • 减少修改字符串时带来的内存重分配次数,举个例子,当len长度为20,free长度为0,buf[]中算上空字符(\0)一共21个字符。当减少字符串时,比如截取前10个,此时len长度为10,free中未使用的长度为10,buf[]的空间长度仍然是21,未使用的空间未延迟释放,这样如果在增加修改此字符串时,如果增加的长度不大于10则不会新增分配空间。而增加为redis修改字符串的速度。
  • 空间预分配,如果对SDS进行修改后,SDS的长度小于1MB,那么len和free数量相同,举例,如果修改之后,SDS的len变成13字节,那么程序会分配13字节未使用空间,此时buf实际长度为13+13+1=27字节(额外的一字节用于保存空字符);SDS修改后的长度大于1MB,则free固定分配1MB,举例,如果修改之后,SDS的len变成30MB,那么程序会分配1MB未使用空间,此时buf实际长度为30MB+1MB+1byte
  • 二进制安全,为了确保redis可以适用于各种不同的使用场景,所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中的数据做任何限制,过滤,或者假设,数据在写入时是什么样的,它被读取时就是什么样。这也是我们将SDS的buf属性称为字节数组的原因-redis不是用这个数组来保存字符,而是用它来保存一系列二进制数据。

二、链表

1.链表和链表节点的实现

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

typedef struct list {
    
    //表头节点
    listNode *head;
    
    //表尾节点
    listNode *tail;
    
    //链表所包含的节点数量
    unsigned long len;
    
    //节点值复制函数
    void *(*dup) (void *ptr);
    
    //节点值释放函数
    void *(*free) (void *ptr);
    
    //节点值释放函数
    void *(*match) (void *ptr,void *key);
}list;

复制代码

2.redis的链表实现的特性总结如下

  • 双端:链表节点带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)。
  • 无环:表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点。
  • 带表头指针和表尾指针:通过list结构的head指针和tail指针,程序获取链接表的表头节点和表尾节点的复杂度为O(1)。
  • 带链表长度计数器:程序使用list结构的head指针和tail指针,程序获取链表的表头节点和表尾节点的复杂度为O(1)。
  • 多态:链表节点使用使用void*指针来保存节点值,并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值
关注下面的标签,发现更多相似文章
评论