首页 > 编程知识 正文

redis数据类型的数据结构,redis8种数据结构

时间:2023-05-03 16:40:03 阅读:23180 作者:3412

另一方面,redis这5种数据类型的redis作为当前最流行的密钥值类型的存储器数据库,对数据库的操作都在存储器中进行,可以定期将数据异步地持久化在磁盘上。 由于它是一种纯内存操作,所以性能比普通关系数据库高很多,而且由于它以单线程方式串行执行指令,因此也避免了锁定和解除锁定的开销。 与memcache相比,redis的每个value值最多存储1GB的yydh,但memcache只有10MB,redis比memcache速度更快,而且可以持久化。 redis的最大特点是可以支持字符串string、列表list、集合[set]、有序集合zset和HL DDP (混列)这五种基本数据类型。 以下,对这些特征和内部安装进行具体说明。

二、redisObject用redis表示,各value用一个redisObject结构表示:

类型结构就绪对象{//类型unsigned type:4; 编码无符号编码:4; //指向基础数据结构的指针void *ptr; //参照计数器int refCount; //上次访问时间unsigned lru:} type :

type是这个对象的数据类型,也就是我们平时识别的redis的五种数据类型。 可以使用TYPE命令显示对象的数据类型。 127.0.0.1:6379 se ta123 ok 127.0.0.133606379 type a string 127.0.0.133606379 hmsetbnamejackage hash 127.0.0 . peclist 127.0.0.133606379 saddd 123 ) inte geg 327.0.0.133606379 typedset 127.0.0.1:6379 zadde2a3b (integer ) 227

表示redisObject对象的基本代码实现主要有简单的动态字符串、链表、字典、跳转表、整数集和压缩列表,每个value由两种或多种上述代码组成,后面是*ptr的详细说明

指向底层实现数据结构的指针lru :

上次访问对象的时间可以在Object idletime中显示从键开始的当前时间的lru时间。 即,怠速时间, 127.0.0.133606379 set CBD 123 ok 127.0.0.133606379 objectidletimecbd (integer ) 90127.0.133606379 object 9127.0 由于1:6379 get cbd //访问了此密钥,lru重置了' 123'127.0.0

参照计数器。 创建对象时将值初始化为1,被其他程序引用时加1,不再引用时减1。 当引用计数值为0时,对象占用的内存将被释放。 因此,主要有两种用途。 用于内存回收标志和对象共享。

共享对象:如果两个或多个新创建的键具有相同的整数值,则这些键共享值对象。 这样可以减少内存分配和回收,并在OBJECT REFCOUNT中查看引用情况。 如下所示。 127.0.0.133606379 set first 123 ok 127.0.0.133606379对象计数(integer )。 127.0.0.133606379 set second 127.0.0.133606379 objectrefcountsecond (integer ) 2127.0.0.1:6379 obje cond 如果新创建的键值在此范围内,则添加直接引用。

三.字符串对象的简单动态字符串(SDS ) :

字符串作为redis中最常见的数据结构,所有键值对的键、字符串对象值的基础都是通过简单的动态字符串实现的。 redis不使用c语言字符串,而是独自实现了称为SDS的数据结构。 其结构表示如下。

记录structsdshdr//buf数组中使用的字节长度int len; int free,记录//buf数组的剩馀空间长度; //字符串char buf[]; (; 以下是SDS的示例。

如果free为0,则没有未使用的空间。 len表示字符串的长度,buf包含每个字节和空

字符,由于SDS遵循了C字符串以为’’结尾的特点,因此它也可以直接重用部分C函数库里的函数。
相比于C字符串,SDS具有以下特点:获取长度的时间复杂度为O(1),因为len直接保存了当前字符串的长度;避免缓存区溢出,当C字符串进行拼接之时,如果未事先对当前字符串的空间进行调整,则可能会导致当前字符串的数据溢出,导致拼接过来的字符串内容被意外的修改,而SDS在拼接之前会进行自动的调整和扩展;减少内存分配次数,在SDS拼接发生以后,如果此时的len小于1MB则它会多分配和len大小相同的未使用空间,用free表示,如果大于1MB,则会分配1MB的为使用空间;惰性空间释放,当字符串进行缩短的时候,程序并不会立即回收空间(也可以调用API立即释放),而是记录到free之中,以便于后序拼接的使用。

编码:
字符串对象的编码可以是int、raw或者embstr。其中int表示整型的值,embstr表示小于等于39字节的字符串值,剩余的均用raw表示,并且int和embstr都是只读的,一旦发生了append操作,即会转换为raw。如下:

127.0.0.1:6379> set age 12OK127.0.0.1:6379> Object encoding age"int"127.0.0.1:6379> APPEND age 3(integer) 3127.0.0.1:6379> Object encoding age"raw"127.0.0.1:6379> set name jackOK127.0.0.1:6379> Object encoding name"embstr"127.0.0.1:6379> APPEND name ja(integer) 6127.0.0.1:6379> Object encoding name"raw" 四、列表对象

链表提供了节点重排以及节点顺序访问的能力,redis中的列表对象主要是由压缩列表和双端链表实现。
双端链表(linkedlist)结构如下:

