Redis基本数据类型底层数据结构
Redis数据类型底层数据结构
Redis目前基本的数据类型有String、List、Set、ZSet、Hash五种,首先Redis是C语言开发的,所以底层就是用C语言封装数据结构或者C语言本身提供的数据结构来存储。redis内部的主要数据结构主要有简单字符串(SDS)、双端链表、字典、压缩列表、跳跃表、整数集合。Redis内部并没有直接使用这些数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这个对象系统包含了我们所熟知的五种基本类型数据,也就是字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象。而它们每一种对象都使用到了至少一种前面所介绍的数据结构。下面介绍一下redis内部的主要几个数据结构简单字符串(SDS)、双端链表、压缩列表、跳跃表的定义。然后再介绍一下redis基本的五种数据类型,也就是五种类型的对象用到了上面的哪些数据结构。
redis的数据结构
SDS(Simple Dynamic String)简单字符串
1、redis定义:
文章图片
2、使用范围:在redis里面,C本身的字符串只会作为字符串字面量(String literal)只用在一些不必对字符串值修改的地方,比如打印日志。
而redis需要使用字符串存储并且会修改的地方,都使用了SDS来存储。例如Key值。
3、优点:使用SDS来存储字符串的优点:
- SDS的len属性直接记录了长度,获取字符串长度的复杂度为O(1)。
- C字符串本身不记录长度容易产生缓存区溢出,而SDS杜绝了缓冲区的溢出。
- C字符串本身不记录长度,每次修改都要重新分配内存,SDS减少了重新分配内存次数。
- 优化了字符串缩短操作。并且可以保存任意格式的二进制数据,而C字符串必须含有编码。
2、redis定义:
- 节点listNode
文章图片
- 链表list
文章图片
跳跃表(zskiplist) 1、跳跃表:是一种有序得数据结构,通过在每个节点上维持多个指向其他节点的指针,从而达到快速访问的目的,可以理解为改进版的双端链表,改进的手段是通过空间换取了时间。
2、复杂度:跳跃表支持平均O(logN)、最坏O(N)的查找复杂度,大部分条件下,跳跃表的效率可以和平衡树媲美,并且实现比平衡树简单。
- 跳跃表节点zskiplistNode
文章图片
- 跳跃表zskiplist
文章图片
文章图片
仔细观察上图跳跃表的结构后,发现如果节点的层数越高,那么这个节点访问其他节点的速度就越快。换言之,level越高,代表了这个跳跃表的查找效率可能会比较高。当然并不是绝对的,因为redis每次创建跳跃表节点时,程序是根据幂次定律(越大的数出现概率越小), 生成层数高度。同时,节点的顺序是根据每个节点的分值排序的,如果分值相同,那么根据对象的大小排序。
压缩列表(ziplist) 1、压缩列表:是redis为了节省内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表的可以包含多个节点,每个节点可以保存一个字节数组或者一个整数值。
2、压缩列表结构图:
文章图片
3、压缩列表特点:
- 是一种为节省内存开发的顺序性数据结构
- 可以包含多个节点,每个节点保存一个字节数组或者整数值
- 添加新节点到压缩列表,或者从压缩列表删除节点,可能会引发连锁更新操作,但是机率不高
redisObject对象
1、对象:redis的键值对都是一个redisObject结构,该结构中有三个属性,type类型属性、encoding编码属性、ptr指向底层数据结构属性。
- redisObject对象定义
文章图片
文章图片
- 数据库的key值都是一个string字符串对象
文章图片
String类型 字符串对象的编码是int、raw、embstr。参考上面的编码常量表,也就是说字符串类型的数据底层的数据结构使用的是整数、SDS、embstr编码的SDS。
1、编码转换
即上述几种编码会在何时转换,也就是redis底层决定用什么存储字符串数据?。
当int类型的编码通过操作存储的是字符串值,那么字符串对象的编码将从int变为raw。
List类型 列表对象的编码可以是zipList压缩列表和linkedlist双端链表。
1、编码转换
即上述两种编码会在何时转换,也就是redis底层什么时候会用压缩列表存储列表数据?什么时候会使用双端链表存储列表数据。
当列表同时满足以下两个条件时,列表对象会使用zipList编码,也就是压缩列表
- 列表对象保存的所有字符串元素的长度都小于64字节
- 列表保存的元素少于512个,
上述两个条件是支持配置的,也就是说我们可以redis直接读取我们的配置,来决定列表list类型底层使用什么样的数据结构来存储数据
- list-max-ziplist-value
- list-max-ziplist-entries
1、编码转换
当集合对象同时满足下面两个条件,会使用intset编码
- 集合对象保存的所有对象都是整数值
- 集合对象保存的元素数量小于512个;
上述第二个条件是支持配置的。
- set-max-intset-entries
注意:上面介绍skiplist的时候我们可以从结构图中明显看到存储集合元素的时候,score在每个节点中式如何存储的。那么如果ZSet使用的式ziplist压缩列表,redis怎么存储score和value值呢?其实很简单,每个集合的元素都使用两个节点来存储,第一个节点保存的是成员(member),第二个元素保存的是元素的分值(score)
1、编码转换
当有序集合对象可以同时满足以下两个条件时,使用ziplist编码
- 有序集合的所有元素长度都小于64字节
- 有序集合的元素数量小于128个;
上述两个条件是支持配置的。
- zset-max-ziplist-value
- zset-max-ziplist-entries
1、编码转换
当哈希对象同时满足下面两个条件,使用ziplist压缩列表
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对的数量小于512个;
上述两个条件是支持配置的。
- hash-max-ziplist-value
- hash-max-ziplist-entries
推荐阅读
- Docker应用:容器间通信与Mariadb数据库主从复制
- 做一件事情的基本原理是什么()
- dubbo基本认识
- 使用协程爬取网页,计算网页数据大小
- Java|Java基础——数组
- Python数据分析(一)(Matplotlib使用)
- Jsr303做前端数据校验
- Spark|Spark 数据倾斜及其解决方案
- 数据库设计与优化
- 爬虫数据处理HTML转义字符