一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树 _搜索树

文章插图
我们假设B+树一个节点可以有100个关键字，那么3层的B树可以容纳大概1000000多个关键字（100+101100+101101*100）。而红黑树要存储这么多至少要20层。所以使用B树相对于红黑树和AVL可以减少IO操作大纲在了解 B树、B+树、AVL树、红黑树之前，我们先看一下各种树型结构的大致实际应用场景：
B和B+树：主要用在文件系统以及数据库中做索引等AVL树：平衡二叉树之一，应用相对其他数据结构比较少，windows对进程地址空间的管理用到了AVL红黑树：平衡二叉树，广泛应用在C++STL中，比如map和set，JAVA的TreeMap
树结构已经有了很多种形式，为何出现 B树、B+树、AVL树、红黑树？下面我们按照这个大纲来看一下这些问题？

文章插图
二叉搜索树概念二叉搜索树 (平衡二叉树) 是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度。
我们在二叉搜索树的深度遍历过程中，使用中序遍历，就能获取得到有序的序列。

文章插图
特点

如果任意节点左子树不为空，则左子树的值均小于根节点的值。
如果任意节点右子树不为空，则右子树的值均大于于根节点的值。
任意节点的左右子树也分别是二叉查找树。
没有键值相等的节点。

存在的局限对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)，和树的深度是一样的。这种依靠比较大小来逐步查找的方式，和二分查找算法非常相似。
【一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树】出现一些特殊的情况的时候，会导致搜索节点的时间复杂度变高。什么特殊情况呢？下面请试着在二叉查找树中依次插入10、11、9、8、7、6、5、4，看看会出现什么 ? 好好的一个二叉树，变成“跛脚”啦！

文章插图
不只是外观看起来变得怪异了，查询节点的时间复杂度也退化成了O(n) 。怎么解决这个问题呢？这就涉及二叉树的自平衡了。二叉树自平衡的方式有多种，如红黑树、AVL树等，这两种我们在后面会介绍到，我们先来看一下B树和B+树。
B树概念B树又名平衡多路查找树（也把B树称为B-树）查找路径不只两个，不同于常见的二叉树，它是一种多叉树，我们常见的使用场景一般是在数据库索引技术里，大量使用者B树和B+树的数据结构。

文章插图
B树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据，有可能没有办法一次将需要的所有数据加入到内存中，所以只能逐一加载磁盘页，每个磁盘页就对应一个节点，而对于B树来说，B树很好的将树的高度降低了，这样就会减少IO查询次数，虽然一次加载到内存的数据变多了，但速度绝对快于AVL或是红黑树的。
特点：

所有键值分布在整个树中（区别与B+树，B+树的值只分部在叶子节点上）
任何关键字出现且只出现在一个节点中（区别与B+树）
搜索有可能在非叶子节点结束（区别与B+树，因为值都在叶子节点上，只有搜到叶子节点才能拿到值）
在关键字全集内做一次查找，性能逼近二分查找算法

查询分析

如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，
通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，
通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO 。

B+树概念