asp手机网站源码下载,门户网站建设方案中信息公开,wordpress字体编辑插件下载,电子商务网站平台建设策划SDS
无论是 Redis 的 Key 还是 Value#xff0c;其基础数据类型都是字符串。虽然 Redis是使用标准 C 语言开发的#xff0c;但并没有直接使用 C 语言中传统的字符串表示#xff0c;而是自定义了一 种字符串。这种字符串本身的结构比较简单#xff0c;但功能却非常强大其基础数据类型都是字符串。虽然 Redis是使用标准 C 语言开发的但并没有直接使用 C 语言中传统的字符串表示而是自定义了一 种字符串。这种字符串本身的结构比较简单但功能却非常强大称为简单动态字符串Simple Dynamic String简称 SDS。
SDS 结构
SDS 不同于 C 字符串。C 字符串本身是一个以双引号括起来以空字符’\0’结尾的字符序 列。但 SDS 是一个结构体定义在 Redis 安装目录下的 src/sds.h 中
struct sdshdr {
// 字节数组用于保存字符串
char buf[];
// buf[]中已使用字节数量称为 SDS 的长度
int len;
// buf[]中尚未使用的字节数量
int free;
} 通过以上结构可以看出SDS 的 buf 值实际是一个 C 字符串包含空字符’\0’共占 6 个字 节。**但 SDS 的 len 是不包含空字符’\0’的。 **
SDS 的优势 对于 C 字符串若要获取其长度则必须要通过遍历整个字符串才可获取到的。对于超 长字符串的遍历会成为系统的性能瓶颈。 SDS 结构体中直接就存放着字符串的长度数据 SDS 采用了空间预分配策略与惰性空间释放策略来避免内存再分配问题。 空间预分配策略是指每次 SDS 进行空间扩展时程序不但为其分配所需的空间还会 为其分配**额外的未使用空间以减少内存再分配次数。**而额外分配的未使用空间大小取决于 空间扩展后 SDS 的 len 属性值。 如果 len 属性值**小于 1M**那么分配的未使用空间 free 的大小与 len 属性值相同。如果 len 属性值大于等于 1M 那么分配的未使用空间 free 的大小固定是 1M。 SDS 对于空间释放采用的是惰性空间释放策略。 该策略是指SDS 字符串长度如果缩短 那么多出的未使用空间将暂时不释放而是增加到 free 中。以使后期扩展 SDS 时减少内存 再分配次数。 如果要释放 SDS 的未使用空间则可通过 sdsRemoveFreeSpace()函数来释放。
集合的底层实现原理
Redis 中对于 Set 类型的底层实现直接采用了 hashTable。hashtable就是普通的哈希表key为set的值value为null。但对于 Hash、ZSet、List 集 合的底层实现进行了特殊的设计使其保证了 Redis 的高性能。
1 两种实现的选择
对于Hash与ZSet集合其底层的实现实际有两种压缩列表zipList与跳跃列表skipList。这两种实现对于用户来说是透明的但用户写入不同的数据系统会自动使用不同的实现。 只有同时满足以配置文件 redis.conf 中相关集合元素数量阈值与元素大小阈值两个条件****使用的就是压缩列表 zipList只要有一个条件不满足使用的就是跳跃列表 skipList。、例如对于ZSet 集合中这两个条件如下 集合元素个数小于 redis.conf 中 zset-max-ziplist-entries 属性的值其默认值为 128每个集合元素大小都小于 redis.conf 中 zset-max-ziplist-value 属性的值其默认值为 64字节
2什么是 zipList
zipList通常称为压缩列表是一个经过特殊编码的用于存储字符串或整数的双向链表。 其底层数据结构由三部分构成**head、entries 与 end。**这三部分在内存上是连续存放的。
prevlength该部分用于记录上一个 entry 的长度以实现逆序遍历。encoding该部分用于标志后面的 data 的具体类型。如果 data 为整数类型encoding固定长度为 1 字节。如果 data 为字符串类型则 encoding 长度可能会是 1 字节、2 字 节或 5 字节。data 字符串不同的长度对应着不同的 encoding 长度。压缩的体现。
什么是** skipList
skipList跳跃列表简称跳表是一种**随机化的数据结构基于并联的链表**实现简单 查找效率较高。简单来说跳表也是链表的一种只不过它在链表的基础上增加了跳跃功能。 也正是这个跳跃功能使得在查找元素时能够提供较高的效率。
skipList 原理
假设有一个带头尾结点的有序链表。 为了提升查找效率在偶数结点上增加一个指针让其指向下一个偶数结点。 这样所有偶数结点就连成了一个新的链表简称高层链表当然高层链表包含的节 点个数只是原来链表的一半。此时再想查找某个数据时先沿着高层链表进行查找。当遇到 第一个比待查数据大的节点时立即从该大节点的前一个节点回到原链表中进行查找。 问题这种对链表分层级的方式从原理上看确实提升了查找效率但在实际操作时就出现了问 题由于固定序号的元素拥有固定层级所以列表元素出现增加或删除的情况下会导致列表整体元素层级大调整但这样势必会大大降低系统性能。
优化
为了避免前面的问题skipList 采用了随机分配层级方式。即在确定了总层级后每添 加一个新的元素时会自动为其随机分配一个层级。这种随机性就解决了节点序号与层级间的 固定关系问题。
上图演示了列表在生成过程中为每个元素随机分配层级的过程。从这个 skiplist 的创建 和插入过程可以看出每一个节点的层级数都是随机分配的而且新插入一个节点不会影响 到其它节点的层级数。只需要**修改插入节点前后的指针**而不需对很多节点都进行调整。这 就降低了插入操作的复杂度。
什么是 quickList List的底层实现 quickList快速列表quickList 本身是一个双向无循环链表它的每一个节点都是一个zipList。 quickList 本质上是 zipList 和 linkedList 的混合体。其将 linkedList 按段切分每一段使用 zipList 来紧凑存储若干真正的数据元素多个 zipList 之间使用双向指针串接起来。当然 对于每个 zipList 中最多可存放多大容量的数据元素在配置文件中通过 list-max-ziplist-size属性可以指定。
