Redis之SDS数据结构的使用
来源:脚本之家
时间:2022-12-30 12:18:46 456浏览 收藏
在数据库实战开发的过程中,我们经常会遇到一些这样那样的问题,然后要卡好半天,等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《Redis之SDS数据结构的使用》,聊聊数据结构、RedisSDS,希望可以帮助到正在努力赚钱的你。
序言
Redis的几种基本数据结构有字符串(String)、哈希(Hash)、列表(List)、集合(Set)、有序集合(Sorted Set),这些是最常见的,也能在官网上查看到。
官网链接:Redis 教程_redis教程
字符串
前面也提到过字符串是设计了简单动态字符串SDS(Simple Dynamic String)结构来表示字符串。这种数据结构可以提升字符串的操作效率,并可以保存二进制数据。
先思考一个问题:
Redis是用C语言实现的,那么为什么没有复用C语言的字符串实现方法,而选用了SDS呢?
char*字符串数组
C语言实现字符串使用的是char*字符串数组,它是一块连续的内存空间,一次存放了字符串的每一个字符,并且最后一个字符是“\0”,用来标识字符串的结尾位置,如下图,
连续的内存空间的所有字符串没有分隔符计算机就没办法区分字符串与字符串之间的位置。在C语言标准库中字符串的操作函数就会通过检查字符串数组中是否有“\0”来判断字符串是否结束。例如字符串操作函数strlen函数,它就是在遍历字符串数组中的每一个字符,并进行计数,直到检查到“\0”,它的时间复杂度是O(n)。流程如下,
简单动态字符串SDS
SDS的数据结构里包含:字符串实际长度,字符串分配空间长度,SDS类型,字符数组,其中字符数组buf[]用来保存实际数据,如下图,
再来看看类似的字符操作函数sdslen函数的源码(在sds.h文件中),直接根据SDS类型返回对应的字符串现有长度,避免了对字符串的遍历,时间复杂度变成了O(1),当然也会付出一点代价增加了空间复杂度。这都是设计人员让数据操作更加高效。源码如下,
static inline size_t sdslen(const sds s) { unsigned char flags = s[-1]; switch(flags&SDS_TYPE_MASK) { case SDS_TYPE_5: return SDS_TYPE_5_LEN(flags); case SDS_TYPE_8: return SDS_HDR(8,s)->len; case SDS_TYPE_16: return SDS_HDR(16,s)->len; case SDS_TYPE_32: return SDS_HDR(32,s)->len; case SDS_TYPE_64: return SDS_HDR(64,s)->len; } return 0; }
再来看一下字符串的拷贝源码,操作都使用了字符串的现有长度,拷贝后进行更新。
sds sdscpylen(sds s, const char *t, size_t len) { // 判断字符串数组分配的空间长度是不是小于字符串数组当前长度 if (sdsalloc(s)SDS把目标字符串的空间检查和扩容封装在了sdsMakeRoomFor函数中,追加、打印、复制等操作都会调用该函数。可以看到该函数根据sds的信息进行动态扩容,源码如下,
sds sdsMakeRoomFor(sds s, size_t addlen) { void *sh, *newsh; // 获取sds可用空间 size_t avail = sdsavail(s); size_t len, newlen; char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; // 如果可用空间大于等于要增加的空间,则直接返回 if (avail >= addlen) return s; // sds长度 len = sdslen(s); // sds指针 sh = (char*)s-sdsHdrSize(oldtype); // 新字符串长度 newlen = (len+addlen); // 如果新长度小于最大预分配长度,则进行两倍扩容 if (newlen可以看到sdsMakeRoomFor函数中sdshdr5类型不再使用直接转换成了sdshdr8类型,它们是SDS设计的5种类型,分别表示sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64,下面就看一下这几种类型的结构源码,如下图,
struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* used */ uint8_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 { uint16_t len; /* used */ uint16_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 { uint32_t len; /* used */ uint32_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 { uint64_t len; /* used */ uint64_t alloc; /* excluding the header and null terminator */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ char buf[]; };sdshdr5已不再使用,所以在函数中做了处理,把sdshdr5类型转换为sdshdr8类型。前面也提到过SDS是紧凑型字符串数据结构,以sdshdr8为例,它是用的是uint8_t即8位无符号整型,会占用1字节的内存空间。SDS之所以设计不同的结构是为了能灵活保存不同大小的字符串,从而有效节省内存空间。
另外,__attribute__ ((__packed__))标志可以告诉编译器在编译以上数据结构时,不实用字节对齐的方式(不满8字节的整数倍,则会自动补齐),而是采用紧凑的方式分配内存。
今天关于《Redis之SDS数据结构的使用》的内容就介绍到这里了,是不是学起来一目了然!想要了解更多关于redis的内容请关注golang学习网公众号!
-
148 收藏
-
406 收藏
-
280 收藏
-
185 收藏
-
183 收藏
-
342 收藏
-
361 收藏
-
159 收藏
-
164 收藏
-
221 收藏
-
156 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 507次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习
-
- 震动的羊
- 太详细了,码住,感谢up主的这篇技术贴,我会继续支持!
- 2023-06-06 16:02:49
-
- 清脆的柠檬
- 赞 👍👍,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,看完之后很有帮助,总算是懂了,感谢大佬分享技术贴!
- 2023-04-26 20:48:26
-
- 沉默的小鸽子
- 这篇文章真是及时雨啊,细节满满,赞 👍👍,收藏了,关注博主了!希望博主能多写数据库相关的文章。
- 2023-02-24 11:27:31
-
- 复杂的柚子
- 很棒,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,看完之后很有帮助,总算是懂了,感谢师傅分享文章内容!
- 2023-02-20 03:55:33
-
- 辛勤的翅膀
- 这篇文章内容出现的刚刚好,老哥加油!
- 2023-02-04 07:42:03
-
- 沉静的野狼
- 这篇文章内容出现的刚刚好,好细啊,赞 👍👍,mark,关注楼主了!希望楼主能多写数据库相关的文章。
- 2023-01-29 11:44:29
-
- 靓丽的雪碧
- 很详细,码起来,感谢作者的这篇技术贴,我会继续支持!
- 2023-01-27 12:07:59
-
- 机灵的小土豆
- 这篇技术贴真是及时雨啊,老哥加油!
- 2023-01-27 08:19:50
-
- 花痴的烤鸡
- 太详细了,已加入收藏夹了,感谢作者大大的这篇文章,我会继续支持!
- 2023-01-27 04:00:05
-
- 甜美的墨镜
- 这篇技术文章真是及时雨啊,很详细,太给力了,收藏了,关注楼主了!希望楼主能多写数据库相关的文章。
- 2023-01-26 05:17:59
-
- 欣慰的雪糕
- 这篇文章内容出现的刚刚好,作者大大加油!
- 2023-01-26 00:46:10
-
- 孝顺的超短裙
- 这篇文章内容太及时了,太详细了,很棒,收藏了,关注up主了!希望up主能多写数据库相关的文章。
- 2023-01-17 16:32:47
-
- 殷勤的小蘑菇
- 这篇技术文章真是及时雨啊,细节满满,很棒,码住,关注师傅了!希望师傅能多写数据库相关的文章。
- 2023-01-12 12:44:07
-
- 仁爱的猫咪
- 很有用,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,看完之后很有帮助,总算是懂了,感谢师傅分享博文!
- 2023-01-08 13:17:10
-
- 爱撒娇的草莓
- 受益颇多,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,帮助很大,总算是懂了,感谢楼主分享文章内容!
- 2023-01-04 22:58:32
-
- 陶醉的世界
- 很详细,已收藏,感谢大佬的这篇博文,我会继续支持!
- 2023-01-03 22:21:02
-
- 美好的冬日
- 很棒,一直没懂这个问题,但其实工作中常常有遇到...不过今天到这,帮助很大,总算是懂了,感谢大佬分享技术贴!
- 2023-01-01 16:46:09