当前位置: 首页 > news >正文

哪个网站做免费小程序seo点击工具帮你火21星热情

哪个网站做免费小程序,seo点击工具帮你火21星热情,深圳网络排名优化,网上做ps赚钱的网站跳跃表 跳跃表(skiplist)是一种随机化的数据, 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— …

跳跃表

跳跃表(skiplist)是一种随机化的数据, 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 跳跃表的实现要简单直观得多。

image
从图中可以看到, 跳跃表主要由以下部分构成:

  • 表头(head):负责维护跳跃表的节点指针。
  • 跳跃表节点:保存着元素值,以及多个层。
  • 层:保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率,程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。
  • 表尾:全部由 NULL 组成,表示跳跃表的末尾。

因为跳跃表的定义可以在任何一本算法或数据结构的书中找到,所以本章不介绍跳跃表的具体实现方式或者具体的算法, 而只介绍跳跃表在 Redis 的应用、核心数据结构和 API 。

跳跃表的实现

为了满足自身的功能需要, Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改:

  1. 允许重复的 score 值:多个不同的 member 的 score 值可以相同。
  2. 进行对比操作时,不仅要检查 score 值,还要检查 member :当 score 值可以重复时,单靠 score 值无法判断一个元素的身份,所以需要连 member 域都一并检查才行。
  3. 每个节点都带有一个高度为 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 论文中描述的跳跃表进行了修改,包括:
    1. score 值可重复。
    2. 对比一个元素需要同时检查它的 score 和 memeber 。
    3. 每个节点带有高度为 1 层的后退指针,用于从表尾方向向表头方向迭代。

为啥 redis 使用 跳表 (skiplist) 而不是使用 red-black?

  1. 实现简单。
  2. 区间查找快。跳表可以做到O(logn)的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。
  3. 并发环境优势。红黑树在插入和删除的时候可能需要做一些rebalance的操作,这样的操作可能会涉及到整个树的其他部分,而skiplist的操作显然更加局部性一些,需要锁住的节点更少,因此在这样的情况下性能好一些。
http://www.dinnco.com/news/35329.html

相关文章:

  • 做胃肠科网站兴安盟新百度县seo快速排名
  • 网站mssql 导出数据网络营销师证书有用吗
  • 网站在线咨询系统山东建站管理系统
  • 永久免费的网站空间seo优化培训班
  • 厦门做网站建设网站推广平台搭建
  • 网站建设 海口数据分析培训班
  • 北京哪里招聘网页设计惠州抖音seo策划
  • 网站推广主要怎么做网店运营的工作内容
  • 用主机宝建立的网站上传之后404国外推广网站有什么
  • 怎样购买网站程序新手怎么做网络销售
  • 深圳国税局深圳做网站公司收录好的网站
  • 汉滨网站建设网络营销比较好的企业
  • 中国核工业第二二建设有限公司宁波seo费用
  • 移动网站建设信息长沙网站关键词排名推广公司
  • 标智客logo设计免费生成sem和seo的区别
  • 国务院政府网站发展建设的意见企业网络规划设计方案
  • 做淘客网站 知乎second是什么意思
  • 有专门做宝宝用品的网站吗seo网站关键词排名优化
  • 如何处理公关危机品牌推广百度seo
  • 厦门大型企业网站开发公司磁力神器
  • 以前有个自助建设网站网站seo推广公司靠谱吗
  • 325平台代理seo服务公司招聘
  • 网站建设平台方案设计搜索引擎优化代理
  • wordpress网站首页链接乱码广州白云区新闻头条最新消息今天
  • 河南企业网站建设优化关键词是什么意思
  • 济南自适应网站建设seo和sem的联系
  • 有没有只做软装方案收设计费的网站百度账号怎么注册
  • 境内境外网站区别seo查询系统
  • 企业培训网站网站推广优化外包公司
  • 网站链接提交软文关键词排名推广