001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.index;
007:
008: import java.sql.SQLException;
009:
010: import org.h2.constant.SysProperties;
011: import org.h2.engine.Constants;
012: import org.h2.engine.Session;
013: import org.h2.message.Message;
014: import org.h2.result.Row;
015: import org.h2.result.SearchRow;
016: import org.h2.store.DataPage;
017: import org.h2.store.DiskFile;
018: import org.h2.table.Column;
019: import org.h2.util.IntArray;
020: import org.h2.util.ObjectArray;
021: import org.h2.value.Value;
022:
023: /**
024: * An inner page of a b-tree index.
025: *
026: * Page format:
027: * <pre>
028: * N children.len children[0..len] data.len { data[0].pos [data[0]], ... }
029: *</pre>
030: */
031: public class BtreeNode extends BtreePage {
032:
033: private boolean writePos;
034: private IntArray pageChildren;
035:
036: BtreeNode(BtreeIndex index, DataPage s) throws SQLException {
037: super (index);
038: int len = s.readInt();
039: int[] array = new int[len];
040: for (int i = 0; i < array.length; i++) {
041: array[i] = s.readInt();
042: }
043: pageChildren = new IntArray(array);
044: pageData = index.readRowArray(s);
045: }
046:
047: BtreeNode(BtreeIndex index, BtreePage left, SearchRow pivot,
048: BtreePage right) {
049: super (index);
050: pageChildren = new IntArray();
051: pageChildren.add(left.getPos());
052: pageChildren.add(right.getPos());
053: pageData = new ObjectArray();
054: pageData.add(pivot);
055: }
056:
057: BtreeNode(BtreeIndex index, IntArray pageChildren,
058: ObjectArray pageData) {
059: super (index);
060: this .pageChildren = pageChildren;
061: this .pageData = pageData;
062: }
063:
064: protected SearchRow getData(int i) throws SQLException {
065: SearchRow r = (SearchRow) pageData.get(i);
066: if (r == null) {
067: int p = pageChildren.get(i + 1);
068: Session session = index.getDatabase().getSystemSession();
069: BtreePage page = index.getPage(session, p);
070: r = page.getFirst(session);
071: pageData.set(i, r);
072: }
073: return r;
074: }
075:
076: public int add(Row newRow, Session session) throws SQLException {
077: int l = 0, r = pageData.size();
078: if (!Constants.ALLOW_EMPTY_BTREE_PAGES
079: && pageChildren.size() == 0) {
080: throw Message.getInternalError("Empty btree page");
081: }
082: while (l < r) {
083: int i = (l + r) >>> 1;
084: SearchRow row = getData(i);
085: int comp = index.compareRows(row, newRow);
086: if (comp == 0) {
087: if (index.indexType.isUnique()) {
088: if (!index.isNull(newRow)) {
089: throw index.getDuplicateKeyException();
090: }
091: }
092: comp = index.compareKeys(row, newRow);
093: }
094: if (comp > 0) {
095: r = i;
096: } else {
097: l = i + 1;
098: }
099: }
100: int at = l;
101: BtreePage page = index.getPage(session, pageChildren.get(at));
102: int splitPoint = page.add(newRow, session);
103: if (splitPoint == 0) {
104: return 0;
105: }
106: SearchRow pivot = page.getData(splitPoint);
107: BtreePage page2 = page.split(session, splitPoint);
108: index.deletePage(session, this );
109: pageChildren.add(at + 1, page2.getPos());
110: pageData.add(at, pivot);
111: splitPoint = getSplitPoint();
112: if (splitPoint > 1) {
113: return splitPoint;
114: }
115: index.updatePage(session, this );
116: return 0;
117: }
118:
119: public SearchRow remove(Session session, Row oldRow)
120: throws SQLException {
121: int l = 0, r = pageData.size();
122: if (!Constants.ALLOW_EMPTY_BTREE_PAGES
123: && pageChildren.size() == 0) {
124: throw Message.getInternalError("Empty btree page");
125: }
126: int comp = 0;
127: while (l < r) {
128: int i = (l + r) >>> 1;
129: SearchRow row = getData(i);
130: comp = index.compareRows(row, oldRow);
131: if (comp == 0) {
132: comp = index.compareKeys(row, oldRow);
133: }
134: if (comp > 0) {
135: r = i;
136: } else {
137: l = i + 1;
138: }
139: }
140: int at = l;
141: // merge is not implemented to allow concurrent usage of btrees
142: BtreePage page = index.getPage(session, pageChildren.get(at));
143: SearchRow first = page.remove(session, oldRow);
144: if (first == null) {
145: // the first row didn't change - nothing to do here
146: return null;
147: }
148: if (first == oldRow) {
149: // this child is now empty
150: index.deletePage(session, this );
151: pageChildren.remove(at);
152: if (pageChildren.size() == 0) {
153: // no more children - this page is empty as well
154: // it can't be the root otherwise the index would have been
155: // truncated
156: return oldRow;
157: }
158: if (at == 0) {
159: // the first child is empty - then the first row of this subtree
160: // has changed
161: first = getData(0);
162: pageData.remove(0);
163: } else {
164: // otherwise the first row didn't change
165: first = null;
166: pageData.remove(at == 0 ? 0 : at - 1);
167: }
168: index.updatePage(session, this );
169: return first;
170: } else {
171: // the child still exists, but the first element has changed
172: if (at == 0) {
173: // no change in this page, but there is a new first row for this
174: // subtree
175: return first;
176: } else {
177: // the first row of another child has changed - need to update
178: index.deletePage(session, this );
179: pageData.set(at - 1, first);
180: index.updatePage(session, this );
181: // but then the first row of this subtree didn't change
182: return null;
183: }
184: }
185: }
186:
187: public BtreePage split(Session session, int splitPoint)
188: throws SQLException {
189: ObjectArray data = new ObjectArray();
190: IntArray children = new IntArray();
191: splitPoint++;
192: int max = pageData.size();
193: if (SysProperties.CHECK
194: && index.getDatabase().getLogIndexChanges()
195: && !getDeleted()) {
196: // page must have been deleted already before calling
197: // getSplitPoint()
198: throw Message.getInternalError();
199: }
200: for (int i = splitPoint; i < max; i++) {
201: data.add(getData(splitPoint));
202: children.add(getChild(splitPoint));
203: pageData.remove(splitPoint);
204: pageChildren.remove(splitPoint);
205: }
206: children.add(getChild(splitPoint));
207: pageData.remove(splitPoint - 1);
208: pageChildren.remove(splitPoint);
209: BtreeNode n2 = new BtreeNode(index, children, data);
210: index.updatePage(session, this );
211: index.addPage(session, n2);
212: return n2;
213: }
214:
215: int getChild(int i) {
216: return pageChildren.get(i);
217: }
218:
219: public boolean findFirst(BtreeCursor cursor, SearchRow compare,
220: boolean bigger) throws SQLException {
221: int l = 0, r = pageData.size();
222: if (!Constants.ALLOW_EMPTY_BTREE_PAGES
223: && pageChildren.size() == 0) {
224: throw Message.getInternalError("Empty btree page");
225: }
226: while (l < r) {
227: int i = (l + r) >>> 1;
228: SearchRow row = getData(i);
229: int comp = index.compareRows(row, compare);
230: if (comp > 0 || (!bigger && comp == 0)) {
231: r = i;
232: } else {
233: l = i + 1;
234: }
235: }
236: if (l >= pageData.size()) {
237: BtreePage page = index.getPage(cursor.getSession(),
238: pageChildren.get(l));
239: cursor.push(this , l);
240: boolean result = page.findFirst(cursor, compare, bigger);
241: if (result) {
242: return true;
243: }
244: cursor.pop();
245: return false;
246: }
247: BtreePage page = index.getPage(cursor.getSession(),
248: pageChildren.get(l));
249: cursor.push(this , l);
250: if (page.findFirst(cursor, compare, bigger)) {
251: return true;
252: }
253: cursor.pop();
254: int i = l + 1;
255: for (; i < pageData.size(); i++) {
256: SearchRow row = getData(i);
257: int comp = index.compareRows(row, compare);
258: if (comp >= 0) {
259: page = index.getPage(cursor.getSession(), pageChildren
260: .get(i));
261: cursor.push(this , i);
262: if (page.findFirst(cursor, compare, bigger)) {
263: return true;
264: }
265: cursor.pop();
266: }
267: }
268: page = index.getPage(cursor.getSession(), pageChildren.get(i));
269: cursor.push(this , i);
270: boolean result = page.findFirst(cursor, compare, bigger);
271: if (result) {
272: return true;
273: }
274: cursor.pop();
275: return false;
276: }
277:
278: public void next(BtreeCursor cursor, int i) throws SQLException {
279: i++;
280: if (i <= pageData.size()) {
281: cursor.setStackPosition(i);
282: BtreePage page = index.getPage(cursor.getSession(),
283: pageChildren.get(i));
284: page.first(cursor);
285: return;
286: }
287: nextUpper(cursor);
288: }
289:
290: private void nextUpper(BtreeCursor cursor) throws SQLException {
291: cursor.pop();
292: BtreePosition upper = cursor.pop();
293: if (upper == null) {
294: cursor.setCurrentRow(null);
295: } else {
296: cursor.push(upper.page, upper.position);
297: upper.page.next(cursor, upper.position);
298: }
299: }
300:
301: public void first(BtreeCursor cursor) throws SQLException {
302: cursor.push(this , 0);
303: BtreePage page = index.getPage(cursor.getSession(),
304: pageChildren.get(0));
305: page.first(cursor);
306: }
307:
308: public void prepareWrite() throws SQLException {
309: if (getRealByteCount() >= DiskFile.BLOCK_SIZE * BLOCKS_PER_PAGE) {
310: writePos = true;
311: } else {
312: writePos = false;
313: }
314: }
315:
316: public void write(DataPage buff) throws SQLException {
317: buff.writeByte((byte) 'N');
318: int len = pageChildren.size();
319: buff.writeInt(len);
320: for (int i = 0; i < len; i++) {
321: buff.writeInt(pageChildren.get(i));
322: }
323: len = pageData.size();
324: buff.writeInt(len);
325: Column[] columns = index.getColumns();
326: for (int i = 0; i < len; i++) {
327: if (writePos) {
328: buff.writeInt(-1);
329: } else {
330: SearchRow row = getData(i);
331: buff.writeInt(row.getPos());
332: for (int j = 0; j < columns.length; j++) {
333: Value v = row.getValue(columns[j].getColumnId());
334: buff.writeValue(v);
335: }
336: }
337: }
338: if (buff.length() > BtreePage.BLOCKS_PER_PAGE
339: * DiskFile.BLOCK_SIZE) {
340: throw Message.getInternalError("indexed data overflow");
341: }
342: }
343:
344: int getRealByteCount() throws SQLException {
345: DataPage dummy = index.getDatabase().getDataPage();
346: int len = pageChildren.size();
347: int size = 2 + dummy.getIntLen() + dummy.getIntLen() * len;
348: len = pageData.size();
349: size += dummy.getIntLen();
350: size += len * dummy.getIntLen();
351: for (int i = 0; i < len; i++) {
352: SearchRow row = getData(i);
353: size += getRowSize(dummy, row);
354: }
355: return size + index.getRecordOverhead();
356: }
357:
358: SearchRow getLast(Session session) throws SQLException {
359: if (!Constants.ALLOW_EMPTY_BTREE_PAGES
360: && pageChildren.size() == 0) {
361: throw Message.getInternalError("Empty btree page");
362: }
363: for (int i = pageChildren.size() - 1; i >= 0; i--) {
364: BtreePage page = index
365: .getPage(session, pageChildren.get(i));
366: if (page != null) {
367: return page.getLast(session);
368: }
369: }
370: return null;
371: }
372:
373: SearchRow getFirst(Session session) throws SQLException {
374: for (int i = 0; i < pageChildren.size(); i++) {
375: BtreePage page = index
376: .getPage(session, pageChildren.get(i));
377: if (page != null) {
378: return page.getFirst(session);
379: }
380: }
381: return null;
382: }
383:
384: }
|