redis的底层数据结构以及常用的命令是什么(redis的底层数据结构以及常用的命令有),本文通过数据整理汇集了redis的底层数据结构以及常用的命令是什么(redis的底层数据结构以及常用的命令有)相关信息,下面一起看看。

Redis出现在互联网的很多应用场景中,它能做的事情远远超出我们的想象。Redis的底层数据结构是什么,为什么能做这么多事情?本文将探讨Redis的底层数据结构和常用命令。

知识图谱如下:

一、Redis的数据模型使用键值对名称:“晓明”来表示Redis的数据模型如下:

Dicentry:在某些编程语言中,键值对的数据结构称为dictionary,而在Redis中,每个键值对都会被赋予一个dictionary实体,这个实体就是“DicEntry”。DicEntry由三部分组成:键指针、值指针和下一个指针。下一个指针指向下一个字典,试图形成一个链表。这个next指针可以链接多个具有相同哈希值的键值对,通过链地址的方法解决哈希冲突问题。sds:简单动态字符串,简单动态字符串,存储字符串数据。Rediscobject:Redis的五种常见类型存储为Rediscobject,Rediscobject中的type字段表示值的数据类型(即五种基本类型)。ptr字段指向对象所在的地址。RedRediscobject非常重要。Rediscobject的功能,如类型、内部编码、内存回收、共享对象等,都是基于Rediscobject实现的。

这种设计的好处是可以根据不同的使用场景,为五种常见类型设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效率。

Redis使用jemalloc作为默认的内存分配器来减少内存碎片。在64位系统中,jemalloc将内存空间分为小、大、巨三个范围。每个范围被分成许多小的存储块单元;Redis存储数据时,会选择最合适的内存块进行存储。

二。Redis支持的数据结构。Redis支持哪些数据结构?

如果答案是String、List、Hash、Set、Zset,这五种基本数据类型是redis常用的,每种数据类型也包含多种数据结构。

使用编码指令查看值的数据结构。例如:

27.0.0.1: 6379集合名称tomok127.0.0.1: 6379对象编码名称' embstr '在此设置。名称值为Tom,其数据结构为embstr,下面介绍字符串时会详细说明。

27 . 0 . 0 . 1:6379 set age 18ok 127 . 0 . 0 . 1:6379对象编码age' int '下表总结了Redis中的所有数据结构类型:

底层数据结构编码常量对象编码指令输出整数类型REDIS_ENCODING_INT'int'embstr类型REDIS_ENCODING_EMBSTR'embstr '简单动态字符串REDIS_ENCODING_RAW '字典类型REDIS_ENCODING_HT'has Htable '双端链表REDIS _ ENCODING _ linked list ' zip list ' zip list ' integer set REDIS _ ENCODING _ INT set ' INT set '跳转表和字典REDIS _ ENCODING _ skip list ' skip list '补充说明

如果面试官问:redis的数据类型有哪些?

答案:字符串,列表,哈希,集合,zet

总的来说,这个答案是正确的。如前所述,redis的数据类型确实包括这五种类型,但细心的同学一定发现了之前* *“常用”* *的五种数据类型。事实上,随着Redis的不断更新和完善,Redis的数据类型已经超过5种。

登录redis官网打开数据类型官方介绍:

0.11948192052971263 http 0.1828221159117609s 0.11948192052971263://0.1828221159117609 redis . io/topics/data-types-intro

发现Redis支持的数据结构不止五种,而是八种。最后三种类型是:

位数组(或简称位图):字符串值可以用特殊的命令处理,比如位数组:可以设置和清除每个位,设置所有位为1,查找第一个位或未设置的位,等等。超对数:这是一种概率数据结构,用于估计一个集合的基数。别怕,比看起来简单。Streams:只是类似map的条目的附加集合,提供抽象的日志数据类型。本文主要介绍五种常用的数据类型,以上三种类型以后一起探讨。

2.1 string字符串字符串类型是redis最常用的数据类型。在Redis中,字符串是可以修改的,它以字节数组的形式存在于底层。

Redis中的字符串称为简单动态字符串“SDS”。这种结构非常类似于Java中的ArrayList,长度是动态可变的。

结构SDST { T容量;//数组容量T len//数组长度byte[]内容;//数组内容}

Content[]存储一个字符串的内容,capacity表示数组的分配长度,len表示字符串的实际长度。

字符串有三种编码类型:int、embstr和raw,如上表所示。那么这三种编码类型有什么区别呢?

Int code:保存可以用long类型表示的整数值。

编码raw:保存长度大于44字节的字符串(redis3.2版之前为39字节,之后为44字节)。

Embstr编码:保存长度小于44字节的字符串(redis3.2版之前为39字节,之后为44字节)。

设置一个值来测试它:

127.0.0 . 1:6379 set num 300127 . 0 . 0 . 1:6379对象编码num ' int ' 127 . 0 . 0 . 1:6379 set key 1 wealwaysbyhappyhahahahaok 127 . 0 . 0 . 1:6379对象编码key 1 ' emb str ' 127 . 0 . 0 . 1:6379 set key 2哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈127 . 0 . 0

原始编码的结构:

Embstr和raw都是由redisObject和sds组成的。不同的是embstr的redisObject和sds是连续的,只需要用malloc分配一次内存;Raw需要分别为redisObject和sds分配内存,也就是需要分配两次内存。

相比较而言,embstr一次分配的内存更少,更方便。但是embstr也有明显的缺点:为了增加长度,redisObject和sds都需要重新分配内存。

上面介绍了embstr和raw之间的结构差异。重点来了~为什么选择44作为两个码的分界点?为什么3.2版之前是39?这两个值是怎么出来的?

1)计算RedisObject占用的字节大小。

