Redis-五种数据结构之列表（ziplist、quicklist）

2024-06-20 05:36
文章标签 数据结构 redis 五种 列表 ziplist quicklist

本文主要是介绍Redis-五种数据结构之列表（ziplist、quicklist），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

列表

文章目录

  • 列表
    • 压缩列表-ziplist
      • ziplist 定义
      • 级联更新
    • 快速列表-quicklist
      • quicklistNode 定义
      • quicklist 定义
      • quicklist常用操作
      • 其他操作
      • quicklist 相对于普通链表优点
      • quick应用场景
      • 在redis 中使用quicklist

列表数据类型可以存储一组按插入顺序排序的字符串，他很灵活，支持两端插入、弹出数据可以充当栈和队列的角色。

压缩列表-ziplist

链表和数组都可以实现列表类型，Redis 使用的是链表结构，下面是一种常见的链表实现方式：

typedef struct listNode {struct listNode *prev;  //上一个数据节点struct listNode *next;	//下一个数据节void *value;   			//数据内容
} listNode;typedef struct list {listNode *head;listNode *tail;void *(*dup)(void *ptr);void (*free)(void *ptr);int (*match)(void *ptr, void *key);unsigned long len;
} list;

Redis 内部使用该链表来保存运行数据，比如主服务器下的所有从服务器的信息。

但Redis 并不使用该链表来保存用户列表的数据，因为他对内存管理不够友好，原因如下：

  • 链表的每个节点都占用一块独立的内存，导致了内存碎片古过多。
  • 链表节点中前后节点指针占用过多的额外内存。

那数组就可以完美的解决这两个问题

ziplist就是一个类似数组的紧凑型链表，他会申请一整块的内存，在这个内存上存放所有的数据，

这就是ziplist的设计思想。

ziplist 定义

ziplist 的总体布局如下

…

  • zlbytes：ziplist的长度。 4字节
  • zltail：ziplist头部到末尾元素的长度，通过zltail字段可以很方便获取末尾元素的地址。4字节
  • zllen：元素的个数，最大可以存放65535个元素。2字节
  • zlend：结束标志，值固定为0xFF。
  • entry: ziplist 中保存的节点 1字节

节点布局

  • entry-data : 该节点元素，即节点存储的数据

  • prevlen: 记录前驱节点的长度，该属性的长度为1字节或者5字节

    • 如果前一个元素长度小于254，则该属性占用1byte
    • 否则，第一个字节固定为254，剩余4byte存放前一个元素的长度，不为255的原因是255和结尾标志重复

  • enconding:表示编码类型有以下几种：

    • 字符串编码：字符串类型有1、2、5三种编码长度，前两位表示编码类型，剩余位表示字符串长度

      00|aaaaaa：存储长度小于等于63byte的字符串。
01|aaaaaa bbbbbbbb：存储长度小于等于16383byte的字符串。
10|...... bbbbbbbb cccccccc dddddddd eeeeeeee：存储长度小于等于4294967295byte的字符串，'.'固定为0。

    • 整型编码

      1100 0000：表示16位有符号整数，entry-data占用2byte。
1101 0000：表示32位有符号整数，entry-data占用4byte。
1110 0000：表示64位有符号整数，entry-data占用8byte。
1111 0000：表示24位有符号整数，entry-data占用3byte。
1111 1110：表示8位有符号整数，entry-data占用1byte。
1111 0001 - 1111 1101：没有entry-data部分，依次表示整数0-12。

级联更新

级联更新是指因为插入、删除、更新等操作导致后续连续多个元素出现更新的现象。核心原因是ziplist的每个元素存放着上一个元素的长度。最差情况下，后面所有元素都得更新，但是这种情况很少见。

快速列表-quicklist

quicklist 的设计思想很简单，将一个ziplist 拆分成多个短的ziplist ,避免插入或者删除元素时会导致大量内存拷贝

**quicklist 其实就是简单的双链表，但每个双链表节点中保存一个 ziplist，**然后每个 ziplist 中存一批 list 中的数据 (具体 ziplist 大小可配置)，这样既可以避免大量链表指针带来的内存消耗，也可以避免 ziplist 更新导致的大量性能损耗，将大的 ziplist 化整为零。

quicklistNode 定义

