redis数据结构的底层实现.pdf

redis 数据结构的底层实现 redis 中的数据结构 Redis 支持五种数据类型：string （字符串）、hash （散列）、list （列表）、set （无序集）和zset （有序集）。 在 spike 项目中，我使用了 redis 的 Set 和 Hash 结构： String ：一个 key 对应一个 string，是 Redis 最基本的数据类型。 （bytes 的 abase 框架只实现了 redis 的字符串数据结构，所以如 果我们要存储复杂的数据结构，只能将其转成 json 格式的字符串进 行存储） list ：一个键对应一个字符串列表。 底层使用双向链表实现。 它支 持双向链表支持的许多操作。 redis 数据结构底层实现 string 使用一种叫简单动态字符串（SDS）的数据类型来实现。 SDS 相对于 C 字符串的优势： SDS 保存字符串的长度，而 C 字符串不保存长度，需要遍历整个数 组（直到找到\0）才能得到字符串的长度。 修改 SDS 时，检查给定的 SDS 空间是否足够。 如果没有，则首 先扩展 SDS 空间以防止缓冲区溢出。 C 字符串不检查字符串空间 是否足够，调用某些函数（如 strcat 字符串拼接函数）时容易造成 缓冲区溢出。 SDS 预分配空间的机制可以减少为字符串重新分配空间的次数。 list 使用双向链表来实现。 hash hash 结构里其实是一个字典，有许多的键值对（类似于 python 的 dict 类型）。 redis 的哈希表是一个 dictht 结构体： 哈希表节点的结构体如下： 解决哈希冲突的方法之一是 zipper 方法。 为了将哈希表的负载因子保持在合理的范围内，需要对哈希表的大 小进行扩展或收缩，这称为 rehash。字典中一共有两个哈希表 dicttht 结构，ht[0]用于存储键值对，ht[1]用于 rehash 时临时存储 数据。通常，它指向的哈希表是空的，需要扩展或收缩。 Ht[0] 的 哈希表为其分配了空间。 比如扩展哈希表就是为 ht[1]分配一个 ht[0]的两倍大的空间，然后 通过 rehash 将 ht[0]的所有数据迁移到 ht[1]，最后释放 ht[0 ] ]， 使 ht[1] 变为 ht[0] ，并为 ht[1] 分配一个空的哈希表。类似于缩 小哈希表。 渐进式 rehash ：redis 并没有专门找时间一次执行 rehash ，而是 逐步进行。在 rehash 期间，它不会影响对 ht[0] 的外部访问。修 改字典时需要将对应的数据同步到 ht[1]。 ，当所有数据传输完成 后，rehash 结束。 set set 可以用 intset 或者字典实现。 intset 只有当数据全是整数值，而且数量少于 512 个时，才使用 intset， intset 是一个由整数组成的有序集合，可以进行二分查找。 zset zset 中的每个元素都包含数据本身和相应的分数。 经典例子：一个 zset 的 key 是“math”，代表数学课的成绩，然 后这个 key 里面可以插入很多数据。输入数据时，每次都需要输入 姓名和对应的等级。那么名称就是数据本身，分数就是它的分数。 zset 本身的数据是不允许重复的，但是 score 是允许重复的。 zset 的底层实现原理： 数据少的时候使用 ziplist ：ziplist 占用连续内存，每个元素以 (data+score)的形式连续存储，按照 score 从小到大排序。为了节 省 ziplist 中的内存，每个元素占用的空间可以不同。对于大数据 （long long），使用更多的字节来存储，对于小数据（short）， 使用更少的字节来存储。因此，在搜索时，需要按顺序遍历。 ziplist 节省内存，但搜索效率低。 当数据很多时，使用字典+跳过表： 使用字典根据数据查找分数，使用跳表根据分数查找数据（查找效 率