首页 > 数据库 >Redis数据结构ZipList详解、ZipList的连锁更新问题

Redis数据结构ZipList详解、ZipList的连锁更新问题

时间:2024-08-15 22:55:51浏览次数:14  
标签:字节 bytes ZipList Redis 列表 长度 数据结构 节点

ZipList

ZipList 是一种特殊的“双端链表” ,由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

属性类型长度用途
zlbytesuint32_t4 字节记录整个压缩列表占用的内存字节数
zltailuint32_t4 字节记录压缩列表表尾节点距离压缩列表的起始地址有多少字节,通过这个偏移量,可以确定表尾节点的地址。
zllenuint16_t2 字节记录了压缩列表包含的节点数量。 最大值为UINT16_MAX (65534),如果超过这个值,此处会记录为65535,但节点的真实数量需要遍历整个压缩列表才能计算得出。
entry列表节点不定压缩列表包含的各个节点,节点的长度由节点保存的内容决定。
zlenduint8_t1 字节特殊值 0xFF (十进制 255 ),用于标记压缩列表的末端。

ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针,因为记录两个指针要占用16个字节,浪费内存。而是采用了下面的结构:

  • previous_entry_length:前一节点的长度,占1个或5个字节。

    • 如果前一节点的长度小于254字节,则采用1个字节来保存这个长度值

    • 如果前一节点的长度大于254字节,则采用5个字节来保存这个长度值,第一个字节为0xfe,后四个字节才是真实长度数据

  • encoding:编码属性,记录content的数据类型(字符串还是整数)以及长度,占用1个、2个或5个字节

  • contents:负责保存节点的数据,可以是字符串或整数

ZipList中所有存储长度的数值均采用小端字节序,即低位字节在前,高位字节在后。例如:数值0x1234,采用小端字节序后实际存储值为:0x3412

Encoding编码

ZipListEntry中的encoding编码分为字符串和整数两种: 字符串:如果encoding是以“00”、“01”或者“10”开头,则证明content是字符串

编码编码长度字符串大小
|00pppppp|1 bytes<= 63 bytes
|01pppppp|qqqqqqqq|2 bytes<= 16383 bytes
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt|5 bytes<= 4294967295 bytes

例如,我们要保存字符串:“ab”和 “bc”

ZipListEntry中的encoding编码分为字符串和整数两种:

  • 整数:如果encoding是以“11”开始,则证明content是整数,且encoding固定只占用1个字节

编码编码长度整数类型
110000001int16_t(2 bytes)
110100001int32_t(4 bytes)
111000001int64_t(8 bytes)
11110000124位有符整数(3 bytes)
1111111018位有符整数(1 bytes)
1111xxxx1直接在xxxx位置保存数值,范围从0001~1101,减1后结果为实际值

ZipList的连锁更新问题

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小,长度是1个或5个字节: 如果前一节点的长度小于254字节,则采用1个字节来保存这个长度值 如果前一节点的长度大于等于254字节,则采用5个字节来保存这个长度值,第一个字节为0xfe,后四个字节才是真实长度数据 现在,假设我们有N个连续的、长度为250~253字节之间的entry,因此entry的previous_entry_length属性用1个字节即可表示,如图所示:

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新(Cascade Update)。新增、删除都可能导致连锁更新的发生。

总结:

ZipList特性:

  • 压缩列表的可以看做一种连续内存空间的"双向链表"

  • 列表的节点之间不是通过指针连接,而是记录上一节点和本节点长度来寻址,内存占用较低

  • 如果列表数据过多,导致链表过长,可能影响查询性能

  • 增或删较大数据时有可能发生连续更新问题

标签:字节,bytes,ZipList,Redis,列表,长度,数据结构,节点
From: https://blog.csdn.net/m0_73864806/article/details/141233111

相关文章

  • Redis数据结构:动态字符串SDS、Intset、Dict详解
    动态字符串:我们都知道Redis中保存的Key是字符串,value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。不过Redis没有直接使用C语言中的字符串,因为C语言字符串存在很多问题:获取字符串长度的需要通过运算非二进制安全不可修改Redis构建了一种新的......
  • redis哨兵,集群和运维
    RedisSentinel(哨兵)7.1哨兵介绍Sentinel介绍redis的主从模式下,主节点一旦发生故障不能提供服务,需要人工干预,将从节点晋升为主节点同时还需要修改客户端配置。对于很多应用场景这种方式无法接受。Sentinel(哨兵)架构解决了redis主从人工干预的问题。redissentinel是redis的高......
  • 基于Spring AOP与Redisson的令牌桶限流注解实践
    1.什么是限流举个例子......
  • 数据结构(一)
    目录1. 链表(LinkedList)链表的基本类型链表的基本操作链表的C语言实现示例(单向链表)链表的时间复杂度链表的空间复杂度2.栈(Stack)栈的基本操作栈的实现栈的应用场景示例:中缀表达式转后缀表达式(逆波兰表达式)3.队列队列应用场景1. 链表(LinkedList)链表是一......
  • Redis集群之Redis分片集群
    前序:Redis集群搭建直接一步到位:支持海量数据以及高并发写分片集群顾名思义,将数据分开存储到Redis集群中,这样能够存储更多的数据,避免浪费资源,基础搭建如:三主三从(一拖一)、三主六从(一拖二),本次搭建采用一拖一,一拖二情况可根据文末图文介绍进行添加从节点即可cluster不能选择db,只......
  • 数据结构
    数据结构莫队intn,m;/*====================*/intS;structQuery{ intl,r,idx; Query(int_l=0,int_r=0,int_idx=0) { l=_l,r=_r,idx=_idx; } friendbooloperator<(constQuery&a,constQuery&b) { return(a.l/S==b.l......
  • redis面试(十七)MultiLock加锁和释放锁
    MultiLockMultiLock,英语直译为多个锁。redisson分布式锁中的MultiLock这个机制,可以将多个锁合并为一个大锁,对一个大锁进行统一的申请加锁以及释放锁一次性锁定多个资源,再去处理一些事情,然后事后一次性释放所有的资源对应的锁RLocklock1=redisson.getLock("anyLock1")......
  • 【数据结构】TreeMap和TreeSet
    目录前言TreeMap实现的接口内部类常用方法TreeSet实现的接口常用方法前言Map和set是一种专门用来进行搜索的容器或者数据结构,其搜索的效率与其具体的实例化子类有关。一般把搜索的数据称为关键字(Key),和关键字对应的称为值(Value),将其称之为Key-value的键值对。......
  • 地理位置存储方案——Redis GEO
    地理位置存储方案——RedisGEO场景引入操作geoaddgeoradius总结场景假设我们需要开发一个代驾程序,司机端的小程序实时把自己的GPS定位上传,然后定位信息缓存到Redis里面。咱们怎么能利用Redis计算出,上车点方圆几公里的司机都有谁呢?这就需要使用Redis的Geo功能。R......
  • Redis Desktop Manager(Redis可视化工具)安装及使用详细教程
    一、安装包下载直接从官网下载,官网下载链接地址:Downloads-Redis二、安装步骤2.1说明RedisDesktopManager是一款简单快速、跨平台的Redis桌面管理工具,也也被称作Redis可视化工具。支持命令控制台操作,以及常用,查询key、rename、delete等操作。2.2安装步骤2.2.1双击运......