Redis 五种数据结构
2021-03-14 本文已影响0人
猿来是八阿哥
一、SDS 简单动态字符串
Redis 在存储
可能发生改变、非字面量的字符串时，都会使用SDS，比如：redis 的 key 和 value 等。
1. 结构体定义
struct sdshdr{
// 字符串真是长度
int len;
// buf 中空闲的长度
int free;
// 存储字符串的 char 数组
char buf[];
}
-
len，字符串真实长度。 -
free，buf中空闲的长度（与预分配和惰性释放有关） -
buf，用于存储字符串的char数组。
2. SDS 和 C 字符串的区别
-
SDS获取字符串长度的时间复杂度是O(1)，C获取字符串长度的时间复杂度是0(n) - 通过
SDS的 API 操作字符串（末尾追加、截取等）完全避免了内存的溢出和泄露，而 C 字符串则需要手动维护内存，存在溢出和泄露风险。 -
SDS减少了内存分配的次数-
内存预分配：SDS通过alloc = (len <= 1024) ? 2 * len : len + 1024的方式，预留了一部分内存空间，相比 C 字符串，在增加字符串长度的场景上，有效的减少了内存分配的次数。 -
惰性释放：SDS在释放空间时，并不立即释放空间，而是在 free 字段中记录了【空闲】空间的长度，等待未来使用。C 字符串则每次都需要手动释放。且SDS的 API 也支持像 C 字符串那样的立即释放。
-
- 相比 C 字符串，
SDS是二进制安全的（不会像 C 字符串一样，以为空格是结尾）
二、链表
redis 通过链表，实现了
队列相关的操作。
1. 结构体
- 链表节点：
listNode（双向）
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点值
void *value;
} listNode;
- 链表：
list
typedef stuct list {
// 头结点
listNode *head;
// 尾节点
listNode *tail;
// 链表长度
unsigned long len;
// 节点复制函数
void *(*dup)(void *ptr);
// 节点释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
} list;
2. 特点
-
双向：获取某个节点的前置、后置节点的时间负责度是0(1) -
无环：head.prev和tail.next是null -
带头、尾指针：获取链表的表头节点和表尾节点的时间复杂度是O(1)
3. 部分API
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
listLength |
获取链表长度 | 0(1) |
listFirst |
获取链表头节点 | 0(1) |
listLast |
获取链表尾节点 | 0(1) |
listPrevNode |
获取指定节点的前置节点 | 0(1) |
listNextNode |
获取指定节点的后置节点 | 0(1) |
listNodeValue |
获取指定节点的值 | 0(1) |
listAddNodeHead |
设置新的头节点 | 0(1) |
listAddNodeTail |
设置新的尾节点 | 0(1) |
三、字典
四、跳跃表
redis 的有序结合，当有序集合的
元素数量比较多或者元素的值是比较长的字符串时，redis 使用跳跃表来实现有序集合。
1. 结构体
- 节点：
zskiplistNode
typedef struct zskiplistNode {
// 前一个节点的指针
struct zskiplistNode *backword;
// 当前节点的分值
double score;
// 当前节点的值对象
robj *obj;
struct zskiplistLevel {
// 下一个节点的指针
zskiplistNode *forword;
// 到下一个节点的跨度
unsigned int span;
} level[];
} zskiplistNode;
- 跳跃表：
zskiplist
typedef struct zskiplist {
// 跳跃表头节点
struct zskiplistNode *head;
// 跳跃表尾节点
struct zskiplistNode *tail;
// 跳跃表的长度
unsigned long length;
// 跳跃表中层数最大的节点的层数
int level;
} zskiplist;
2. 有序集合的 查找
- 普通的双向链表节点：
DoubleLinkedListNode
typedef struct DoubleLinkedListNode {
// 后一个节点的指针
struct DoubleLinkedListNode *next;
// 前一个节点的指针
struct DoubleLinkedListNode *prev;
// 当前节点的分值
double score;
// 当前节点的值对象
robj *obj;
} DoubleLinkedListNode;
- 普通的双向链表节点，查找的逻辑就是遍历，时间复杂度是
O(n)
10万元素跳跃表.png
如上图，假设一个跳跃表存储了
a1 到 a100001这 10 万个元素，他们的分数分别是1.0 到 100001.0
- 上述跳跃表有
五层：- 第一层跨度为1，即：
1->2->3... - 第二层跨度为10，即：
1->11->21... - 第三层跨度为100，即：
1->101->201... - 第四层跨度为1000，即：
1->1001->2001... - 第五层跨度为10000，即：
1->10001->20001...
- 第一层跨度为1，即：
- 查找
65536的过程：-
第五层查找（8次）：1->10001->20001->30001->40001->50001->60001，看到 70001 时发现：比 65536 大，去第四层继续查找。 -
第四层查找（6次）：61001->62001->63001->64001->65001，看到 66001 时发现：比 65536 大，去第三层继续查找。 -
第三层查找（6次）：65101->65201->65301->65401->65501，看到 65601 时发现：比 65536 大，去第二层继续查找。 -
第二层查找（4次）：65511->65521->65531，看到 65541 时发现：比 65536 大，去第一层继续查找。 -
第一层查找（4次）：65532->65533->65534，看到 65535 时发现目标，得到结果。
-
- 结论：
- 跳跃表的节点，将普通双向链表的节点的
next指针，从1个升级到了多个，以层的方式管理。 - 不同层级的指针，跨度不一样：第一层就是普通双向链表节点的
next指针。以后的各层，跨度不断增大，以达到跳过一些节点，进行查找的目的。 - 指针的层数越高，对查找的性能优化越明显，即：时间复杂度从
O(n)减少到了O(logN)
- 跳跃表的节点，将普通双向链表的节点的
3. 其他有序集合操作
其他有序集合操作，像 范围查找（正向、逆向）、是否存在 等，其实都是基于 查找 的结果，利用 前置、后置指针 进行的遍历。
五、整数集合
当集合中的元素都是整数时，Redis 会使用
整数集合作为集合的底层实现
1. 结构体
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合长度
uint32_t length;
// 集合元素
int8_t contents[];
} intset;
其中，encoding 指明了 contents 中的数据类型：
-
INTSET_ENC_INT16，范围：[-2^15=-32768, 2^15-1=32767] -
INTSET_ENC_INT32，范围：[-2^31=-2147483648, 2^31-1=2147483647] -
INTSET_ENC_INT64，范围：[-2^63, 2^63-1]
2. 编码升级
当一个编码为更小范围，如 INTSET_ENC_INT16 ，的整数集合，要添加一个更大范围，如 INTSET_ENC_INT32，的元素时，整体集合的编码方式需要升级。具体思路是：
- 根据新元素的类型和集合的元素数量，扩展集合空间。
- 将集合中的其他元素升级，并保证之前的有序顺序。
- 将新元素添加到集合中（因为范围更大，所以位置一定是：第一个或者最后一个）
3. 升级的好处
- 集合更加灵活。屏蔽了不同范围整数的存储实现。
- 更加节省空间。在有需要的时候再进行升级，避免了一开始就使用
INTSET_ENC_INT64来存储集合元素。
4. 不存在降级
升级后的整数集合，并不会因为，唯一一个更大范围的元素被删除，就进行降级。
