• Redis 数据结构与对象
  • SDS 简单动态字符串
    • sds结构
    • SDS和C字符串的区别
    • 总结
  • 链表
    • 链表结构
    • 总结
  • 字典
    • 基本结构
    • 哈希表的收缩与扩展
    • 总结
  • 跳表
    • 跳表具有如下性质：
  • 压缩列表
  • 对象
    • 总结

Redis 数据结构与对象

SDS 简单动态字符串

sds结构

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

SDS和C字符串的区别

• 常数复杂度获取字符串长度 strlen。
• 杜绝缓冲区溢出:strcat函数执行时假定用户在执行这个函数时已分配足够多的内存（空间），sds在执行拼接操作时会检查长度然后决定是否扩展。
• 减少修改字符串时带来的内存重新分配的次数（利用未使用空间，实现空间预分配和惰性空间释放两种优化策略）
• 二进制安全
• 兼容部分c字符串函数

总结

1. 使用场景，除了简单的字面量，大部分需要用到字符串的都使用它。

   链表

   链表结构

   typedef struct list{
    listNode *head;
    listNode *tail;
    //链表长度
    unsigned long len;
    //节点复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void *(*free)(void *ptr);
    //节点值比对函数
    void (*match)(void *ptr,void *key);
   }
   

总结

1. 无环，双向链表，有表头、表尾指针
2. 有长度计数器
3. 多态（用void*指针保存节点的值，可以用来保存各种不同类型的值）
4. 应用场景（列表键、发布订阅、慢查询、监视器）

字典

基本结构

• 哈希表结构

  typedef struct dictht{
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    long size;
    // hash大小掩码，计算索引值 等于size-1
    long sizemask;
    // 已有节点数量
    long used;
  }
  

• hash表节点主要包括： 键 值 指向下一个节点的next指针（处理冲突:头插法处理新冲突的节点）

哈希表的收缩与扩展

• 当满足以下任一条件时，都将执行哈希表的自动扩展操作。
  1. 服务器目前没有执行BGSAVE，BGREWRITEAOF命令时。并且负载因子大于1；
  2. 正在执行上述命令时，负载因子大于5；
• 渐进式rehash
  1. 为新表分配空间，查找在两个表进行，而插入只会在新表进行，这样，组ht[0]将最后变成空表。
  2. 分而治之，避免集中式rehash为服务器带来庞大计算量

     总结

• 应用：数据库、哈希键
• 字典使用hash表作为底层实现，每个字典有两个，一个平时用，一个rehash用。
• hash值类似于Java的HashMap的hash值计算
• 拉链法解决冲突、新冲突节点 头插法（插入）
• 渐进式地rehah。

  跳表

• 一种有序的数据结构，在每个节点维持多个指向其他节点的指针，从而达到快速访问节点的目的。
• 平均O(log(N)) 最坏O(N)的复杂度，还可以顺序性批量地处理节点，大部分其效率可以媲美平衡树，但其实现更加简单。

跳表具有如下性质：

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。

(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。 ### 总结 - 应用：zset，集群节点中的内部数据结构 ## 集合(整数集合)

压缩列表

• 当一个列表键只包含少量的列表项，并且每个列表项要么是小整数值，要么是长度短的字符串，那么redis采用压缩列表来做底层的实现。

  对象

• 对于redis底层数据库所保存的键值来说，键总是一个字符串对象，值是字符串对象、列表对象、哈希对象、集合对象、有序集合对象。
• 我们称呼一个键为列表键时，指的是这个键所对应的值为列表对象。

总结