Redis设计与实现 读书笔记,用于提炼书中干货,便于学习、复习。
一、数据结构
1、简单动态字符串 SDS
①在Redis的数据库里面,包含字符串值的键值对在底层都是由SDS实现的。
②redis> RPUSH fruits "apple”“banana”"cherry"
(integer) 3
键值对的键是一千字符串对象,对象的底层实现是-斗保存了字符串 ” fruits” 的 sos。
键值对的值是一个列表对象,列表对象包含了三个字符串对象,这三个字符串对象分别由三个 sos 实现:第一个SDS保存着字符串 ” apple”,第二个SDS保存着字符串 "banana ”,第三个SDS保存着字符串 " cherry” 。
③除了用来保存数据库中的字符串值之外,sos 还被用作缓冲区(buffer ) : AOF模块中的AOF缓冲区, 以及客户端状态中的输人缓冲区,都是由SDS实现的。
④ free属性的值为0, 表示这个SDS没有分配任何未使用空间。
len属性的值为5, 表示这个SDS保存了一个五字节长的字符串。
buf属性是一个char类型的数组, 数组的前五个字节分别保存了 'R'、'e'、'd'、'i'、's'五个字符,最后添加了一个空字符'\0'
⑤保存空字符的1字节空间不计算在SDS的 len属性里面,好处是SDS可以直接重用一部分C字符串函数库里面的函数。
⑥总结C字符串与SDS的区别:
比起C字符串, SDS具有以下优点
1)常数复杂度获取字符串长度。
2) 杜绝缓冲区溢出。
3) 减少修改字符串长度时所需的内存重分配次数。
4) 二进制安全。
5) 兼容部分C字符串函数。2、链表
①C言并没有内置链表数据结构,所以Redis构建了自己的链表实现
②链表结构,除了用于链表键之外, 发布与订阅、 慢查询、监视器等功能也用到了链表,Redis服务器本身还使用链表来保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区
③链表结构图
④list结构为链表提供了表头指针head、表尾指针tail, 以及链表长度计数器len,而dup、free和match成员则是用于实现多态链表所需的类型特定画数。
⑤一个list结构和三个listNode 归结构组成的链表。
⑥
3、字典
4、跳跃表
5、整数集合
6、压缩列表
7、对象