关于B树

感觉B树的知识点有点繁琐，经过一天的复习，我总结了一下B树比较重要的几个点。（错误的望指正）

（１）首先Ｂ树是一颗ｍ叉搜索树。其特点是：

    除了根节点之外，每个节点最少有ｍ／２个孩子，最多有ｍ个孩子。也就是说，除根结点之外每个节点，每个节点最少有ｍ／２－１个关键字，最多有ｍ－１个关键字。根节点最多有ｍ－１个关键字，ｍ个孩子；最少有一关键字，两个孩子。

（２）关于B树的建立和删除

    我们在建立B树的时候，首先将第一个节点填满，当关键字的个数超过其最大容量时，我们需要将中间的元素（ｍ／２）提起。然后根据规则继续插入。

当我们在删除元素的时候，要注意分好几中情况：

  １、 若删除的元素在叶子节点上，并且节点内不止有一个元素，那么我们可以直接删除。

  ２、 若叶子节点中只有待删除元素一个，则删除后会出现不平衡现象，我们优先从其左右兄弟中借元素。若可以借，我们需要将兄弟节点和双亲节点中的关键字同时旋转。即兄弟节点中的关键字提到双亲结点中，双亲结点中的关键字下到改节点内。

   ３、若兄弟节点没有可以借的元素，此时应该采用合并的方法。即将双亲中一关键字与被删除节点的一兄弟节点合并。若合并后导致父节点不平衡，则需要对父节点进行平衡处理。不过此时应注意旋转时将某些节点更换父节点。

 ４、  若删除的元素不是叶子节点中的元素，则需要寻找其左边序列中最大的元素来代替待删除元素，并且将代替之后的树进行平衡调整，方法与以上例子相同。