太喜歡這個Post代碼的功能了，先發(fā)一個我最近寫的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????????//?此函數(shù)專門用來創(chuàng)建大多數(shù)情況下主鍵僅包含一個屬性的情況
?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????????//?找到應(yīng)該插入的節(jié)點
?33????????BTNode?inPoint?=?search(keyValue,?root);
?34????????//?在葉節(jié)點中找到空閑空間，有的話就把鍵放在那里
?35????????if?(!inPoint.isFull())?{
?36????????????//?插入keyValue到inPoint
?37????????????inPoint.insert(keyValue,?pointer);
?38????????????return;
?39????????}
?40????????//?如果在適當(dāng)?shù)娜~節(jié)點沒有空間，就把該葉節(jié)點分裂成兩個，并正確分配鍵值
?41????????BTNode?theNew?=?separateLeaf(keyValue,?pointer,?inPoint);
?42????????//?如果分裂的是根節(jié)點，就新建一個新的根節(jié)點將新建的節(jié)點作為他的字節(jié)點
?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????????//?將新建立的節(jié)點的指針插入到上層節(jié)點
?68????????insertToUpperNode(inPoint.getHeader().getParent(),?theNew,?theNew
?69????????????????.getKey()[0]);
?70????}
?71
?72????/**?*//**
?73?????*?這個函數(shù)把頁節(jié)點分裂后產(chǎn)生的新的節(jié)點插入到上層的非頁節(jié)點中。
?74?????*?
?75?????*?@param?upperNodeID
?76?????*????????????接納新鍵的上層節(jié)點
?77?????*?@param?lowerNode
?78?????*????????????新鍵值的指針，此指針指向的節(jié)點的第一個鍵值大于等于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????????//?上層節(jié)點有空位就直接插入
?93????????if?(!upper.isFull())?{
?94????????????upper.insert(keyValue,?new?Pointer(lowerNode.getPageID()));
?95????????????//?重置父節(jié)點指針
?96????????????lowerNode.parentRedirect(upper.getPageID());
?97????????????lowerNode.flush();
?98????????????return;
?99????????}
100
101????????//?上層如果沒有空位，就分裂結(jié)點
102????????//?進(jìn)行分裂和插入操作
103????????separateInnerNode(keyValue,?lowerNode,?upper);
104
105????}
106
107????/**?*//**
108?????*?將對應(yīng)的內(nèi)部節(jié)點進(jìn)行分裂并正確分配鍵值，返回新建的節(jié)點?這個分裂的算法還有點問題，目前認(rèn)為B樹擴(kuò)展節(jié)點不可超過3層
109?????*?
110?????*?@param?key
111?????*????????????要插入的鍵值
112?????*?@param?pointer
113?????*????????????要插入的指針，此指針指向的節(jié)點的第一個鍵大于等于key
114?????*?@param?cNode
115?????*????????????要被分裂的節(jié)點，?the?Node?to?be?cracked
116?????*?@return
117?????*/
118????private?void?separateInnerNode(Keys?key,?BTNode?lowNode,?BTNode?cNode)?{
119????????int?cap?=?root.getCapacity();?//?得到一個節(jié)點的最大容量
120????????//?被分裂節(jié)點的全部鍵值
121????????Keys[]?k?=?cNode.getKey();
122????????Pointer[]?p?=?cNode.getPtr();
123
124????????//?拷貝所有的鍵-指針對到緩沖區(qū)
125????????//?并且找到插入點
126????????Keys[]?tk?=?new?Keys[cap?+?1];
127????????Pointer[]?tp?=?new?Pointer[cap?+?1?+?1];
128????????int?pos?=?cap;?//?插入點標(biāo)記，默認(rèn)插入到末尾
129????????boolean?not_found?=?true;?//?找到標(biāo)記
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????????//?挪動，為新插入的節(jié)點藤一個位子
141????????//?插入緩沖區(qū)
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????????//?重置下層節(jié)點父節(jié)點
163????????if?(pos?<?old_amount)
164????????????lowNode.parentRedirect(cNode.getPageID());
165????????else
166????????????lowNode.parentRedirect(newNode.getPageID());
167????????lowNode.flush();
168
169????????//?如果被分裂的節(jié)點是根節(jié)點，重新建立根節(jié)點
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????????????//?設(shè)置根節(jié)點指針
175????????????newRoot.getPtr()[0]?=?new?Pointer(cNode.getPageID());
176????????????newRoot.getPtr()[1]?=?new?Pointer(newNode.getPageID());
177????????????//?重置父節(jié)點
178????????????cNode.parentRedirect(newRoot.getPageID());
179????????????newNode.parentRedirect(newRoot.getPageID());
180????????????//?設(shè)置根節(jié)點鍵值
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????????//?否則，將多出來的鍵向上層節(jié)點插入。
194????????newNode.parentRedirect(cNode.getHeader().getParent());
195????????newNode.flush();
196????????insertToUpperNode(cNode.getHeader().getParent(),?newNode,
197????????????????tk[old_amount]);
198????????return;
199????}
200
201????/**?*//**?給出搜索鍵值所在的或應(yīng)該插入的葉結(jié)點的引用?*/
202????//?TEMP?此函數(shù)為了測試而暫時置為公有
203????public?BTNode?search(Keys?keyValue,?BTNode?curPage)?{
204????????//?如果當(dāng)前節(jié)點是葉結(jié)點，那么返回
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????????//?否則逐一掃描鍵值數(shù)組
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????????????//?如果是結(jié)點中最后一個鍵，那么搜索ptr[i+1]子樹，因為指針比結(jié)點多一個
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????/**?*//**?分裂葉子結(jié)點，返回新的頁的引用?*/
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????????//?臨時數(shù)組，拷貝所有的鍵值
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????????????//?這里不可能出現(xiàn)等于的情況，因為鍵值不可以重復(fù)
243????????????if?(flag?&&?key[i].compareTo(keyValue)?>?0)?{
244????????????????pos?=?i;
245????????????????flag?=?false;
246????????????}
247????????}
248????????tempPtr[capacity]?=?ptr[capacity];
249
250????????//?為新插入的節(jié)點藤位置，然后插入
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????????//?產(chǎn)生新節(jié)點
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????????//?計算鍵值數(shù)量分配
268????????oldnode?=?(capacity?+?1)?/?2;
269????????newnode?=?(capacity?+?1)?-?oldnode;
270
271????????//?重新為分裂前的節(jié)點賦值
272????????curPage.keyCopy(tempKey,?0,?oldnode);
273????????curPage.pointerCopy(tempPtr,?0,?oldnode,
274????????????????new?Pointer(theNew.getPageID()));
275
276????????//?為新節(jié)點的賦值
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????/**?*//**返回搜索的鍵值對應(yīng)的RID?如果鍵值不存在，也返回RID?但是RID內(nèi)的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?節(jié)點，外部調(diào)用一般給根節(jié)點
344?????*?@param?level?節(jié)點n所在的層數(shù)，root的層數(shù)為1，也即本樹第一層是根節(jié)點
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