太喜欢这个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