极简理解二叉树、红黑树、B Tree,B+Tree

过去的,未来的
2020-03-27 / 0 评论 / 0 点赞 / 1,154 阅读 / 0 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2020-03-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一、二叉树

1、例子

image.png

2、缺点

当数据是自增顺序的,查找就很慢,和链表一样了
image.png

突然发现,链表也是二叉树。。。

二、红黑树

1、例子

image.png
可以看出,数据是自增顺序的,他会自己调整,这样查找也是方便。

2、缺点

例如数据量特别大,这样他的树的深度,很深,如果要查找的数据,在最底层叶子节点,查询也很慢。
image.png

三、B Tree

1、例子

image.png
为了解决树深度太深问题,我们可以扩展横向,这样就是B Tree ,解决深度问题。
image.png

2、缺点

但是横向扩展也不是一直无线扩展的,凡是都有个度。

四、B+Tree

1、例子

image.png
去除非子节点的数据,有利于每层储存的数据索引更多。这样数据就不占用空间。

2、特点
 B+Tree的搜索与B-Tree也基本相同,区别是B+Tree只有达到叶子结点才命中(B-Tree可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
0

评论区