redis数据结构之压缩列表
目录
压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，redis就会使用压缩列表来做列表键的底层实现
当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。
压缩列表是Redis为了节约内存而开发的是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值
ziplist 数据结构：压缩列表各个组成部分
压缩列表各个组成部分详细说明：
压缩列表节点的构成：
每个压缩列表节点可以保存一个字节数组或者一个整数值，其中字节数组可以是以下三种长度的其中一种
长度小于等于63字节的字节数组
长度小于等于16383字节的字节数组
长度小于等于4294967295字节的字节数组
数值则可以是以下六种长度的其中一种：
- 1: 4位长介于0至12之间的无符号整数
- 2：1字节长的有符号整数
- 3: 3字节长的有符号整数
- 4：int16类型整数
- 5：int32类型整数
- 6 : int64类型整数
压缩列表的数据结构：
压缩列表是redis为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点保存一个字节数组或者一个整数值。
创建一个空的ziplist：
/*
* 新创建一个空 ziplist
*
* 复杂度：O(1)
*
* 返回值：新创建的 ziplist
*/
unsigned char *ziplistNew(void) {
// 分配 2 个 32 bit，一个 16 bit，以及一个 8 bit
// 分别用于 <zlbytes><zltail><zllen> 和 <zlend>
unsigned int bytes = ZIPLIST_HEADER_SIZE+1;
unsigned char *zl = zmalloc(bytes);
// 设置长度
ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
// 设置表尾偏移量
ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
// 设置列表项数量
ZIPLIST_LENGTH(zl) = 0;
// 设置表尾标识
zl[bytes-1] = ZIP_END;
return zl;
}
压缩列表包含任意多个压缩列表节点，每个节点可以保存一个字节数组或者一个整数值。
压缩列表组成部分：
zlbytes：记录整个压缩列表占用的内存字节数zltail：记录压缩列表表尾节点距离压缩列表的起始地址的字节数entryX：列表节点zlend：用于标记压缩列表的末端
压缩列表节点的构成：
preivous_entry_length：记录压缩列表中前一个节点的长度encoding：记录节点content属性保存数据的类型以及长度content：负责保存节点的值，值的类型和长度由节点的encoding属性决定。
当我们知道一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的preivous_entry_length属性，我们可以一直向前一个节点回溯，最终到达压缩列表的表头节点。
连锁更新：
每个节点的preivous_entry_length属性记录前一个节点的长度
如果前一个节点长度小于254字节，preivous_entry_length属性需要用1字节长的空间来保存这个长度值
如果前一个节点长度大于等于254字节，preivous_entry_length属性需要用5字节长的空间来保存这个长度值
如果前一个节点长度变大，这个节点的preivous_entry_length就要扩展，这个节点的扩展引起下一个节点的扩展，这就是连锁更新
redis将这种在特殊情况下产生的连续多次空间扩展操作称之为连锁更新
在添加新节点和删除节点都可能引发连锁更新。
连锁更新最坏情况下需要对压缩列表进行N次空间重分配操作，每次空间重分配的最坏复杂度为O(N)，所以连锁更新的最坏复杂度为O(N的平方)，平均复杂度为O(N)
总结：
压缩列表是为了节约内存而开发的顺序型数据结构，它是列表键和哈希键的底层实现之一，压缩列表可以包含多个节点，每个节点可以保存一个字节数组或整数值，添加新节点或删除节点可能引发连锁更新操作，这种操作出现几率不高。
到此这篇关于redis数据结构之压缩列表 的文章就介绍到这了,更多相关redis压缩列表 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
压缩列表牺牲速度来节省内存，Redis是膨胀了吗
正常情况下我们选择使用 Redis 就是为了提升查询速度,然而让人意外的是,Redis 当中却有一种比较有意思的数据结构,这种数据结构通过牺牲部分读写速度来达到节省内存的目的,这就是 ziplist(压缩列表),Redis 为什么要这么做呢?难道真的是觉得自己的速度太快了,牺牲一点速度也不影响吗? 什么是压缩列表 ziplist 是为了节省内存而设计出来的一种数据结构.ziplist 是由一系列特殊编码组成的连续内存块的顺序型数据结构,一个 ziplist 可以包含任意多个 entry,而每一个
-
详解redis数据结构之压缩列表
详解redis数据结构之压缩列表 redis使用压缩列表作为列表键和哈希键的底层实现之一.当一个列表键只包含少量的列表项,并且每个列表项都是由小整数值或者是短字符串组成,那么redis就会使用压缩列表存储列表项:同理,当一个哈希表包含的键值对都是由小整数值或者是短字符串组成,并且存储的键值对数目不多时,redis也会使用压缩列表来存储哈希表.以下是压缩列表存储结构: zlbytes长度为4个字节,记录了整个压缩列表所占用的字节数 zltail长度为4个字节,记录了压缩列表起始位置到压缩列表尾节
-
redis数据结构之压缩列表
目录 压缩列表是列表键和哈希键的底层实现之一.当一个列表键只包含少量列表项,并且每个列表项要么就是小整数,要么就是长度比较短的字符串,redis就会使用压缩列表来做列表键的底层实现 当一个哈希键只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希键的底层实现. 压缩列表是Redis为了节约内存而开发的是由一系列特殊编码的连续内存块组成的顺序型数据结构,一个压缩列表可以包含任意多个节点,每个节点可以保存一个字节数组或者一个整数
-
Redis ziplist 压缩列表的源码解析
目录 前言 源码解读 ziplist 布局 entry 节点 prelen encoding 编码 总结 前言 相信对使用过 Redis 的人来说,数据类型 List 是不会陌生的吧.大多数人需要实现一个队列时候,首选的就是 List 了.但是其实 Redis 的 List 类型有多种实现方式.这篇文章就是介绍其中一种实现 ziplist - 压缩列表. 源码解读 一如既往,关于 ziplist 的定义和实现还是放在一对文件中,分别是 ziplist.h 和 ziplist.c.在 ziplis
-
通俗易懂的Redis数据结构基础教程(入门)
Redis有5个基本数据结构,string.list.hash.set和zset.它们是日常开发中使用频率非常高应用最为广泛的数据结构,把这5个数据结构都吃透了,你就掌握了Redis应用知识的一半了. string 首先我们从string谈起.string表示的是一个可变的字节数组,我们初始化字符串的内容.可以拿到字符串的长度,可以获取string的子串,可以覆盖string的子串内容,可以追加子串. Redis的字符串是动态字符串,是可以修改的字符串,内部结构实现上类似于Java的ArrayL
-
Redis数据结构SortedSet的底层原理解析
目录 概述 一些常用命令 实现 跳跃表 跳表的插入 压缩列表 概述 一些常用命令 存储:zadd key score value 获取:zrange key start end 获取:同时获取分数:zrange key start end with score 删除:zrem key value 存储的时候我们可以发现,是有一个score(分数)的,这个就是用来排序的字段. 实现 先说结论,SortedSet底层,根据配置会在不同的时候选用两种不同的数据结构zset,或ziplist进行存储:
-
详解redis数据结构之sds
详解redis数据结构之sds 字符串在redis中使用非常广泛,在redis中,所有的数据都保存在字典(Map)中,而字典的键就是字符串类型,并且对于很大一部分字典值数据也是又字符串组成的.以下是sds的具体存储结构: 从图中可以看出,sds的属性有三个:len.free和buf数组.这里len字段是用来保存sds字符串中所包含字符数目的,free字段则是用来保存buf数组中空余的部分的长度的,而buf数组则是实际用来保存字符串的.比如如下结构保存了"Hello World!"这个字
-
Java数据结构之散列表(动力节点Java学院整理)
基本概念 散列表(Hash table,也叫哈希表),是根据关键字(key value)而直接进行访问的数据结构. 说的具体点就是它通过吧key值映射到表中的一个位置来访问记录,从而加快查找的速度. 实现key值映射的函数就叫做散列函数 存放记录的数组就就叫做散列表 实现散列表的过程通常就称为散列(hashing),也就是常说的hash 散列 这里的散列的概念不仅限于数据结构了,在计算机科学领域中,散列-哈希是一种对信息的处理方法,通过某种特定的函数/算法(散列函数/hash()方法)将要检索的
-
详解Redis数据结构之跳跃表
1.简介 我们先不谈Redis,来看一下跳表. 1.1.业务场景 场景来自小灰的算法之旅,我们需要做一个拍卖行系统,用来查阅和出售游戏中的道具,类似于魔兽世界中的拍卖行那样,还有以下需求: 拍卖行拍卖的商品需要支持四种排序方式,分别是:按价格.按等级.按剩余时间.按出售者ID排序,排序查询要尽可能地快.还要支持输入道具名称的精确查询和不输入名称的全量查询. 这样的业务场景所需要的数据结构该如何设计呢?拍卖行商品列表是线性的,最容易表达线性结构的是数组和链表.假如用有序数组,虽然查找的时候可以使用
-
redis数据结构之intset的实例详解
redis数据结构之intset的实例详解 在redis中,intset主要用于保存整数值,由于其底层是使用数组来保存数据的,因而当对集合进行数据添加时需要对集合进行扩容和迁移操作,因而也只有在数据量不大时redis才使用该数据结构来保存整数集合.其具体的底层数据结构如下: typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 uint32_t length; // 保存元素的数组 int8_t contents[]; }