Redis基础数据结构 基础数据结构 sds简单动态字符串 数据结构
typedef struct sdstr{ int len // 字符串分配的字节 int free // 未使用的字节数 char buff[] // 存储字符串的数组 }
sds是字符串对象的底层实现之一
sds的特性赋值操作会统计字符串的长度然后将字符串存入buff里面,同时设定长度和使用的长度
例如 "hello"这个字符串的存储结构如下
{ len:5, free:0, buff:['h','e','l','l','o','\0'] }
修改的时候会比较麻烦,分为两种情况
一是由段字符串变长:例如:由"hello"变为"hello,redis".
这个时候系统会检查原本的sds字符串是否有空余空间,剩余空间为0,会分配等同于修改后字符串长度的剩余空间给sds,这个时候字符串的free属性会变为11,然后执行sdscat(),这个时候buff会变为['h','e','l','l','o',',','r','e','d','i','s','\0'],然后将字符串长度len修改为11
最终结构如下
{ len:11, free:11, buff:['h','e','l','l','o',',','r','e','d','i','s','\0'] }
ps:当长度小于1M是翻倍扩容,超过1M时是以1M为标准定量扩容
二是由长字符串变短
例如:由"hello,redis"变为"redis",这个时候会释放多余空间,同时把free值设为多出来的空间,以便下次使用方便
修改后的结构大概如下
{ len:5, // 字符串长度 free:17, // 原本11,加上释放到的6个字节 buff:['r','e','d','i','s','\0'] }
需要释放的时候可以手动调用函数来释放空间
为什么要使用sds?sds可以杜绝缓冲区溢出的问题,获取字符串长度复杂度为常数
二进制安全,sds使用len属性来判断字符串的结束
减少字符串修改时的内存重分配次数
链表 数据结构//链表节点 typedef struct listNode{ struct listNode *pre; struct listNode *next; void *value; }listNode; //链表 typedef struct list{ listNode * head; //头节点 listNode * tail; //尾节点 unsigned long len; //节点数量 void *(*dup)(void *ptr); //节点值复制函数 void (*free)(void *ptr); //节点值释放函数 void (*match)(void *ptr,void *key); //节点值对比函数 }
链表是列表对象的底层实现之一
链表在redis中主要负责的是存储和维护某一类对象,所常用到的操主要有遍历,修改等
链表在redis中使用极为广泛,redis的事务,发布与订阅,服务器中维护的redisClient信息等都是用链表结构进行的存储
字典 数据结构//哈希表 typedef struct dictht{ dictEntry **table; //哈希节点 unsigned long size; //哈希表大小 unsigned long sizemask; //哈希表掩码,用于计算索引值 unsigned long used; // 已有节点数量 } dictht; //哈希节点 typedef struct dictEntry{ void *key;//键 union { void *val; uint64_tu64; int64_ts64; } v; struct dictEntry *next; }dictEntry; //字典 typedef struct dict{ dictType *type; //类型特定函数 void *privdata; //私有数据 dictht ht[2]; //哈希表 ht[0]常用 ht[1]rehash时候使用 int rehashidx; //rehash标识 }dict;
字典是数据库的底层实现
解决键冲突