什么是QuickList
Redis 中的 Quicklist 是一种高效存储小块二进制数据的数据结构,是由两个有序列表组成的双向链表,其中每个节点可以包含多个小块数据。Quicklist 通常用于处理缓存、队列和列表等场景,相比于单纯使用链表或数组存储小块数据,在内存占用、遍历速度和插入/删除操作上都具有更优秀的性能。
原理
Quicklist 内部实现细节如下:
- 双向链表结构:quicklist 由多个有序列表组成,列表是通过双向指针连接起来的双向链表。
- 节点大小限制:每个 quicklist 节点最大为 4KB。
- 压缩与不压缩:当 quicklist 中的所有小块数据(也称为 blob)平均较小且数量众多时,会启用自动压缩机制,并将多个小块数据合并为较大的块以节约空间和加快遍历速度;而当数据块较大或数量不足时,压缩机制失效,节点中的 - blob 仍然保持原样(不压缩)。
- 按插入顺序存储:Quicklist 内的元素是按照添加时间排序的,最新的小块数据始终排在链表的最前面。
- ziplist 数据结构:在 Quicklist 节点中存储小块数据使用的是 ziplist 数据结构,这是一种紧凑高效的连续内存布局,可以减少内存分配和指针跳转的脆弱性。
- 多层级索引:quicklist 中还有一个多层级索引,可以根据 blob 的下标位置快速定位到对应节点的列表,并减少遍历操作的次数。
- 本文作者: Hongker
- 本文链接: https://hongker.github.io/2023/05/05/algorithm-quicklist/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!