万丈高楼平地起-redis基础数据结构string
大家好,我是热心的大肚皮,皮哥。我们又多了一个系列-redis。
redis是互联网技术架构在存储系统中使用最多的中间件,也是面试必问的技能之一。希望通过自己实战经验,能帮助更多后端开发者更深更快的掌握redis。不多说了,开整。
什么是redis?
redis是"Remote Dictionary Service"(远程字典服务)的首字母缩写。具有超高的性能、完美的文档、简洁易懂的源码和丰富的客户端在开源中间件领域中广受好评。
redis有几种数据结构呢?
redis有以下5种数据结构。
- string(字符串)
- list(列表)
- hash(字典)
- set(集合)
- zset(有序集合)
今天我们先通关第一种string。
string
数据结构
redis中的字符串也叫做"SDS",也就是Simple Dynamic String。是一个带长度信息的字节数组。如下图。
直接上源码。
// 对象属性
struct SDS<T> {
// 数组容量
T capacity;
// 数组长度
T len;
// 特殊标志位,暂时不用管
byte flags;
//数组内容
byte[] content;
}
//追加 SDS 字符串
sds sdscatlen(sds s, const void *t, size_t len){
// 原字符串的长度
size_t curlen = sdslen(s);
//按需调整空间,如果capacity不够容纳追加d的内容,就会从新分配
//字节数据,并将原内容复制到新数组中
s = sdsMakeRoomFor(s, len);
//内存不足
if(s == NULL) return NULL;
//追加目标字符串内容到字节数组
memcpy(s+curlen, t, len);
//设置追加后的字符串长度
sdssetlen(s, curlen + len);
//让字符串以\0结尾,便于调试打印。
s[curlen+len]='\0';
return s;
}
/*空间调整,注意只是调整空间,后续自己组装字符串*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
// 当前剩下的空间
size_t avail = sdsavail(s);
size_t len, newlen;
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* 空间足够 */
if (avail >= addlen) return s;
// 长度
len = sdslen(s);
// 真正的数据体
sh = (char*)s-sdsHdrSize(oldtype);
// 新长度
newlen = (len+addlen);
// < 1M 2倍扩容
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
// > 1M 扩容1M
else
newlen += SDS_MAX_PREALLOC;
// 获取sds 结构类型
type = sdsReqType(newlen);
// type5 默认转成 type8
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
// 头长度
hdrlen = sdsHdrSize(type);
if (oldtype==type) { // 长度够用 并且 数据结构不变
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
s = (char*)newsh+hdrlen;
} else {
// 重新申请内存
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);
s = (char*)newsh+hdrlen;
s[-1] = type;
sdssetlen(s, len);
}
sdssetalloc(s, newlen);
return s;
}
细心的小伙伴有没有发现,为什么capacity与len 不用int 而是 T呢?原因是当字符串比较短时,capacity与len可以用short 或者byte来表示,也是为了对内存极致的优化。
扩容规则
每次创建时capacity与len一样大,点那个字符串长度小于1MB时,每次扩容都是加倍现有的空间,如果长度大于1MB,则每次只会扩容1MB的空间,注意字符串在这里最大长度为512MB。
存储方式
分为embstr与raw两种。当字符串超过44字节,则采用raw存储。那么为什么是44字节呢?首先我们要了解,在redis中,每一个对象都有一个对象头结构。
struct RedisObject {
//不同的对象都有不同的类型 4bits
int4 type;
//同一个类型会有不同的存储形式 4bits
int4 encoding;
//对象d的lru信息,使用24bits
int24 lru;
//引用计数,为0时则对象会被销毁 4bytes
int32 refcount;
//指向对象内容的具体存储位置,8bytes
void *ptr;
}
一个字符串在内存的结构如下图。
我们可以看出来对象头RedisObject需要16个字节的空间。er内存分配器jemalloc、tcmalloc分配内存大小都是2/4/8/16/32/64 字节,而字符串不算内容最少需要19个字节,redis的作者考虑到性能,将64字节作为分界线,这样计算,也就是当字符串长度等于 64-19=45,但是字符串又是以null作为结尾,所以边界则是44字节。具体的存储方式为连续内存与,非连续内存,如下图。
相关文章
- 数据结构深入浅出Redis之字典数据结构(redis字典)
- 利用Redis灵活保存复杂数据结构(redis保存复杂对象)
- Redis 过期指令:控制数据生命周期(redis过期命令)
- 开启Redis之旅从一个端口绽放无穷火种(开启一个redis端口)
- 基于Redis的高效并发队列实现(并发队列redis)
- 查看Redis中有多少数据表(查看redis有多少表)
- 探索用Redis编写微博体验超越常规(用redis怎么写微博)
- 有哪些深入理解Redis它的数据结构有哪些(数据库redis使用的数据结构)
- 拥抱云·Redis高效运行在云服务器上(云服务器运行redis)
- 深入学习Redis,了解数据结构存储(学习redis书籍)
- 如何轻松实现Redis数据库自动启动(怎么自动启动redis库)
- 从零开始,一路走进Redis的精通(redis零基础到精通)
- 利用Redis实现多数据结构存储(redis集合的数据结构)
- Redis实现无序集合数据结构(redis 集合无序)
- 简单实用Redis读写策略调优指南(redis读写策略设置)
- Redis评论灵活的数据结构(redis评论什么结构)
- 深入浅出Redis 中 Hash 数据结构的设置使用(redis设置hash值)
- Redis使用密码安全性有多高(redis设置密码安全吗)
- Redis缓存技术构建数据库基础(redis缓存数据库基础)