1 軟體結構設計
1.1 軟體功能結構
用下圖所示的方式描述軟體的功能結構。
1.1.1 B-樹的查找
B-樹的查找過程：根據給定值查找結點和在結點的關鍵字中進行查找交叉進行。首先從根結點開始重複如下過程：
若比結點的第一個關鍵字小，則查找在該結點第一個指針指向的結點進行；若等于結點中某個關鍵字，則查找成功；若在兩個關鍵字之間，則查找在它們之間的指針指向的結點進行；若比該結點所有關鍵字大，則查找在該結點最後一個指針指向的結點進行；若查找已經到達某個葉結點，則說明給定值對應的資料記錄不存在，查找失敗。
1.1.2 B-樹的插入
插入的過程分兩步完成：
利用前述的B-樹的查找算法查找關鍵字的插入位置。若找到，則說明該關鍵字已經存在，直接傳回。否則查找操作必失敗于某個最低層的非終端結點上
判斷該結點是否還有空位置。即判斷該結點的關鍵字總數是否滿足n<=m-1。若滿足，則說明該結點還有空位置，直接把關鍵字k插入到該結點的合适位置上。若不滿足，說明該結點己沒有空位置，需要把結點分裂成兩個
分裂的方法是：
生成一新結點。把原結點上的關鍵字和k按升序排序後，從中間位置把關鍵字(不包括中間位置的關鍵字)分成兩部分。左部分所含關鍵字放在舊結點中，右部分所含關鍵字放在新結點中，中間位置的關鍵字連同新結點的存儲位置插入到父結點中。如果父結點的關鍵字個數也超過(m-1)，則要再分裂，再往上插。直至這個過程傳到根結點為止。
1.1.3 B-樹的删除找到被删關鍵字KEY在結點node中的位置idx —— 即：node->key[idx]為将被删除的關鍵字
找到以子結點child = node->child[idx]為根節點的子樹
再找到該子樹中的最大關鍵字KEY2，并将之拿去填充被删關鍵字KEY的位置，即：node->key[idx] = KEY2。 —— 子樹最大關鍵字MaxKey被拿走後，相當于子樹最大關鍵字的原位置被空缺了出來，也可在一定意義上了解為最終删除的子樹中的最大關鍵字
經過思考後可發現：以子結點child = node->child[idx]為根節點的子樹中最大關鍵字一定是在最底層某個結點中，不管要求被删的關鍵字KEY在哪個結點，均可視為最終被删的關鍵字都是在最底層結點中，而最底層結點的處理請參考2)的處理流程。
情況2：被删關鍵字KEY所在結點node為最底層結點時
删除操作前，結點node的關鍵字個數num>[m/2]-1時，則進行删除操作後，結點node關鍵字個數num仍然處在min <= num <= max的範圍之中，此時删除操作處理完成
删除操作前，結點node的關鍵字個數num=[m/2]-1時，則進行删除操作後，結點node的關鍵字個數num< ，顯然已經不符合B樹的特征，為了維護B樹的特征，此時需要進行的處理有2種情況：
如果結點node的兄弟結點brother的結點個數num>[m/2]-1時，則結點node可以向brother借用一個結點，但是需要以父結點的關鍵字為跳闆，此時删除操作處理完成
如果結點node的兄弟結點brother的節點個數num=[m/2]-1時，則将node和brother進行合并為一個結點new，同時需要将父結點parent中夾在node和brother之間的關鍵字插入到新結點new中。如果父結點parent中的一個關鍵字被插入到了新結點後，父結點parent的關鍵字個數num>[m/2]-1，則删除操作處理完成; 如果父結點parent的關鍵字個數num
1.2 插入關鍵字子產品名稱：InsertBTree(BTree &T, KeyType K, BTree q, int i)
初始條件：m階B-樹T及關鍵字K已存在；q，i為關鍵字K查找結果傳回
操作結果：在m階B-樹T上*q的key[i]與key[i+1]之間插入關鍵字K
1.3 生成新結點子產品名稱：NewRoot(BTree &T, KeyType x, BTree ap)
初始條件：m階B-樹T及關鍵字K已存在
操作結果：生成含資訊(T, x, ap)的新的根結點*T
1.4 結點分裂子產品名稱：split(BTree &q, BTree &ap)
初始條件：原結點q及新結點ap已存在
操作結果：将q->key[s+1..m]和q->ptr[s..m]移入新結點*ap關鍵字插入結點
1.5 查找關鍵字子產品名稱：SearchBTree(BTree T, KeyType K)
初始條件：m階B-樹T及關鍵字K已存在
操作結果：在m階B-樹T上查找關鍵字K，傳回結果(pt, i, tag)删除關鍵字
1.6 結點查找子產品名稱：SearchBTree(BTree T, KeyType K)
初始條件：m階B-樹T及關鍵字K已存在
操作結果：在m階B-樹T上找到并删除關鍵字K
1.7 合并結點子產品名稱：Merge_BTree(BTree &T, BTree left, BTree right, int mid)
初始條件：m階B-樹T及待删除的左右兄弟已存在
操作結果：結點q過小，對其進行必要的結點合并調整，使T仍是m階B-樹
1.8 删除關鍵字子產品名稱：DeleteBTree(BTree &T, BTree node, int i)
初始條件：m階B-樹T及待删除的位置已存在
操作結果：在m階B-樹T上找到并删除關鍵字K
2 資料結構設計
本項目所用線性表采用連結清單而非順序表，因為在處理過程中，插入和删除操作比較頻繁，而連結清單的這兩種操作無需移動結點，順序表則不然。也就是說，在前述情況下，連結清單比順序表的時間效率高。采用結構如下：
#definem3//B-樹的階，暫設為3
#definen17//關鍵字個數，暫設為16
//B-樹結點和B-樹的類型
typedefstructBTNode
{
intkeynum;//結點中關鍵字個數
structBTNode*parent;//指向雙親結點
KeyTypekey[m+1];//關鍵字向量，0号機關元未用
structBTNode*ptr[m+1];//子樹指針向量
}BTNode,*BTree;
//B-樹的查找結果類型
typedefstruct
{
BTNode*pt;//指向找到的結點
inti;//1...m,在結點中的關鍵字序号
inttag;//1:查找成功；0：查找失敗
}Result;
3 關鍵算法設計
3.1 節點查找函數算法函數名：SearchNode()
功能：在節點中查找關鍵字，傳回該關鍵字在節點中的位置
實作過程： Search ()函數代入的參數是指向關鍵字可能所在節點的指針p和關鍵字k，從該節點的第一個關鍵字找起，依次将要查找的關鍵字與節點中的關鍵字比較，傳回結果是所給關鍵字應該在節點中的位置
時間複雜度：O(n)，空間複雜度：O(0)
3.2 B-樹查找函數算法函數名稱：SearchBTree()
功能：從B-樹的根節點開始查找，查找所給關鍵字在該B-樹中的節點位置以及在所在節點中的位置，該函數傳回結果為Result類型，result.i表示關鍵字在節點中應該插入的位置，result.pt 表示關鍵字應該所在的節點，result.tag表示是否能夠在B-樹中查找到該關鍵字
實作過程：如圖所示，代入B-樹的根節點指針和要查找的關鍵字，從根節點開始，對每個節點使用SearchNode()函數，查找所給關鍵字所在的節點以及在該節點中的位置，如果該關鍵字已經存在于B-樹中，則傳回關鍵字所在節點、以及所在序号以及查找到的标志；如果不存在，則傳回應該插入的節點指針、在節點中的序号以及沒有找到的标志
時間複雜度：O(n)，空間複雜度：O(1)
3.3 結點插入函數函數名：Insert()
函數功能：将所給關鍵字插入到正确節點的正确位置
實作過程：如圖2.1.2(c)所示，代入指向所給關鍵字應該插入節點的指針、所給關鍵字、關鍵字應該插入的位置，然後再将該關鍵字插入到節點的正确位置上，節點關鍵字個數加1，傳回指向該節點的指針q
時間複雜度：O(n)，空間複雜度：O(0)
3.4 結點分裂函數函數名：split()
函數功能：當節點中關鍵字個數不符合要求時，進行節點分裂
實作過程：如圖2.1.2(d)所示，該函數帶入的參數是指向要産生分裂的節點的指針q、節點最小子樹個數s以及空指針ap，首先給ap配置設定BTree類型的空間，然後再将q中序号大于s的關鍵字插入到ap節點中，同時紙箱子樹的指針也插入到ap中，然後再分别計算q和ap中的關鍵字個數，對q和ap進行處理。最後傳回ap指針
時間複雜度：O(n)，空間複雜度：O(1)
3.5 結點建立函數函數名：NewRoot()
函數功能：建立新的節點，并且傳回指向該節點的指針
實作過程：該函數的代入參數是根節點T、指向子樹的指針p和ap以及關鍵字x，建立這個新節點，需要将關鍵字插入到該節點序号1的位置上，0号和1号的子樹指針分别指向空。如果p和ap不為空，則它們的父節點指向T節點。該函數最後傳回的是指針T
時間複雜度：O(1)，空間複雜度：O(0)
3.6 B-樹建立函數函數名：InsertBTree()
函數功能：從空樹開始建立B-樹，傳回的是B-樹的根指針
實作過程：該函數代入參數是根節點T、要插入到的節點q、要插入的關鍵字可以及在節點中應該插入的位置序号i。該函數從根節點開始建立B-樹，當根節點為空時，需要建立新的根節點并且插入關鍵字；如果根節點不為空，則直接插入即可，但是插入完成後，要考慮是否有節點分裂的情況産生，入伏哦需要進行節點分裂，則要調用split()函數分裂節點(根節點分裂以及子樹節點分裂的情況都考慮到)重新進行分裂插入。函數最後傳回指向B-樹根節點的指針T
時間複雜度：O(n)，空間複雜度：O(0)
4 測試