21
红黑树 PK 跳跃表 （内存占用，查询性能）1500万数据查询更新1.5万 数据，时间都在100...
source link: https://www.tuicool.com/articles/MZvUvyV
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
跳跃表和红黑树都是常用的数据结构，二者都能实现快速查询
一、跳跃表结构
从图中可以看到， 跳跃表主要由以下部分构成：
表头（head）：负责维护跳跃表的节点指针。
跳跃表节点：保存着元素值，以及多个层。
层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
表尾：全部由 NULL 组成，表示跳跃表的末尾。
跳跃表以空间换取时间，来实现快速查找
二、红黑树
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
1、节点是红色或黑色。
2、根是黑色。
3、所有叶子都是黑色（叶子是NIL节点）。
4、每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
红黑树，和跳跃表性能对比
模拟实验一千五百万，id自增，从1到一千五百万，查询更新时间效率对比
代码太多，不贴代码了，具体代码在github里面具体文件如下
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK