当前位置:首页 > 知乎 > 正文内容

redis专题系列1_数据结构底层设计

知乎君2年前 (2022-05-25)469

redis数据结构解析redis安装

1. 下载redis的安装包(直接去官网下一个就行)

2. tar -zxvf 解压

3. cd 到解压后的目录

4. 执行make 完成编译

可能会遇到的错误

- 需要安装tcl (yum -y install tcl 、 yum -y install gcc)

- error: jemalloc/jemalloc.h: No such file or directory 说关于分配器allocator, 如果有MALLOC 这个 环境变量, 会有用这个环境变量的 去建立Redis。 而且libc 并不是默认的 分配器, 默认的是 jemalloc, 因为 jemalloc 被证明 有更少的 fragmentation problems 比libc。 但是如果你又没有jemalloc 而只有 libc 当然 make 出错。 所以加这么一个参数。 解决办法 make MALLOC=libc

5. make test 测试编译状态

6. make install {PREFIX=/path} (示例:make PREFIX=/soft/redis install)

7. 环境变量配置

export REDIS_HOME=/soft/redis

export PATH=$PATH:$REDIS_HOME/bin

redis服务文件相关命令

Redis-server Redis服务器

Redis-cli Redis命令行客户端

Redis-benchmark Redis性能测试工具

Redis-check-aof Aof文件修复工具

Redis-check-dump Rdb文件检查工具

Redis-sentinel Sentinel服务器(2.8以后)

reids对基于key-value存储,数据基础命令

KEYS * 获得当前数据库的所有键

EXISTS key [key ...] 判断键是否存在,返回个数,如果key有一样的也是叠加数

DEL key [key ...] 删除键,返回删除的个数

TYPE key 获取减值的数据类型(string,hash,list,set,zset)

FLUSHALL 清空所有数据库

CONFIG [get、set] redis配置

详解redis数据结构 Redis的五种数据类型:

字符串(String)

存储说明:

字符串类型是redis中最基本的数据类型,它能存储任何形式的字符串,包括二进制数据。你可以用它存储用户的邮箱、json化的对象甚至是图片。一个字符类型键允许存储的最大容量是512M。

数据结构:

在Redis内部,String类型通过int、SDS(simpledynamicstring)作为结构存储,int用来存放整型数据,sds存放字节/字符串和浮点型数据.redis是用C语言写的。可以在redis的源码[sds.h]中看到sds的结构如下:

typedef char *sds;

redis3.2分支引入了五种sdshdr类型,默认是sdshdr8。目的是为了满足不同长度字符串可以使用不同大小的Header,从而节省内存,每次在创建一个sds时根据sds的实际长度判断应该选择什么类型的sdshdr,不同类型的sdshdr占用的内存空间不同。这样细分一下可以省去很多不必要的内存开销。

sdshdr8数据结构如下:

