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.ErrorCode;
011: import org.h2.constant.SysProperties;
012: import org.h2.engine.Database;
013: import org.h2.engine.Session;
014: import org.h2.message.Message;
015: import org.h2.result.Row;
016: import org.h2.result.SearchRow;
017: import org.h2.store.DataPage;
018: import org.h2.store.Record;
019: import org.h2.store.RecordReader;
020: import org.h2.store.Storage;
021: import org.h2.table.Column;
022: import org.h2.table.IndexColumn;
023: import org.h2.table.TableData;
024: import org.h2.util.ObjectArray;
025: import org.h2.value.Value;
026: import org.h2.value.ValueNull;
027:
028: /**
029: * This is the most common type of index, a b tree index.
030: * The index structure is:
031: * <ul>
032: * <li>There is one {@link BtreeHead} that points to the root page.
033: * The head always stays where it is.
034: * </li><li>There is a number of {@link BtreePage}s. Each page is either
035: * a {@link BtreeNode} or a {@link BtreeLeaf}.
036: * </li><li>A node page links to other leaf pages or to node pages.
037: * Leaf pages don't point to other pages (but may have a parent).
038: * </li><li>The uppermost page is the root page. If pages
039: * are added or deleted, the root page may change.
040: * </li>
041: * </ul>
042: * Only the data of the indexed columns are stored in the index.
043: */
044: public class BtreeIndex extends BaseIndex implements RecordReader {
045:
046: // TODO index / btree: tune page size
047: // final static int MAX_PAGE_SIZE = 256;
048:
049: private Storage storage;
050: private BtreePage rootPage;
051: private TableData tableData;
052: private BtreeHead head;
053: private boolean needRebuild;
054: private int headPos;
055: private long lastChange;
056:
057: public BtreeIndex(Session session, TableData table, int id,
058: String indexName, IndexColumn[] columns,
059: IndexType indexType, int headPos) throws SQLException {
060: // TODO we need to log index data
061: super (table, id, indexName, columns, indexType);
062: this .tableData = table;
063: Database db = table.getDatabase();
064: storage = db.getStorage(this , id, false);
065: this .headPos = headPos;
066: if (headPos == Index.EMPTY_HEAD || database.getRecovery()) {
067: truncate(session);
068: needRebuild = true;
069: } else {
070: Record rec = storage.getRecordIfStored(session, headPos);
071: if (rec != null && (rec instanceof BtreeHead)) {
072: head = (BtreeHead) rec;
073: }
074: if (head != null && head.getConsistent()) {
075: needRebuild = false;
076: rowCount = table.getRowCount(session);
077: } else {
078: truncate(session);
079: needRebuild = true;
080: }
081: }
082: }
083:
084: private BtreePage getRoot(Session session) throws SQLException {
085: if (rootPage == null) {
086: setRoot((BtreePage) storage.getRecord(session, head
087: .getRootPosition()));
088: }
089: return rootPage;
090: }
091:
092: private BtreePage setRoot(BtreePage newRoot) {
093: if (rootPage != null) {
094: rootPage.setRoot(false);
095: }
096: newRoot.setRoot(true);
097: rootPage = newRoot;
098: return rootPage;
099: }
100:
101: public int getHeadPos() {
102: return headPos;
103: }
104:
105: public void remove(Session session) throws SQLException {
106: storage.delete(session);
107: storage = null;
108: }
109:
110: private void setChanged(Session session) throws SQLException {
111: if (head != null && !database.getLogIndexChanges()) {
112: // maybe there was a checkpoint, need to invalidate the summary in
113: // this case too
114: database.invalidateIndexSummary();
115: if (head.getConsistent()) {
116: deletePage(session, head);
117: head.setConsistent(false);
118: flushHead(session);
119: }
120: lastChange = System.currentTimeMillis();
121: }
122: }
123:
124: void updatePage(Session session, Record p) throws SQLException {
125: if (database.getLogIndexChanges()) {
126: storage.addRecord(session, p, p.getPos());
127: } else {
128: storage.updateRecord(session, p);
129: }
130: }
131:
132: void deletePage(Session session, Record p) throws SQLException {
133: if (database.getLogIndexChanges()) {
134: storage.removeRecord(session, p.getPos());
135: }
136: }
137:
138: void addPage(Session session, Record p) throws SQLException {
139: storage.addRecord(session, p, Storage.ALLOCATE_POS);
140: }
141:
142: public BtreePage getPage(Session session, int i)
143: throws SQLException {
144: return (BtreePage) storage.getRecord(session, i);
145: }
146:
147: public void flush(Session session) throws SQLException {
148: lastChange = 0;
149: if (storage != null) {
150: storage.flushFile();
151: deletePage(session, head);
152: // if we log index changes now, then the index is consistent
153: // if we don't log index changes, then the index is only consistent
154: // if there are no in doubt transactions
155: if (database.getLogIndexChanges()
156: || !database.getLog().containsInDoubtTransactions()) {
157: head.setConsistent(true);
158: }
159: flushHead(session);
160: }
161: }
162:
163: public void close(Session session) throws SQLException {
164: flush(session);
165: storage = null;
166: }
167:
168: public void add(Session session, Row r) throws SQLException {
169: // create a row that only contains the key values
170: setChanged(session);
171: Row row = table.getTemplateRow();
172: row.setPos(r.getPos());
173: for (int i = 0; i < columns.length; i++) {
174: Column col = columns[i];
175: int idx = col.getColumnId();
176: Value v = r.getValue(idx);
177: row.setValue(idx, v);
178: }
179: BtreePage root = getRoot(session);
180: int splitPoint = root.add(row, session);
181: if (splitPoint != 0) {
182: SearchRow pivot = root.getData(splitPoint);
183: BtreePage page1 = root;
184: BtreePage page2 = root.split(session, splitPoint);
185: root = setRoot(new BtreeNode(this , page1, pivot, page2));
186: addPage(session, root);
187: deletePage(session, head);
188: head.setRootPosition(root.getPos());
189: flushHead(session);
190: }
191: rowCount++;
192: }
193:
194: SearchRow getSearchRow(Row row) {
195: SearchRow r = table.getTemplateSimpleRow(columns.length == 1);
196: r.setPos(row.getPos());
197: for (int j = 0; j < columns.length; j++) {
198: int idx = columns[j].getColumnId();
199: r.setValue(idx, row.getValue(idx));
200: }
201: return r;
202: }
203:
204: public void remove(Session session, Row row) throws SQLException {
205: setChanged(session);
206: if (rowCount == 1) {
207: // TODO performance: maybe improve truncate performance in this case
208: truncate(session);
209: } else {
210: BtreePage root = getRoot(session);
211: root.remove(session, row);
212: rowCount--;
213: }
214: }
215:
216: public boolean canFindNext() {
217: return true;
218: }
219:
220: public Cursor findNext(Session session, SearchRow first,
221: SearchRow last) throws SQLException {
222: return find(session, first, true, last);
223: }
224:
225: public Cursor find(Session session, SearchRow first, SearchRow last)
226: throws SQLException {
227: return find(session, first, false, last);
228: }
229:
230: private Cursor find(Session session, SearchRow first,
231: boolean bigger, SearchRow last) throws SQLException {
232: if (SysProperties.CHECK && storage == null) {
233: throw Message.getSQLException(ErrorCode.OBJECT_CLOSED);
234: }
235: BtreePage root = getRoot(session);
236: if (first == null) {
237: BtreeCursor cursor = new BtreeCursor(session, this , last);
238: root.first(cursor);
239: return cursor;
240: } else {
241: BtreeCursor cursor = new BtreeCursor(session, this , last);
242: if (getRowCount(session) == 0
243: || !root.findFirst(cursor, first, bigger)) {
244: cursor.setCurrentRow(null);
245: }
246: return cursor;
247: }
248: }
249:
250: public int getLookupCost(int rowCount) {
251: for (int i = 0, j = 1;; i++) {
252: j *= BtreePage.BLOCKS_PER_PAGE;
253: if (j > rowCount) {
254: return (i + 1);
255: }
256: }
257: }
258:
259: public double getCost(Session session, int[] masks)
260: throws SQLException {
261: return 10 * getCostRangeIndex(masks, tableData
262: .getRowCount(session));
263: }
264:
265: public Record read(Session session, DataPage s) throws SQLException {
266: char c = (char) s.readByte();
267: if (c == 'N') {
268: return new BtreeNode(this , s);
269: } else if (c == 'L') {
270: return new BtreeLeaf(this , session, s);
271: } else if (c == 'H') {
272: return new BtreeHead(s);
273: } else {
274: throw Message.getSQLException(ErrorCode.FILE_CORRUPTED_1,
275: getName());
276: }
277: }
278:
279: ObjectArray readRowArray(DataPage s) throws SQLException {
280: int len = s.readInt();
281: ObjectArray rows = new ObjectArray(len);
282: for (int i = 0; i < len; i++) {
283: int pos = s.readInt();
284: SearchRow r;
285: if (pos < 0) {
286: r = null;
287: } else {
288: r = table.getTemplateSimpleRow(columns.length == 1);
289: r.setPos(pos);
290: for (int j = 0; j < columns.length; j++) {
291: int idx = columns[j].getColumnId();
292: r.setValue(idx, s.readValue());
293: }
294: }
295: rows.add(r);
296: }
297: return rows;
298: }
299:
300: public Row getRow(Session session, int pos) throws SQLException {
301: return tableData.getRow(session, pos);
302: }
303:
304: private void flushHead(Session session) throws SQLException {
305: updatePage(session, head);
306: if (!database.getLogIndexChanges() && !database.getReadOnly()) {
307: storage.flushRecord(head);
308: }
309: trace.debug("Index " + getSQL() + " head consistent="
310: + head.getConsistent());
311: }
312:
313: public void truncate(Session session) throws SQLException {
314: setChanged(session);
315: storage.truncate(session);
316: head = new BtreeHead();
317: addPage(session, head);
318: BtreePage root = setRoot(new BtreeLeaf(this , new ObjectArray()));
319: addPage(session, root);
320: deletePage(session, head);
321: head.setRootPosition(root.getPos());
322: head.setConsistent(database.getLogIndexChanges());
323: lastChange = System.currentTimeMillis();
324: flushHead(session);
325: headPos = head.getPos();
326: rowCount = 0;
327: }
328:
329: public void checkRename() throws SQLException {
330: // ok
331: }
332:
333: public boolean needRebuild() {
334: return needRebuild;
335: }
336:
337: public int getRecordOverhead() {
338: return storage.getRecordOverhead();
339: }
340:
341: public long getLastChange() {
342: return lastChange;
343: }
344:
345: public boolean canGetFirstOrLast() {
346: return true;
347: }
348:
349: public SearchRow findFirstOrLast(Session session, boolean first)
350: throws SQLException {
351: if (first) {
352: // TODO optimization: this loops through NULL elements
353: Cursor cursor = find(session, null, false, null);
354: while (cursor.next()) {
355: SearchRow row = cursor.getSearchRow();
356: Value v = row.getValue(columnIds[0]);
357: if (v != ValueNull.INSTANCE) {
358: return row;
359: }
360: }
361: return null;
362: } else {
363: return getRoot(session).getLast(session);
364: }
365: }
366:
367: }
|