Redis数据结构——快速列表quicklist、快表

这篇具有很好参考价值的文章主要介绍了Redis数据结构——快速列表quicklist、快表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

定义

Redis中的数据结构,链表和压缩列表这两种数据结构是列表对象的底层实现方式。
当时考虑到链表的附加空间太大,节点的内存都是单独分配的,还会导致内存碎片化问题严重。
因此从Redis3.2开始,对列表的底层数据结构进行了改造,即使用quickList代替链表list和压缩列表ziplist

快速链表quickList实际上是ziplist和linkedlist的混合体,它将linkedlist按段切分,每一段使用ziplist来紧凑存储,多个ziplist之间使用双向指针串接起来。
Redis数据结构——快速列表quicklist、快表,redis,数据结构,数据库
每个节点的类型是quickListNode,一个quickListNode就是一个压缩列表ziplist,quickListNode的结构是这样的:

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    unsigned int sz;             //ziplist 的大小 
    unsigned int count : 16;     // 压缩列表中节点的数量 
    unsigned int encoding : 2;   // 编码格式 
   // ..... 
} quicklistNode;

quickList的常用操作

插入

当插入一个数据时,就会有两种可能:

  • 要么新建一个quickListNode,即一整个ziplist;
  • 要么直接在ziplist中进行插入

同时插入的位置也有两种可能,要么在表头或表尾,要么在中间位置。
因此Redis结合以上因素,规定的插入操作
当插入位置是表头或表尾时:

  • 当在表头或表尾插入数据时,如果数据没有超过规定的大小,那么就插入到表头或表尾节点的ziplist中。
  • 如果要插入的数据的大小超过了限制,那么就会新创建一个quickListNode,即新创建一个压缩列表,然后插入到表尾或表尾

当插入的位置是中间时,还要考虑是在这个ziplist中的那个位置插入:
当插入的位置是ziplist的头部或尾部时:

  • 当要插入的位置所在的ziplist能够继续放得下这个数据,那么就插入到这个ziplist中;
  • 当要插入的位置所在的ziplist,如果继续存放该数据,那么就会超出单个ziplist的大小限制,如果此时这个ziplist相邻的ziplist能够放得下这个数据,就放到相邻的ziplist中。
  • 如果当前的ziplist无法放得下这个数据,同时相邻的ziplist也无法放得下这个数据,那么就要新创建一个quickListNode,即一个新的ziplist。

当要插入的位置是ziplist的中间时,既不是ziplist的首尾位置:

  • 如果当前的ziplist能够放得下这个数据,则进行插入
  • 如果要当前的ziplist无法放得下这个数据,则会在指定的位置进行分裂,将此数据放下,前后溢出的数据就放在前后的ziplist中

查找

quicklist的查找操作就是遍历每个quickListNode,因为每个quickListNode有前后指针,所以可以进行查找操作。

参考文章

Redis数据结构——快速列表(quicklist) - 随心所于 - 博客园文章来源地址https://www.toymoban.com/news/detail-652020.html

到了这里,关于Redis数据结构——快速列表quicklist、快表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Redis从入门到精通【高阶篇】之底层数据结构压缩列表(ZipList)详解

    前面的Redis从入门到精通的基础篇和进阶篇都是在使用层面和概念层面,本章节,我们了解一下redis的底层数据结构,上几个章节,我们讲了SDS,字典 。本章节我们聊一下ZipList。 压缩列表(ZipList)就是redis为了节约内存而设计开发的数据结构,并且作为列表键和哈希键的底层

    2024年02月08日
    浏览(91)
  • 数据结构:快速的Redis有哪些慢操作?

    redis 为什么要这莫快?一个就是他是基于内存的,另外一个就是他是他的数据结构 说到这儿,你肯定会说:“这个我知道,不就是 String(字符串)、List(列表)、 Hash(哈希)、Set(集合)和 Sorted Set(有序集合)吗?”其实,这些只是 Redis 键 值对中值的数据类型,也就是

    2024年02月15日
    浏览(45)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(58)
  • 数据结构基础--散列表

    散列表,又叫 哈希表 (Hash Table),是能够通过给定的的值直接访问到具体对应的值的一个数据结构。也就是说,把映射到一个表中的位置来直接访问记录,以加快访问速度。 通常,把这个称为 Key,把对应的记录称为 Value,所以也可以说是通过 Key 访问

    2024年02月04日
    浏览(45)
  • 哈希表-散列表数据结构

    哈希表也叫散列表,哈希表是根据关键码值(key value)来直接访问的一种数据结构,也就是将关键码值(key value)通过一种映射关系映射到表中的一个位置来加快查找的速度,这种映射关系称之为哈希函数或者散列函数,存放记录的数组称之为哈希表。 哈希表采用的是一种转换思

    2024年01月21日
    浏览(56)
  • 数据结构—散列表的查找

    7.4散列表的查找 7.4.1散列表的基本概念 基本思想:记录的存储位置域之间存在对应关系 ​ 对应关系——hash函数 ​ Loc(i)= H(keyi) 如何查找 : 根据散列函数 H(key) = k 查找key=9,则访问H(4)= 18号地址,若内容为18则成功; 若查不到,则返回一个特殊值,如空指针或

    2024年02月12日
    浏览(45)
  • R语言数据结构-----列表

    目录 (1)创建列表  (2)列表索引 (3)增加或删除列表元素 (4)访问列表元素和值 (5)apply()函数 (6)递归型列表 列表的基本操作 函数hist()中的数据,也是通过列表保存的 (1)创建列表  (2)列表索引 (3)增加或删除列表元素 添加新的组件 使用索引添加组件 删除

    2024年02月08日
    浏览(43)
  • 数据结构——散列函数、散列表

    散列表的基本概念 散列函数的构造方法 处理冲突的方法 散列查找及性能分析 提示:以下是本篇文章正文内容,下面案例可供参考 概念:之前的算法建立在“比较”基础上,效率取决于比较次数 散列函数:将映射成该对应地址的函数,记为Hash(key)=Addr,散列函

    2024年02月07日
    浏览(42)
  • Linux内核数据结构 散列表

    在Linux内核中,散列表(哈希表)使用非常广泛。本文将对其数据结构和核心函数进行分析。和散列表相关的数据结构有两个: hlist_head 和 hlist_node 对应的结构如下 hash_table 为散列表(数组),其中的元素类型为 struct hlist_head 。以 hlist_head 为链表头的链表,其中的节点 hash 值

    2024年02月10日
    浏览(40)
  • 数据结构——带头节点的双向循环列表

    带头节点的双向循环链表 是一种特殊的双向链表,它与普通的双向链表相比,最大的区别是链表头结点的 next 指针不再指向第一个实际节点,而是指向链表中的第一个节点。同时,链表尾结点的 prev 指针也不再指向 NULL,而是指向链表中的最后一个节点。 另外, 带头节点的

    2024年02月11日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包