Redis笔记1-Redis的数据结构

日期

Dec 2, 2021

Redis数据库是什么？

Redis（Remote Dictionary Server）数据库，是现在最流行的NoSQL数据库，具备了高性能、可扩展性强、高可用的优点，它基于内存，可以存储多种数据结构类型，性能高效，支持分布式扩展。

Redis常在Web应用中使用，一般而言 Redis 在 Java Web 应用中存在两个主要的场景：一个是缓存常用的数据，另一个是在需要高速读/写的场合使用它快速读/写，比如一些需要进行商品抢购和抢红包的场合。

Redis 的应用场景包括：缓存系统（“热点”数据：高频读、低频写）、计数器、消息队列系统、排行榜、社交网络和实时系统。

Redis的主要数据结构

Redis的数据结构如下图所示：

Redis提供的数据类型有字符串类型、哈希类型、列表类型、集合类型和有序集合类型，不同的数据类型在使用时根据具体情况（主要是对象所需的字节长度）的不同，由不同的底层数据结构实现。

下表是对Redis底层数据结构的介绍：

名称	数据结构	作用	特点
简单动态字符串（Simple dynamic string（SDS））	`struct sdshdr { int len; int free; char buf[]; }`	表示Redis默认的字符串值，实现包含字符串值的键值对等	相较于C字符串：1. 常数复杂度获取字符串长度 2. 杜绝缓冲区溢出 3. 减少修改字符串时带来的内存重分配次数 4. 二进制安全 5. 兼容部分C字符串函数（<string.h>库）
链表（List）	`typedef struct list {//表头节点listNodehead;//表尾节点listNode tail;//链表所包含的节点数量unsigned long len;//节点值复制函数void (dup) (void ptr);//节点值释放函数void (free) (void ptr);//节点值对比函数int (match) (void ptr,void key); } list;`	列表键的底层实现	1. 双端；2. 无环；3. 带表头指针和表尾指针；4. 带链表长度计数器；5. 多态（可以保存各种类型的值）
字典（Dict）	`typedef struct dict {//类型特定函数dictTypetype;//私有数据void privdata;` `//哈希表dictht` `ht[2];` `/dictEntry哈希表节点/ // rehash 索引 //当rehash不在进行时，值为-1int rehashidx;/* rehashing not in progress' if rehashidx -1 */` `} dict;`	Redis数据库的底层实现，对数据库增、删、改、查操作构建在对字典的操作上；哈希键的底层实现之一	1. Redis使用MurmurHash2算法计算键的哈希值；2. 使用链地址法解决键冲突；3. 通过rehash来完成扩展和收缩哈希表的大小的工作，rehash过程不是一次性完成的，是渐进式完成的
跳跃表（Skiplist） [跳跃表的相关操作实现]	`typedef struct zskiplist {` `//表头节点和表尾节点structzskiplistNodeheader, tail;//表中节点的数量unsugned long length;//表中层数最大的节点的层数int level; } zskiplist;`	Redis中有序集合键的底层实现之一	1. 是一种有序数据结构，可以通过在每个节点中维持多个指向其他结点的指针，从而达到快速访问结点的目的；2. 支持平均O(logN）和最坏O(N)复杂度的节点查找；3. 可以通过顺序性操作批量处理节点 4. 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
整数集合	`typedef struct intset {// 编码方式uint32_t encoding;` `// 集合包含的元素数量uint32_t length;// 保存元素的数组int8_tcontents[]; } intset;`	Redis中集合键的底层实现之一	以有序、无重复的方式保存集合元素；每次向整数集合添加新元素时都会判断是否进行升级时，好处是1. 提升整数集合的灵活性 2. 尽可能地节约内存；整数集合不支持降级操作
压缩列表	压缩列表的组成 ziplist `//压缩列表占用的内存字节数zlbytes;//压缩列表表尾节点偏移量zltail;//压缩列表包含的节点数量zllen;//压缩列表包含的各个节点，个数不定entryX;//标记压缩列表的末端zlend;`	Redis中列表键和哈希键的底层实现之一	是 Redis 为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构；可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值；在添加新节点或删除节点时都有可能触发连锁更新，连锁更新的最坏复杂度为O(N^2)

Redis的对象系统

Redis提供的数据类型有字符串类型、哈希类型、列表类型、集合类型和有序集合类型。

下表是对于五种类型对象的编码介绍：

名称	编码
字符串对象 [Redis 五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象]	字符串对象的编码可以是: `int` 【保存的是整数值，且这个整数值可以用 long 类型来表示】; `raw` 【保存的是一个字符串值，并且这个字符串值的长度大于 39 字节】; `embstr`【保存的是一个字符串值，并且这个字符串值的长度小于等于 39 字节】;
列表对象	列表对象的编码可以是： `ziplist` 【列表对象保存的所有字符串元素的长度都小于 64 字节；列表对象保存的元素数量小于 512 个；不能满足这两个条件的列表对象需要使用 linkedlist 编码。】 `linkedlist` 【linkedlist 编码的列表对象使用双端链表作为底层实现】
哈希对象	哈希对象的编码可以是： `ziplist`【ziplist 编码的哈希对象使用压缩列表作为底层实现；哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；哈希对象保存的键值对数量小于 512 个；不能满足这两个条件的哈希对象需要使用 hashtable 编码。】 `hashtable` 【hashtable 编码的哈希对象使用字典作为底层实现】
集合对象	集合对象的编码可以是： `intset`【intset 编码的集合对象使用整数集合作为底层实现；集合对象保存的所有元素都是整数值；集合对象保存的元素数量不超过 512 个；不能满足这两个条件的集合对象需要使用 hashtable 编码。】 `hashtable` 【hashtable 编码的集合对象使用字典作为底层实现】
有序集合对象	有序集合的编码可以是： `ziplist` 【ziplist 编码的有序集合对象使用压缩列表作为底层实现；有序集合保存的元素数量小于 128 个；有序集合保存的所有元素成员的长度都小于 64 字节；不能满足以上两个条件的有序集合对象将使用 skiplist 编码。】 `skiplist` 【skiplist 编码的有序集合对象使用 zset 结构作为底层实现】

Redis对象的好处/特点：

类型检查与命令多态

使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率

内存回收：实现了基于引用计数技术的内存回收机制：当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放；

对象共享：通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。

对象的空转时长：对象带有访问时间记录信息，该信息可以用于计算数据库键的空转时长。如果服务器打开了 maxmemory 选项，并且服务器用于回收内存的算法为 volatile-lru 或者 allkeys-lru ，那么当服务器占用的内存数超过了 maxmemory 选项所设置的上限值时，空转时长较高的那部分键会优先被服务器释放，从而回收内存。