Redis - 底层数据结构 - 《基础技术知识》

string
listnode
dict
skiplist
intset
ziplist

string

没有直接用char[]，而是构建了simple dynamic string（sds）的格式来存储：

struct sds{
    int len;// 已用长度
    int free;// 可用长度
    char[] buf;// 实际存储元素
}

好处：

获取字符串长度的时间复杂度为O(1)。
字符串拼接时可以根据len进行数组创建，不会出现内存溢出的情况。
由于存在len字段，所以实际为字符串分配大小可以进行预分配，减少字符串内容变更时扩容的消耗。

listnode

C语言没有链表结构，redis自己构建了链表结构（java也一样）：

struct ListNode{
    ListNode pre;
    ListNode next;
    Object value;
}
struct list{
    ListNode head;
    ListNode tail;
    int len;
    // some methods
}

规则：

双向链表，获取上下节点的时间复杂度为O(1)。
存在len，获取长度的时间复杂度为O(1)。
head.pre和tail.next一定为null，也就是无环。

dict

同样C语言没有字典结构，redis构建了字典结构物：

struct Entry{
    Object key;
    Object value;
    Entry next;// 链地址法
}
struct dictEntry{
    ht[] dictht;
    int rehashidx;
}

采用MurmurHash算法计算哈希值：优点是即使是有规律的key也能获得很好的散列性。
使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，一个在rehash时使用。
通过渐进式进行rehas保证服务不中断。
需要注意的是redis的cluster的工作模式和dict有相似之处，都是hash散列+扩容rehash，区别在于：
1. cluster采用的hash方法是CRC16算法，散列槽的大小固定为16384个。
2. cluster的扩容指的是节点扩容，也就是将一部分槽数据从原来几个节点重新分配给新增节点，由于从一个节点将哈希槽移动到另一个节点并不会停止服务，所以无论添加删除或者改变某个节点的哈希槽的数量都不会造成集群不可用的状态。
```
> ./redis-trib.rb reshard 127.0.0.1:6379 
> How many slots do you want to move (from 1 to 16384)? 4000 //输入被迁移的solt的数量 
> What is the receiving node ID? //输入目的地节点的id,执行第一行命 
> Please enter all the source node IDs.//输入被迁移的槽 
> Do you want to proceed with the proposed reshard plan (yes/no)? Yes //迁移计划确认
```

skiplist

struct SkipNode{
    struct Level{
        SkipNode forward; //前进指针
        int span;//跨度
    }
    Level[] levels;//层
    SkipNode backward;//后退指针
    double score;// 分值
    Object member;// 成员对象
}
struct SkipList{
    SkipNode head;
    SkipNode tail;
    long len;
    int level;
}

该数据结构只用在zset场景中。

intset

整数集合（intset）是Redis用于保存整数值的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

ziplist

为了节省空间而设计的。压缩列表并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。