typedef struct quicklistNode {struct quicklistNode *prev;struct quicklistNode *next;unsigned char *zl; 				// quicklist节点对应的ziplist -指向了一个 ziplist 结构unsigned int sz;                // ziplist的字节数 unsigned int count : 16; 		// ziplist的元素数量unsigned int encoding : 2; 		// 数据类型，2表示节点已压缩，1表示节点未压缩unsigned int container : 2;     // 目前固定为2 表示使用ziplist 存储数据unsigned int recompress : 1; 	// 1表示暂时解压，后续需要时再将其解压- 表示该节点是否需要重新压缩。unsigned int attempted_compress : 1; // 节点无法压缩；太小了 unsigned int extra : 10; 		// 预留暂未使用
} quicklistNode;

quicklist 定义

当链表很长时，中间节点的访问频率较低，这时Redis 会将中间节点进行压缩，更进一步的节省内存空间–采用LZF压缩

//压缩后的节点定义
typedef struct quicklistLZF {size_t sz; // 压缩后的ziplist大小char compressed[];//存放压缩后的ziplist字节数组
} quicklistLZF;typedef struct quicklist {quicklistNode *head; /* 头结点 */quicklistNode *tail; /* 尾结点 */unsigned long count; /* 在所有的ziplist中的entry总数 */unsigned long len; /* quicklist节点总数 */int fill : QL_FILL_BITS; /* 16位，每个节点的最大容量 */unsigned int compress : QL_COMP_BITS; /* 16位，quicklist的压缩深度，0表示所有节点都不压缩，否则就表示从两端开始有多											少个节点不压缩 */unsigned int bookmark_count: QL_BM_BITS; /*4位，bookmarks数组的大小，bookmarks是一个可选字段，用来quicklist重新													分配内存空间时使用，不使用时不占用空间*/quicklistBookmark bookmarks [];
} quicklist;

其中，fill 和 compress 是两个重要的字段，它们决定了 quicklist 的内存和性能特性。

  • fill 表示每个 quicklistNode 节点的最大容量，不同的数值有不同的含义，默认是 -2，当然也可以配置为其他数值，具体数值含义如下：
fill含义
-1每个 quicklistNode 节点的 ziplist 所占字节数不能超过 4kb。
-2每个 quicklistNode 节点的 ziplist 所占字节数不能超过 8kb。 （默认配置&建议配置）
-3每个 quicklistNode 节点的 ziplist 所占字节数不能超过 16kb。
-4每个 quicklistNode 节点的 ziplist 所占字节数不能超过 32kb。
-5每个 quicklistNode 节点的 ziplist 所占字节数不能超过 64kb。
任意正数表示：ziplist 结构所最多包含的 entry 个数，最大为 215215。
  • compress 表示 quicklist 的压缩深度，0 表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩。例如，compress 为 1 表示从两端开始，有 1 个节点不做 LZF 压缩。LZF 是种无损压缩算法。Redis 为了节省内存空间，会将 quicklist 的节点用 LZF 压缩后存储，但这里不是全部压缩，可以配置 compress 的值。

在这里插入图片描述

quicklist常用操作

  • 创建
quicklist *quicklistCreate(void); // 创建quicklist
quicklist *quicklistNew(int fill, int compress); // 用一些指定参数创建一个新的quicklist
void quicklistSetCompressDepth(quicklist *quicklist, int depth); // 设置压缩深度
  • 头插和尾插
void quicklistPushHead(quicklist *quicklist, void *value, size_t sz); // 头插
void quicklistPushTail(quicklist *quicklist, void *value, size_t sz); // 尾插
  • 头删和尾删
int quicklistPop(quicklist *quicklist, int where, unsigned char **data, size_t *sz, long long *slong); // 头删或尾删
  • 查找

​ 查找操作需要遍历整个 quicklist，对每个 ziplist 进行查找。如果找到了匹配的元素，就返回一个 quicklistEntry 结构体，表示该元素在哪个 ziplist 中，以及在 ziplist 中的位置。

typedef struct quicklistEntry {const quicklist *quicklist; //指向所属的quicklist的指针quicklistNode *node;		//指向所属的quicklistNode节点的指针unsigned char *zi;			//指向当前ziplist结构的指针unsigned char *value;		//查找到的元素如果是字符串，则存在value字段long long longval;			//查找到的元素如果是整数，则存在longval字段	size_t sz;					//保存当前元素的长度int offset;					//保存查找到的元素距离压缩列表头部/尾部隔了多少个节点
} quicklistEntry;int quicklistIndex(const quicklist *quicklist, const long long idx, quicklistEntry *entry); // 根据索引查找元素
void quicklistRewind(const quicklist *quicklist, quicklistIter **iter); // 创建一个从头开始的迭代器
void quicklistRewindTail(const quicklist *quicklist, quicklistIter **iter); // 创建一个从尾开始的迭代器
int quicklistNext(quicklistIter *iter, quicklistEntry *node); // 迭代器获取下一个元素
void quicklistReleaseIterator(quicklistIter *iter); // 释放迭代器
  • 删除

