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.Session;
012: import org.h2.message.Message;
013: import org.h2.result.Row;
014: import org.h2.result.SearchRow;
015: import org.h2.table.IndexColumn;
016: import org.h2.table.TableData;
017: import org.h2.value.Value;
018: import org.h2.value.ValueNull;
019:
020: /**
021: * The tree index is an in-memory index based on a binary AVL trees.
022: */
023: public class TreeIndex extends BaseIndex {
024:
025: private TreeNode root;
026: private TableData tableData;
027:
028: public TreeIndex(TableData table, int id, String indexName,
029: IndexColumn[] columns, IndexType indexType) {
030: super (table, id, indexName, columns, indexType);
031: tableData = table;
032: }
033:
034: public void close(Session session) throws SQLException {
035: root = null;
036: }
037:
038: public void add(Session session, Row row) throws SQLException {
039: TreeNode i = new TreeNode(row);
040: TreeNode n = root, x = n;
041: boolean isLeft = true;
042: while (true) {
043: if (n == null) {
044: if (x == null) {
045: root = i;
046: rowCount++;
047: return;
048: }
049: set(x, isLeft, i);
050: break;
051: }
052: Row r = n.row;
053: int compare = compareRows(row, r);
054: if (compare == 0) {
055: if (indexType.isUnique()) {
056: if (!isNull(row)) {
057: throw getDuplicateKeyException();
058: }
059: }
060: compare = compareKeys(row, r);
061: }
062: isLeft = compare < 0;
063: x = n;
064: n = child(x, isLeft);
065: }
066: balance(x, isLeft);
067: rowCount++;
068: }
069:
070: private void balance(TreeNode x, boolean isLeft) {
071: while (true) {
072: int sign = isLeft ? 1 : -1;
073: switch (x.balance * sign) {
074: case 1:
075: x.balance = 0;
076: return;
077: case 0:
078: x.balance = -sign;
079: break;
080: case -1:
081: TreeNode l = child(x, isLeft);
082: if (l.balance == -sign) {
083: replace(x, l);
084: set(x, isLeft, child(l, !isLeft));
085: set(l, !isLeft, x);
086: x.balance = 0;
087: l.balance = 0;
088: } else {
089: TreeNode r = child(l, !isLeft);
090: replace(x, r);
091: set(l, !isLeft, child(r, isLeft));
092: set(r, isLeft, l);
093: set(x, isLeft, child(r, !isLeft));
094: set(r, !isLeft, x);
095: int rb = r.balance;
096: x.balance = (rb == -sign) ? sign : 0;
097: l.balance = (rb == sign) ? -sign : 0;
098: r.balance = 0;
099: }
100: return;
101: default:
102: throw Message
103: .getInternalError("b: " + x.balance * sign);
104: }
105: if (x == root) {
106: return;
107: }
108: isLeft = x.isFromLeft();
109: x = x.parent;
110: }
111: }
112:
113: private TreeNode child(TreeNode x, boolean isLeft) {
114: return isLeft ? x.left : x.right;
115: }
116:
117: private void replace(TreeNode x, TreeNode n) {
118: if (x == root) {
119: root = n;
120: if (n != null) {
121: n.parent = null;
122: }
123: } else {
124: set(x.parent, x.isFromLeft(), n);
125: }
126: }
127:
128: private void set(TreeNode parent, boolean left, TreeNode n) {
129: if (left) {
130: parent.left = n;
131: } else {
132: parent.right = n;
133: }
134: if (n != null) {
135: n.parent = parent;
136: }
137: }
138:
139: public void remove(Session session, Row row) throws SQLException {
140: TreeNode x = findFirstNode(row, true);
141: if (x == null) {
142: throw Message.getInternalError("not found!");
143: }
144: TreeNode n;
145: if (x.left == null) {
146: n = x.right;
147: } else if (x.right == null) {
148: n = x.left;
149: } else {
150: TreeNode d = x;
151: x = x.left;
152: for (TreeNode temp = x; (temp = temp.right) != null;) {
153: x = temp;
154: }
155: // x will be replaced with n later
156: n = x.left;
157: // swap d and x
158: int b = x.balance;
159: x.balance = d.balance;
160: d.balance = b;
161:
162: // set x.parent
163: TreeNode xp = x.parent;
164: TreeNode dp = d.parent;
165: if (d == root) {
166: root = x;
167: }
168: x.parent = dp;
169: if (dp != null) {
170: if (dp.right == d) {
171: dp.right = x;
172: } else {
173: dp.left = x;
174: }
175: }
176: // TODO index / tree: link d.r = x(p?).r directly
177: if (xp == d) {
178: d.parent = x;
179: if (d.left == x) {
180: x.left = d;
181: x.right = d.right;
182: } else {
183: x.right = d;
184: x.left = d.left;
185: }
186: } else {
187: d.parent = xp;
188: xp.right = d;
189: x.right = d.right;
190: x.left = d.left;
191: }
192:
193: if (SysProperties.CHECK && (x.right == null || x == null)) {
194: throw Message.getInternalError("tree corrupted");
195: }
196: x.right.parent = x;
197: x.left.parent = x;
198: // set d.left, d.right
199: d.left = n;
200: if (n != null) {
201: n.parent = d;
202: }
203: d.right = null;
204: x = d;
205: }
206: rowCount--;
207:
208: boolean isLeft = x.isFromLeft();
209: replace(x, n);
210: n = x.parent;
211: while (n != null) {
212: x = n;
213: int sign = isLeft ? 1 : -1;
214: switch (x.balance * sign) {
215: case -1:
216: x.balance = 0;
217: break;
218: case 0:
219: x.balance = sign;
220: return;
221: case 1:
222: TreeNode r = child(x, !isLeft);
223: int b = r.balance;
224: if (b * sign >= 0) {
225: replace(x, r);
226: set(x, !isLeft, child(r, isLeft));
227: set(r, isLeft, x);
228: if (b == 0) {
229: x.balance = sign;
230: r.balance = -sign;
231: return;
232: }
233: x.balance = 0;
234: r.balance = 0;
235: x = r;
236: } else {
237: TreeNode l = child(r, isLeft);
238: replace(x, l);
239: b = l.balance;
240: set(r, isLeft, child(l, !isLeft));
241: set(l, !isLeft, r);
242: set(x, !isLeft, child(l, isLeft));
243: set(l, isLeft, x);
244: x.balance = (b == sign) ? -sign : 0;
245: r.balance = (b == -sign) ? sign : 0;
246: l.balance = 0;
247: x = l;
248: }
249: break;
250: default:
251: throw Message
252: .getInternalError("b: " + x.balance * sign);
253: }
254: isLeft = x.isFromLeft();
255: n = x.parent;
256: }
257: }
258:
259: private TreeNode findFirstNode(SearchRow row, boolean withKey)
260: throws SQLException {
261: TreeNode x = root, result = x;
262: while (x != null) {
263: result = x;
264: int compare = compareRows(x.row, row);
265: if (compare == 0 && withKey) {
266: compare = compareKeys(x.row, row);
267: }
268: if (compare == 0) {
269: if (withKey) {
270: return x;
271: }
272: x = x.left;
273: } else if (compare > 0) {
274: x = x.left;
275: } else {
276: x = x.right;
277: }
278: }
279: return result;
280: }
281:
282: public Cursor find(Session session, SearchRow first, SearchRow last)
283: throws SQLException {
284: if (first == null) {
285: TreeNode x = root, n;
286: while (x != null) {
287: n = x.left;
288: if (n == null) {
289: break;
290: }
291: x = n;
292: }
293: return new TreeCursor(this , x, null, last);
294: } else {
295: TreeNode x = findFirstNode(first, false);
296: return new TreeCursor(this , x, first, last);
297: }
298: }
299:
300: public int getLookupCost(int rowCount) {
301: for (int i = 0, j = 1;; i++) {
302: j += j;
303: if (j >= rowCount) {
304: return i;
305: }
306: }
307: }
308:
309: public double getCost(Session session, int[] masks)
310: throws SQLException {
311: return getCostRangeIndex(masks, tableData.getRowCount(session));
312: }
313:
314: public void remove(Session session) throws SQLException {
315: truncate(session);
316: }
317:
318: public void truncate(Session session) throws SQLException {
319: root = null;
320: rowCount = 0;
321: }
322:
323: TreeNode next(TreeNode x) {
324: if (x == null) {
325: return null;
326: }
327: TreeNode r = x.right;
328: if (r != null) {
329: x = r;
330: TreeNode l = x.left;
331: while (l != null) {
332: x = l;
333: l = x.left;
334: }
335: return x;
336: }
337: TreeNode ch = x;
338: x = x.parent;
339: while (x != null && ch == x.right) {
340: ch = x;
341: x = x.parent;
342: }
343: return x;
344: }
345:
346: public void checkRename() throws SQLException {
347: }
348:
349: public boolean needRebuild() {
350: return true;
351: }
352:
353: public boolean canGetFirstOrLast() {
354: return true;
355: }
356:
357: public SearchRow findFirstOrLast(Session session, boolean first)
358: throws SQLException {
359: if (first) {
360: // TODO optimization: this loops through NULL values
361: Cursor cursor = find(session, null, null);
362: while (cursor.next()) {
363: SearchRow row = cursor.getSearchRow();
364: Value v = row.getValue(columnIds[0]);
365: if (v != ValueNull.INSTANCE) {
366: return row;
367: }
368: }
369: return null;
370: } else {
371: TreeNode x = root, n;
372: while (x != null) {
373: n = x.right;
374: if (n == null) {
375: break;
376: }
377: x = n;
378: }
379: if (x != null) {
380: return x.row;
381: }
382: return null;
383: }
384: }
385:
386: }
|