Redis底层-数据结构

没有用C的语言的传统字符串表示，而是自己建立了一种简单动态字符串(simple dynamic string)的抽象类型来用作Redis默认字符串的表示。数据结构：

struct sdshdr {

    // buf 已占用长度等于SDS保存的字符串长度
    int len;

    // buf 剩余可用长度
    int free;

    // 实际保存字符串数据的地方
    char buf[];
};

SDS遵循C语言字符串以空字符串结尾的惯例。保存空字符串的一个空间不计算在len字段里面。

使用动态字符串的好处：
- 常数的获取字符串的长度。时间复杂度为O(1)。在C语言中字符串并不记录自身的长度信息，所以为了获取一个字符串的长度需要遍历整个字符串。操作复杂度为O(n)。
- 杜绝缓冲区溢出。每次进行字符拼接的时候回去检查是否分配了足够的空间。通过free字段就能很容易的知道。
- 减少修改字符串带来的内存重新分配次数。 使用空间预分配和惰性空间释放
- 二进制安全
- 兼容部分C字符串函数

字典在高级语言如Java叫做Map ，Redis 字典实现使用的哈希表作为底层的实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

跳跃表是一种有序的数据结构，他通过在每一个节点中维持多个指向其他的节点的指针，来达到快速访问的节点的目的。

跳表的支持平均O(logN),最坏O(N)的复杂度的节点查找，跳跃表可以和平衡树媲美，并且跳跃表的实现比平衡树简单。所以有不少程序用跳跃表来代替平衡树。Redis跳跃表来实现有效集合键的底层实现。

跳跃表在Redis里面只有两个地方用到：

参考：