关于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;
    ...
}