太喜歡這個Post代碼的功能了，先發一個我最近寫的B+樹的代碼試驗一下，哈哈……
??1
package?logicLayer.index;
??2
??3import?global.GlobalConst;
??4import?logicLayer.heapFile.RID;
??5
??6
public?class?BTree?
{
??7
??8????BTNode?root?=?null;
??9
?10
????/**?*//**
?11?????*?*Use?the?pageID?of?the?root?node?can?creat?a?B+?Tree?this?constructor?is
?12?????*?uesd?to?search.?When?the?user?want?to?search,?he?know?the?root?pageID?of
?13?????*?the?B+?Tree.
?14
?????*/
?15????public?BTree(int?attrType,?int?attrLength)?{
?16????????//?此函數專門用來創建大多數情況下主鍵僅包含一個屬性的情況
?17????????int[]?at?=?new?int[1];
?18????????at[0]?=?attrType;
?19????????int[]?al?=?new?int[1];
?20????????al[0]?=?attrLength;
?21????????root?=?new?BTNode(GlobalConst.LEAF,?1,?at,?al);
?22????????root.pinNode();
?23????}
?24
?25????public?BTree(int?attrNum,?int[]?attrType,?int[]?attrLength)?{
?26????????root?=?new?BTNode(GlobalConst.LEAF,?attrNum,?attrType,?attrLength);
?27????????root.pinNode();
?28????}
?29
?30????public?void?insert(Keys?keyValue,?Pointer?pointer)?{
?31
?32????????//?找到應該插入的節點
?33????????BTNode?inPoint?=?search(keyValue,?root);
?34????????//?在葉節點中找到空閑空間，有的話就把鍵放在那里
?35????????if?(!inPoint.isFull())?{
?36????????????//?插入keyValue到inPoint
?37????????????inPoint.insert(keyValue,?pointer);
?38????????????return;
?39????????}
?40????????//?如果在適當的葉節點沒有空間，就把該葉節點分裂成兩個，并正確分配鍵值
?41????????BTNode?theNew?=?separateLeaf(keyValue,?pointer,?inPoint);
?42????????//?如果分裂的是根節點，就新建一個新的根節點將新建的節點作為他的字節點
?43????????if?(inPoint?==?root)?{
?44????????????//?nodeInMem.remove(new?Integer(root.pageID));
?45????????????root.unpinNode();
?46????????????root?=?new?BTNode(GlobalConst.NONLEAF,?inPoint.getHeader()
?47????????????????????.getAtt_num(),?inPoint.getHeader().getKey_type(),?inPoint
?48????????????????????.getHeader().getKeyLenArray());
?49????????????root.pinNode();
?50????????????Keys[]?key?=?root.getKey();
?51????????????Pointer[]?ptr?=?root.getPtr();
?52????????????Keys[]?thenewkey?=?theNew.getKey();
?53
?54????????????//?nodeInMem.put(new?Integer(root.pageID),?root);
?55????????????key[0]?=?thenewkey[0];
?56????????????ptr[0]?=?new?Pointer(inPoint.getPageID());
?57????????????ptr[1]?=?new?Pointer(theNew.getPageID());
?58
?59????????????inPoint.parentRedirect(root.getPageID());
?60????????????theNew.parentRedirect(root.getPageID());
?61????????????root.getHeader().amountInc();
?62????????????root.flush();
?63????????????inPoint.flush();
?64????????????theNew.flush();
?65????????????return;
?66????????}
?67????????//?將新建立的節點的指針插入到上層節點
?68????????insertToUpperNode(inPoint.getHeader().getParent(),?theNew,?theNew
?69????????????????.getKey()[0]);
?70????}
?71
?72????/**?*//**
?73?????*?這個函數把頁節點分裂后產生的新的節點插入到上層的非頁節點中。
?74?????*?
?75?????*?@param?upperNodeID
?76?????*????????????接納新鍵的上層節點
?77?????*?@param?lowerNode
?78?????*????????????新鍵值的指針，此指針指向的節點的第一個鍵值大于等于keyValue
?79?????*?@param?keyValue
?80?????*????????????新的鍵值
?81?????*/
?82????private?void?insertToUpperNode(int?upperNodeID,?BTNode?lowerNode,
?83????????????Keys?keyValue)?{
?84
?85????????BTNode?upper;//?=(BTNode)nodeInMem.get(new?Integer(upperNodeID));
?86????????if?(upperNodeID?==?root.getPageID())?{
?87????????????upper?=?root;
?88????????}?else?{
?89????????????upper?=?BTNode.loadNode(upperNodeID);
?90????????}
?91
?92????????//?上層節點有空位就直接插入
?93????????if?(!upper.isFull())?{
?94????????????upper.insert(keyValue,?new?Pointer(lowerNode.getPageID()));
?95????????????//?重置父節點指針
?96????????????lowerNode.parentRedirect(upper.getPageID());
?97????????????lowerNode.flush();
?98????????????return;
?99????????}
100
101????????//?上層如果沒有空位，就分裂結點
102????????//?進行分裂和插入操作
103????????separateInnerNode(keyValue,?lowerNode,?upper);
104
105????}
106
107????/**?*//**
108?????*?將對應的內部節點進行分裂并正確分配鍵值，返回新建的節點?這個分裂的算法還有點問題，目前認為B樹擴展節點不可超過3層
109?????*?
110?????*?@param?key
111?????*????????????要插入的鍵值
112?????*?@param?pointer
113?????*????????????要插入的指針，此指針指向的節點的第一個鍵大于等于key
114?????*?@param?cNode
115?????*????????????要被分裂的節點，?the?Node?to?be?cracked
116?????*?@return
117?????*/
118????private?void?separateInnerNode(Keys?key,?BTNode?lowNode,?BTNode?cNode)?{
119????????int?cap?=?root.getCapacity();?//?得到一個節點的最大容量
120????????//?被分裂節點的全部鍵值
121????????Keys[]?k?=?cNode.getKey();
122????????Pointer[]?p?=?cNode.getPtr();
123
124????????//?拷貝所有的鍵-指針對到緩沖區
125????????//?并且找到插入點
126????????Keys[]?tk?=?new?Keys[cap?+?1];
127????????Pointer[]?tp?=?new?Pointer[cap?+?1?+?1];
128????????int?pos?=?cap;?//?插入點標記，默認插入到末尾
129????????boolean?not_found?=?true;?//?找到標記
130????????for?(int?i?=?0;?i?<?cap;?i++)?{
131????????????tk[i]?=?k[i];
132????????????tp[i]?=?p[i];
133????????????if?(not_found?&&?k[i].compareTo(key)?>?0)?{
134????????????????pos?=?i;
135????????????????not_found?=?false;
136????????????}
137????????}
138????????tp[cap]?=?p[cap];
139
140????????//?挪動，為新插入的節點藤一個位子
141????????//?插入緩沖區
142????????for?(int?i?=?cap?-?1;?i?>?pos?-?1;?i--)?{
143????????????tk[i?+?1]?=?tk[i];
144????????????tp[i?+?2]?=?tp[i?+?1];
145????????}
146????????tk[pos]?=?key;
147????????tp[pos?+?1]?=?new?Pointer(lowNode.getPageID());
148
149????????//?重新分配
150????????BTNode?newNode?=?new?BTNode(GlobalConst.NONLEAF,?root.getHeader()
151????????????????.getAtt_num(),?root.getHeader().getKey_type(),?root.getHeader()
152????????????????.getKeyLenArray());
153????????int?old_amount?=?cap?/?2;
154????????//?int?new_amount?=?cap?-?old_amount;
155
156????????cNode.keyCopy(tk,?0,?old_amount);
157????????cNode.pointerCopy(tp,?0,?old_amount?+?1);
158
159????????newNode.keyCopy(tk,?old_amount?+?1,?cap?+?1);
160????????newNode.pointerCopy(tp,?old_amount?+?1,?cap?+?1?+?1);
161
162????????//?重置下層節點父節點
163????????if?(pos?<?old_amount)
164????????????lowNode.parentRedirect(cNode.getPageID());
165????????else
166????????????lowNode.parentRedirect(newNode.getPageID());
167????????lowNode.flush();
168
169????????//?如果被分裂的節點是根節點，重新建立根節點
170????????if?(cNode?==?root)?{
171????????????BTNode?newRoot?=?new?BTNode(GlobalConst.NONLEAF,?root.getHeader()
172????????????????????.getAtt_num(),?root.getHeader().getKey_type(),?root
173????????????????????.getHeader().getKeyLenArray());
174????????????//?設置根節點指針
175????????????newRoot.getPtr()[0]?=?new?Pointer(cNode.getPageID());
176????????????newRoot.getPtr()[1]?=?new?Pointer(newNode.getPageID());
177????????????//?重置父節點
178????????????cNode.parentRedirect(newRoot.getPageID());
179????????????newNode.parentRedirect(newRoot.getPageID());
180????????????//?設置根節點鍵值
181????????????newRoot.getHeader().setAmount(1);
182????????????newRoot.getKey()[0]?=?tk[old_amount];
183????????????//?nodeInMem.remove(new?Integer(root.pageID));
184????????????root.unpinNode();
185????????????root?=?newRoot;
186????????????root.pinNode();
187????????????newRoot.flush();
188????????????cNode.flush();
189????????????newNode.flush();
190????????????return;
191????????}
192
193????????//?否則，將多出來的鍵向上層節點插入。
194????????newNode.parentRedirect(cNode.getHeader().getParent());
195????????newNode.flush();
196????????insertToUpperNode(cNode.getHeader().getParent(),?newNode,
197????????????????tk[old_amount]);
198????????return;
199????}
200
201????/**?*//**?給出搜索鍵值所在的或應該插入的葉結點的引用?*/
202????//?TEMP?此函數為了測試而暫時置為公有
203????public?BTNode?search(Keys?keyValue,?BTNode?curPage)?{
204????????//?如果當前節點是葉結點，那么返回
205????????if?(curPage.isLeaf())?{
206????????????return?curPage;
207????????}
208
209????????int?amount?=?curPage.getKeyAmount();
210????????Keys[]?key?=?curPage.getKey();
211????????Pointer[]?ptr?=?curPage.getPtr();
212
213????????//?否則逐一掃描鍵值數組
214????????for?(int?i?=?0;?i?<?amount;?i++)?{
215????????????//?如果比key[i]要小，那么搜索ptr[i]指向的子樹
216????????????if?(keyValue.compareTo(key[i])?<?0)?{
217????????????????BTNode?next?=?BTNode.loadNode(ptr[i].getPageId());
218????????????????return?search(keyValue,?next);
219????????????}
220????????????//?如果是結點中最后一個鍵，那么搜索ptr[i+1]子樹，因為指針比結點多一個
221????????????if?(i?==?amount?-?1)?{
222????????????????BTNode?next?=?BTNode.loadNode(ptr[i?+?1].getPageId());
223????????????????return?search(keyValue,?next);
224????????????}
225????????}
226????????return?null;
227????}
228
229????/**?*//**?分裂葉子結點，返回新的頁的引用?*/
230????private?BTNode?separateLeaf(Keys?keyValue,?Pointer?pointer,?BTNode?curPage)?{
231????????int?capacity?=?root.getCapacity();
232????????Keys[]?key?=?curPage.getKey();
233????????Pointer[]?ptr?=?curPage.getPtr();
234????????//?臨時數組，拷貝所有的鍵值
235????????Keys[]?tempKey?=?new?Keys[capacity?+?1];
236????????Pointer[]?tempPtr?=?new?Pointer[capacity?+?1?+?1];
237????????int?pos?=?capacity;
238????????boolean?flag?=?true;
239????????for?(int?i?=?0;?i?<?capacity;?i++)?{
240????????????tempKey[i]?=?key[i];
241????????????tempPtr[i]?=?ptr[i];
242????????????//?這里不可能出現等于的情況，因為鍵值不可以重復
243????????????if?(flag?&&?key[i].compareTo(keyValue)?>?0)?{
244????????????????pos?=?i;
245????????????????flag?=?false;
246????????????}
247????????}
248????????tempPtr[capacity]?=?ptr[capacity];
249
250????????//?為新插入的節點藤位置，然后插入
251????????tempPtr[capacity?+?1]?=?tempPtr[capacity];
252????????if?(pos?!=?capacity)?{
253????????????for?(int?i?=?capacity;?i?>?pos;?i--)?{
254????????????????tempKey[i]?=?tempKey[i?-?1];
255????????????????tempPtr[i]?=?tempPtr[i?-?1];
256????????????}
257????????}
258????????tempKey[pos]?=?keyValue;
259????????tempPtr[pos]?=?pointer;
260
261????????//?產生新節點
262????????BTNode?theNew?=?new?BTNode(GlobalConst.LEAF,?curPage.getHeader()
263????????????????.getAtt_num(),?curPage.getHeader().getKey_type(),?curPage
264????????????????.getHeader().getKeyLenArray());
265
266????????int?oldnode,?newnode;
267????????//?計算鍵值數量分配
268????????oldnode?=?(capacity?+?1)?/?2;
269????????newnode?=?(capacity?+?1)?-?oldnode;
270
271????????//?重新為分裂前的節點賦值
272????????curPage.keyCopy(tempKey,?0,?oldnode);
273????????curPage.pointerCopy(tempPtr,?0,?oldnode,
274????????????????new?Pointer(theNew.getPageID()));
275
276????????//?為新節點的賦值
277????????theNew.keyCopy(tempKey,?oldnode,?oldnode?+?newnode);
278????????theNew.pointerCopy(tempPtr,?oldnode,?oldnode?+?newnode,
279????????????????tempPtr[capacity?+?1]);
280
281????????return?theNew;
282????}
283
284????private?BTree()?{
285
286????}
287
288????/**?*//**
289?????*?Load?a?existed?B+?Tree.
290?????*?
291?????*?@param?root
292?????*????????????the?user?must?tell?out?the?pageID?of?the?root?page.
293?????*/
294????public?static?BTree?loadBTree(int?rootID)?{
295????????BTree?t?=?new?BTree();
296????????t.root?=?BTNode.loadNode(rootID);
297????????t.root.pinNode();
298????????return?t;
299????}
300
301????/**?*//**返回搜索的鍵值對應的RID?如果鍵值不存在，也返回RID?但是RID內的PageID和SlotNo的值均為-1
302?????*?
303?????*?@param?keyValue?搜索的鍵值
304?????*?@return?RID?返回RID，如果不存在，返回的為RID（-1，-1）
305?????*/
306????public?RID?search(Keys?keyValue)?{
307????????BTNode?keyNode?=?search(keyValue,?root);
308????????RID?r?=?keyNode.searchKey(keyValue);
309????????return?r;
310????}
311
312????/**?*//**?刪除一個鍵值?如果給的鍵不存在，則不會抱錯
313?????*?
314?????*?@param?keyValue??要刪除的鍵
315?????*/?
316????public?void?delete(Keys?keyValue)?{
317????????BTNode?keyNode?=?search(keyValue,?root);
318????????keyNode.deleteKey(keyValue);
319????}
320
321????/**?*//**?Just?for?test?*/
322????public?void?printTree()?{
323????????for?(int?i?=?0;?i?<?root.getKeyAmount();?i++)?{
324????????????System.out.print("("?+?root.getKey()[i].toString()?+?","
325????????????????????+?root.getPtr()[i].getPageId()?+?")");
326????????}
327????????System.out.println("");
328????????if?(root.isLeaf())
329????????????return;
330????????for?(int?i?=?0;?i?<?root.getKeyAmount()?+?1;?i++)?{
331????????????BTNode?leaf?=?BTNode.loadNode(root.getPtr()[i].getPageId());
332????????????for?(int?j?=?0;?j?<?leaf.getKeyAmount();?j++)?{
333????????????????System.out.print("("?+?leaf.getKey()[j].toString()?+?","
334????????????????????????+?leaf.getPtr()[j].getPageId()?+?")");
335????????????}
336????????????System.out.println("");
337????????????System.out.println("***************************");
338????????}
339????}
340
341????/**?*//**遞歸打印整棵B+Tree
342?????*?僅作測試用途
343?????*?@param?n?節點，外部調用一般給根節點
344?????*?@param?level?節點n所在的層數，root的層數為1，也即本樹第一層是根節點
345?????*/
346????public?void?betterPrint(BTNode?n,?int?level)?{
347????????System.out.println("level--->"?+?level);
348????????for?(int?i?=?0;?i?<?n.getKeyAmount();?i++)?{
349????????????System.out.print("("?+?n.getKey()[i].toString()?+?","
350????????????????????+?n.getPtr()[i].getPageId()?+?")");
351????????}
352
353????????if?(n.isLeaf())
354????????????return;
355
356????????System.out.println("");
357????????//?System.out.println("level--->"+(index+1));
358????????for?(int?i?=?0;?i?<?n.getKeyAmount()?+?1;?i++)?{
359????????????BTNode?leaf?=?BTNode.loadNode(n.getPtr()[i].getPageId());
360????????????betterPrint(leaf,?level?+?1);
361????????????System.out.println("");
362????????????System.out.println("***************************");
363????????}
364????}
365
366????public?int?getRoot()?{
367????????return?root.getPageID();
368????}
369????//?private?Hashtable?nodeInMem?=?new?Hashtable();
370
}
371