redis链表实现

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: redis的链表实现3.0以前:linkedlist(链表)和ziplist(压缩)3.2+:quicklist(快速列表)

一、3.0以前的列表实现

链表是由许多内存碎片组成,而压缩列表是为了节约内存而开发的,由一系列特殊编码的连续内存块组成的顺序型数据结构,这个和各种语言的数组类似。当redis的列表包含了比较多的元素时,或者包含的元素都是比较长的字符串时,会使用链表来存储数据结构;而当包含了少量的列表项,并且每个元素要么是小整数值,要么是长度比较短的字符串时,会使用压缩列表来作为列表键的底层实现。


linkedlist(链表

1、链表的实现

每个链表节点使用一个adlist.h/listNode结构来表示:

typedefstructlistNode {
// 前置节点指针structlistNode*prev;
//后置节点指针structlistNode*next;
//节点的值的指针void*value;
} listNode;

image.png

多个listNode可以通过pre(前置)和next(后置)组成双端链表;

虽然仅仅使用多个listNode结构可以组成链表,但使用adlist.h/list来持有链表的话,操作起来会更方便:

typedefstructlist {
//头部节点指针listNode*head;
//尾部节点指针listNode*tail;
//节点值复制void*(*dup)(void*ptr);
//节点值释放void (*free)(void*ptr);
//节点值对比int (*match)(void*ptr, void*key);
//链表所包含的节点数量unsignedlonglen;
} list;

list结构为链表提供了表头指针head、表尾指针tail以及链表长度计数器len,而dup、free、match则是用于实现多态链表所需的类型特定函数。

image.png


2、链表的特性:

  • 双端:带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)
  • 无环:prev指针和next指针都指向NULL
  • 带表头指针和表尾指针:通过list结构的head和tail指针,程序获取链表的表头节点和表尾节点的复杂度为O(1)
  • 带链表长度计数器:获取链表中节点数量的复杂度为O(1)
  • 多态:链表节点使用void*指针保存节点值,通过dup、free、match为节点值设置类型特定函数,所以链表可以保存各种不同类型的值


ziplist(压缩列表)

1、压缩列表的构成

image.png

2、压缩列表节点的构成

image.png

2.1 previous_entry_length

image.png

image.png

2.2 encoding

节点的encoding记录了节点的content属性所保存数据的类型以及长度:

image.png

2.3 content

image.png

3、连锁更新

image.png

image.png


二、3.2以后的列表实现

1、quicklist的数据结构

typedefstructquicklist {
//quicklist的链表头quicklistNode*head;
//quicklist的链表尾quicklistNode*tail; 
//所有压缩列表中的总元素个数unsignedlongcount;
//链表节点的个数 quicklistNodeunsignedlonglen;       
    ...
} quicklist;

2、quicklistNode的结构

typedefstructquicklistNode {
//指向前节点的指针structquicklistNode*prev;     //前一个quicklistNode//指向后节点的指针structquicklistNode*next;     //后一个quicklistNode//quicklistNode指向的压缩列表unsignedchar*zl;  
//压缩列表的的字节大小unsignedintsz;    
//压缩列表的元素个数unsignedintcount : 16;        //ziplist中的元素个数     ....
} quicklistNode;

可以看到 node节点有指向前节点和后节点的指针,以及节点的元素保存的不是单纯的元素值,而是保存了一个压缩链表,所以有个指向压缩链表的指针*zl

image.png

在向quicklist添加一个元素的时候,不会像普通的链表那样,直接新建一个链表节点。而是会检查插入位置的压缩链表是否能容纳该元素,如果能够容纳,那么就直接保存到quicklistNode结构里面的压缩列表,如果不能容纳,才会新建一个Node结构。

quicklist会控制quicklistNode结构里面的压缩列表的大小或者元素个数,用来规避潜在的连锁更新的风险,但是并没有完全解除。


相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
5月前
|
存储 NoSQL Redis
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
|
6月前
|
存储 机器学习/深度学习 NoSQL
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)(二)
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)
79 0
|
6月前
|
存储 缓存 NoSQL
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)(一)
作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(链表)
61 0
|
6月前
|
存储 NoSQL Go
Redis 双端链表
Redis 双端链表
46 0
|
缓存 NoSQL API
【Redis基础知识 六】Redis底层数据编码之链表
【Redis基础知识 六】Redis底层数据编码之链表
60 0
【Redis基础知识 六】Redis底层数据编码之链表
|
机器学习/深度学习 NoSQL API
Redis的设计与实现(2)-链表
链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现.
88 0
|
存储 NoSQL Java
Redis-05Redis数据结构--链表( linked-list)
Redis-05Redis数据结构--链表( linked-list)
74 0
|
存储 NoSQL Redis
Redis(八)-Redis的list列表的数据结构-快速链表
数组时需要一块连续的内存空间来存储的,而链表值需要零散的内存碎片,数组的插入和删除的时间复杂度是0(n),查询的某个元素的时间复杂度是O(1)。
102 0
Redis(八)-Redis的list列表的数据结构-快速链表
|
NoSQL Redis
Redis学习4:List数据类型、拓展操作、实现日志等
注意点:对存储空间的顺序进行分析!
Redis学习4:List数据类型、拓展操作、实现日志等
|
存储 NoSQL Redis
Redis学习3:hash类型操作、拓展操作、实现购物等
首先可以理解成一个redis里面有一个小的redis。同时要注意引入了一个field的名字。
Redis学习3:hash类型操作、拓展操作、实现购物等