一点点关于B树的总结

发表于 2018-03-08 更新于 2023-07-26 分类于 jekyll ， data structure ， B tree 阅读次数： Valine：

本文字数： 2.9k 阅读时长 ≈ 3 分钟

本文主要讲了b树的一些性质,给出了一份c的参考代码

前提说明:

B树是上次自己在数据结构实训时学到的一个知识点，据笔者写这篇文章也有点岁月了，在接下来提供的代码可能会有错误，原因是我在学的时候写的太乱，只记得当时自己整理出三个B树的代码，（为啥那，无他，笔者太笨了，所以只有通过这种笨方法来学习），第一份是B树是用类模板写的（源自网络，自己抄写了几遍，帮助自己理解B树的插入，删除过程，现在可能有点忘了。。。），第二份是笔者根据类模板的改成用类的形式书写，第三份是笔者根据之前写前两份累计的经验，用结构体写的。现在，笔者只敢肯定最后用结构体写的是正确的（原因：只有这一份源码，B树构建的大概意思应该还是知道的）！

B树的源码我会在文章最后给出！

学习B树的大致流程：

B树的基本性质

自己摸索，自己构建，最后找一份源码比较一下两者之间的差距。（最佳方法）

找一份源码看，看懂后自己写出B树的构建过程

如果哦自己并没有完全掌握、明白B树的构建删除过程，建议抄写代码（一定要考虑为什么要这么写，以及这样写能带来的好处）。

B树的性质(笔者在这给出多种理解方式，自己找到最适合自己理解的吧)：

1.简洁版：

B-树是一种多路搜索树（并不是二叉的）：

       1.定义任意非叶子结点最多只有M个儿子；且M>2；

       2.根结点的儿子数为[2, M]；

       3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

       4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

       5.非叶子结点的关键字个数=指向儿子的指针个数-1；

       6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

       7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的

子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

       8.所有叶子结点位于同一层；

2.理解版

B-树的特性：

       1.关键字集合分布在整颗树中；

       2.任何一个关键字出现且只出现在一个结点中；

       3.搜索有可能在非叶子结点结束；

       4.其搜索性能等价于在关键字全集内做一次二分查找；

       5.自动层次控制；

       由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少

利用率，其最底搜索性能为：o(log2N);

  由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占

M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并；

B_tree 的插入

	1）定位：利用前述的B树查找算法，找出插入该关键字的最底层中某个非叶结点
	（注意，B树中的插入关键字一定是插入在最底层中的某个非叶子结点内）
	2）插入：在B树中，每个非失败结点的关键字个数都在【(m/2)向下取整-1，m-1】之间。
		当插入后的结点关键字个数小于m，则可以直接插入；插入后检查被插入结点内关键字的个数，
		当插入后的结点关键字个数大于m-1时，则必须对结点进行分裂。
		分裂的方法是：取一个新结点，将插入key后的原结点从中间位置将其中的关键字分为两部分，左部分包含的关键字放在原结点中，
		右部分包含的关键字放在新的结点中，中间位置（【m/2】向下取整）的结点插入到原结点的父结点中。
		若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，
		直到这个过程传到根结点为止，这样导致B树高度增1。

4.B树的删除

	B树中的删除操作与插入操作类似，但要稍微复杂些，要使删除后的结点的关键字个数>=([m/2]向下取整)-1，因此涉及结点的合并问题。
	当所删除的关键字k不在终端结点（最底层非叶结点）中时，有下列几种情况：
	1）如果小于k的子树中关键字个数>([m/2]向下取整)-1，则找出k的的前驱值K'，并且用K'来取代k,再递归地删除K'即可。
	2）如果大于k的子树中关键字个数>([m/2]向下取整)-1，则找出k的的后继值K'，并且用K'来取代k,再递归地删除K'即可。
	3）如果前后两个子树中关键字个数均为([m/2]向下取整)-1，则直接将两个子结点合并，直接删除k即可。
	当被删除的关键字在终端结点（最低层非叶结点）中时，有下列几种情况：
	1）直接删除关键字：若被删除关键字所在结点的关键字个数>【m/2】(向下取整)-1，表明删除该关键字后仍满足B树的定义，则直接删去该关键字。
	2）兄弟够借：若被删除关键字所在结点删除前的关键字个数=【m/2】(向下取整)-1，且与此结点相邻的左（右）兄弟结点的关键字个数>=【m/2】(向下取整)，
		需要调整该结点左（右）兄弟结点及其双亲结点（父子换位法），以达到新的平衡。
	3）兄弟不够借：若被删除关键字所在结点删除前的关键字个数=【m/2】(向下取整)-1，且此时与该结点相邻的左（右）兄弟结点的关键字个数=【m/2】
		(向下取整)-1，则将关键字删除后，将左（右）兄弟结点及双亲结点中的关键字合并。
		在合并的过程中，双亲结点的关键字个数会减少。若其双亲结点是根结点并且关键字个数减少至0（根结点关键字个数为1时，有两棵子树），
		则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，
		且关键字个数减少至【m/2】-2，又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合B树的要求为止。

有关B树的模板：

B树的类定义完整版

B树的类定义实现完整版

B树的结构体实现

B树插入过程的简单描述：

插入的具体流程如下：
    1判断是否为空树.是否为空树
    2.树中是否存在此关键字信息
    3.叶子中插入
        a. 小于m-1 挖空，填空 i
        b:  先分裂节点，递归处理（插入后中间值上移（定义 parent指针用作上移））

B树删除过程的简单描述：


删除的两大部分：删除（叶节点，非叶节点），调整
1.删除对应的节点信息
    如果在叶子上直接删除
    如果在内节点上，找到p最右边相邻叶子节点交换，叶子节点信息进行覆盖
2.调整（循环）
    如果是删除信息的所在的节点是富裕的叶子节点，或者说是树根的情况，退出循环
    否则，需要去找删除节点在其父亲节点中子树的位置，如果是位于0号位置，进行右调整，其他位置进行左调整
    左右调整大致分为两个情况：
        如果兄弟节点富裕的话，直接进行相应的节点信息调整即可，否则的话，合并两个节点信息，生成一个新节点
    节点上移,调整父亲节点信息
        合并两个节点信息采用大的给小的的形式，所以对于左调整，选择合适合并节点进行合并即可
3.退出循环后特殊判断一下空树的情况

补充说明：

其实，我在自己最后一次写B树模板的时候对自己找到知识点做了一个简单的汇总，上文所说的可以在我的[结构体]模板中找到.

注意:

以上内容，作者一字一句码出来的，纯属不易，欢迎大家转载，转载是还请您表明出处。另外如果我有侵权行为，请在下方留言，确认后我会及时撤销相应内容，谢谢大家！