代码4.分裂节点
通过概念和代码不难看出，节点的分裂相对比较消耗IO，这也是为什么SQL Server中需要一些最佳实现比如不用GUID做聚集索引，或是设置填充因子等来减少页分裂。
而如果需要插入元素的节点不满，则不需要页分裂，则需要从根开始查找，找到需要被插入的节点，如代码5所示。
-
- public void BTreeInsertNotFull(TreeNode<T> Node, T KeyWord)
- {
- int i=Node.elementNum;
-
- if (Node.IsLeaf)
- {
-
- while (i >= 1 && KeyWord.CompareTo(Node.Elements[i - 1]) < 0)
- {
- Node.Elements[i] = Node.Elements[i - 1];
- i -= 1;
- }
- Node.Elements[i - 1] = KeyWord;
- Node.elementNum += 1;
-
- }
-
- else
- {
- while (i >= 1 && KeyWord.CompareTo(Node.Elements[i - 1]) < 0)
- {
- i -= 1;
- }
-
- if (Node.Pointer[i].elementNum == NumPerNode)
- {
-
- BTreeSplitNode(Node, i, Node.Pointer[i]);
-
- }
- if (KeyWord.CompareTo(Node.Elements[i - 1]) > 0)
- {
-
- i += 1;
- }
-
- BTreeInsertNotFull(Node.Pointer[i], KeyWord);
-
-
- }
- }
|
代码5.插入
通过代码5可以看出，我们没有进行任何迭代。而是从根节点开始遇到满的节点直接进行分裂。从而减少了性能损失。
再将根节点分裂的特殊情况考虑进去，我们从而将插入操作合为一个函数，如代码6所示。
- public void BtreeInsert(T KeyWord)
- {
- if (RootNode.elementNum == NumPerNode)
- {
-
-
- TreeNode<T> newRoot = new TreeNode<T>();
- newRoot.elementNum = 0;
- newRoot.IsLeaf = false;
-
- BTreeSplitNode(newRoot, 1, RootNode);
-
- BTreeInsertNotFull(newRoot, KeyWord);
-
- RootNode = newRoot;
- }
- else
- {
-
- BTreeInsertNotFull(RootNode, KeyWord);
- }
- }
|
