关于redis:一-Redis数据结构SDS和链表

最近在看《Redis设计与构造》这本书。整顿了一些笔记。

SDS

Redis中的字符串基本上用的都是本人定义的sdshdr构造。

struct sdshdr {
    int len;
    int free;
    char buf[];
};

len属性记录了以后字符串的长度，值得注意的是，这个长度并不包含\0
free为0时，代表以后SDS没有空余的空间。
buf保留了一个c类型的字符串。并且以\0作为结尾。

这样子的设计有这些益处。

1. 记录了字符串的长度，能够让咱们在O(1)工夫内获取长度。
2. 咱们能够给buf调配更大的空间，这样子在后续对字符串进行操作时，就不必频繁地分配内存了。
3. SDS是二进制平安的。因为C类型的字符串永远以\0作为结尾，如果咱们须要保留的数据中蕴含了\0这样的字符，会导致拜访不到后续的字符。SDS则能够通过len元素来判断是否达到字符串的起点。
4. 依然能够应用C语言的字符串函数库。

链表

Redis应用了双向链表。

struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
};

并且链表构造中保留了表头结点，表尾节点，链表长度以及一些函数。

struct list {
    listNode *head;
    listNode *tail;
    unsigned long len;
    ...
}