(一) Redis数据结构:SDS和链表
文章目录
最近在看《Redis设计与结构》这本书。整理了一些笔记。
SDS
Redis中的字符串基本上用的都是自己定义的sdshdr结构。
struct sdshdr {
int len;
int free;
char buf[];
};len属性记录了当前字符串的长度,值得注意的是,这个长度并不包括\0free为0时,代表当前SDS没有空余的空间。buf保存了一个c类型的字符串。并且以\0作为结尾。
这样子的设计有这些好处。
- 记录了字符串的长度,可以让我们在
O(1)时间内获取长度。 - 我们可以给
buf分配更大的空间,这样子在后续对字符串进行操作时,就不用频繁地分配内存了。 SDS是二进制安全的。因为C类型的字符串永远以\0作为结尾,如果我们需要保存的数据中包含了\0这样的字符,会导致访问不到后续的字符。SDS则可以通过len元素来判断是否到达字符串的终点。- 仍然可以使用C语言的字符串函数库。
链表
Redis使用了双向链表。
struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
};并且链表结构中保存了表头结点,表尾节点,链表长度以及一些函数。
struct list {
listNode *head;
listNode *tail;
unsigned long len;
...
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论