struct RedisObject { int4 type//4bits int4编码;//4 bits int 24 LRU;//24 bits int 32 ref count;//4 bytes=32 bits void * ptr;//8bytes,64位系统}类型:不同的redis对象会有不同的数据类型(string,list,hash等。),4位将用于类型记录类型。编码:存储编码形式,使用4位。Lru:用24位记录一个对象的LRU信息。Refcount:指计数器,使用32位。*ptr:指针指向对象的具体内容,需要64位。计算:4 4 24 32 64=128位=16字节

第一步完成。RedisObject头信息将占用16个字节,通常是固定的。

2)计算SDS占用的字节大小

旧版本:

struct SDS {无符号整数容量;//4字节无符号整数长度;//4byte byte[]内容;//长度为capacity的内联数组}这里的无符号int是4个字节,加起来是8个字节。

如果内存分配器jemalloc分配的内存超过64字节,将被认为是一个大字符串,将使用原始编码。

如前所述,SDS结构中的内容字符串是以byte \0结尾的字符串。多出来这个字节的原因是为了方便直接使用glibc的字符串处理功能,以及调试和打印字符串。所以我们要减去1字节64字节-16字节-8字节-1字节=39字节。

新版本:

struct SDS { int8 capacity//1 byte int 8 len;//1字节int8标志;//1byte byte[]内容;//Inline array,length是capacity}这里unsigned int变成了uint8_t,uint16 _ t .的形式,并且增加了一个char flags标识符,总共只需要3个字节。相当于优化了sds的内存使用量,对应的用来存储字符串的内存会变大。

然后计算:

64字节- 16字节-3字节-1字节=44字节.

总结:

所以,在Redis版之后embstr可以容纳的最大字符串长度是44,之前是39。长度变化的原因是SDS中内存的优化。

2.2 listredis中List对象的底层由quicklist实现,支持从链表的头尾添加元素,可以获取指定位置元素的内容。

那么,快速列表的底层是如何实现的呢?为什么能达到这么快的性能?

罗马不是一天建成的,也不是一天就能实现的。起初,redis列表的底部是Zip列表(压缩列表)或linkedlist(双端列表)。首先,分别介绍这两种数据结构。

Ziplist压缩列表当一个列表只包含几个列表项,是小整数值或者短字符串时,redis使用ziplist(压缩列表)作为列表键的底层实现。

测试:

27.0.0.1: 6379R推送dota英雄sf qop doom(整数)3127.0.0.1: 6379对象编码Dota英雄‘zip list’在这里是用旧版redis测试的。Dota英雄列表中增加了Qop痛苦女王、SF暗影恶魔、Doom末日三个英雄,数据结构编码。

顾名思义,压缩列表是压缩的。每个节点之间没有指针,但是多个元素是相邻的,没有间隙。所以Redis为了节省内存开发了ziplist,它是由一系列连续的内存块用特殊代码组成的顺序数据结构。具体结构比较复杂,有兴趣可以多了解一下。

struct ziplistT { int32 zlbytes//整个压缩列表占用的字节数是int32 zltail _ offset//压缩列表中最后一个元素距开头的偏移量,用于快速定位最后一个节点int16 zllength//元素T[]条目的数量;//元素内容列表,并逐个紧凑存储int8 zlend//标记压缩列表的结尾,常数值为0xFF}

Linkedlist双端列表大家都很熟悉,这里的双端列表和java中的linkedlist很像。

从图中可以看出,Redis的linkedlist双头链表有以下特点:节点有prev、next、head和tail指针,获取前节点、后节点、head节点和footer节点的复杂度,长度均为O(1)。

压缩列表占用内存较少,但它是一种顺序数据结构,插入和删除元素的操作比较复杂,所以压缩列表适用于数据比较少的情况。当数据较多时,高效插入和删除双端链表仍然是较好的选择。

在Redis开发者看来,数据结构的选择应该在时间和空间上达到极致。因此,他们将压缩列表和双端列表合二为一,创建了quicklist。和java中的hashmap一样,它结合了数组和链表的优点。

快速列表r push:listaddnodehead-o(1)l push:listaddnodetail-o(1)push:listinternode-o(1)index:listindex-o(n)pop:list first/list last-o(

结构ziplist {.} struct zip list _ compressed { int 32 size;byte[]compressed _ data;} struct quick list node { quick list node * prev;quicklistNode * nextziplist * zl//指向压缩列表int32 sizeziplist的总字节数是int16 countziplist int2编码中的元素数;//存储形式为2bit、原生字节数组或LZF压缩存储.}结构快速列表{ quicklistnode * headquicklistNode * tail长计数;int节点的元素总数;ziplist节点数int compressDepth//LZF算法压缩深度.}quicklist的默认压缩深度是0,表示不压缩。实际压缩深度由配置参数list-compress-depth决定。为了支持快速推送/弹出操作,quicklist的第一个和第二个ziplist不压缩,深度为1。如果深度为2,则意味着第一个ziplist和第二个ziplist没有被压缩。

2.3 hash hash数据类型的底层实现是ziplist(压缩列表)或dictionary(也称为hashtable或hash表)。这里压缩列表或字典的选择也是由元素的数量决定的。

如图hset所示,有三个键值对。当每个值的字节数不超过64时,默认使用的数据结构是ziplist。

当我们添加值超过64字节的数据时,默认的数据结构就变成了哈希表。

哈希对象仅在满足以下两个条件时使用ziplist:

中哈希元素的数量小于512;哈希中所有键-值对的键和值字符串的长度小于64个字节。压缩列表刚知道,哈希表类似于jdk1.7之前的hashmap,Hashmap使用链地址法解决哈希冲突问题。如果想了解更多,可以参考之前写的一篇博客:hashmap。你真的知道吗?

redis中的字典在Redis中的dict结构内部包含两个哈希表,通常只有一个哈希表有值。但是当dict伸缩时,就需要分配一个新的哈希表,然后逐步移动。此时,两个哈希表分别存储旧哈希表和新哈希表。重新定位后,旧的哈希表将被删除,新的哈希表将替换它。

2.4 setset数据类型的底层可以是intset(整数集),也可以是hashtable(哈希表也叫哈希表)。

当数据都是整数且数量较少时,使用intset作为底层数据结构;当存在整数以外的数据或者数据量增加时,使用hashtable作为底层数据结构。

27 . 0 . 0 . 1:6379 Sadd Myset 111 222 333(整数)3127.0.0.1: 6379对象编码Myset ' int set ' 127.0.0 . 1:6379 Sadd Myset哈哈哈(整数)127 . 0 . 0。

typefstructintset {//编码模式uint32_t编码;//集合uint32_t length中包含的元素个数;//保存int8_t contents[]的元素数组;} intset基础集合被实现为没有重复的有序数组。集合的整数类型可以是16位、32位和64位。如果数组中的所有整数都是16位长,并且添加了一个新的32位整数,那么整个16位数组将升级为32位数组。升级可以提高intset的灵活性,节省内存,但不可逆。

2.5 Zsetedis中的Zset,也称为有序集。它的底层是ziplist(压缩列表)或skiplist(跳过列表)。

压缩列表前面已经介绍过了,在元素数量比较少的情况下也会用到。这里主要介绍跳转列表。

跳转列表,顾名思义,可以跳转,跳转到查询你想找的元素。你可能不熟悉这种数据结构。虽然你平时接触不多,但它确实是一个各方面性能都很好的数据结构。可以支持快速查询、插入、删除操作,开发难度比红黑树容易很多。

跳表为什么性能这么高?它是怎么“跳”起来的?跳表利用了二分法的思想,可以在数组中快速查找,在链表中也可以。

例如,链表如下所示:

假设要找到节点10,需要逐个遍历,确定是否是要找的节点。如何提高效率?相信大家都很熟悉mysql索引,可以提高效率。你也可以在这里使用索引。取出一个索引图层:

这样你只需要找到9然后再找到10,大大节省了搜索时间。

你也可以画出另一层索引,这样可以更好地节省时间:

这种基于链表的“二分搜索法”支持快速插入和删除,时间复杂度为O(logn)。

因为跳转表的快速查找效率,以及简单易读的实现。于是Redis放弃了红黑树,选择了更简单的跳转表。

Redis中的跳转表:

typefstructzsk iplist {//页眉节点和页脚节点structzskiplistnode * header,* tail//表中的节点数是无符号长整型;//表中层数最多的节点的层数int level} zskiplisttypestructzskiplistnode {//成员对象robj * obj//得分加倍得分;//back pointer struct zskip listnode * backward;//layer struct zskiplistLevel {//正向指针struct zskiplistNode * forward//span-正向指针指向的节点与当前节点之间的距离为无符号int span} level[];} zskiplistNodeZadd - zslinsert -平均O(logN),最差O(N)

Zrem - zsldelete -平均O(logN),最差O(N)

Zrank - zslGetRank -平均O(logN),最差O(N)

本文总结了Redis五种常用数据类型的基本实现,希望大家结合源代码和数据有更深的理解。

数据结构之美在Redis中体现的淋漓尽致。从字符串到压缩列表、快速列表、哈希表、跳转表,这些数据结构在不同的地方都适用,各司其职。

更重要的是,Redis对这些数据结构进行升级和组合,以实现内存存储的极致效率。正因为如此,Redis可以成为很多互联网公司不可或缺的高性能、二级键值内存数据库。

更多redis的底层数据结构以及常用的命令是什么(redis的底层数据结构以及常用的命令有)相关信息请关注本站,本文仅仅做为展示!