红黑树 PK 跳跃表 (内存占用,查询性能)1500万数据查询更新1.5万 数据,时间都在100ms以下

单龙攀 · · 1738 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

跳跃表和红黑树都是常用的数据结构,二者都能实现快速查询

一、跳跃表结构

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

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

跳跃表以空间换取时间,来实现快速查找

二、红黑树

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

1、节点是红色或黑色。
2、根是黑色。
3、所有叶子都是黑色(叶子是NIL节点)。
4、每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
5、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

clipboard.png

红黑树,和跳跃表性能对比

模拟实验一千五百万,id自增,从1到一千五百万,查询更新时间效率对比
clipboard.png
代码太多,不贴代码了,具体代码在github里面具体文件如下
红黑树代码 https://github.com/shanlongpa...
跳跃表代码 https://github.com/shanlongpa...


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1738 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传