Redis学习笔记-Redis内部数据结构

mouse

　　Redis内部数据结构
　　Redis和其他key-value数据库的很大区别是它支持非字符串类型的value值。它支持的value值的类型如下：

• sds (simple dynamic string) 简单动态字符串
  
• 双端链表
  
• 字典(dictionary/map/associative array)
  
• 跳跃表(skiplist)
  

　　下面将对以上的各个类型在redis内部的实现进行分析。
　　
　　一、sds (simple dynamic string) 简单动态字符串
　　Redis并没有使用C的字符串，而是在其上面进行了封装，以适应更多频繁的耗时操作。在前面的内容中，我们一直将sds 作为一种抽象数据结构来说明，实际上，它的实现由以下两部分组成：



1 typedef char *sds;


1 struct sdshdr {
2 // buf 已占用长度
3 int len;
4 // buf 剩余可用长度
5 int free;
6 // 实际保存字符串数据的地方
7 char buf[];
8 };
　　这样的设计对于strlen()和append()操作来说是效率很高的。对于strlen()操作来说，很明显可以通过len属性在O(1)的时间内拿到。对于append()操作，参考下面的例子：



redis> SET msg "hello world"
OK
redis> APPEND msg " again!"
(integer) 18
redis> GET msg
"hello world again!"
　　看看这个过程中sdshdr的变化情况：
　　首先，set msg后，sdshdr如下：



1 struct sdshdr {
2 len = 11;
3 free = 0;
4 buf = "hello world\0";
5 }
　　然后，append msg后，sdshdr如下：



1 struct sdshdr {
2 len = 18;
3 free = 18;
4 // 空白的地方为预分配空间，共18 + 18 + 1 个字节
5 buf = "hello world again!\0 ";
6 }
　　可以看到，Redis的sds会预分配2倍自己大小的空间，这样就减少了内存的追加操作，即减少了字符串追加操作的时间。