Redis内部数据结构
Redis和其他key-value数据库的很大区别是它支持非字符串类型的value值。它支持的value值的类型如下:
- sds (simple dynamic string) 简单动态字符串
- 双端链表
- 字典(dictionary/map/associative array)
- 跳跃表(skiplist)
下面将对以上的各个类型在redis内部的实现进行分析。
一、sds (simple dynamic string) 简单动态字符串
Redis并没有使用C的字符串,而是在其上面进行了封装,以适应更多频繁的耗时操作。在前面的内容中,我们一直将sds 作为一种抽象数据结构来说明,实际上,它的实现由以下两部分组成:
typedef char *sds;
struct sdshdr {
// buf 已占用长度
int len;
// buf 剩余可用长度
int free;
// 实际保存字符串数据的地方
char buf[];
};
这样的设计对于strlen()和append()操作来说是效率很高的。对于strlen()操作来说,很明显可以通过len属性在O(1)的时间内拿到。对于append()操作,参考下面的例子:
redis> SET msg "hello world"
OK
redis> APPEND msg " again!"
(integer)
redis> GET msg
"hello world again!"
看看这个过程中sdshdr的变化情况:
首先,set msg后,sdshdr如下:
struct sdshdr {
len = ;
free = ;
buf = "hello world\0";
}
然后,append msg后,sdshdr如下:
struct sdshdr {
len = ;
free = ;
// 空白的地方为预分配空间,共18 + 18 + 1 个字节
buf = "hello world again!\0 ";
}
可以看到,Redis的sds会预分配2倍自己大小的空间,这样就减少了内存的追加操作,即减少了字符串追加操作的时间。