嘉兴网站建设模板网站,下载代码的网站,网站建设仟首先金手指12,网络营销平台概念
Redis作为一个开源的用C编写的非关系型数据库#xff0c;基于优秀的CRUD效率#xff0c;常用于软件系统的缓存#xff0c;其本身提供了以下五种数据格式#xff1a;
string#xff1a;字符串list#xff1a;列表hash#xff1a;散列表set#xff1a;无序集合zse…概念
Redis作为一个开源的用C编写的非关系型数据库基于优秀的CRUD效率常用于软件系统的缓存其本身提供了以下五种数据格式
string字符串list列表hash散列表set无序集合zset有序集合
接下来我们就要针对这五种数据结构来分析其底层的结构 这里选用的版本是redis-5.0.4所以可能有很多地方和如今网络上的其他博文不太一致不同的地方我会在文中指出 string 因为redis使用c语言开发所以自然没有java和c的那些字符串类库在redis中其自己定义了一种字符串格式叫做SDSSimple Dynamic String即简单动态字符串 这个结构定义在sds.h中
typedef char *sds;但是这个sds类型仅作为参数和返回值使用并不是真正用于操作的类型真正核心的部分是下面的这些类
struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; uint8_t alloc; unsigned char flags; char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len;uint16_t alloc; unsigned char flags;char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len;uint32_t alloc; unsigned char flags; char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; uint64_t alloc;unsigned char flags; char buf[];
};除掉第一个结构体已经弃用sds具体类型的结构可以分为以下部分
len已使用的长度即字符串的真实长度alloc除去标头和终止符(’\0’)后的长度flags低3位表示字符串类型其余5位未使用我暂时没发现redis在哪里使用过这个属性buf[]存储字符数据
这里和老版本做一下对比因为我手头只有4.x和5.x的版本它们sds的实现是一致的但是据其他人说sds之前的版本实现方式不同有时间我会去下载下来看一下其将字符串分为以下部分
lenbuf中已经占有的长度表示此字符串的实际长度freebuf中未使用的缓冲区长度buf[]实际保存字符串数据的地方
redis同时写重写了大量的与sds类型相关的方法那redis为什么要这么下功夫呢有以下4个优点
降低获取字符串长度的时间复杂度到O(1)减少了修改字符串时的内存重分配次数兼容c字符串的同时提高了一些字符串工具方法的效率二进制安全数据写入的格式和读取的格式一致
list 我们查看源文件可以看到有两个list一个是ziplist字面意是压缩列表另一个是quicklist字面意是快速列表在redis中直接使用的是quicklist但是我们先来看ziplist ziplist ziplist并不是一个类名其结构是下面这样的 … 其中各部分代表的含义如下
zlbytes4个字节32bits表示ziplist占用的总字节数zltail4个字节32bits表示ziplist中最后一个节点在ziplist中的偏移字节数entries2个字节16bits表示ziplist中的元素数 entry长度不定表示ziplist中的数据zlend1个字节8bits表示结束标记这个值固定为ff255
这些数据均为小端存储所以可能有些人查看数据的二进制流与其含义对应不上其实是因为读数据的方式错了 ziplist内部采取数据压缩的方式进行存储压缩方式就不是重点了我们仅从宏观来看ziplist类似一个封装的数组通过zltail可以方便地进行追加和删除尾部数据、使用entries可以方便地计算长度 但是其依然有数组的缺点就是当插入和删除数据时会频繁地引起数据移动所以就引出了quicklist数据类型 quicklist 其核心数据结构如下
typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count; /* ziplist所有节点的个数 */unsigned long len; /* quicklistNode节点的个数 */int fill : 16; /* 单个节点的填充因子 */unsigned int compress : 16; /* 压缩端结点的深度 */
} quicklist;我们可以明显地看出quicklist是一个双向链表的结构但是内部又涉及了ziplist我们可以这么说在宏观上quicklist是一个双向链表在微观上每一个quicklist的节点都是一个ziplist 在redis.conf中可以使用下面两个参数来进行优化
list-max-ziplist-size表示每个quicklistNode的字节大小。默认为2表示8KBlist-compress-depth表示quicklistNode节点是否要压缩。默认为0表示不压缩
这种存储方式的优点和链表的优点一致就是插入和删除的效率很高而链表查询的效率又由ziplist来进行弥补所以quicklist就成为了list数据结构的首选 hash hash这种结构在redis的使用时最为常见在redis中hash这种结构有两种表示zipmap和dict zipmap zipmap其格式形如下面这样 zmlenlenfoolenfreebarlenhellolenfreeworld 各部分的含义如下
zmlen1个字节表示zipmap的总字节数len1~5个字节表示接下来存储的字符串长度free1个字节是一个无符号的8位数表示字符串后面的空闲未使用字节数由于修改与键对应的值而产生
这其中相邻的两个字符串就分别是键和值比如在上面的例子中就表示foo bar, hello world这样的对应关系
这种方式的缺点也很明显就是查找的时间复杂度为O(n)所以只能当作一个轻量级的hashmap来使用 dict 这种方式就适于存储大规模的数据其格式如下
typedef struct dict {dictType *type;/* 指向自定义类型的指针可以存储各类型数据 */void *privdata; /* 私有数据的指针 */dictht ht[2];/* 两个hash表一般只有h[0]有效h1[1]只在rehash的时候才有值 */long rehashidx; /* -1没有在rehash的过程中大于等于0表示执行rehash到第几步 */unsigned long iterators; /* 正在遍历的迭代器个数 */
} dict;如果我们不想更深入的话了解到这种程度就可以了其中真正存储数据的是dictEntry结构如下
typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;
} dictEntry;很明显是一个链表我们知道这是采用链式结构存储就足够了 这种方式会消耗较多的内存所以一般数据较少时会采用轻量级的zipmap set 在redis中我们可以查看intset.h文件这是一个存储整数的集合其结构如下
typedef struct intset {uint32_t encoding;uint32_t length;int8_t contents[];
} intset;其中各字段含义如下
encoding数据编码格式表示每个数据元素用几个字节存储可取的值有2、4和8length元素个数contents柔性数组这部分内存单独分配不包含在intset中
具体的操作我们就不详细展开了了解集合这种数据结构的应该都很清楚我们这里说一下intset有一个数据升级的概念比方说我们有一个16位整数的set这时候插入了一个32位整数所以就导致整个集合都升级为32位整数但是反过来却不行这也就是柔性数组的由来 如果集合过大会采用dict的方式来进行存储 zset zset有很多地方也叫做sorted set是一个键值对的结构其键被称为member也就是集合元素zset依然是set所以member不能相同其对应的值被称为score是一个浮点数可以理解为优先级用于排列zset的顺序 其也有两种存储方式一种是ziplist/zipmap的格式这种方式我们就不过多介绍了只需要了解这种格式将数据按照score的顺序排列即可 另一种存储格式是采用了skiplist意为跳跃表可以看成平衡树映射的数组其查找的时间复杂度和平衡树基本没有差别但是实现更为简单形如下面这样的结构图来源跳跃表的原理
