参考:https://blog.csdn.net/ysl19910806/article/details/99326455 在Redis内部,string类型的底层储存结构是SDS。 SDS: 简单动态字符串 simple dynamic string SDS的数据结构如下所示
typedef struct sdshdr {
// buf中已经占用的字符长度
unsigned int len;
// buf中剩余可用的字符长度
unsigned int free;
// 数据空间
char buf[];
}
既然C语言有字符串,为什么还需要重新设计一个SDS呢?原因有如下几点:
因为 C 字符串并不记录自身的长度信息, 所以为了获取一个 C 字符串的长度, 程序必须遍历整个字符串, 对遇到的每个字符进行计数, 直到遇到代表字符串结尾的空字符为止, 这个操作的复杂度为 O(N) 。
和 C 字符串不同, 因为 SDS 在 len 属性中记录了 SDS 本身的长度, 所以获取一个 SDS 长度的复杂度仅为 O(1) 。
C 字符串中的字符必须符合某种编码(比如 ASCII), 并且除了字符串的末尾之外, 字符串里面不能包含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据, 而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
举个例子, 如果有一种使用空字符来分割多个单词的特殊数据格式, 如下图 所示, 那么这种格式就不能使用 C 字符串来保存, 因为 C 字符串所用的函数只会识别出其中的 “Redis” , 而忽略之后的 “Cluster” 。
使用 SDS 来保存之前提到的特殊数据格式就没有任何问题, 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束
因为 C 字符串不记录自身的长度, 所以 strcat(两个字符串相加) 假定用户在执行这个函数时, 已经为 dest 分配了足够多的内存, 可以容纳 src 字符串中的所有内容, 而一旦这个假定不成立时, 就会产生缓冲区溢出。
与 C 字符串不同, SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性: 当 SDS API 需要对 SDS 进行修改时, API 会先检查 SDS 的空间是否满足修改所需的要求, 如果不满足的话, API 会自动将 SDS 的空间扩展至执行修改所需的大小, 然后才执行实际的修改操作, 所以使用 SDS 既不需要手动修改 SDS 的空间大小, 也不会出现前面所说的缓冲区溢出问题。
空间预分配用于优化 SDS 的字符串增长操作: 当 SDS 的 API 对一个 SDS 进行修改, 并且需要对 SDS 进行空间扩展的时候, 程序不仅会为 SDS 分配修改所必须要的空间, 还会为 SDS 分配额外的未使用空间。
其中, 额外分配的未使用空间数量由以下公式决定: 1)如果对 SDS 进行修改之后, SDS 的长度(也即是 len 属性的值)将小于 1 MB , 那么程序分配和 len 属性同样大小的未使用空间, 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子, 如果进行修改之后, SDS 的 len 将变成 13 字节, 那么程序也会分配 13字节的未使用空间, SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节(额外的一字节用于保存空字符)。 2)如果对 SDS 进行修改之后, SDS 的长度将大于等于 1 MB , 那么程序会分配 1 MB 的未使用空间。 举个例子, 如果进行修改之后, SDS 的 len 将变成 30 MB , 那么程序会分配 1 MB 的未使用空间, SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。 通过空间预分配策略, Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。
惰性空间释放用于优化 SDS 的字符串缩短操作: 当 SDS 的 API 需要缩短 SDS 保存的字符串时, 程序并不立即使用内存重分配来回收缩短后多出来的字节, 而是使用 free 属性将这些字节的数量记录起来, 并等待将来使用。
虽然 SDS 的 API 都是二进制安全的, 但它们一样遵循 C 字符串以空字符结尾的惯例: 这些 API 总会将 SDS 保存的数据的末尾设置为空字符, 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符, 这是为了让那些保存文本数据的 SDS 可以重用一部分 <string.h> 库定义的函数。
参考:https://www.cnblogs.com/hunternet/p/12651530.html
hash是日常开发过程中使用Redis的一个数据结构,其底层实现方式有两种,如下所示。一种是zipList,这种是当hash结构的V值较小的时候使用的编码方式,另一种是字典dict
同时满足以下条件使用压缩列表:
哈希表dict类似于Java中的HashMap,字典dict采用连链地址法解决冲突碰撞问题。 参考:https://www.cnblogs.com/reecelin/p/13362104.html
参考:https://www.cnblogs.com/hunternet/p/12624691.html List的底层使用压缩列表ziplist和双向链表list实现(3.0之后list键已经不直接用ziplist和linkedlist作为底层实现了,取而代之的是quicklist)
参考:https://www.cnblogs.com/hunternet/p/12695738.html Set的底层数据结构有两种:intset 和 hashtable。
当一个集合满足以下两个条件时,Redis 会选择使用 intset 编码:
哈希表
参考:https://www.cnblogs.com/hunternet/p/12717643.html
有序集合对象的底层数据结构有两种:skiplist 和 ziplist
当有序集合对象同时满足以下两个条件时,会使用 ziplist 编码进行存储:
跳表:有索引的链表结构,查询效率可以媲美红黑树。