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

单龙攀 · · 148 次点击 · · 开始浏览    

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

一、跳跃表结构

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中文网 QQ交流群:798786647 或 加微信入微信群:274768166 备注:入群; 公众号:Go语言中文网

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