btreeindex.java

非常棒的java数据库

/*
 * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
 * (http://h2database.com/html/license.html).
 * Initial Developer: H2 Group
 */
package org.h2.index;

import java.sql.SQLException;

import org.h2.constant.ErrorCode;
import org.h2.constant.SysProperties;
import org.h2.engine.Database;
import org.h2.engine.Session;
import org.h2.message.Message;
import org.h2.result.Row;
import org.h2.result.SearchRow;
import org.h2.store.DataPage;
import org.h2.store.Record;
import org.h2.store.RecordReader;
import org.h2.store.Storage;
import org.h2.table.Column;
import org.h2.table.IndexColumn;
import org.h2.table.TableData;
import org.h2.util.ObjectArray;
import org.h2.value.Value;
import org.h2.value.ValueNull;

/**
 * This is the most common type of index, a b tree index.
 * The index structure is:
 * <ul>
 * <li>There is one {@link BtreeHead} that points to the root page.
 * The head always stays where it is.
 * </li><li>There is a number of {@link BtreePage}s. Each page is either
 * a {@link BtreeNode} or a {@link BtreeLeaf}.
 * </li><li>A node page links to other leaf pages or to node pages.
 * Leaf pages don't point to other pages (but may have a parent).
 * </li><li>The uppermost page is the root page. If pages
 * are added or deleted, the root page may change.
 * </li>
 * </ul>
 * Only the data of the indexed columns are stored in the index.
 */
public class BtreeIndex extends BaseIndex implements RecordReader {

    // TODO index / btree: tune page size
    // final static int MAX_PAGE_SIZE = 256;

    private Storage storage;
    private BtreePage rootPage;
    private TableData tableData;
    private BtreeHead head;
    private boolean needRebuild;
    private int headPos;
    private long lastChange;

    public BtreeIndex(Session session, TableData table, int id, String indexName, IndexColumn[] columns,
            IndexType indexType, int headPos) throws SQLException {
        // TODO we need to log index data
        super(table, id, indexName, columns, indexType);
        this.tableData = table;
        Database db = table.getDatabase();
        storage = db.getStorage(this, id, false);
        this.headPos = headPos;
        if (headPos == Index.EMPTY_HEAD || database.getRecovery()) {
            truncate(session);
            needRebuild = true;
        } else {
            Record rec = storage.getRecordIfStored(session, headPos);
            if (rec != null && (rec instanceof BtreeHead)) {
                head = (BtreeHead) rec;
            }
            if (head != null && head.getConsistent()) {
                needRebuild = false;
                rowCount = table.getRowCount(session);
            } else {
                truncate(session);
                needRebuild = true;
            }
        }
    }

    private BtreePage getRoot(Session session) throws SQLException {
        if (rootPage == null) {
            setRoot((BtreePage) storage.getRecord(session, head.getRootPosition()));
        }
        return rootPage;
    }

    private BtreePage setRoot(BtreePage newRoot) {
        if (rootPage != null) {
            rootPage.setRoot(false);
        }
        newRoot.setRoot(true);
        rootPage = newRoot;
        return rootPage;
    }

    public int getHeadPos() {
        return headPos;
    }

    public void remove(Session session) throws SQLException {
        storage.delete(session);
        storage = null;
    }

    private void setChanged(Session session) throws SQLException {
        if (head != null && !database.getLogIndexChanges()) {
            // maybe there was a checkpoint, need to invalidate the summary in
            // this case too
            database.invalidateIndexSummary();
            if (head.getConsistent()) {
                deletePage(session, head);
                head.setConsistent(false);
                flushHead(session);
            }
            lastChange = System.currentTimeMillis();
        }
    }

    void updatePage(Session session, Record p) throws SQLException {
        if (database.getLogIndexChanges()) {
            storage.addRecord(session, p, p.getPos());
        } else {
            storage.updateRecord(session, p);
        }
    }

    void deletePage(Session session, Record p) throws SQLException {
        if (database.getLogIndexChanges()) {
            storage.removeRecord(session, p.getPos());
        }
    }

    void addPage(Session session, Record p) throws SQLException {
        storage.addRecord(session, p, Storage.ALLOCATE_POS);
    }

    public BtreePage getPage(Session session, int i) throws SQLException {
        return (BtreePage) storage.getRecord(session, i);
    }

    public void flush(Session session) throws SQLException {
        lastChange = 0;
        if (storage != null) {
            storage.flushFile();
            deletePage(session, head);
            // if we log index changes now, then the index is consistent
            // if we don't log index changes, then the index is only consistent
            // if there are no in doubt transactions
            if (database.getLogIndexChanges() || !database.getLog().containsInDoubtTransactions()) {
                head.setConsistent(true);
            }
            flushHead(session);
        }
    }

    public void close(Session session) throws SQLException {
        flush(session);
        storage = null;
    }