​ 删除操作需要先找到要删除的元素在哪个 ziplist 中，然后调用 ziplist 的删除函数删除该元素。如果删除后导致 ziplist 空了，就把整 个 ziplist 节点从链表中删除

void quicklistDelEntry(quicklistIter *iter, quicklistEntry *entry); // 删除迭代器指向的元素
int quicklistDelRange(quicklist *quicklist, const long start, const long stop); // 删除指定范围内的元素

其他操作

除了上面介绍的操作，quicklist 还有一些其它的操作，例如：

quicklistRotate(quicklist *quicklist); // 将尾部的元素移动到头部
quicklistDup(quicklist *orig); // 复制一个 quicklist
quicklistRelease(quicklist *quicklist); // 释放一个 quicklist
quicklistCompare(unsigned char *p1, unsigned char *p2, int p2_len); // 比较两个元素是否相等

quicklist 相对于普通链表优点

  • 节省内存空间，因为每个节点是一个压缩列表，可以存储多个元素，并且可以根据配置进行 LZF 压缩。
  • 降低更新复杂度，因为每次插入或删除元素时，只需要更新对应的压缩列表，而不需要重新分配整个链表的内存空间。
  • 提高查询效率，因为每个节点有一个计数器，可以快速定位到目标元素所在的压缩列表，而不需要遍历整个链表。

quick应用场景

quicklist 的应用场景主要是在需要使用 list 类型的数据结构时，例如：

  • 存储有序的数据，如时间线、消息队列、日志等。
  • 实现栈或队列的功能，如 LIFO 或 FIFO 的数据结构。
  • 实现发布订阅模式，如使用 BLPOP 或 BRPOP 命令阻塞地弹出元素。
  • 实现阻塞队列，如使用 LPUSH 和 RPOP 命令实现生产者消费者模式

在redis 中使用quicklist

在 Redis 中使用 quicklist 的方法很简单，只需要使用 list 类型的命令，

如 lpush, rpush, lpop, rpop 等，就可以自动创建和操作 quicklist。

Redis 会根据配置文件中的参数，如 list-max-ziplist-size, list-compress-depth 等，来决定 quicklist 的结构和压缩策略。

你不需要关心 quicklist 的内部实现细节，只需要按照 list 的语义来使用即可。

这篇关于Redis-五种数据结构之列表（ziplist、quicklist）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1077242。

相关文章

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

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

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习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 ...]
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

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++的初始化列表与const成员

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量，在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员，因为执行构造函数时，类对象已经创建完成，只有类对象创建完成才能调用成员函数，构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化，该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面，主要用于给
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（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
阅读更多...
Spring+MyBatis+jeasyui 功能树列表

Spring+MyBatis+jeasyui 功能树列表

java代码@EnablePaging@RequestMapping(value = "/queryFunctionList.html")@ResponseBodypublic Map<String, Object> queryFunctionList() {String parentId = "";List<FunctionDisplay> tables = query(parent
阅读更多...
Redis中使用布隆过滤器解决缓存穿透问题

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

一、缓存穿透(失效)问题 缓存穿透是指查询一个一定不存在的数据，由于缓存中没有命中，会去数据库中查询，而数据库中也没有该数据，并且每次查询都不会命中缓存，从而每次请求都直接打到了数据库上，这会给数据库带来巨大压力。 二、布隆过滤器原理 布隆过滤器（Bloom Filter）是一种空间效率很高的随机数据结构，它利用多个不同的哈希函数将一个元素映射到一个位数组中的多个位置，并将这些位置的值置
阅读更多...
Lua 脚本在 Redis 中执行时的原子性以及与redis的事务的区别

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

在 Redis 中，Lua 脚本具有原子性是因为 Redis 保证在执行脚本时，脚本中的所有操作都会被当作一个不可分割的整体。具体来说，Redis 使用单线程的执行模型来处理命令，因此当 Lua 脚本在 Redis 中执行时，不会有其他命令打断脚本的执行过程。脚本中的所有操作都将连续执行，直到脚本执行完成后，Redis 才会继续处理其他客户端的请求。 Lua 脚本在 Redis 中原子性的原因
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2