如何手写b-树，b+树建立过程？
2018-05-13 本文已影响0人
zhansanking
- 要想手写b-树和b+树的建立过程，就得清楚b-树和b+树性质
性质不清楚的人请看文章最后，我们现在先开始建树吧。
b-树 建树过程 ：
给定元素 [3,7,9,23,45,1,5,14,25,24,13,8,11,19,4,31,35,56]建立一棵5阶b-树
要诀:其实最重要的就是分裂了，分裂时取结点的关键字数目中位数的那个关键字作为父结点，考虑是否满足性质，先考虑是不是满了，然后就是要让树平衡。
1.png
插入7:
2.png
插入9：
3.png
插入23：
4.png
插入45：超了最大关键字个数，所以要分裂，分裂取关键字中位数9作为父节点
5.png
插入1：
6.png
插入5：
7.png
插入14：
8.png
插入25:
9.png
插入24：
10.png
插入13：
11.png
插入8：
12.png
插入11：
13.png
插入19：
14.png
插入4：
15.png
插入31：
16.png
插入35：
17.png
插入56：因为两层都满，所以分裂两次
18.png
b+树建树过程
- 和b-树的原则差不多，不过要注意在分裂时选出中位数的时候，把中位数得放在子结点中，至于左右看不同书的要求。我们这里采用放右边。边界条件应该是不影响的，取一种方法一直采用就好，所以构建b树的方法也不唯一。只要满足条件即可。
仍然插入[3,7,9,23,45,1,5,14,25,24,13,8,11,19,4,31,35,56]
插入3：
1.png
插入7：
2.png
插入9：
3.png
插入23：
4.png
插入45：
5.png
插入1：
6.png
插入5：
7.png
插入14：
8.png
插入25：
9.png
插入24：
10.png
插入13：
11.png
插入8：
12.png
插入11：
13.png
插入19：
14.png
插入4：
15.png
插入31：
16.png
插入35：
17.png
插入56：
18.png
b-树性质要求：
1.M为树的阶数，B-树或为空树，否则满足下列条件：
定义任意非叶子结点最多只有M个儿子；且M>2；
1.png
-如图 ，一个五阶的b-树的一个结点，深色的点个数就是树的阶数也就是最大儿子数，
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字,根节点至少一个关键字）；
5.非叶子结点的关键字个数=指向儿子的指针个数-1（即为上图中的浅色方块）；
6.非叶子结点的关键字：K[i]< K[i+1] ；
7.非叶子结点的指针：关键字左边的指针指向<关键字的结点，关键字右边的指针指向>关键字的结点
8.所有叶子结点位于同一层；
b+树的性质要求：
b树（即b-树）的要求b+树也需满足，此外b+树需要叶子结点中的元素是所有数据，也就是说上层的数据只是用来索引不作为最终结果。
- b+树的关键字也是在叶子结点中的，所以对于关键字左右两边的指针指向等号取在左边还是右边不同书是不一样的，本文使用的是右边。（即右边的指针所指结点的数据>=关键字数据，左边的<）
