Redis数据结构之跳跃表-skiplist
在Redis
中,zset
是一个复合结构:
使用
hash
来存储value
和score
的映射关系使用跳跃表来提供按照
score
进行排序的功能,同时可以指定score
范围来获取value
列表
结构
zset
内部是一个hash
字典加一个跳跃表skiplist
struct zslnode {
string value;
double score;
zslnode *[]forwards; // 多层连接指针
zslnode *backward // 回溯指针
} zslnode;
struct zsl {
zslnode *header; // 跳跃表头指针
int maxLevel; // 跳跃表当前最高层
map<string, zslnode*> ht; // hash结构的所有键值对
} zsl;
图为跳跃表示意图,实际上在Redis
中共有64
层,即最多可容纳2^64
个元素。
每一个kv
块即代码中zslnode
,header
中value
为NULL
值,score
为Double.MIN_VALUE
。kv
之间使用指针链接成为双向链表,这些键值对根据score
进行有序排列,不同的kv
层高可能不同,层数越高则kv
越少,同一层的kv
之间使用指针进行串接,对于每一层的元素的遍历都是从kv header
出发的。
常用操作
查找
如图所示,需要定位紫色的kv
时,首先从header
最高层开始进行遍历,遍历到第一个比k
值小的节点,然后下降一层继续查找该层最后一个比k
小的元素,依此类推,直到查找到该元素为止。
搜索时中间的一系列节点称之为搜索路径,它是从最高层一直到最底层的每一层最后一个比目标节点小的元素节点列表。
插入
插入新节点时,首先需要搜索合适的插入点,类似于查找过程找到合适节点之后就可以开始创建新的节点。创建时需要为节点随机分配一个层数,再将搜索路径上的节点和新节点通过前后指针进行串接。
如果分配的新的节点比当前跳跃表最大高度高的话,需要更新一下跳跃表的最大高度。
删除
删除过程和插入过程类似,需要先将搜索路径找出来,然后对于每一个层的相关节点,都需要重排一下前后指针,同时注意更新一下最高层数maxLevel
。
更新
调用zadd
方法时,如果对应的value
不存在,直接进行插入;如果已经存在且只是更新score
的话,需要进行更新。
如果新值的score
不会带来排序位置的改变,则不需要调整位置,直接修改元素的score
值即可,否则需要调整该节点位置。
Redis
在更新节点位置时,采用先删除这个元素,再插入这个元素的方法,这样就不需要判断是否需要调整位置,只需要进行两次路径搜索即可。
如果score
值一样
极端情况下,zset
中所有元素的score
一样,此时查找性能也不会退化为O(n)
,因为zset
的排序不只考虑score
,如果score
一样的话还会再比较value
值。
计算元素排名
zset
可以使用rank
获取元素排名,主要是因为Redis
中,对于skiplist
的节点的forward
指针进行了优化,给每一个forward
指针添加了span
属性,表示从前一个节点沿当前层的forward
指针跳到当前节点时中间会跳过多少个节点。
借助span
属性,在计算一个元素的排名时,只需要将搜索路径上经过的所有节点的span
属性进行叠加即可计算出最终的rank
值。
最新文章
- android获得图片
- Git.Framework 框架随手记-- 分享一个";比较垃圾";的项目
- 搜索引擎选择: Elasticsearch与Solr
- mvc EF框架中,加载外键对象序列化对象时报错 序列化类型为XX的对象时检测到循环引用
- [UE4]Tile View
- 【网络编程】time_wait状态产生的原因,危害,如何避免
- Webpack傻瓜式指南(转)
- keras如何求分类问题中的准确率和召回率
- Oracle使用——oracle用户相关操作
- 查看Linux系统版本信息(转)
- [UE4]运行模式
- python3.x:No matching distribution found for PIL
- va_start(),va_end()函数应用【转】
- BIEE11G配置Oracle 12c数据源
- sqlserver 索引优化 CPU占用过高 执行分析 服务器检查
- docker 安装vim
- windows下使用GNU make命令报错的解决方法
- 解决You are using pip version 10.0.1, however version 18.1 is available. You should consider upgrading via the &#39;python -m pip install --upgrade pip&#39; command.
- 第一百五十九节,封装库--JavaScript,表单序列化结合ajax提交数据
- jstl c
热门文章
- POJ 2254 Globetrotter (计算几何 - 球面最短距离)
- postgis常用的函数
- Django框架(十八)—— auth框架:用户登录、注册、认证
- Win7下VS2008安装cocos2d-2.0-x-2.0.4模板时, 运行InstallWizardForVS2008.js文件执行失败的解决办法
- Laravel4 最佳学习代码以及资料推荐(转)
- 使用python解析C代码
- C/C++ 吐槽第一期:你最讨厌的C/C++里面的数据类型是什么
- css图片文字
- less&;sass
- Codeforces 1163D DP + KMP