企业网站管理系统多站多语言版,电子书推送网站怎么做,建网站有什么用,用vue做多页面网站一、键值对数据库是怎么实现的#xff1f;
在开始讲数据结构之前#xff0c;先给介绍下 Redis 是怎样实现键值对#xff08;key-value#xff09;数据库的。 Redis 的键值对中的 key 就是字符串对象#xff0c;而 value 可以是字符串对象#xff0c;也可以是集合数据类型…一、键值对数据库是怎么实现的
在开始讲数据结构之前先给介绍下 Redis 是怎样实现键值对key-value数据库的。 Redis 的键值对中的 key 就是字符串对象而 value 可以是字符串对象也可以是集合数据类型的对象比如 List 对象、Hash 对象、Set 对象和 Zset 对象。 举个例子我这里列出几种 Redis 新增键值对的命令 SET name mingjing
OKHSET person name mingjing age 18
0RPUSH stu mingjing huahua
(integer) 这些命令代表着 ● 第一条命令name 是一个字符串键因为键的值是一个字符串对象 ● 第二条命令person 是一个哈希表键因为键的值是一个包含两个键值对的哈希表对象 ● 第三条命令stu 是一个列表键因为键的值是一个包含两个元素的列表对象
1.1 这些键值对是如何保存在 Redis 中的呢
Redis 是使用了一个「哈希表」保存所有键值对哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对。哈希表其实就是一个数组数组中的元素叫做哈希桶。
1.2 Redis 的哈希桶是怎么保存键值对数据的呢
哈希桶存放的是指向键值对数据的指针dictEntry*这样通过指针就能找到键值对数据然后因为键值对的值可以保存字符串对象和集合数据类型的对象所以键值对的数据结构中并不是直接保存值本身而是保存了 void * key 和 void * value 指针分别指向了实际的键对象和值对象这样一来即使值是集合数据也可以通过 void * value 指针找到。如下图
这些数据结构的内部细节我先不展开讲后面在讲哈希表数据结构的时候在详细的说说因为用到的数据结构是一样的。这里先大概说下图中涉及到的数据结构的名字和用途 ● redisDb 结构表示 Redis 数据库的结构结构体里存放了指向了 dict 结构的指针 ● dict 结构结构体里存放了 2 个哈希表正常情况下都是用「哈希表1」「哈希表2」只有在 rehash 的时候才用具体什么是 rehash我在本文的哈希表数据结构会讲 ● ditctht 结构表示哈希表的结构结构里存放了哈希表数组数组中的每个元素都是指向一个哈希表节点结构dictEntry的指针 ● dictEntry 结构表示哈希表节点的结构结构里存放了 void * key 和 void * value 指针 key 指向的是 String 对象而 value 则可以指向 String 对象也可以指向集合类型的对象比如 List 对象、Hash 对象、Set 对象和 Zset 对象。 特别说明下void * key 和 void * value 指针指向的是 Redis 对象Redis 中的每个对象都由 redisObject 结构表示如下图
对象结构里包含的成员变量 ● type标识该对象是什么类型的对象String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对象 ● encoding标识该对象使用了哪种底层的数据结构 ● ptr指向底层数据结构的指针。 所以Redis 键值对数据库的全景图如下你就能清晰知道 Redis 对象和数据结构的关系了
接下里就好好聊一下底层数据结构
二、SDS简洁
字符串在 Redis 中是很常用的键值对中的键是字符串类型值有时也是字符串类型。 Redis 是用 C 语言实现的但是它没有直接使用 C 语言的 char 字符数组来实现字符串而是自己封装了一个名为简单动态字符串simple dynamic stringSDS 的数据结构来表示字符串也就是 Redis 的 String 数据类型的底层数据结构是 SDS。 既然 Redis 设计了 SDS 结构来表示字符串肯定是 C 语言的 char 字符数组存在一些缺陷。 要了解这一点得先来看看 char 字符数组的结构。
2.1 Redis为什么不直接使用C 语言字符串
C 语言的字符串其实就是一个字符数组即数组中每个元素是字符串中的一个字符。 比如下图就是字符串“mingjing”的 char 字符数组的结构 char* name “mingjing”
mingjing\0
在 C 语言里对字符串操作时char * 指针只是指向字符数组的起始位置而字符数组的结尾位置就用“0”表示意思是指字符串的结束。 因此C 语言标准库中的字符串操作函数就通过判断字符是不是 “0” 来决定要不要停止操作如果当前字符不是 “0” 说明字符串还没结束可以继续操作如果当前字符是 “0” 是则说明字符串结束了就要停止操作。
C 语言字符串用 “0” 字符作为结尾标记有个缺陷。假设有个字符串中有个 “0” 字符这时在操作这个字符串时就会提早结束
因此除了字符串的末尾之外字符串里面不能含有 “0” 字符否则最先被程序读入的 “0” 字符将被误认为是字符串结尾这个限制使得 C 语言的字符串只能保存文本数据不能保存像图片、音频、视频文化这样的二进制数据这也是一个可以改进的地方 另外 C 语言标准库中字符串的操作函数是很不安全的对程序员很不友好稍微一不注意就会导致缓冲区溢出。 举个例子strcat 函数是可以将两个字符串拼接在一起。
//将 src 字符串拼接到 dest 字符串后面
char*strcat(char*dest,constchar* src);C 语言的字符串是不会记录自身的缓冲区大小的所以 strcat 函数假定程序员在执行这个函数时已经为 dest 分配了足够多的内存可以容纳 src 字符串中的所有内容而一旦这个假定不成立就会发生缓冲区溢出将可能会造成程序运行终止这是一个可以改进的地方。 而且strcat 函数和 strlen 函数类似时间复杂度也很高也都需要先通过遍历字符串才能得到目标字符串的末尾。然后对于 strcat 函数来说还要再遍历源字符串才能完成追加对字符串的操作效率不高。 好了 通过以上的分析我们可以得知 C 语言的字符串不足之处以及可以改进的地方 ● 获取字符串长度的时间复杂度为 ON ● 字符串的结尾是以 “0” 字符标识字符串里面不能包含有 “0” 字符因此不能保存二进制数据 ● 字符串操作函数不高效且不安全比如有缓冲区溢出的风险有可能会造成程序运行终止 Redis 实现的 SDS 的结构就把上面这些问题解决了接下来我们一起看看 Redis 是如何解决的。
三、 SDS 结构设计
下图就是 Redis 5.0 的 SDS 的数据结构
结构中的每个成员变量分别介绍下 ● len记录了字符串长度。这样获取字符串长度的时候只需要返回这个成员变量值就行时间复杂度只需要 O1。 ● alloc分配给字符数组的空间长度。这样在修改字符串的时候可以通过 alloc - len 计算出剩余的空间大小可以用来判断空间是否满足修改需求如果不满足的话就会自动将 SDS 的空间扩展至执行修改所需的大小然后才执行实际的修改操作所以使用 SDS 既不需要手动修改 SDS 的空间大小也不会出现前面所说的缓冲区溢出的问题。 ● flags用来表示不同类型的 SDS。一共设计了 5 种类型分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64后面在说明区别之处。 ● buf[]字符数组用来保存实际数据。不仅可以保存字符串也可以保存二进制数据。 总的来说Redis 的 SDS 结构在原本字符数组之上增加了三个元数据len、alloc、flags用来解决 C 语言字符串的缺陷。
3.1 O(1)复杂度获取字符串长度
C 语言的字符串长度获取 strlen 函数需要通过遍历的方式来统计字符串长度时间复杂度是 ON。 而 Redis 的 SDS 结构因为加入了 len 成员变量那么获取字符串长度的时候直接返回这个成员变量的值就行所以复杂度只有 O(1)。
3.2 二进制安全
因为 SDS 不需要用 “0” 字符来标识字符串结尾了而是有个专门的 len 成员变量来记录长度所以可存储包含 “0” 的数据。但是 SDS 为了兼容部分 C 语言标准库的函数 SDS 字符串结尾还是会加上 “0” 字符。 因此 SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据程序不会对其中的数据做任何限制数据写入的时候时什么样的它被读取时就是什么样的。 通过使用二进制安全的 SDS而不是 C 字符串使得 Redis 不仅可以保存文本数据也可以保存任意格式的二进制数据。
3.3 不会发生缓冲区溢出
C 语言的字符串标准库提供的字符串操作函数大多数比如 strcat 追加字符串函数都是不安全的因为这些函数把缓冲区大小是否满足操作需求的工作交由开发者来保证程序内部并不会判断缓冲区大小是否足够用当发生了缓冲区溢出就有可能造成程序异常结束。 所以Redis 的 SDS 结构里引入了 alloc 和 len 成员变量这样 SDS API 通过 alloc - len 计算可以算出剩余可用的空间大小这样在对字符串做修改操作的时候就可以由程序内部判断缓冲区大小是否足够用。 而且当判断出缓冲区大小不够用时Redis 会自动将扩大 SDS 的空间大小以满足修改所需的大小。 SDS 扩容的规则代码如下
hisds hi_sdsMakeRoomFor(hisds s,size_t addlen)
{......// s目前的剩余空间已足够无需扩展直接返回if(avail addlen)return s;//获取目前s的长度len hi_sdslen(s);sh (char*)s -hi_sdsHdrSize(oldtype);//扩展之后 s 至少需要的长度newlen (len addlen);//根据新长度为s分配新空间所需要的大小if(newlen HI_SDS_MAX_PREALLOC)//新长度HI_SDS_MAX_PREALLOC 则分配所需空间*2的空间newlen *2;else//否则分配长度为目前长度1MBnewlen HI_SDS_MAX_PREALLOC;...
}● 如果所需的 sds 长度小于 1 MB那么最后的扩容是按照翻倍扩容来执行的即 2 倍的newlen ● 如果所需的 sds 长度超过 1 MB那么最后的扩容长度应该是 newlen 1MB。 在扩容 SDS 空间之前SDS API 会优先检查未使用空间是否足够如果不够的话API 不仅会为 SDS 分配修改所必须要的空间还会给 SDS 分配额外的「未使用空间」。 这样的好处是下次在操作 SDS 时如果 SDS 空间够的话API 就会直接使用「未使用空间」而无须执行内存分配有效的减少内存分配次数。 所以使用 SDS 即不需要手动修改 SDS 的空间大小也不会出现缓冲区溢出的问题。