struct __attribute__ ((__packed__)) sdshdr8 { //8表示字符串最大长度是2^8-1 (长度为255)uint8_t len;//表示当前sds的长度(单位是字节)uint8_t alloc; //表示已为sds分配的内存大小(单位是字节)unsigned char flags; //用一个字节表示当前sdshdr的类型,因为有sdshdr有五种类型,所以至少需要3位来表示000:sdshdr5,001:sdshdr8,010:sdshdr16,011:sdshdr32,100:sdshdr64。高5位用不到所以都为0。char buf[];//sds实际存放的位置};String的函数说明:

最基本的命令:GET、SET 语法:GET key,SET key value value如果有空格需要双引号以示区分

整数递增:INCR 语法:INCR key 默认值为0,所以首先执行命令得到 1 ,不是整型提示错误

增加指定的整数:INCRBY 语法:INCRBY key increment

整数递减:DECR 语法:DECR key 默认值为0,所以首先执行命令得到 -1,不是整型提示错误

减少指定的整数:DECRBY 语法:DECRBY key increment

增加指定浮点数:INCRBYFLOAT 语法:INCRBYFLOAT key increment

与INCR命令类似,只不过可以递增一个双精度浮点数

向尾部追加值:APPEND 语法:APPEND key value redis客户端并不是输出追加后的字符串,而是输出字符串总长度

获取字符串长度:STRLEN 语法:STRLEN key 如果键不存在返回0,注意如果有中文时,一个中文长度是3,redis是使用UTF-8编码中文的

获取多个键值:MGET 语法:MGET key [key ...] 例如:MGET key1 key2

设置多个键值:MSET 语法:MSET key value [key value ...] 例如:MSET key1 1 key2 "hello redis"

二进制指定位置值:GETBIT 语法:GETBIT key offset 例如:GETBIT key1 2 ,key1为hello 返回 1,返回的值只有0或1,当key不存在或超出实际长度时为0

设置二进制位置值:SETBIT 语法:SETBIT key offset value ,返回该位置的旧值

二进制是1的个数:BITCOUNT 语法:BITCOUNT key [start end] ,start 、end为开始和结束字节

位运算:BITOP 语法:BITOP operation destkey key [key ...] ,operation支持AND、OR、XOR、NOT

偏移:BITPOS 语法:BITPOS key bit [start] [end]

列表(list)

存储说明:

列表类型(list)可以存储一个有序的字符串列表,常用的操作是向列表两端添加元素或者获得列表的某一个片段,value值的列表元素只能是字符串。

数据结构:

redis3.2之后使用的是quicklist实现的列表。其中quicklist是否ziplist的双向列表。

redis查询两端的复杂度是O(1),中间查询复杂度很高。

redis专题系列1_数据结构底层设计

quicklist 的指针指向quicklistnode,其中quicklistnode就包含了ziplist,

ziplist一个经过特殊处理的双向链表。可以存储多个数据

list的函数说明:

添加左边元素:LPUSH 语法:LPUSH key value [value ...] ,返回添加后的列表元素的总个数

添加右边元素:RPUSH 语法:RPUSH key value [value ...] ,返回添加后的列表元素的总个数

移除左边第一个元素:LPOP 语法:LPOP key ,返回被移除的元素值

移除右边第一个元素:RPOP 语法:RPOP key ,返回被移除的元素值

列表元素个数:LLEN 语法:LLEN key, 不存在时返回0,redis是直接读取现成的值,并不是统计个数

获取列表片段:LRANGE 语法:LRANGE key start stop,如果start比stop靠后时返回空列表,0 -1 返回整个列表

正数时:start 开始索引值,stop结束索引值(索引从0开始)

负数时:例如 lrange num -2 -1,-2表示最右边第二个,-1表示最右边第一个

删除指定值:LREM 语法:LREM key count value,返回被删除的个数

ount>0,从左边开始删除前count个值为value的元素

count<0,从右边开始删除前|count|个值为value的元素

count=0,删除所有值为value的元素

索引元素值:LINDEX 语法:LINDEX key index ,返回索引的元素值,-1表示从最右边的第一位

设置元素值:LSET 语法:LSET key index value

保留列表片段:LTRIM 语法:LTRIM key start stop,start、top 参考lrange命令

一个列表转移另一个列表:RPOPLPUSH 语法:RPOPLPUSH source desctination ,从source列表转移到desctination列表该命令分两步看,首先source列表RPOP右移除,再desctination列表LPUSH

hash类型

存储说明:

value值是一个map结构

数据结构:

map提供两种结构来存储,一种是hashtable、另一种是前面讲的ziplist,数据量小的时候用ziplist. 在redis中,哈希表分为三层,分别是,源码地址【dict.h】

对于hashmap大家可能非常熟悉了,但是redis如何实现,桶位置确认,hash碰撞和rehash的扩容呢。分析redis底层map结构:

1. dictEntry

管理一个key-value,同时保留同一个桶中相邻元素的指针,用来维护哈希桶的内部链;

typedef struct dictEntry {void *key;union { //因为value有多种类型,所以value用了union来存储void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;//下一个节点的地址,用来处理碰撞,所有分配到同一索引的元素通过next指针链接起来形成链2. dictht

这个结构体就是对于桶大小和元素位置的存储

实现一个hash表会使用一个buckets存放dictEntry的地址,一般情况下通过hash(key)%len得到的值就是buckets的索引,这个值决定了我们要将此dictEntry节点放入buckets的哪个索引里,这个buckets实际上就是我们说的hash表。dict.h的dictht结构中table存放的就是buckets的地址

typedef struct dictht {dictEntry **table;//buckets的地址unsigned long size;//buckets的大小,总保持为 2^nunsigned long sizemask;//掩码,用来计算hash值对应的buckets索引unsigned long used;//当前dictht有多少个dictEntry节点} dictht;3. dict

这个结构体用于扩容

dictht实际上就是hash表的核心,但是只有一个dictht还不够,比如rehash、遍历hash等操作,所以redis定义了一个叫dict的结构以支持字典的各种操作,当dictht需要扩容/缩容时,用来管理dictht的迁移

typedef struct dict {dictType *type;//dictType里存放的是一堆工具函数的函数指针,void *privdata;//保存type中的某些函数需要作为参数的数据dictht ht[2];//两个dictht,ht[0]平时用,ht[1] rehash时用long rehashidx; //当前rehash到buckets的哪个索引,-1时表示非rehash状态int iterators; //安全迭代器的计数。}dict;Hash的函数说明:

设置单个:HSET 语法:HSET key field value,不存在时返回1,存在时返回0,没有更新和插入之分

设置多个:HMSET 语法:HMSET key field value [field value ...]

读取单个:HGET 语法:HGET key field,不存在是返回nil

读取多个:HMGET 语法:HMGET key field [field ...]

读取全部:HGETALL 语法:HGETALL key,返回时字段和字段值的列表

判断字段是否存在:HEXISTS 语法:HEXISTS key field,存在返回1 ,不存在返回0

字段不存在时赋值:HSETNX 语法:HSETNX key field

value,与hset命令不同,hsetnx是键不存在时设置值

增加数字:HINCRBY 语法:HINCRBY key field increment ,返回增加后的数,不是整数时会提示错误

删除字段:HDEL 语法:HDEL key field [field ...] ,返回被删除字段的个数

只获取字段名:HKEYS 语法:HKEYS key ,返回键的所有字段名

只获取字段值:HVALS 语法:HVALS key ,返回键的所有字段值

字段数量:HLEN 语法:HLEN key ,返回字段总数

集合类型(set)

存储说明:

集合类型中,每个元素都是不同的,也就是不能有重复数据,同时集合类型中的数据是无序的。集合类型和列表类型的最大的区别是有序性和唯一性集合类型的常用操作是向集合中加入或删除元素、判断某个元素是否存在。由于集合类型在redis内部是使用的值为空的散列表(hashtable),所以这些操作的时间复杂度都是O(1).

数据结构:

Set在的底层数据结构以intset或者hashtable来存储。当set中只包含整数型的元素时,采用intset来存储,否则,采用hashtable存储,但是对于set来说,该hashtable的value值用于为NULL。通过key来存储元素,hashtable取key的复杂度是O(1)的。

Set的函数说明:

添加元素:SADD 语法:SADD key member [member ...] ,向一个集合添加一个或多个元素,因为集合的唯一性,所以添加相同值时会被忽略。

返回成功添加元素的数量。

删除元素:SREM 语法:SREM key member [member ...] 删除集合中一个或多个元素,返回成功删除的个数。

获取全部元素:SMEMBERS 语法:SMEMBERS key ,返回集合全部元素

值是否存在:SISMEMBER 语法:SISMEMBER key member ,如果存在返回1,不存在返回0

差运算:SDIFF 语法:SDIFF key [key ...] ,例如:集合A和集合B,差集表示A-B,在A里有的元素B里没有,返回差集合;多个集合(A-B)-C

交运算:SINTER 语法:SINTER key [key ...],返回交集集合,每个集合都有的元素

并运算:SUNION 语法:SUNION key [key ...],返回并集集合,所有集合的元素

集合元素个数:SCARD 语法:SCARD key ,返回集合元素个数

弹出元素:SPOP 语法:SPOP key [count] ,因为集合是无序的,所以spop会随机弹出一个元素

有序集合

储存说明:

有序集合类型,顾名思义,和前面讲的集合类型的区别就是多了有序的功能在集合类型的基础上,有序集合类型为集合中的每个元素都关联了一个分数,这使得我们不仅可以完成插入、删除和判断元素是否存在等集合类型支持的操作,还能获得分数最高(或最低)的前N个元素、获得指定分数范围内的元素等与分数有关的操作。虽然集合中每个元素都是不同的,但是他们的分数却可以相同

数据结构:

zset类型的数据结构就比较复杂一点,内部是以ziplist或者skiplist+hashtable来实现,这里面最核心的一个结构就是skiplist,也就是跳跃表,跳跃表是实现有序集合的核心,跳跃表的设计思路和方法本人目前也未融会贯通,后续算法博客补上.

redis专题系列1_数据结构底层设计

zset的函数说明:

添加集合元素:ZADD 语法:ZADD key [NX|XX] [CH] [INCR] score member [score member ...],不存在添加,存在更新。

获取元素分数:ZSCORE 语法:ZSCORE key member ,返回元素成员的score 分数

元素小到大:ZRANGE 语法:ZRANGE key start top [WITHSCORES] ,参考LRANGE ,加上withscores 返回带元素,即元素,分数

当分数一样时,按元素排序

元素大到小:ZREVRANGE 语法:ZREVRANGE key start [WITHSCORES] ,与zrange区别在于zrevrange是从大到小排序

指定分数范围元素:ZRANGEBYSCORE 语法:ZRANGEBYSCORE key min max [WITHSCORE] [LIMIT offest count]返回从小到大的在min和max之间的元素,(符号表示不包含,例如:80-100,(80 100,withscore返回带分数limit offest count向左偏移offest个元素,并获取前count个元素

指定分数范围元素:ZREVRANGESCORE 语法:ZREVRANGEBYSCORE key max min [WITHSCORE] [LIMIT offest count]与zrangebyscore类似,只不过该命令是从大到小排序的。

增加分数:ZINCRBY 语法:ZINCRBY key increment member ,注意是增加分数,返回增加后的分数;如果成员不存在,则添加一个为0的成员。

更多精品博客请点击下方的了解更多:

版权声明:本文由爱知乎发布,如需转载请注明出处。

本文链接:http://www.izhihu.cn/post/410.html

分享给朋友:

“redis专题系列1_数据结构底层设计” 的相关文章

杜江的家庭背景是富二代吗?都江的女朋友是霍思燕吗

杜江的家庭背景是富二代吗?都江的女朋友是霍思燕吗

霍思燕与都江的姐夫关系曝光后,都江的家庭背景和都江的个人信息也引起了网友的关注。很多网友都问:杜江是富二代吗?杜江的家庭背景是什么?接下来,关注网站了解杜江的个人信息和家庭背景。杜江的个人资料杜江,1...

每次都是阴性,为什么还要持续做核酸?

每次都是阴性,为什么还要持续做核酸?

文/汪俐辰 近期,全国多地疫情散发,上海疫情防控形势依然严峻,不少地方都组织了大规模、高频次核酸检测。 每次结果都是阴性,为什么还要持续检测?现在继续高频次地做核酸检测,是否有必要? 用核酸检测和病...

如何快速了解nba?

如何快速了解nba?

谢邀。 第一个网址是NBA中文官方网的常见问题解答,第二个网址是NBA英文官方网的常见问题解答。 我想,这应该是一个从未看过或者关注过NBA的篮球迷最快速的了解NBA联盟的渠道,看熟了之后...

NBA和CBA差距有多大?

NBA和CBA差距有多大?

我们自己的CBA联赛在亚洲来说是水平最高的联赛,可和美国的NBA还是有很大差距的,差距表现在全方面的,球员水平,设施建设,联赛管理水平,裁判等等每个方面都照NBA有着不小的差距。 首先看球员水平;N...

在NBA有哪些不为人知的场外事?

在NBA有哪些不为人知的场外事?

庄神德拉蒙德只比大帝恩比德大一岁。 扬尼斯-阿德托昆博(字母哥)是希腊国籍。 波尔津吉斯的身高2.21米比周琦还要高。 NBA有名球员叫拜纳姆,他顶薪过,底薪过,后来他非主流了,他现在才31岁。 历史...

如何下载YouTube视频字幕

如何下载YouTube视频字幕

如何下载YouTube视频字幕,首先这个是下载YouTube视频的网址:en.savefrom.net打开网页,把YouTube视频链接地址黏贴到该网页就可下载,这里就不一一介绍了。今天主要讲如何下...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。