Redis数据结构及对象

对象（数据类型）

redis数据库存储的是一个个键值对(key-value)，每个键值对都是由对象组成

• 键总是一个字符串对象
• 值可以是字符串对象(string)、列表对象(list)、哈希对象(hash)、集合对象(set)、有序集合对象(sorted set)

数据类型	可以存储的值	操作
STRING	字符串、整数或者浮点数	对整个字符串或者字符串的其中一部分执行操作 对整数和浮点数执行自增或者自减操作
LIST	列表	从两端压入或者弹出元素 对单个或者多个元素 进行修剪，只保留一个范围内的元素
SET	无序集合	添加、获取、移除单个元素 检查一个元素是否存在于集合中 计算交集、并集、差集 从集合里面随机获取元素
HASH	包含键值对的无序散列表	添加、获取、移除单个键值对 获取所有键值对 检查某个键是否存在
ZSET	有序集合	添加、获取、删除元素 根据分值范围或者成员来获取元素 计算一个键的排名

数据结构

简单动态字符串

SDS，类似于C++封装的string，Java封装的String，Redis 自己构建了一种简单动态字符串的抽象类型，用在Redis 的字符串类型；

链表

应用场景

1. 列表键的底层实现之一；
2. 发布与订阅、慢查询、监视器等功能也用到了链表；
3. Redis 服务器本身使用链表来保存多个客户端的状态信息；构建客户端输出缓冲区。

字典

又称符号表、关联数组、映射，一种保存键值对的抽象数据结构

应用场景

1. Redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查也是构建在字典的操作上的；

   

   在数据库中创建一个键为”msg”，值为”hello world“ 的键值对，保存在字典中。

2. 字典也是哈希键的的底层实现；每个哈希键对应一个数据库，里面的键值对保存的地方就是字典

实现

字典 (dict) 类似于Java的HashMap，具有一个散列表结构，散列表中存放键值对，使用拉链法解决哈希冲突；

dict 字典

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

dictht 散列表

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

dictEntry散列表中的键值对

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

rehash 扩容操作

• 字典包含两个哈希表dictht，这是为了方便扩容 rehash 操作；
• 扩容时，将其中一个 dictht 上的键值对 rehash 到另一个 dictht 上，完成之后释放空间并交换两个 dictht 的角色；
• rehash 操作不是一次性完成，而是采用渐进式，这是为了避免一次性执行过多的 rehash 操作给服务器带来过大的负担；

渐进式 rehash

• rehashidx ，字典结构中的一个属性，如果该值为 -1 ，字典不采用渐进式 rehash；
• 渐进式 rehash 通过记录 dict 的 rehashidx 完成，从0开始，然后每执行一次 rehash 都会递增；例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，这一次会把 dict[0] 中的 table[rehashidx] 的键值对 rehash 到 dict[1] 中，并令 dict[0] 的 table[rehashidx] 指向 null，rehashidx++；
• 在渐进式 rehash 期间，每次对字典增删改查操作时，都会执行一次 rehash；
• 采用渐进式 rehash 会导致字典中的数据分散在两个 dictht 上，因此对字典的查找操作也需要到对应的 dictht 去查找。

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n * 10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while (n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long) d->rehashidx);
        while (d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }

跳跃表

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

节点查找复杂度：平均O(logN)、最坏O(N).

应用场景

1. 有序集合的底层实现之一；
2. 在集群节点中用作内部数据结构

实现

• 跳跃表是基于多指针有序链表实现的，可以看成多个有序链表

• 查找时，从上层指针开始，找到对应的区间之后再到下一层去查找；

• 与红黑树等平衡树相比，跳跃表具有以下优点：
  • 插入速度非常快速，因为不需要进行旋转等操作来维护平衡性；
  • 更容易实现；
  • 支持无锁操作

整数集合

压缩列表

对象

• Redis 并没有直接使用以上数据结构来实现键值对数据库，而是基于这些数据结构创建一个对象系统，这个系统包含字符串对象、哈希对象、列表对象、集合对象、有序集合对象这五种类型的对象。而每个对象都用到了至少一种以上的数据结构。

• 对象系统实现了基于引用计数技术的内存回收机制、对象共享机制（让多个数据库键共享同一个对象来节约内存）

• Redis 中的每个对象都由一个redisObject 结构表示，该结构中有 type 、encoding、 ptr 三个属性；

  typedef struct redisObject{
      //类型 (5种对象)
      unsigned type:4;
      
      //编码
      unsigned encoding:4;
      
      //指向底层实现数据结构的指针
      void *ptr;
      
      // ...
  } robj;

  一部分对象的编码：