    public void add(Session session, Row r) throws SQLException {
        // create a row that only contains the key values
        setChanged(session);
        Row row = table.getTemplateRow();
        row.setPos(r.getPos());
        for (int i = 0; i < columns.length; i++) {
            Column col = columns[i];
            int idx = col.getColumnId();
            Value v = r.getValue(idx);
            row.setValue(idx, v);
        }
        BtreePage root = getRoot(session);
        int splitPoint = root.add(row, session);
        if (splitPoint != 0) {
            SearchRow pivot = root.getData(splitPoint);
            BtreePage page1 = root;
            BtreePage page2 = root.split(session, splitPoint);
            root = setRoot(new BtreeNode(this, page1, pivot, page2));
            addPage(session, root);
            deletePage(session, head);
            head.setRootPosition(root.getPos());
            flushHead(session);
        }
        rowCount++;
    }

    SearchRow getSearchRow(Row row) {
        SearchRow r = table.getTemplateSimpleRow(columns.length == 1);
        r.setPos(row.getPos());
        for (int j = 0; j < columns.length; j++) {
            int idx = columns[j].getColumnId();
            r.setValue(idx, row.getValue(idx));
        }
        return r;
    }

    public void remove(Session session, Row row) throws SQLException {
        setChanged(session);
        if (rowCount == 1) {
            // TODO performance: maybe improve truncate performance in this case
            truncate(session);
        } else {
            BtreePage root = getRoot(session);
            root.remove(session, row);
            rowCount--;
        }
    }

    public boolean canFindNext() {
        return true;
    }

    public Cursor findNext(Session session, SearchRow first, SearchRow last) throws SQLException {
        return find(session, first, true, last);
    }

    public Cursor find(Session session, SearchRow first, SearchRow last) throws SQLException {
        return find(session, first, false, last);
    }

    private Cursor find(Session session, SearchRow first, boolean bigger, SearchRow last) throws SQLException {
        if (SysProperties.CHECK && storage == null) {
            throw Message.getSQLException(ErrorCode.OBJECT_CLOSED);
        }
        BtreePage root = getRoot(session);
        if (first == null) {
            BtreeCursor cursor = new BtreeCursor(session, this, last);
            root.first(cursor);
            return cursor;
        } else {
            BtreeCursor cursor = new BtreeCursor(session, this, last);
            if (getRowCount(session) == 0 || !root.findFirst(cursor, first, bigger)) {
                cursor.setCurrentRow(null);
            }
            return cursor;
        }
    }

    public int getLookupCost(int rowCount) {
        for (int i = 0, j = 1;; i++) {
            j *= BtreePage.BLOCKS_PER_PAGE;
            if (j > rowCount) {
                return (i + 1);
            }
        }
    }

    public double getCost(Session session, int[] masks) throws SQLException {
        return 10 * getCostRangeIndex(masks, tableData.getRowCount(session));
    }

    public Record read(Session session, DataPage s) throws SQLException {
        char c = (char) s.readByte();
        if (c == 'N') {
            return new BtreeNode(this, s);
        } else if (c == 'L') {
            return new BtreeLeaf(this, session, s);
        } else if (c == 'H') {
            return new BtreeHead(s);
        } else {
            throw Message.getSQLException(ErrorCode.FILE_CORRUPTED_1, getName());
        }
    }

    ObjectArray readRowArray(DataPage s) throws SQLException {
        int len = s.readInt();
        ObjectArray rows = new ObjectArray(len);
        for (int i = 0; i < len; i++) {
            int pos = s.readInt();
            SearchRow r;
            if (pos < 0) {
                r = null;
            } else {
                r = table.getTemplateSimpleRow(columns.length == 1);
                r.setPos(pos);
                for (int j = 0; j < columns.length; j++) {
                    int idx = columns[j].getColumnId();
                    r.setValue(idx, s.readValue());
                }
            }
            rows.add(r);
        }
        return rows;
    }

    public Row getRow(Session session, int pos) throws SQLException {
        return tableData.getRow(session, pos);
    }

    private void flushHead(Session session) throws SQLException {
        updatePage(session, head);
        if (!database.getLogIndexChanges() && !database.getReadOnly()) {
            storage.flushRecord(head);
        }
        trace.debug("Index " + getSQL() + " head consistent=" + head.getConsistent());
    }

    public void truncate(Session session) throws SQLException {
        setChanged(session);
        storage.truncate(session);
        head = new BtreeHead();
        addPage(session, head);
        BtreePage root = setRoot(new BtreeLeaf(this, new ObjectArray()));
        addPage(session, root);
        deletePage(session, head);
        head.setRootPosition(root.getPos());
        head.setConsistent(database.getLogIndexChanges());
        lastChange = System.currentTimeMillis();
        flushHead(session);
        headPos = head.getPos();
        rowCount = 0;
    }

    public void checkRename() throws SQLException {
        // ok
    }

    public boolean needRebuild() {
        return needRebuild;
    }

    public int getRecordOverhead() {
        return storage.getRecordOverhead();
    }

    public long getLastChange() {
        return lastChange;
    }

    public boolean canGetFirstOrLast() {
        return true;
    }

    public SearchRow findFirstOrLast(Session session, boolean first) throws SQLException {
        if (first) {
            // TODO optimization: this loops through NULL elements
            Cursor cursor = find(session, null, false, null);
            while (cursor.next()) {
                SearchRow row = cursor.getSearchRow();
                Value v = row.getValue(columnIds[0]);
                if (v != ValueNull.INSTANCE) {
                    return row;
                }
            }
            return null;
        } else {
            return getRoot(session).getLast(session);
        }
    }

}