B+樹的代碼實現(xiàn)

1、B+樹的實現(xiàn)。這個B+樹是建立在操作系統(tǒng)的文件系統(tǒng)之上的,并沒有自己的 文件系統(tǒng)。B+樹的節(jié)點全部存儲在一個文件中。由于每個節(jié)點的大小是相同的，所 以我對每個節(jié)點進行編號 , 即每個節(jié)點的 id 。這樣每個節(jié)點在文件的字節(jié)位置就可以通過計 算 sizeof(BPNode)*(c-id - 1) 得到。所以,每個B+樹的節(jié)點有一個id屬性,就是記錄自己的標號。同時對B+樹建立一個結構體,這個結構體中的root屬性,用于指向讀入內存 后的樹的根節(jié)點。locate屬性記錄樹的根節(jié)點的在文件中的標號。num屬性記錄這棵樹的節(jié)點 個數(shù) , 每次新增一個節(jié)點都會加一。name屬性記錄用于存儲這個B+樹的文

2、件名(相對cpp文件所在的文件夾),fp 屬性用于記錄打開這個文件時的文件指針因為這個文件只記錄B+樹的節(jié)點，所以每次插入的時候只需要直接插入最后 ( 只有 num 個節(jié)點 , 同時新插入的節(jié)點的 id 是 num+1)暫時不考慮刪除節(jié)點的文件空間回收。打開文件是要注意打開模式 ,r+ 模式可以才可以隨意用 fseek() 定位之后,讀 或寫。fseek() 和 fread() 和 fwrite() 是用于二進制打開的文件 , 如果文本模式打開 , 可能出現(xiàn)問題 , 如: 覆蓋。#include #include #include #include #define T 3 /b+ 樹的度數(shù)#d

3、efine KeyType int#define Pointer int/ 節(jié)點結構體typedef struct BPNodeunsigned int id;/記錄這個節(jié)點在文件的中的編號unsigned int n; /記錄這個節(jié)點有多少個關鍵字int leaf; / 判斷是否為頁節(jié)點KeyType key2*T;/ 關鍵字 （及對應每個孩子節(jié)點的中關鍵字最小的關鍵字 ）Pointer child2*T;/指針, 記錄每個孩子在文件的第幾個位置Pointer next;/ 指針 , 記錄下一個兄弟BPNode,*P_BPNode;/ 樹的結構體typedef struct BPTreeP_

