18-数据结构-查找-B树和B+树

        简介：B树和B+树，都是当存储数据较大时，从硬盘读取数据的优化。emm，我这么说有点迷糊。还是从应试考试的角度解释吧，B树和B＋树，都是在二叉排序树的基础上，优化的，跟二叉排序树很像，但B树它由于相比于二叉排序树，降低了树高，即一个结点内可存取多个数据，这就导致树的高度有效减少，从而减少了从硬盘访问的次数。而B+树，则是对B树的优化，在B树的基础上，最下层为真实数据，B+树类似于分块查找的索引存储结构，树的最下层结点用单链表串起来，为表中真实数据，而上面的每一层都是一个小的索引表，最上面的根为总目录，用户用B+树的时候，是从上面开始查，就跟翻看课本的目录一样，先看大目录，之后小目录套小目录，直到查到最后一层（真实数据），随后在最后一层的单链表对应的位置，往后顺序查找。

---

目录

一、B树

        1.1-简介：

1.2-B树的高（磁盘存取次数）

1.3-B树的插入

1.4-B树的删除

1.4.1-第一种情况是：在终端节点删除

1.4.2-第二种情况是：在非终端结点删除

二、B+树

2.1-简介

2.2-B+树于B树的不同点：​编辑

一、B树

        1.1-简介：

        总的计算知识点，全在图里。主要有B树中结点总数据范围的计算。根结点，终端节点，叶子节点的区分，首先公式中的字母含义。m为几阶B树（B树中结点中度最多的便是m），n为总数据个数，即关键字数。此外，查找的时候，是类中序查找的，大小排序就根平衡二叉树差不多只不过B树中的平衡因子都为0，左小又大，支持随机查找——先在结点内遍历，遍历不到，再去相应区间去往下遍历。

1.2-B树的高（磁盘存取次数）

树的高度越低，就可以减少内外存互访的次数，大大节约时间，提高效率。而树高的计算。即上下限，看上图即可。公式里面的树高计算都是向上取整。

1.3-B树的插入

B树的插入（考虑结点内数据上限，避免失衡），有很多种情况，每次插入的时候都要判断，结点内数据是否失衡，即是否超过上限m-1个数据，如果超过，则需要进行相应的调整。每次调整都是先选该结点内数据中间位置那个数据作为新根，融进其原父结点中去，其他剩余结点，根据左小右大原则，进行分配。

1.4-B树的删除

删除需要注意结点内数据的下限，其中结点分根节点和非根终端节点。

删除分两种情况

1.4.1-第一种情况是：在终端节点删除

例题：

1.4.2-第二种情况是：在非终端结点删除

我觉得最好的方法是，先给中序遍历写出来，然后删除谁，让它的前驱或者后继，补过去就行，原来前驱或后继的位置就空了，然后再根据终端节点删除规则，进行平衡调整即可，

二、B+树

2.1-简介

        B+树，则是对B树的优化，在B树的基础上，最下层为真实数据，B+树类似于分块查找的索引存储结构，树的最下层结点用单链表串起来，为表中真实数据，而上面的每一层都是一个小的索引表，最上面的根为总目录，用户用B+树的时候，是从上面开始查，就跟翻看课本的目录一样，先看大目录，之后小目录套小目录，直到查到最后一层（真实数据），随后在最后一层的单链表对应的位置，往后顺序查找。

2.2-B+树于B树的不同点：

1-B+树中的叶子节点为真实数据，B树中的叶子节点为空，

2-B+树中m阶树，每个分支节点至少有m/2相向上取整个子树。最多有m棵子树

3-B+树支持快速查找，顺序查找，即只要遍历到最底层叶子节点，就可以通过叶子节点这个串成的单链表，进行顺序查找，无序再往上挨个遍历了。

4-B+树适合范围查找。先通过根节点出发，找到特定范围的学生，然后顺着这个结点往下，直到叶子节点单链表，随后按照顺序查找也好，折半查找也好，往后查找范围即可。

5-B+树根结点范围【2，m-1】（因为B+树根节点其实就是个大目录，索引表，好多个分叉，最后汇总，目录里肯定之上有两个目录信息）,B+树的非根结点范围【向上取整，m】

  B树的根节点范围【1,m-1】，B树的非根结点范围【向上取整-1，m-1】

6-B+树中只有叶节点才包含有效信息，其他索引表内结点都是索引作用。

其实根据上面解释，加看图就知道这些区别啦