Redis数据结构七之listpack和quicklist

2023-11-12 00:44

本文主要是介绍Redis数据结构七之listpack和quicklist,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文首发于公众号:Hunter后端
原文链接:Redis数据结构七之listpack和quicklist

本篇笔记介绍 listpack 和 quicklist 两种结构

按照顺序,本来应该先介绍 quicklist 的结构,quicklist 在 7.0 之前的版本是由双向链表和压缩列表构成的,但是在 7.0 版本已经变成了由双向链表和 listpack 实现,所以在这里我们先介绍一下 listpack 的结构。

1、listpack

listpack 是替换 ziplist 的数据结构,所以在结构上两者是有些相似的,listpack 的结构如下:

| 总字节长度 | entry个数 | entry1 | entry2 | ... | entryN | end |

相比 ziplist,listpack 去除了到尾部节点,也就是到 entryN 的偏移量,但保留了其他属性。

对于单个 entry 元素,其结构如下:

| encoding | content | length |

encoding 表示 content 的编码,endocing 表示实际存储的内容,length 表示该 entry 的长度

避免连锁更新

使用 listpack 替代 ziplist 的一个好处是避免了连续更新的问题。

因为 ziplist 的每个元素都有一个属性用于保存前一个节点元素的长度,因此前一个节点修改后会可能需要修改后一个节点的属性,但是 listpack 没有这个关联关系,从而避免了影响后续元素的长度,也因此避免了连锁更新的问题。

获取最后一个节点

虽然 listpack 没有了指向尾部节点的偏移量,但是同样可以快速找到 listpack 的尾部节点,方式是通过 总字节长度属性的值,可以直接获取到 listpack 的尾部,然后根据 entry 元素尾部的 length 属性,就可以找到尾部 entry 的起始地址了。

2、 quicklist

在 Redis 3.2 版本,列表对象的底层实现变成了由 quicklist 实现,quicklist 实际上是压缩列表和双向链表的组合结构,因为 quicklist 就是一个链表,而链表中每一个元素就是压缩列表。

而在 Redis 7.0 版本,quicklst 变成了由双向链表和 listpack 构成的结构。

这里直接介绍 quicklist 由双向链表和 listpack 构成的结构。

quicklist 的结构和双向链表的结构类似:

typedef struct quicklist {quicklistNode *head;quicklistNode *tail;unsigned long count; unsigned long len; ...
} quicklist;

对于一个 quicklist,它也有指向 quicklist 的头节点和尾节点的指针,如结构中的 head 和 tail。

count 属性统计每个 quicklist 节点的 listpack 总数量的属性

len 则是统计 quicklist 中 quicklistNode 的数量的属性。

typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *entry;size_t sz;             unsigned int count : 16; ...
} quicklistNode;

对于一个 quicklistNode,拥有指向前置节点和后置节点的指针,还有指向其下 listpack 的 entry,以及 sz 表示该 listpack 的总字节长度,count 属性则表示该 listpack 中包含的元素个数。

这篇关于Redis数据结构七之listpack和quicklist的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/393934

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

Redis中使用布隆过滤器解决缓存穿透问题

一、缓存穿透(失效)问题 缓存穿透是指查询一个一定不存在的数据,由于缓存中没有命中,会去数据库中查询,而数据库中也没有该数据,并且每次查询都不会命中缓存,从而每次请求都直接打到了数据库上,这会给数据库带来巨大压力。 二、布隆过滤器原理 布隆过滤器(Bloom Filter)是一种空间效率很高的随机数据结构,它利用多个不同的哈希函数将一个元素映射到一个位数组中的多个位置,并将这些位置的值置

Lua 脚本在 Redis 中执行时的原子性以及与redis的事务的区别

在 Redis 中,Lua 脚本具有原子性是因为 Redis 保证在执行脚本时,脚本中的所有操作都会被当作一个不可分割的整体。具体来说,Redis 使用单线程的执行模型来处理命令,因此当 Lua 脚本在 Redis 中执行时,不会有其他命令打断脚本的执行过程。脚本中的所有操作都将连续执行,直到脚本执行完成后,Redis 才会继续处理其他客户端的请求。 Lua 脚本在 Redis 中原子性的原因

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

laravel框架实现redis分布式集群原理

在app/config/database.php中配置如下: 'redis' => array('cluster' => true,'default' => array('host' => '172.21.107.247','port' => 6379,),'redis1' => array('host' => '172.21.107.248','port' => 6379,),) 其中cl

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Redis的rehash机制

在Redis中,键值对(Key-Value Pair)存储方式是由字典(Dict)保存的,而字典底层是通过哈希表来实现的。通过哈希表中的节点保存字典中的键值对。我们知道当HashMap中由于Hash冲突(负载因子)超过某个阈值时,出于链表性能的考虑,会进行Resize的操作。Redis也一样。 在redis的具体实现中,使用了一种叫做渐进式哈希(rehashing)的机制来提高字典的缩放效率,避