哪有网站给光头强做面,河南国基建设集团有限公司网站,电脑商业网站怎的做,公司网站怎样做维护跳跃表
跳跃表#xff08;skiplist#xff09;是一种随机化的数据#xff0c; 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出#xff0c; 跳跃表以有序的方式在层次化的链表中保存元素#xff0c; 效率和平衡树媲美 —— …跳跃表
跳跃表skiplist是一种随机化的数据 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出 跳跃表以有序的方式在层次化的链表中保存元素 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成 并且比起平衡树来说 跳跃表的实现要简单直观得多。 从图中可以看到 跳跃表主要由以下部分构成
表头head负责维护跳跃表的节点指针。跳跃表节点保存着元素值以及多个层。层保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针为了提高查找的效率程序总是从高层先开始访问然后随着元素值范围的缩小慢慢降低层次。表尾全部由 NULL 组成表示跳跃表的末尾。
因为跳跃表的定义可以在任何一本算法或数据结构的书中找到所以本章不介绍跳跃表的具体实现方式或者具体的算法 而只介绍跳跃表在 Redis 的应用、核心数据结构和 API 。
跳跃表的实现
为了满足自身的功能需要 Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改
允许重复的 score 值多个不同的 member 的 score 值可以相同。进行对比操作时不仅要检查 score 值还要检查 member 当 score 值可以重复时单靠 score 值无法判断一个元素的身份所以需要连 member 域都一并检查才行。每个节点都带有一个高度为 1 层的后退指针用于从表尾方向向表头方向迭代当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时就会用到这个属性。 这个修改版的跳跃表由 redis.h/zskiplist 结构定义
typedef struct zskiplist {// 头节点尾节点struct zskiplistNode *header, *tail;// 节点数量unsigned long length;// 目前表内节点的最大层数int level;} zskiplist;跳跃表的节点由 redis.h/zskiplistNode 定义
typedef struct zskiplistNode {// member 对象robj *obj;// 分值double score;// 后退指针struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 这个层跨越的节点数量unsigned int span;} level[];} zskiplistNode;小结
跳跃表是一种随机化数据结构查找、添加、删除操作都可以在对数期望时间下完成。跳跃表目前在 Redis 的唯一作用就是作为有序集类型的底层数据结构之一另一个构成有序集的结构是字典。为了满足自身的需求Redis 基于 William Pugh 论文中描述的跳跃表进行了修改包括 score 值可重复。对比一个元素需要同时检查它的 score 和 memeber 。每个节点带有高度为 1 层的后退指针用于从表尾方向向表头方向迭代。
为啥 redis 使用 跳表 (skiplist) 而不是使用 red-black
实现简单。区间查找快。跳表可以做到O(logn)的时间复杂度定位区间的起点然后在原始链表中顺序往后遍历就可以了。并发环境优势。红黑树在插入和删除的时候可能需要做一些rebalance的操作这样的操作可能会涉及到整个树的其他部分而skiplist的操作显然更加局部性一些需要锁住的节点更少因此在这样的情况下性能好一些。
