File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\index\PageBtreeNode.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.index;
8
9 import org.h2.api.DatabaseEventListener;
10 import org.h2.constant.ErrorCode;
11 import org.h2.constant.SysProperties;
12 import org.h2.engine.Session;
13 import org.h2.message.DbException;
14 import org.h2.result.SearchRow;
15 import org.h2.store.Data;
16 import org.h2.store.Page;
17 import org.h2.store.PageStore;
18 import org.h2.util.Utils;
19
20 /**
21 * A b-tree node page that contains index data. Format:
22 * <ul>
23 * <li>page type: byte</li>
24 * <li>checksum: short</li>
25 * <li>parent page id (0 for root): int</li>
26 * <li>index id: varInt</li>
27 * <li>count of all children (-1 if not known): int</li>
28 * <li>entry count: short</li>
29 * <li>rightmost child page id: int</li>
30 * <li>entries (child page id: int, offset: short)</li>
31 * </ul>
32 * The row contains the largest key of the respective child,
33 * meaning row[0] contains the largest key of child[0].
34 */
35 public class PageBtreeNode extends PageBtree {
36
37 private static final int CHILD_OFFSET_PAIR_LENGTH = 6;
38 private static final int MAX_KEY_LENGTH = 10;
39
40 private final boolean pageStoreInternalCount;
41
42 /**
43 * The page ids of the children.
44 */
45 private int[] childPageIds;
46
47 private int rowCountStored = UNKNOWN_ROWCOUNT;
48
49 private int rowCount = UNKNOWN_ROWCOUNT;
50
51 private PageBtreeNode(PageBtreeIndex index, int pageId, Data data) {
52 super(index, pageId, data);
53 this.pageStoreInternalCount = index.getDatabase().getSettings().pageStoreInternalCount;
54 }
55
56 /**
57 * Read a b-tree node page.
58 *
59 * @param index the index
60 * @param data the data
61 * @param pageId the page id
62 * @return the page
63 */
64 public static Page read(PageBtreeIndex index, Data data, int pageId) {
65 PageBtreeNode p = new PageBtreeNode(index, pageId, data);
66 p.read();
67 return p;
68 }
69
70 /**
71 * Create a new b-tree node page.
72 *
73 * @param index the index
74 * @param pageId the page id
75 * @param parentPageId the parent page id
76 * @return the page
77 */
78 static PageBtreeNode create(PageBtreeIndex index, int pageId, int parentPageId) {
79 PageBtreeNode p = new PageBtreeNode(index, pageId, index.getPageStore().createData());
80 index.getPageStore().logUndo(p, null);
81 p.parentPageId = parentPageId;
82 p.writeHead();
83 // 4 bytes for the rightmost child page id
84 p.start = p.data.length() + 4;
85 p.rows = SearchRow.EMPTY_ARRAY;
86 if (p.pageStoreInternalCount) {
87 p.rowCount = 0;
88 }
89 return p;
90 }
91
92 private void read() {
93 data.reset();
94 int type = data.readByte();
95 data.readShortInt();
96 this.parentPageId = data.readInt();
97 onlyPosition = (type & Page.FLAG_LAST) == 0;
98 int indexId = data.readVarInt();
99 if (indexId != index.getId()) {
100 throw DbException.get(ErrorCode.FILE_CORRUPTED_1,
101 "page:" + getPos() + " expected index:" + index.getId() +
102 "got:" + indexId);
103 }
104 rowCount = rowCountStored = data.readInt();
105 entryCount = data.readShortInt();
106 childPageIds = new int[entryCount + 1];
107 childPageIds[entryCount] = data.readInt();
108 rows = entryCount == 0 ? SearchRow.EMPTY_ARRAY : new SearchRow[entryCount];
109 offsets = Utils.newIntArray(entryCount);
110 for (int i = 0; i < entryCount; i++) {
111 childPageIds[i] = data.readInt();
112 offsets[i] = data.readShortInt();
113 }
114 check();
115 start = data.length();
116 written = true;
117 }
118
119 /**
120 * Add a row. If it is possible this method returns -1, otherwise
121 * the split point. It is always possible to add two rows.
122 *
123 * @param row the now to add
124 * @return the split point of this page, or -1 if no split is required
125 */
126 private int addChildTry(SearchRow row) {
127 if (entryCount < 4) {
128 return -1;
129 }
130 int startData;
131 if (onlyPosition) {
132 // if we only store the position, we may at most store as many
133 // entries as there is space for keys, because the current data area
134 // might get larger when _removing_ a child (if the new key needs
135 // more space) - and removing a child can't split this page
136 startData = entryCount + 1 * MAX_KEY_LENGTH;
137 } else {
138 int rowLength = index.getRowSize(data, row, onlyPosition);
139 int pageSize = index.getPageStore().getPageSize();
140 int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
141 startData = last - rowLength;
142 }
143 if (startData < start + CHILD_OFFSET_PAIR_LENGTH) {
144 return entryCount / 2;
145 }
146 return -1;
147 }
148
149 /**
150 * Add a child at the given position.
151 *
152 * @param x the position
153 * @param childPageId the child
154 * @param row the row smaller than the first row of the child and its children
155 */
156 private void addChild(int x, int childPageId, SearchRow row) {
157 int rowLength = index.getRowSize(data, row, onlyPosition);
158 int pageSize = index.getPageStore().getPageSize();
159 int last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
160 if (last - rowLength < start + CHILD_OFFSET_PAIR_LENGTH) {
161 readAllRows();
162 onlyPosition = true;
163 // change the offsets (now storing only positions)
164 int o = pageSize;
165 for (int i = 0; i < entryCount; i++) {
166 o -= index.getRowSize(data, getRow(i), true);
167 offsets[i] = o;
168 }
169 last = entryCount == 0 ? pageSize : offsets[entryCount - 1];
170 rowLength = index.getRowSize(data, row, true);
171 if (SysProperties.CHECK && last - rowLength < start + CHILD_OFFSET_PAIR_LENGTH) {
172 throw DbException.throwInternalError();
173 }
174 }
175 int offset = last - rowLength;
176 if (entryCount > 0) {
177 if (x < entryCount) {
178 offset = (x == 0 ? pageSize : offsets[x - 1]) - rowLength;
179 }
180 }
181 rows = insert(rows, entryCount, x, row);
182 offsets = insert(offsets, entryCount, x, offset);
183 add(offsets, x + 1, entryCount + 1, -rowLength);
184 childPageIds = insert(childPageIds, entryCount + 1, x + 1, childPageId);
185 start += CHILD_OFFSET_PAIR_LENGTH;
186 if (pageStoreInternalCount) {
187 if (rowCount != UNKNOWN_ROWCOUNT) {
188 rowCount += offset;
189 }
190 }
191 entryCount++;
192 written = false;
193 changeCount = index.getPageStore().getChangeCount();
194 }
195
196 int addRowTry(SearchRow row) {
197 while (true) {
198 int x = find(row, false, true, true);
199 PageBtree page = index.getPage(childPageIds[x]);
200 int splitPoint = page.addRowTry(row);
201 if (splitPoint == -1) {
202 break;
203 }
204 SearchRow pivot = page.getRow(splitPoint - 1);
205 index.getPageStore().logUndo(this, data);
206 int splitPoint2 = addChildTry(pivot);
207 if (splitPoint2 != -1) {
208 return splitPoint2;
209 }
210 PageBtree page2 = page.split(splitPoint);
211 readAllRows();
212 addChild(x, page2.getPos(), pivot);
213 index.getPageStore().update(page);
214 index.getPageStore().update(page2);
215 index.getPageStore().update(this);
216 }
217 updateRowCount(1);
218 written = false;
219 changeCount = index.getPageStore().getChangeCount();
220 return -1;
221 }
222
223 private void updateRowCount(int offset) {
224 if (rowCount != UNKNOWN_ROWCOUNT) {
225 rowCount += offset;
226 }
227 if (rowCountStored != UNKNOWN_ROWCOUNT) {
228 rowCountStored = UNKNOWN_ROWCOUNT;
229 index.getPageStore().logUndo(this, data);
230 if (written) {
231 writeHead();
232 }
233 index.getPageStore().update(this);
234 }
235 }
236
237 PageBtree split(int splitPoint) {
238 int newPageId = index.getPageStore().allocatePage();
239 PageBtreeNode p2 = PageBtreeNode.create(index, newPageId, parentPageId);
240 index.getPageStore().logUndo(this, data);
241 if (onlyPosition) {
242 // TODO optimize: maybe not required
243 p2.onlyPosition = true;
244 }
245 int firstChild = childPageIds[splitPoint];
246 readAllRows();
247 for (int i = splitPoint; i < entryCount;) {
248 p2.addChild(p2.entryCount, childPageIds[splitPoint + 1], getRow(splitPoint));
249 removeChild(splitPoint);
250 }
251 int lastChild = childPageIds[splitPoint - 1];
252 removeChild(splitPoint - 1);
253 childPageIds[splitPoint - 1] = lastChild;
254 if (p2.childPageIds == null) {
255 p2.childPageIds = new int[1];
256 }
257 p2.childPageIds[0] = firstChild;
258 p2.remapChildren();
259 return p2;
260 }
261
262 protected void remapChildren() {
263 for (int i = 0; i < entryCount + 1; i++) {
264 int child = childPageIds[i];
265 PageBtree p = index.getPage(child);
266 p.setParentPageId(getPos());
267 index.getPageStore().update(p);
268 }
269 }
270
271 /**
272 * Initialize the page.
273 *
274 * @param page1 the first child page
275 * @param pivot the pivot key
276 * @param page2 the last child page
277 */
278 void init(PageBtree page1, SearchRow pivot, PageBtree page2) {
279 entryCount = 0;
280 childPageIds = new int[] { page1.getPos() };
281 rows = SearchRow.EMPTY_ARRAY;
282 offsets = Utils.EMPTY_INT_ARRAY;
283 addChild(0, page2.getPos(), pivot);
284 if (pageStoreInternalCount) {
285 rowCount = page1.getRowCount() + page2.getRowCount();
286 }
287 check();
288 }
289
290 void find(PageBtreeCursor cursor, SearchRow first, boolean bigger) {
291 int i = find(first, bigger, false, false);
292 if (i > entryCount) {
293 if (parentPageId == PageBtree.ROOT) {
294 return;
295 }
296 PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
297 next.find(cursor, first, bigger);
298 return;
299 }
300 PageBtree page = index.getPage(childPageIds[i]);
301 page.find(cursor, first, bigger);
302 }
303
304 void last(PageBtreeCursor cursor) {
305 int child = childPageIds[entryCount];
306 index.getPage(child).last(cursor);
307 }
308
309 PageBtreeLeaf getFirstLeaf() {
310 int child = childPageIds[0];
311 return index.getPage(child).getFirstLeaf();
312 }
313
314 PageBtreeLeaf getLastLeaf() {
315 int child = childPageIds[entryCount];
316 return index.getPage(child).getLastLeaf();
317 }
318
319 SearchRow remove(SearchRow row) {
320 int at = find(row, false, false, true);
321 // merge is not implemented to allow concurrent usage
322 // TODO maybe implement merge
323 PageBtree page = index.getPage(childPageIds[at]);
324 SearchRow last = page.remove(row);
325 index.getPageStore().logUndo(this, data);
326 updateRowCount(-1);
327 written = false;
328 changeCount = index.getPageStore().getChangeCount();
329 if (last == null) {
330 // the last row didn't change - nothing to do
331 return null;
332 } else if (last == row) {
333 // this child is now empty
334 index.getPageStore().free(page.getPos());
335 if (entryCount < 1) {
336 // no more children - this page is empty as well
337 return row;
338 }
339 if (at == entryCount) {
340 // removing the last child
341 last = getRow(at - 1);
342 } else {
343 last = null;
344 }
345 removeChild(at);
346 index.getPageStore().update(this);
347 return last;
348 }
349 // the last row is in the last child
350 if (at == entryCount) {
351 return last;
352 }
353 int child = childPageIds[at];
354 removeChild(at);
355 // TODO this can mean only the position is now stored
356 // should split at the next possible moment
357 addChild(at, child, last);
358 // remove and add swapped two children, fix that
359 int temp = childPageIds[at];
360 childPageIds[at] = childPageIds[at + 1];
361 childPageIds[at + 1] = temp;
362 index.getPageStore().update(this);
363 return null;
364 }
365
366 int getRowCount() {
367 if (rowCount == UNKNOWN_ROWCOUNT) {
368 int count = 0;
369 for (int i = 0; i < entryCount + 1; i++) {
370 int child = childPageIds[i];
371 PageBtree page = index.getPage(child);
372 count += page.getRowCount();
373 index.getDatabase().setProgress(DatabaseEventListener.STATE_SCAN_FILE, index.getName(), count, Integer.MAX_VALUE);
374 }
375 rowCount = count;
376 }
377 return rowCount;
378 }
379
380 void setRowCountStored(int rowCount) {
381 if (rowCount < 0 && pageStoreInternalCount) {
382 return;
383 }
384 this.rowCount = rowCount;
385 if (rowCountStored != rowCount) {
386 rowCountStored = rowCount;
387 index.getPageStore().logUndo(this, data);
388 if (written) {
389 changeCount = index.getPageStore().getChangeCount();
390 writeHead();
391 }
392 index.getPageStore().update(this);
393 }
394 }
395
396 private void check() {
397 if (SysProperties.CHECK) {
398 for (int i = 0; i < entryCount + 1; i++) {
399 int child = childPageIds[i];
400 if (child == 0) {
401 DbException.throwInternalError();
402 }
403 }
404 }
405 }
406
407 public void write() {
408 check();
409 writeData();
410 index.getPageStore().writePage(getPos(), data);
411 }
412
413 private void writeHead() {
414 data.reset();
415 data.writeByte((byte) (Page.TYPE_BTREE_NODE | (onlyPosition ? 0 : Page.FLAG_LAST)));
416 data.writeShortInt(0);
417 data.writeInt(parentPageId);
418 data.writeVarInt(index.getId());
419 data.writeInt(rowCountStored);
420 data.writeShortInt(entryCount);
421 }
422
423 private void writeData() {
424 if (written) {
425 return;
426 }
427 readAllRows();
428 writeHead();
429 data.writeInt(childPageIds[entryCount]);
430 for (int i = 0; i < entryCount; i++) {
431 data.writeInt(childPageIds[i]);
432 data.writeShortInt(offsets[i]);
433 }
434 for (int i = 0; i < entryCount; i++) {
435 index.writeRow(data, offsets[i], rows[i], onlyPosition);
436 }
437 written = true;
438 }
439
440 void freeRecursive() {
441 index.getPageStore().logUndo(this, data);
442 index.getPageStore().free(getPos());
443 for (int i = 0; i < entryCount + 1; i++) {
444 int child = childPageIds[i];
445 index.getPage(child).freeRecursive();
446 }
447 }
448
449 private void removeChild(int i) {
450 readAllRows();
451 entryCount--;
452 if (pageStoreInternalCount) {
453 updateRowCount(-index.getPage(childPageIds[i]).getRowCount());
454 }
455 written = false;
456 changeCount = index.getPageStore().getChangeCount();
457 if (entryCount < 0) {
458 DbException.throwInternalError();
459 }
460 if (entryCount > i) {
461 int startNext = i > 0 ? offsets[i - 1] : index.getPageStore().getPageSize();
462 int rowLength = startNext - offsets[i];
463 add(offsets, i, entryCount + 1, rowLength);
464 }
465 rows = remove(rows, entryCount + 1, i);
466 offsets = remove(offsets, entryCount + 1, i);
467 childPageIds = remove(childPageIds, entryCount + 2, i);
468 start -= CHILD_OFFSET_PAIR_LENGTH;
469 }
470
471 /**
472 * Set the cursor to the first row of the next page.
473 *
474 * @param cursor the cursor
475 * @param pageId id of the next page
476 */
477 void nextPage(PageBtreeCursor cursor, int pageId) {
478 int i;
479 // TODO maybe keep the index in the child page (transiently)
480 for (i = 0; i < entryCount + 1; i++) {
481 if (childPageIds[i] == pageId) {
482 i++;
483 break;
484 }
485 }
486 if (i > entryCount) {
487 if (parentPageId == PageBtree.ROOT) {
488 cursor.setCurrent(null, 0);
489 return;
490 }
491 PageBtreeNode next = (PageBtreeNode) index.getPage(parentPageId);
492 next.nextPage(cursor, getPos());
493 return;
494 }
495 PageBtree page = index.getPage(childPageIds[i]);
496 PageBtreeLeaf leaf = page.getFirstLeaf();
497 cursor.setCurrent(leaf, 0);
498 }
499
500 /**
501 * Set the cursor to the last row of the previous page.
502 *
503 * @param cursor the cursor
504 * @param pageId id of the previous page
505 */
506 void previousPage(PageBtreeCursor cursor, int pageId) {
507 int i;
508 // TODO maybe keep the index in the child page (transiently)
509 for (i = entryCount; i >= 0; i--) {
510 if (childPageIds[i] == pageId) {
511 i--;
512 break;
513 }
514 }
515 if (i < 0) {
516 if (parentPageId == PageBtree.ROOT) {
517 cursor.setCurrent(null, 0);
518 return;
519 }
520 PageBtreeNode previous = (PageBtreeNode) index.getPage(parentPageId);
521 previous.previousPage(cursor, getPos());
522 return;
523 }
524 PageBtree page = index.getPage(childPageIds[i]);
525 PageBtreeLeaf leaf = page.getLastLeaf();
526 cursor.setCurrent(leaf, leaf.entryCount - 1);
527 }
528
529
530 public String toString() {
531 return "page[" + getPos() + "] b-tree node table:" + index.getId() + " entries:" + entryCount;
532 }
533
534 public void moveTo(Session session, int newPos) {
535 PageStore store = index.getPageStore();
536 store.logUndo(this, data);
537 PageBtreeNode p2 = PageBtreeNode.create(index, newPos, parentPageId);
538 readAllRows();
539 p2.rowCountStored = rowCountStored;
540 p2.rowCount = rowCount;
541 p2.childPageIds = childPageIds;
542 p2.rows = rows;
543 p2.entryCount = entryCount;
544 p2.offsets = offsets;
545 p2.onlyPosition = onlyPosition;
546 p2.parentPageId = parentPageId;
547 p2.start = start;
548 store.update(p2);
549 if (parentPageId == ROOT) {
550 index.setRootPageId(session, newPos);
551 } else {
552 Page p = store.getPage(parentPageId);
553 if (!(p instanceof PageBtreeNode)) {
554 throw DbException.throwInternalError();
555 }
556 PageBtreeNode n = (PageBtreeNode) p;
557 n.moveChild(getPos(), newPos);
558 }
559 for (int i = 0; i < entryCount + 1; i++) {
560 int child = childPageIds[i];
561 PageBtree p = index.getPage(child);
562 p.setParentPageId(newPos);
563 store.update(p);
564 }
565 store.free(getPos());
566 }
567
568 /**
569 * One of the children has moved to a new page.
570 *
571 * @param oldPos the old position
572 * @param newPos the new position
573 */
574 void moveChild(int oldPos, int newPos) {
575 for (int i = 0; i < entryCount + 1; i++) {
576 if (childPageIds[i] == oldPos) {
577 index.getPageStore().logUndo(this, data);
578 written = false;
579 changeCount = index.getPageStore().getChangeCount();
580 childPageIds[i] = newPos;
581 index.getPageStore().update(this);
582 return;
583 }
584 }
585 throw DbException.throwInternalError();
586 }
587
588 }