本文共 512 字,大约阅读时间需要 1 分钟。
Redis压缩列表
- 概述
- 压缩列表 ziplist 是列表键和哈希键的底层实现之一。
- 为了节约内存而开发
- 构成
- zlbytes
- ztail
- zllen
- entryX
- 列表节点
- encoding
- content
- previouse_entry_length
- zlend
- 连锁更新
- 如果前一节点长度小于254字节,previous_entry_length 用一个字节保存长度值
- 如果前一节点长度大于等于254字节,previous_entry_length用5个字节保存长度值
- 问题
- 前几节点连续几个250-253字节的,一个长度为254的节点插入头结点,后面随之都要重新分配空间
- 删除节点同样会触发连锁更新
- 每次分配时间复杂度O(N),连锁更新最坏时间复杂度O(N^2)
- 注意
- 虽然时间复杂度高,但是发生的概率并不会很高
- 即使发生,只要影响的节点不多也不会对性能造成影响
- 平均时间复杂度O(N)不会影响正常的操作
- 参考
- 《Redis设计与实现》
转载地址:http://ahiii.baihongyu.com/