平衡树vs跳表
平衡树必须满足所有节点的左右子树高度差不超过1,也就是平衡因子范围为[-1,1]。
但是对于范围查询来说,利用平衡树通过中序遍历达到和跳表一样的效果,但是平衡树的每一次插入或者删除操作都需要保证整棵树的绝对平衡,
只要不平衡就会通过旋转的方式来重新保持平衡,这个过程就非常耗时。
红黑树vs跳表
红黑树就是一种黑色平衡树,也就是说从任意节点到另外一个叶子节点,所经过的黑色节点是一样的。如果对红黑树进行
插入操作时,需要通过旋转和染色来保持黑平衡。这个过程相对于平衡树来说需要的开销要小一点。
但是红黑树在查找数据的过程中效率却比不了跳表。
B+树vs跳表
1.B+树可以包含多个子节点,能够有效减少树的高度。
2.每个非叶子节点存储多个key,叶子节点可以存储多个value,因此每个节点更能够存储更多的键。
3.拥有绝对的平衡,每个树的各个分支高度相差不大。
4.能够按照顺序访问。
5.插入数据可以让整棵树分布更加均匀,保证范围查询和删除效率。
B+树更适合用于数据库和文件系统,可以通过较少的IO定位到尽可能多的索引来获取查询数据。
但是对于redis来说,redis是内存数据库不需要存储大量的数据,也就是对于索引不需要通过B+树这种方式进行维护,
只需要按照概率进行随机维护就可以了,这样就能够节省内存。而且使用跳表进行插入操作的时候只需要通过索引将数据插入到
链表中去即可,不需要像B+树那样插入的时候发现失去平衡后还需要对节点进行分裂与合并。
标签:redis,插入,跳表,红黑树,平衡,节点 From: https://www.cnblogs.com/huwy-123/p/18134390