摘要：前言在上一章中我们介绍了的一些内部原理在这一章中我们再来讨论在五种数据结构中的基本使用和一些内部实现基本介绍的呢相当于中的也是双向链表具有一些和同样的特征比如插入和删除一条很快时间复杂度为获取头结点和尾节点也很快时间复杂度也为随机读取则相对
前言
在上一章中我们介绍了 String 的一些内部原理,在这一章中我们再来讨论在五种数据结构中 List 的基本使用和一些内部实现.
基本介绍Redis的List 呢相当于 Java 中的 LinkedList,也是双向链表.具有一些和 LinkedList 同样的特征,比如插入和删除一条很快,时间复杂度为 O(1),获取头结点和尾节点也很快,时间复杂度也为 O(1),随机读取则相对较慢时间复杂度为 O(n).常用作消息队列.
当做队列使用时,遵循先进先出原则:
> rpush books python java golang (integer) 3 > lpop books "python" > lpop books "java"
当做栈使用时,遵循先进后出原则:
> rpush books python java golang (integer) 3 > rpop books "golang" > rpop books "java"
同时还可以通过 get(index)的方法获取:
> rpush books python java golang (integer) 3 > lindex books 0 "python" > lindex books -1 "golang"
index从 0 开始,可以为负数 -1 代表倒数第一个元素
内部实现上述部分我们把 Redis 中的 List当做 Java 中的 LinkedList 操作,因为有很多相同的部分.但实际上在 Redis 中链表的内部实现可不是一个简单的双向链表.在数据量较少的时候它的底层存储结构为一块连续内存,称之为ziplist(压缩列表).当数据量较多的时候将会变成链表的结构.后来因为链表需要 prev 和 next 两个指针占用内存很多,改用 ziplist+链表的混合结构,称之为 quicklist(快速链表).在新的版本中 Redis 链表统一使用 quicklist来存储.下面我们就来详细介绍这种数据结构.
ziplist 压缩列表先来看看 ziplist 的数据结构:
struct ziplist{ int32 zlbytes; //压缩列表占用字节数 int32 zltail_offset; //最后一个元素距离起始位置的偏移量,用于快速定位到最后一个节点 int16 zllength; //元素个数 T[] entries; //元素内容 int8 zlend; //结束位 0xFF }
如图所示:
有了 ztail_offset 就可以快速的定位到最后一个节点,这样就可以倒序遍历了.也就是说 ziplist支持双向遍历.
下面再来看下 entry 的内部实现:
struct entry{
int prevlen; //前一个 entry 的长度
int encoding; //元素类型编码
optional byte[] content; //元素内容
}
当 ziplist 倒序遍历的时候,就是通过这个pervlen定位到前一个元素位置的.
encoding 保存了 content 的编码类型.
content 则是保存的元素内容,它是optional 类型表示是这个字段是可选的.当content 是很小的整数时,他会内联到 encoding 字段的尾部.
quicklist 快速列表quicklist 是 ziplist 和链表的混合体.下面是 quicklist和 node 的部分数据结构:
struct quicklist{
quicklistNode* head; //指向头结点
quicklistNode* tail; //指向尾节点
long count; //元素总数
int nodes; //quicklistNode节点的个数
int compressDepth; //压缩算法深度
...
}
为了节约空间 Redis 还会对 ziplist 使用 LZF 算法进行压缩,可以选择压缩深度.我们待会在说.
如上图所示,quicklist含有两个 quicklistNode 代表头结点和尾节点,其中每个head 和 tail 之间是双向链表.每个quicklistNode指向一个 ziplist.
struct quicklistNode{
quicklistNode* prev; //前一个节点
quicklistNode* next; //后一个节点
ziplist* zl; //压缩列表
int32 size; //ziplist大小
int16 count; //ziplist 中元素数量
int2 encoding; //编码形式 存储 ziplist 还是进行 LZF 压缩储存
...
}
在 quicklist 中每个 ziplist 默认大小是 8kb,超出这个字节就会增加一个 ziplist.这个默认大小是可配置的,由list-max-ziplist-size决定.
上面说到 ziplist 可以使用 LZF 算法压缩,通过list-compress-depth配置.默认情况下quicklist 的压缩深度是 0,也就是不压缩.配置为 1 的话代表从头/尾开始第 1 个ziplsit 进行压缩.
下章预告,Redis 数据结构之 Hash
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/37208.html
摘要：前言在上一章中我们介绍了的一些内部原理在这一章中我们再来讨论在五种数据结构中的基本使用和一些内部实现基本介绍的呢相当于中的也是双向链表具有一些和同样的特征比如插入和删除一条很快时间复杂度为获取头结点和尾节点也很快时间复杂度也为随机读取则相对 前言 在上一章中我们介绍了 String 的一些内部原理,在这一章中我们再来讨论在五种数据结构中 List 的基本使用和一些内部实现. 基本介绍 ...
摘要：前言本章接着上一节继续介绍的基础数据结构中的字典基本介绍也可以用来存储用户信息和不同的是可以对用户信息的每个字段单独存储则需要序列化用户的所有字段后存储并且需要以整个字符串的形式获取用户而可以只获取部分数据从而节约网络流量不过内存占用要大于 前言 本章接着上一节继续介绍 Redis 的基础数据结构中的Hash字典. 基本介绍 Hash 也可以用来存储用户信息,和 String 不同的是...
摘要：前言本章接着上一节继续介绍的基础数据结构中的字典基本介绍也可以用来存储用户信息和不同的是可以对用户信息的每个字段单独存储则需要序列化用户的所有字段后存储并且需要以整个字符串的形式获取用户而可以只获取部分数据从而节约网络流量不过内存占用要大于 前言 本章接着上一节继续介绍 Redis 的基础数据结构中的Hash字典. 基本介绍 Hash 也可以用来存储用户信息,和 String 不同的是...
摘要：前言本章将介绍中和的基本使用和内部原理因为这两种数据结构有很多相似的地方所以把他们放到一章中介绍并且重点介绍内部一个很重要的数据结构跳跃表基本介绍先来看看中集合很像中键值对无序唯一不为空值重复无序是中最特别的基础数据结构其他几个都能和大致对 前言 本章将介绍 Redis中 set 和 zset的基本使用和内部原理.因为这两种数据结构有很多相似的地方所以把他们放到一章中介绍.并且重点介绍...
摘要：前言本章将介绍中和的基本使用和内部原理因为这两种数据结构有很多相似的地方所以把他们放到一章中介绍并且重点介绍内部一个很重要的数据结构跳跃表基本介绍先来看看中集合很像中键值对无序唯一不为空值重复无序是中最特别的基础数据结构其他几个都能和大致对 前言 本章将介绍 Redis中 set 和 zset的基本使用和内部原理.因为这两种数据结构有很多相似的地方所以把他们放到一章中介绍.并且重点介绍...
阅读 2365·2021-11-23 09:51
阅读 629·2021-09-24 10:37
阅读 3406·2021-09-02 15:15
阅读 1851·2019-08-30 13:03
阅读 1770·2019-08-29 15:41
阅读 2493·2019-08-29 14:12
阅读 1303·2019-08-29 11:19
阅读 3187·2019-08-26 13:39
