Redis常用数据类型使用的数据结构

本文参考资源:

Redis数据结构——压缩列表 - 老於` - 博客园

极客时间《数据结构与算法之美》

总体来说,Redis的key-value数据存储是通过哈希表实现的,那么具体到某一数据类型,又是使用了什么数据结构呢?这里我们着重看Redis中的五大数据类型:String、Hash、List、Set、Sorted_set。其中String类型非常简单,就是字符串。

List

我们先来看列表。列表这种数据类型支持存储一组数据。这种数据类型对应两种实现方法,一种是压缩列表(ziplist),另一种是双向循环链表。

压缩列表(ZipList)

当列表中存储的数据量比较小的时候,列表就可以采用压缩列表的方式实现。具体需要同时满足下面两个条件:

  • 列表中保存的单个数据(有可能是字符串类型的)小于 64 字节。
  • 列表中数据个数少于 512 个。

它不是基础数据结构,而是 Redis 自己设计的一种数据存储结构。它有点儿类似数组,通过一片连续的内存空间,来存储数据。不过,它跟数组不同的一点是,它允许存储的数据大小不同(可以混合存储不同类型,不同大小的数据)。

听到“压缩”两个字,直观的反应就是节省内存。之所以说这种存储结构节省内存,是相较于数组的存储思路而言的。我们知道,数组要求每个元素的大小相同,如果我们要存储不同长度的字符串,那我们就需要用最大长度的字符串大小作为元素的大小(假设是20个字节)。存储小于 20 个字节长度的字符串的时候,便会浪费部分存储空间。

Redis常用数据类型使用的数据结构

数组的优势是占用一片连续的空间可以很好的利用CPU缓存访问数据。如果我们想要保留这种优势,又想节省存储空间我们可以对数组进行压缩。

Redis常用数据类型使用的数据结构

但是这样有一个问题,我们在遍历它的时候由于不知道每个元素的大小是多少,因此也就无法计算出下一个节点的具体位置。这个时候我们可以给每个节点增加一个length的属性。

Redis常用数据类型使用的数据结构

这种设计思想并不少见,java的class文件字节码中涉及到字段表、方法表、属性表,都会先给一个数据项数,然后紧跟的是数据项的列表,每一个数据项开头都会记录数据项的长度。这部分相关内容见Java字节码实例探究

Redis中的压缩列表,构成如下图:

Redis常用数据类型使用的数据结构

一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。除了存储节点外,头部还存储了额外的信息:

  • zlbytes:列表总长度
  • zltail:最后一个节点地址据列表起始地址的偏移量
  • zllen:节点个数

尾部附加了一个zlend作为结束的标识。

压缩列表相较于数组,虽然节省了空间,但失去了数组的随机访问性,由于每个数据项的大小都可能不同,不能通过计算偏移量来获取某一中间元素的地址,只能顺序访问,这一点就跟链表一样,比链表好的是物理上的存储还是连续的,不必多次寻址。所以数据项较多时压缩列表就不适用了,进而使用双向循环链表。

双向循环链表

当不满足压缩列表的使用条件时,就使用双向循环链表,这部分较简单。

Redis常用数据类型使用的数据结构

Hash

Hash类型又称字典类型,也有两种实现方式。一种是我们刚刚讲到的压缩列表,另一种是散列表。

同样,只有当存储的数据量比较小的情况下,Redis 才使用压缩列表来实现字典类型。具体需要满足两个条件:

  • 字典中保存的键和值的大小都要小于 64 字节;
  • 字典中键值对的个数要小于 512 个。

当不能同时满足上面两个条件的时候,Redis 就使用散列表来实现字典类型。Redis 使用MurmurHash2 这种运行速度快、随机性好的哈希算法作为哈希函数。对于哈希冲突问题,Redis 使用链表法(拉链法)来解决。除此之外,Redis 还支持散列表的动态扩容、缩容。

当数据动态增加之后,散列表的装载因子会不停地变大。为了避免散列表性能的下降,当装载因子大于 1 的时候(对于使用拉链法解决哈希冲突的哈希表装载因子是有可能大于1的),Redis 会触发扩容,将散列表扩大为原来大小的 2 倍左右。

当数据动态减少之后,为了节省内存,当装载因子小于 0.1 的时候,Redis 就会触发缩容,缩小为字典中数据个数的大约 2 倍大小。

由于扩容缩容要做大量的数据搬移和哈希值的重新计算,比较耗时。针对这个问题,Redis 使用了渐进式扩容缩容策略,将数据的搬移分批进行,避免了大量数据一次性搬移导致的服务停顿。

Set

集合这种数据类型用来存储一组不重复的数据。这种数据类型也有两种实现方法,一种是基于有序数组,另一种是基于散列表。

当要存储的数据,同时满足下面这样两个条件的时候,Redis 就采用有序数组,来实现集合这种数据类型。

  • 存储的数据都是整数。
  • 存储的数据元素个数不超过 512 个。

当不能同时满足这两个条件的时候,Redis 就使用散列表来存储集合中的数据。

Sorted_set

Sorted_set又称有序集合,它用来存储一组数据,并且每个数据会附带一个得分(权重)。根据得分实现对个数据进行排序。

它的底层通过跳表实现,相关内容参考跳表-披着链表外衣的伪搜索树。通过得分的大小,我们将数据组织成跳表这样的数据结构,以支持快速地按照得分值、得分区间获取数据。

实际上,跟 Redis 的其他数据类型一样,有序集合也并不仅仅只有跳表这一种实现方式。当数据量比较小的时候,Redis 会用压缩列表来实现有序集合。具体点说就是,使用压缩列表来实现有序集合的前提,有这样两个:

  • 所有数据的大小都要小于 64 字节。
  • 元素个数要小于 128 个。

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/redis%e5%b8%b8%e7%94%a8%e6%95%b0%e6%8d%ae%e7%b1%bb%e5%9e%8b%e4%bd%bf%e7%94%a8%e7%9a%84%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月6日 13:23
下一篇 2020年4月6日 22:23

相关推荐

  • Redis主从复制、哨兵、集群详解

    【补充】高可用:(总时间-宕机时间)/总时间,目标是99.999% 主从复制 为了避免单点Redis服务器故障,准备多台服务器,互相连通。将数据复制多个副本保存在不同的服务器上,连…

    2020年3月3日
    0600
  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0120
  • leetcode707-设计链表

    原题 设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用…

    算法 2019年12月14日
    0290
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    060
  • 使用Redis实现一个延时队列

    其实今天是我生日来着,本来想着放个假今天博客只更一篇,不过想到计划不能轻易被打破,大晚上地还是起来补了这一篇。←_← 这个内容是在《Redis深度历险:核心原理与应用实践》这本书里…

  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0130
  • leetcode622-设计循环队列

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是…

    算法 2019年11月24日
    0130
  • leetcode232-用栈实现队列

    原题 使用栈实现队列的下列操作: push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – …

    算法 2019年12月13日
    0560
  • Redis通用指令和Jedis使用

    key通用指令 常用操作 del key 删除指定key exists key 获取key是否存在 type key 获取key的类型 key 时效性控制 expire key s…

  • 跳表-披着链表外衣的伪搜索树

    本文参考资源: 【数据结构与算法】之跳表(Java实现)---第九篇Java震哥聊校招-CSDN博客 跳表的原理及实例 - Rogn - 博客园 跳表Java实现Java偏离的定弦…

    2020年3月28日
    0670

发表回复

登录后才能评论