4、BPNode root;unsigned int locate;/ 記錄根節(jié)點的在文件中的標號 , 即 idunsigned int num; / 記錄更有多少個節(jié)點char name100; /用于存儲B+樹的節(jié)點文件的名字FILE *fp; /打開寫入name文件時,使用int start; / 最小的數(shù)據(jù)所在的葉節(jié)點BPTree,*P_BPTree;BPTree indexBPTree; / 全局變量 ,b+ 樹int writeNode(P_BPNode w)fseek(indexBPTree.fp, sizeof(BPNode)*(w-id - 1) + 2*sizeof(int),

5、 SEEK_SET);fwrite(w, sizeof(BPNode),1,indexBPTree.fp);return 0;int readNode(P_BPNode r, Pointer id)fseek(indexBPTree.fp, (sizeof(BPNode)*(id - 1) + 2*sizeof(int), SEEK_SET);fread(r, (sizeof(BPNode),1,indexBPTree.fp);return 0;int pNode(P_BPNode n);int createIndexBPTree (char *tableName, char *attr)/創(chuàng)

6、建B+樹,并進行相應的初始化，B+樹的結構體是一個全局變量P_BPNode root;indexBPTree.root = (P_BPNode)malloc(sizeof(BPNode);indexBPTree.num = 1;indexBPTree.start = 1;memcpy(indexBPT, .table, sizeof(.table);strcat(indexBPT, tableName);strcat(indexBPT, .);strcat(indexBPT, attr);puts(indexBPT

7、);root = indexBPTree.root;root-n = 0;root-leaf = 1;root-next = -1;root-id = 1;indexBPTree.locate = 1;indexBPTree.fp = fopen(indexBPT, wb);fwrite(&indexBPTree.num, sizeof(int),1,indexBPTree.fp); fwrite(&indexBPTree.locate, sizeof(int),1,indexBPTree.fp); writeNode(root);fclose(indexBPTree.fp);

8、/*printf(原始 :%dn, indexBPTree.root-next);memset(indexBPTree.root,0,sizeof(BPNode);prin tf(memset 后:dn, i ndexBPTree.root- next);indexBPTree.fp = fopen(indexBPT,r);fread(indexBPTree.root, sizeof(BPNode),1,indexBPTree.fp);fclose(indexBPTree.fp);printf( 讀取文件后 :%dn, indexBPTree.root-next);*/free

9、(root);indexBPTree.root = NULL;return 0;int splitBPNode (P_BPNode p, P_BPNode c, int i)/ 節(jié)點的分裂 , 要求 p 節(jié)點至少還能插入一個節(jié)點 ,c 節(jié)點是滿的 , 即 n 為 2*T;int j;P_BPNode b;b = (P_BPNode)malloc(sizeof(BPNode);b-leaf = c-leaf;b-n = T;b-id = indexBPTree.num+1; / 為 b 賦值 id 號, 用于表示該節(jié)點 , 同時 id 號就是這個節(jié)點在文件的位置b-next = c-next;

10、/ 為b的next賦值,即原來的c節(jié)點的next/ 將 c 節(jié)點的后半部分關鍵字復制給 bfor (j = 0; j keyj = c-keyj+T;b-childj = c-childj+T;/ 至此 b 節(jié)點的對應元素已經(jīng)建立好了 , 但還需要寫入文件indexBPTree.num+;c-n = T; /c 節(jié)點的關鍵字數(shù)目減半c-next = b-id;/ 將 p 節(jié)點的 i 之后的節(jié)點后移for (j = p-n - 1; j i; j-)p-keyj+1 = p-keyj;p-childj+1 = p-childj;/ 將 b 節(jié)點插入 p 中p-keyi+1 = b-key0;p-

11、childi+1 = b-id;p-n+; /p 關鍵字個數(shù)加一/ 寫入 pwriteNode(p);writeNode(c);writeNode(b);free(b);return 0;/splitBPNodeint insertBPNodeNotFull(P_BPNode s, KeyType k, unsigned int id) / 插入，要求s節(jié)點不是滿的int i = s-n-1;if (s-leaf)/ 葉節(jié)點, 找的合適的位置while (i = 0 & s-keyi k)s-keyi+1 = s-keyi;s-childi+1 = s-childi;i-;s-keyi+1 =

12、 k;s-childi+1 = id;s-n+;writeNode(s);elseP_BPNode tmp = (P_BPNode)malloc(sizeof(BPNode); while (i = 0 & s-keyi k)i-;if (i keyi = k;writeNode(s);readNode(tmp, s-childi); / 讀取對應的if (tmp-n = 2*T)splitBPNode(s, tmp, i);if (k s-keyi+1)i+;readNode(tmp, s-childi); /重新讀取 , 有待優(yōu)化insertBPNodeNotFull(tmp, k, id

13、);free(tmp);return 0;Pointer equalSearch(P_BPTree tree, KeyType k)/ 等值查詢 ,給出 key 值,查找對應的 id, 并返回。如果不存在該節(jié)點 , 返回 一個負數(shù) int i;int result;P_BPNode r;r = tree-root;if (k key0) /比最小的節(jié)點小return -1;P_BPNode tmp = (P_BPNode)malloc(sizeof(BPNode);while (1)i = r-n - 1;while (i = 0 & r-keyi k)i-;if (r-leaf) /是葉子,

14、 結束break;readNode(tmp, r-childi);r = tmp;/whileif (r-keyi childi;free(tmp);tmp = NULL;return result;/equalSearchint rangeSearch (P_BPTree tree, KeyType low, KeyType high)/ 范圍查找 ,key 值大于等于 low, 小于等于 high 。返回范圍內的個數(shù) unsigned int i;P_BPNode r = tree-root;Pointer *result;P_BPNode tmp = (P_BPNode)malloc(s

15、izeof(BPNode);才有能有結果if (high low) /low = highreturn 0;if (high key0)return 0;if (low key0)low = r-key0;while (1)i = r-n - 1;while (i = 0 & r-keyi low) i-;if (r-leaf) /是葉子 , 結束break;readNode(tmp, r-childi);r = tmp;/whileif (r-keyi low)i+;unsigned int num=100;result = (Pointer *)malloc(sizeof(Pointer)

16、*num);unsigned int j = 0;while (1)for (; i n & r-keyi = num)num += 100;realloc(result, sizeof(Pointer)*num);resultj+ = r-childi;/ printf(sid:%d iid: %d id:%dn, r-keyi,r-id, r-childi);if (i n | r-next next);r = tmp;i = 0;/whilefree(tmp);tmp = NULL;return j;/rangeSearchint insertKeyInBPTree (P_BPTree

17、tree, KeyType k, Pointer id)/ 向樹中插入節(jié)點P_BPNode r = tree-root;if (equalSearch(tree, k) 0)printf( 元素已存在 !);return -1;if (tree-root-n = 2*T)/ 根節(jié)點滿了 , 重新分配根節(jié)點 , 并進行初始化P_BPNode s = (P_BPNode)malloc(sizeof(BPNode);s-leaf = 0;s-n = 1;s-key0 = r-key0;s-child0 = r-id;s-id = tree-num + 1;s-next = -1;/ 將新的根寫入磁盤

18、writeNode(s);tree-num+;writeNode(r);splitBPNode (s, r, 0);(tree-/ 根變?yōu)?s, 所以將新根 copy 到 tree-root 指針所指向的內存 root 將一直指向一片開辟了的內存 , 且時刻保存樹根的整個節(jié)點 )memcpy(tree-root, s, sizeof(BPNode);tree-locate = s-id;insertBPNodeNotFull(s, k, id);free(s); / 釋放內存elseinsertBPNodeNotFull(r, k, id);return 0;/insertBPNodeint

19、initIndexBPTree(char *tableName, char *attr)/初始化BPTree,打開相應文件，fp記錄;為root分配內存可以存儲一個節(jié) 點的內存 , 并讀入根節(jié)點indexBPTree.root = (P_BPNode)malloc(sizeof(BPNode);indexBPTree.start = 1;memcpy(indexBPT, .table, sizeof(.table);strcat(indexBPT, tableName);strcat(indexBPT, .);strcat(indexBPTree

20、.name, attr);indexBPTree.fp = fopen(indexBPT, rb+); fread(&indexBPTree.num,sizeof(int),1, indexBPTree.fp); fread(&indexBPTree.locate,sizeof(int),1,indexBPTree.fp); readNode(indexBPTree.root, indexBPTree.locate); return 0;int endBPTree()/ 將建立的樹結束fseek(indexBPTree.fp, 0, SEEK_SET);fwrite(&inde

21、xBPTree.num, sizeof(int),1,indexBPTree.fp); fwrite(&indexBPTree.locate, sizeof(int),1,indexBPTree.fp); free(indexBPTree.root);fclose(indexBPTree.fp);return 0;int pNode(P_BPNode n)/ 輸出節(jié)點printf(%s id:%d next:%d 個數(shù):dn ,n-leaf?是葉節(jié)點:不是葉節(jié)點, n-id, n-next, n-n);for(unsigned int i = 0; i n; i+)printf( key%d:

22、%dt,i,n-keyi);puts();for(i = 0; i n; i+)printf(child%d:%dt,i,n-childi);puts();return 0;/pNodeint replaceKeyInBPTree(P_BPTree tree, KeyType oldkey, KeyTypenewkey)/ 將 oldkey 替換為 newkeyP_BPNode r = tree-root;int i;P_BPNode tmp = (P_BPNode)malloc(sizeof(BPNode);while (1)i = r-n - 1;while (i = 0 & r-keyi

23、 oldkey)i-;if (r-keyi = oldkey)r-keyi = newkey;writeNode(r);if (r-leaf)break;readNode(tmp, r-childi);r = tmp;free(tmp);return 0;指向 xint adjustToDel(P_BPNode p, P_BPNode x, unsigned int i) /p 的父節(jié)點 ,i 指的是 ,x 是 p 的下標unsigned int j;P_BPNode left = NULL;P_BPNode right = NULL;P_BPNode tmp = (P_BPNode)mall

24、oc(sizeof(BPNode);if (i 0 ) /x有左兄弟readNode(tmp, p-childi-1);left = tmp;if (left-n T)for (j = x-n; j 0; j-)x-keyj = x-keyj-1;x-childj = x-childj-1;x-n+;x-key0 = left-keyleft-n-1;x-child0 = left-childleft-n-1;writeNode(x);left-n-;writeNode(left);p-keyi = x-key0;writeNode(p);return 0;/ifif (i n - 1) /x

25、有又兄弟readNode(tmp, p-childi+1);right = tmp;left = NULL;if (right-n T)x-keyx-n = right-key0;x-childx-n = right-child0;x-n+;writeNode(x);for (j = 0; j n-1; j+)right-keyj = right-keyj+1;right-childj = right-childj+1;right-n-;writeNode(right);p-keyi+1 = right-key0;writeNode(p);return 0;if (left = tmp)for

26、 (j = 0; j keyT+j = x-keyj; left-childT+j = x-childj;left-n += T;left-next = x-next;writeNode(left);for (j = i; j n - 1; j+)p-keyj = p-keyj+1;p-childj = p-childj+1;p-n-;writeNode(p);memcpy(x, left, sizeof(BPNode);elsefor (j = 0; j keyT+j = right-keyj;x-childT+j = right-childj;x-n += T;x-next = right

27、-next;writeNode(x);for (j = i+1; j n -1; j+)p-keyj = p-keyj+1;p-childj = p-childj+1;p-n-;writeNode(p);free(tmp);left = right = tmp = NULL;return 0;/調用這個函數(shù)是，參數(shù)節(jié)點P,必須滿足相應的要求：/如果P是根節(jié)點且是葉子節(jié)點，則沒有要求/如果p是根節(jié)點(非葉)，則p節(jié)點的子節(jié)點個數(shù)不小于2(B+樹本身就滿 足這個要求 ) 。/ 如果 P 是非根節(jié)點 , 則節(jié)點 P 的子節(jié)點個數(shù)必須大于 TKeyType delKeyInBPNode(P_BPNod

28、e p, KeyType k)/ 以這個節(jié)點為起點 , 找到 k 并刪除。要求確保 k 存在unsigned int i;unsigned int j;i = p-n - 1;while (p-keyi k)i-;/ 是葉節(jié)點 ( 如果 p 本身又是根節(jié)點 , 則這個是情況 )if (p-leaf)for (j = i; j n-1; j+)p-keyj = p-keyj+1;p-childj = p-childj+1;/whilep-n-;writeNode(p);if (i = 0) /說明刪除的關鍵字是該節(jié)點中最小的replaceKeyInBPTree(&indexBPTree, k,

29、p-keyi); return p-keyi;/if/p 是內節(jié)點P_BPNode x;x = (P_BPNode)malloc(sizeof(BPNode);readNode(x, p-childi);if (x-n T) /x 的子節(jié)點的個數(shù)大于 T, 則直接調用return delKeyInBPNode(x, k);else /x 的子節(jié)點的個數(shù)等于 T, 需要調整adjustToDel(p, x, i);return delKeyInBPNode(x, k);/else/delKeyInNodeint delKeyInBPTree(P_BPTree tree, KeyType k)/1

30、. 如果一個根節(jié)點同時又是葉節(jié)點 , 則沒有子節(jié)點限制 ( 這個子節(jié)點指向的 不再是樹的節(jié)點 )/2.非葉根節(jié)點至少保持有兩個子節(jié)點，其他的節(jié)點至少有T個子節(jié)點。if (equalSearch(tree, k) root;delKeyInBPNode(r, k);if (r-n = 1)tree-locate = r-child0;更換根節(jié)點readNode(tree-root,r-child0); / tree-num-;/ 還應該將原始的根節(jié)點從磁盤上刪除 r = NULL;return 0;/delKeyInBPTreeint main ()unsigned int i = 1;/ cr

31、eateIndexBPTree(student,sid); initIndexBPTree(student, sid);/*insertKeyInBPTree(&indexBPTree, 50, i+);insertKeyInBPTree(&indexBPTree, 30, i+);insertKeyInBPTree(&indexBPTree, 60, i+);insertKeyInBPTree(&indexBPTree, 10, i+);insertKeyInBPTree(&indexBPTree, 90, i+);insertKeyInBPTree(&indexBPTree, 40, i+

32、);insertKeyInBPTree(&indexBPTree, 100, i+);insertKeyInBPTree(&indexBPTree, 110, i+);insertKeyInBPTree(&indexBPTree, 150, i+);insertKeyInBPTree(&indexBPTree, 200, i+);insertKeyInBPTree(&indexBPTree, 0, i+);insertKeyInBPTree(&indexBPTree, 49, i+);insertKeyInBPTree(&indexBPTree, 45, i+);insertKeyInBPTr

33、ee(&indexBPTree, -1, i+);insertKeyInBPTree(&indexBPTree, 210, i+);insertKeyInBPTree(&indexBPTree, 220, i+);insertKeyInBPTree(&indexBPTree, 230, i+); insertKeyInBPTree(&indexBPTree, 240, i+);insertKeyInBPTree(&indexBPTree, 250, i+); insertKeyInBPTree(&indexBPTree, 260, i+); insertKeyInBPTree(&indexBPTree, 270, i+); insertKeyInBPTree(&indexBPTree, 280, i+); insertKeyInBPTree(&indexBPTree, 290, i+); insertKeyInBPTree(&indexBPTree, 300, i+); insertKeyInBPTree(&indexBPTree,