redis-对象使用的底层数据结构（一）

总：底层数据结构有简单动态字符串，链表，字典，跳跃表，整数集合，压缩列表

一.SDS（简单动态字符串）：redis默认字符串

1.结构：

struct sdshdr {        
	// 记录buf数组中已使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;
  
    // 记录buf数组中未使用字节的数量
    int free;
  
    // 字节数组，用于保存字符串
    char buf[];
};

2.使用结尾好处：可以重用一部分C字符串函数库里的函数

3.SDS与C字符串区别：（主要是因为C没有len记录，sds有）

总：

常数复杂度获取字符串长度：
- C字符串不记录长度信息，要遍历整个字符串获得长度->O(N)
- SDS在len属性->O(1)
杜绝缓冲区溢出：
- C字符串不记录长度，假设s1和s2内存紧邻，其中s1保存了字符串“redis”，s2保存了字符串“MongoDb”，将s1的内容修改为“Redis Cluster”，但忘记了为s1分配足够的空间，就会导致s1的数据将溢出到s2所在的空间中，导致s2的内容被修改。
- 当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题

减少修改字符串时的内存分配次数：（因为这个要耗时，但是redis被要求要速度快）
- 修改C字符串：要对保存这个C字符串的数组进行一次内存重分配操作
  - 容易出现两个问题
    - 增长字符串：程序需要先通过内存重分配来扩展底层数组组的空间大小，如果忘了这一步就会产生缓冲区溢出
    - 缩短字符串：程序需要通过内存重分配来释放字符串不再使用的那部分空间，如果忘了这一步就会产生内存泄露
- 在SDS中，可以用free里的字节，如果不够有下面有两种策略
  - 空间预分配：对SDS拓展空间时，还会为SDS分配free未空间：
    - 修改后，如果len属性小于1MB，程序分配和len属性同样大小的未使用空间，len=free
    - 修改后，如果len大于等于1MB，那么程序会分配1MB的free空间

惰性空间释放：对SDS缩短时，不内存重分配，用free保存起来

可存二进制数据：
- c字符串：除了末尾，不能包含空字符串，用表示结尾
- SDS：用len表示字符串长度，可以保存图片，音频，视频等文件

4.SDS API：

二.链表

1.结构：

typedef struct listNode {
	// 前置节点
	struct listNode *prev;
    
	// 后置节点
	struct listNode *next;
    
	// 节点的值
	void *value;
}listNode;

2.使用adlist.h/list来持有链表：

typedef struct list{
	// 表头节点
	listNode *head;
    
    // 表尾节点
    listNode *tail;
    
    // 链表所包含的节点数量
    unsigned long len;
    
    // 节点值复制函数
    void *(*dup) (void *ptr);
    
    // 节点值释放函数
    void (*free) (void *ptr);
    
    // 节点值对比函数
    int (*match)(void *ptr,void *key);
}list;

特点：

Redis的链表实现的特性可以总结如下：

双端：获取某个节点的前置节点和后置节点的复杂度都是O(1)
无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
带表头指针和表尾指针：程序获取链表的表头节点和表尾节点的复杂度为O(1)
带链表长度计数器：len获取链表中节点数量的复杂度O(1)
多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值

3.api

三. 字典（符号表，关联数组，映射）：保存键值对

1.结构：Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表就保存了字典中的一个键值对

哈希表：

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
 
    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码，用于计算索引值
        // 总是等于size-1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;
}dictht;

哈希表节点：dictEntry结构表示，每个dictEntry结构都保存着一个键值对：

typeof struct dictEntry{
    // 键
    void *key;
	    
    // 值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    }
	    
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;（将两个索引值相同的键k1和k0连接在一起）
}dictEntry;

字典：

typedef struct dict {
    // 类型特定函数
    dictType *type;
	    
    // 私有数据
    void *privedata;
	    
    // 哈希表
    dictht  ht[2];
	    
    // rehash 索引
    // 在rehash不在进行时，值为-1
    int trehashidx;
}dict;

2.rehash

4.应用：

redis数据库用字典做底层实现，比如SET msg “hello world”，增删改查是在对字典的操作
哈希键的底层实现之一

redis-对象使用的底层数据结构（一）

Java相关栏目本月热门文章