type struct list{//表头节点listNode *head;//表尾节点listNode *tail;//包含的节点总数unsigned long len;//一些操作函数 dup free match...};

一个链表示例:

其中每个节点都有一个prev指针和一个next指针,而节点中的value则是列表对象具体的值。
压缩列表(ziplist)结构如下:

type struct ziplist{//整个压缩列表的字节数uint32_t zlbytes;//记录压缩列表尾节点到头结点的字节数,直接可以求节点的地址uint32_t zltail_offset;//记录了节点数,有多种类型,默认如下uint16_t zllength;//节点列表节点 entryX;

一个压缩列表示例:

而每个列表节点中主要包括以下几项:previous_entry_length,记录了压缩列表中前一节点的字节长度,当小于254字节时,它的长度为1字节,当大于254字节时,长度为5字节且后4字节保存真正的长度,用于表尾向表头遍历;content,节点所存储的内容,可以是一个字节数组或者整数;encoding,记录content属性中所保存的数据类型以及长度。

编码:
当列表对象所存储的字符串元素长度小于64字节并且元素数量小于512个时,使用ziplist编码,否则使用linkedlist编码,如下:

127.0.0.1:6379> rpush zip "hello" "world"(integer) 2127.0.0.1:6379> OBJECT encoding zip"ziplist"127.0.0.1:6379> rpush zip "fffffffffffffffffffffzzzzzzzzzzzzzzzzzzzzzzzzzzzzzkkkkkkkkkkkkkkkkkkkkkkkkkcccccccccc"(integer) 3127.0.0.1:6379> OBJECT encoding zip"linkedlist"127.0.0.1:6379> 五、集合对象

整数集合与字典:
集合对象的编码可以是整数集合(intset)或者字典(hashtable)。
整数集合结构如下:

typedef struct intset{//编码方式uint32_t encoding;//元素数量uint32_t length;//存储元素的数组int8_t contents[];}

整数集合的每个元素都是contents数组的一个数组项,各个项在数组中按值得大小从小到大有序排列,并且不包含重复的项。contents数组中元素的类型由encoding决定,当新加入元素之时,如果元素的编码大于contents是数组的编码,则会将所有元素的编码升级为新加入元素的编码,然后再插入。编码不会发生降级。
字典的结构如下:

typedef struct dict{//类型特定函数dictType *type;//hlddp表 两个,一个用于实时存储,一个用于rehashdictht ht[2];//rehash索引 数据迁移时使用unsigned rehashidx;}

而hlddp表的结构如下:

typedef struct dictht{//hlddp表数组dictEntry **table;//hlddp表大小unsigned long size;//hlddp表掩码,总是等于size-1,存储时计算索引值unsigned long sizemask;//已有元素数量unsigned long used;}

一个字典示例如下:

其中键值对都保存在节点dictEntry之中,并且通过拉链法解决hlddp冲突,存储时通过MurmurHash算法来计算键的hlddp值,能够更好的提供随机分布性且速度也快。扩容时时采用渐进式的rehash,采用分而治之的方法,通过改变rehashidx的值,来一个个将元素移动到ht[1]中,完成以后将ht[1]变为ht[0],原先的ht[0]变为ht[1],同时将redhashidx置为-1。

编码:
当集合对象所保存的元素都是整数值且元素数量不超过512个时,使用intset编码,否则使用hashtable编码,如下:

127.0.0.1:6379> sadd cloud 1 2 3 4 5(integer) 5127.0.0.1:6379> object encoding cloud"intset"127.0.0.1:6379> sadd cloud a b c(integer) 3127.0.0.1:6379> object encoding cloud"hashtable" 六、有序集合

跳跃表
有序集合的编码可以是压缩列表(ziplist)或者跳跃表(skiplist)。
跳跃表的结构如下:

typedef struct zskiplist{//跳跃表的头结点zskiplistNode header;//尾节点zskiplistNode tail;//跳跃表中层数最大的节点的层数(不包括头结点)unsigned long level;//跳跃表长度(不包括头节点)unsigned int length;

其中的跳跃表节点结构如下:

typedef struct zskiplistNode{//后退指针struct zskiplistNode *backward;//分值double score;//成员对象robj *obj;//层struct zskiplistLevel{//前进指针struct zskiplistNode *forward;//跨度unsigned int span;}level[];};

每个level数组可以包含多个元素,里面存储有指向其他节点(不是下一个)的指针,可以加快访问速度;跨度用于表示两个节点之间的距离,排位时使用;后退指针依次的从后向前访问;分值用于排序;成员是一个指向字符串对象的指针。

编码:
当元素数量小于128个并且所有元素成员的长度都小于64字节之时使用ziplist编码,否则使用skiplist编码,如下:

127.0.0.1:6379> zadd test 2 a 3 b(integer) 2127.0.0.1:6379> OBJECT encoding test"ziplist"127.0.0.1:6379> zadd test 4 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffqwqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq(integer) 1127.0.0.1:6379> OBJECT encoding test"skiplist" 七、hlddp

hlddp对象的编码可以是压缩列表(ziplist)或者字典(hashtable),当hlddp对象保存的所有键值对的键和值得长度都小于64字节并且元素数量小于512个时使用ziplist,否则使用hashtable。使用ziplist时,是依次将键和值压入链表之中,两者相邻。使用hashtable是是将键值对存于dictEntry之中。

参考-《Redis设计与实现》

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。