代码2.初始化B树
这是BTree类的构造函数，初始化一个根节点。全部代码我稍后给出。
下面则要考虑B树的插入，其实B树的构建过程也是向B树插入元素的过程。B树的插入相对来说比较复杂，需要考虑很多因素。
首先，每一个节点可容纳的元素个数是一样并且有限的，这里我声明了一个常量最为每个节点，如代码3所示。
| const int NumPerNode = 4; |
代码3.设置每个节点最多容纳的元素个数
对于B树来说，节点增加的唯一方式就是节点分裂，这个概念和SQL SERVER中的页分裂是一样的。
页分裂的过程首先需要生成新页，然后将大概一半的元素移动到新页中，然后将中间元素提升到父节点。比如我想在现有的元素中插入8，造成已满的页进行分裂，如图3所示：
图3.向已经满的叶子节点插入元素会造成页分裂
通过叶子分裂的概念不难看出，叶子节点分裂才会造成非叶子节点元素的增加。最终传递到根元素。而根元素的分裂是树长高的唯一途径。
在C#中的实现代码如代码4所示。
-
- public void BTreeSplitNode(TreeNode<T> FatherNode, int position, TreeNode<T> NodeToBeSplit)
- {
- TreeNode<T> newNode = new TreeNode<T>();
- newNode.IsLeaf = NodeToBeSplit.IsLeaf;
- newNode.elementNum = NumPerNode - (NumPerNode / 2 + 1);
- for (int i = 1; i < NumPerNode - (NumPerNode / 2 + 1); i++)
- {
-
- newNode.Elements[i - 1] = NodeToBeSplit.Elements[i + NumPerNode / 2];
- }
- if (!NodeToBeSplit.IsLeaf)
- {
- for (int j = 1; j < NumPerNode / 2 + 1; j++)
- {
- newNode.Pointer[j - 1] = NodeToBeSplit.Pointer[NumPerNode / 2];
- }
- }
- NodeToBeSplit.elementNum = NumPerNode / 2;
-
-
- for (int k = FatherNode.elementNum + 1; k > position + 1; k--)
- {
- FatherNode.Pointer[k] = FatherNode.Pointer[k - 1];
- }
-
- for (int k = FatherNode.elementNum; k > position + 1; k--)
- {
- FatherNode.Elements[k] = FatherNode.Elements[k - 1];
- }
-
- FatherNode.Elements[position - 1] = NodeToBeSplit.Elements[NumPerNode / 2];
-
- FatherNode.elementNum += 1;
-
-
- }
|
