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

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

一、二叉树

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可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.fengpt.cn/archives/极简理解二叉树红黑树btreebtree