Redis设计与实现阅读总结（一）数据结构和对象 - 好文

<>Redis设计与实现阅读总结（一）数据结构和对象

最近团队几个人和我聊了下，加上我自己平时的反思，我发现自己问题确实很多

其中一个问题就是，自己学习东西没有系统性，没有总结

这次的博客算是一个总结的开始。

最近由于出实习题，趁着这个机会，自己阅读了《redis设计与实现》这本书

为了解决自己的毛病，准备围绕这个话题写博文，做总结，从细节到总体，围绕这个话题写更多东西

大家可能发现这个部分写的很粗略，因为redis本身设计的就是很简单的，这些数据结构基本没有太多好写的，主要是写了后做一个总结，后面的更为重要的部分会做更多叙述

<>1. SDS(简单动态字符串)

每个 sds.h/sdshdr 结构表示一个 SDS 值：
struct sdshdr { // 记录 buf 数组中已使用字节的数量 // 等于 SDS 所保存字符串的长度 int len; // 记录 buf
数组中未使用字节的数量 int free; // 字节数组，用于保存字符串 char buf[]; };

为什么不使用c语言简单字符串

原因有如下

* 获取长度复杂度为O(1)
* 避免缓冲区溢出
优化策略

redis非常注重性能，于是优化是非常必要的。

<>减少内存重分配

* 空间预分配
内存的分配设计到复杂算法或可能的系统调用，比较耗时

于是，每次再字符串增长操作时，不仅仅会扩容到刚好所需的空间，而是会通过一定策略额外分配空间

* 惰性空间释放
字符串的缩短操作，不会进行内存重分配，而是会通过free记录起来，为未来可能存在的增长提供优化

<>二进制安全

不使用\0辨认结尾，而是通过len

并且在SDS中\0被保留，可以兼容部分c字符串函数

<>2. 链表

redis是一个设计追求简单的数据库，链表这种简单实用的数据结构在很多地方都得到了应用，（事实上应该说是双向链表。）

譬如列表(List)，慢查询，监视器，订阅与发布等。包括客户端状态也是用链表在服务器中进行保存的。

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

<>3. 字典

字典是使用哈希表作为底层实现。

一图胜千言

看的出来，解决键冲突(collision)的办法是通过每个哈希表节点都是一个链表。(链地址法)

* 哈希算法
* 链地址法
以上两者细节就不解释了

<>rehash扩容

要扩多少内容，开多大空间的新dictEntry，然后把之前的dictEntry转到新的。

当然，一次性转会有性能问题，所以

<>渐进式rehash

相当于是搭便车

每次对字典进行更新添加查找删除操作时，会顺带的转移旧的dictEntry的一个index链表到新的dictEntry

详细执行过程不予介绍

<>4. 跳跃表（跳表）

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

跳跃表支持平均 O(\log N) 最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

Redis 使用跳跃表作为有序集合键的底层实现之一：如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，
Redis 就会使用跳跃表来作为有序集合键的底层实现

从上图可以看书，跳表其实就是一种分治思想的，利用空间换取时间的一种算法

在看了上图之后，这个时候再看下图redis的跳表。就应该容易理解多了

<>整数集合

整数集合就比较简单了，重要的一个点主要是升级

redis的整数集合类型其实是会随着存入数字而变化的，当数都比较小的时候，类型可能就是int8_t,int16_t，但是一旦加入一个大数，集合会升级类型为相应类型，此时该集合中所有数都会被更新为该类型

另外注意

整数集合的数组不会出现降级

<>压缩列表

<>对象

热门工具换一换