Redis压缩列表ziplist API

x33g5p2x  于2021-03-14 发布在 Redis  
字(0.6k)|赞(0)|评价(0)|浏览(225)

表 7-4 列出了所有用于操作压缩列表的 API 。

函数作用算法复杂度
ziplistNew创建一个新的压缩列表。O(1)
ziplistPush创建一个包含给定值的新节点, 并将这个新节点添加到压缩列表的表头或者表尾。平均 O(N) ,最坏 O(N^2) 。
ziplistInsert将包含给定值的新节点插入到给定节点之后。平均 O(N) ,最坏 O(N^2) 。
ziplistIndex返回压缩列表给定索引上的节点。O(N)
ziplistFind在压缩列表中查找并返回包含了给定值的节点。因为节点的值可能是一个字节数组, 所以检查节点值和给定值是否相同的复杂度为 O(N) , 而查找整个列表的复杂度则为 O(N^2) 。
ziplistNext返回给定节点的下一个节点。O(1)
ziplistPrev返回给定节点的前一个节点。O(1)
ziplistGet获取给定节点所保存的值。O(1)
ziplistDelete从压缩列表中删除给定的节点。平均 O(N) ,最坏 O(N^2) 。
ziplistDeleteRange删除压缩列表在给定索引上的连续多个节点。平均 O(N) ,最坏 O(N^2) 。
ziplistBlobLen返回压缩列表目前占用的内存字节数。O(1)
ziplistLen返回压缩列表目前包含的节点数量。节点数量小于 65535 时 O(1) , 大于 65535 时 O(N) 。

因为 ziplistPush 、 ziplistInsert 、 ziplistDelete 和 ziplistDeleteRange 四个函数都有可能会引发连锁更新, 所以它们的最坏复杂度都是 O(N^2) 。

相关文章

微信公众号

最新文章

更多