Skip to content

Ghidra is a software reverse engineering (SRE) framework

112 KB
Raw Blame
/* ###
 * IP: GHIDRA
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *      http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package db;

import java.io.IOException;
import java.util.*;

import db.Field.UnsupportedFieldException;
import ghidra.util.Msg;
import ghidra.util.datastruct.IntObjectHashtable;
import ghidra.util.exception.*;
import ghidra.util.task.TaskMonitor;

/**
 * Table implementation class.
 * NOTE: Most public methods are synchronized on the associated DBHandle instance
 * to prevent concurrent modification by multiple threads.
 */
public class Table {

	private DBHandle db;

	private TableRecord tableRecord;

	private Schema schema;

	private NodeMgr nodeMgr;

	private int rootBufferId = -1;
	private int recordCount;
	private long maximumKey;

	private IntObjectHashtable<IndexTable> secondaryIndexes = new IntObjectHashtable<>();
	private int[] indexedColumns = new int[0];
	private boolean isIndexed = false;

	/**
	 * Modification counter
	 */
	int modCount = 0;

	/**
	 * Construct a new or existing Table.
	 * @param db database handle
	 * @param tableRecord master table record for this table.
	 * @throws UnsupportedFieldException if unsupported schema field encountered
	 */
	Table(DBHandle db, TableRecord tableRecord) throws UnsupportedFieldException {
		this.db = db;
		this.tableRecord = tableRecord;

		schema = tableRecord.getSchema();
		tableRecord.setTable(this);

		rootBufferId = tableRecord.getRootBufferId();
		recordCount = tableRecord.getRecordCount();
		maximumKey = tableRecord.getMaxKey();

		nodeMgr = new NodeMgr(this, db.getBufferMgr());
	}

	/**
	 * @return the database handle used by this table.
	 */
	DBHandle getDBHandle() {
		return db;
	}

	/**
	 * Determine if this table uses long keys.
	 * @return true if this table utilizes long keys. 
	 */
	public boolean useLongKeys() {
		return schema.useLongKeyNodes();
	}

	/**
	 * Determine if this table uses FixedField keys.
	 * @return true if this table utilizes FixedField keys. 
	 */
	public boolean useFixedKeys() {
		return schema.useFixedKeyNodes();
	}

	/**
	 * Callback notification indicating that the tableRecord has been
	 * changed by the masterTable.  This method is called via the MasterTable
	 * following an undo or redo.
	 */
	void tableRecordChanged() {
		rootBufferId = tableRecord.getRootBufferId();
		recordCount = tableRecord.getRecordCount();
		maximumKey = tableRecord.getMaxKey();
		++modCount;
	}

	/**
	 * Mark table as invalid.
	 * Subsequent table use may generate an exception.
	 */
	void invalidate() {
		tableRecord = null;
		rootBufferId = -1;
		nodeMgr = null;
		++modCount;
	}

	/**
	 * Get this tables master table number.
	 * @return table number for this table.  Each table has a unique table 
	 * number within the master table.
	 */
	long getTableNum() {
		return tableRecord.getTableNum();
	}

	/**
	 * Get table statistics.
	 * @return list of diagnostic statistics data for this table and related index tables.
	 * @throws IOException database IO error
	 */
	public TableStatistics[] getAllStatistics() throws IOException {

		TableStatistics[] statList = new TableStatistics[indexedColumns.length + 1];

		statList[0] = getStatistics();

		for (int i = 0; i < indexedColumns.length; i++) {
			IndexTable indexTable = secondaryIndexes.get(indexedColumns[i]);
			statList[i + 1] = indexTable.getStatistics();
		}
		return statList;
	}

	private BTreeNode getBTreeNode(int bufferId) throws IOException {
		if (schema.useLongKeyNodes()) {
			return nodeMgr.getLongKeyNode(bufferId);
		}
		if (schema.useFixedKeyNodes()) {
			return nodeMgr.getFixedKeyNode(bufferId);
		}
		return nodeMgr.getVarKeyNode(bufferId);
	}

	/**
	 * Get node identified by buffer - must be released by caller (requires DBHandle lock)
	 * @param bufferId buffer ID
	 * @return buffer node
	 * @throws IOException if IO error occurs
	 */
	private FieldKeyNode getFieldKeyNode(int bufferId) throws IOException {
		if (schema.useFixedKeyNodes()) {
			return nodeMgr.getFixedKeyNode(bufferId);
		}
		return nodeMgr.getVarKeyNode(bufferId);
	}

	/**
	 * Accumulate node statistics (requires DBHandle lock)
	 * @param stats statistics collection object
	 * @param bufferId node buffer ID to examine
	 * @throws IOException thrown if IO error occurs
	 */
	private void accumulateNodeStatistics(TableStatistics stats, int bufferId) throws IOException {
		if (bufferId < 0) {
			return;
		}
		BTreeNode node = getBTreeNode(bufferId);
		++stats.bufferCount;

		int[] ids = node.getBufferReferences();

		if (node instanceof InteriorNode) {
			++stats.interiorNodeCnt;
			for (int id : ids) {
				accumulateNodeStatistics(stats, id);
			}
		}
		else {
			++stats.recordNodeCnt;
			for (int id : ids) {
				ChainedBuffer dbBuf = new ChainedBuffer(nodeMgr.getBufferMgr(), id);
				int cnt = dbBuf.getBufferCount();
				stats.chainedBufferCnt += cnt;
				stats.bufferCount += cnt;
			}
		}
		nodeMgr.releaseNodes(); // no need to hang on to buffers
	}

	/**
	 * Compile table statitics.
	 * @return table statistics data
	 * @throws IOException thrown if an IO error occurs
	 */
	public TableStatistics getStatistics() throws IOException {
		synchronized (db) {
			TableStatistics stats = new TableStatistics();
			stats.name = getName();
			try {
				accumulateNodeStatistics(stats, rootBufferId);
				stats.size = stats.bufferCount * nodeMgr.getBufferMgr().getBufferSize();
			}
			finally {
				nodeMgr.releaseNodes();
			}
			return stats;
		}
	}

	/**
	 * Add an existing secondary index.
	 * NOTE: Records for this table instance must not be modified until
	 * after all existing secondary indexes are added.  Failure to comply may
	 * result in an inconsistent index.
	 * @param indexTable secondary index table
	 */
	void addIndex(IndexTable indexTable) {
		secondaryIndexes.put(indexTable.getColumnIndex(), indexTable);
		indexedColumns = secondaryIndexes.getKeys();
		isIndexed = true;
	}

	/**
	 * Callback method for when a new record is added.
	 * Used for maintaining indexes only.  May be called before 
	 * the old record is actually inserted.
	 * @param record new record which has been added
	 * @throws IOException thrown if IO error occurs
	 */
	void insertedRecord(DBRecord record) throws IOException {
		// Add secondary index entries for new record
		for (int indexedColumn : indexedColumns) {
			IndexTable indexTable = secondaryIndexes.get(indexedColumn);
			indexTable.addEntry(record);
		}
	}

	/**
	 * Callback method for when an existing record is modified.
	 * Used for maintaining indexes only.  May be called before 
	 * the old record is actually updated.
	 * @param oldRecord old record
	 * @param newRecord new record
	 * @throws IOException thrown if IO error occurs
	 */
	void updatedRecord(DBRecord oldRecord, DBRecord newRecord) throws IOException {
		// Update secondary indexes which have been affected
		for (int colIx : indexedColumns) {
			Field oldField = oldRecord.getField(colIx);
			Field newField = newRecord.getField(colIx);
			if (!oldField.equals(newField)) {
				IndexTable indexTable = secondaryIndexes.get(colIx);
				indexTable.deleteEntry(oldRecord);
				indexTable.addEntry(newRecord);
			}
		}
	}

	/**
	 * Callback method for when existing records are deleted.
	 * Used for maintaining indexes only.  May be called before 
	 * the old record is actually deleted.
	 * @param oldRecord record which has been deleted
	 * @throws IOException thrown if IO error occurs
	 */
	void deletedRecord(DBRecord oldRecord) throws IOException {
		// Delete secondary index entries
		for (int indexedColumn : indexedColumns) {
			IndexTable indexTable = secondaryIndexes.get(indexedColumn);
			indexTable.deleteEntry(oldRecord);
		}
	}

	/**
	 * Rebuild table and associated indexes to ensure consistent state.
	 * @param monitor task monitor
	 * @throws IOException if unable to rebuild
	 * @throws CancelledException if task was cancelled
	 */
	public void rebuild(TaskMonitor monitor) throws IOException, CancelledException {
		synchronized (db) {

			db.checkTransaction();

			if (rootBufferId < 0) {
				return;
			}

			try {
				BTreeNode rootNode = getBTreeNode(rootBufferId);
				if (!rootNode.isConsistent(getName(), monitor)) {
					throw new IOException("Low level tree consistency error (" + getName() +
						"): Unable to rebuild database");
				}
			}
			catch (IOException t) {
				throw new IOException("Low level tree consistency error (" + getName() +
					"): failed to fetch root buffer: " + t.getMessage());
			}
			finally {
				nodeMgr.releaseNodes();
			}

			// Rebuild table indexes
			try {
				// Remove all index records
				for (int indexedColumn : indexedColumns) {
					IndexTable indexTable = secondaryIndexes.get(indexedColumn);
					monitor.setMessage("Clear Index Table " + getName() + "." +
						schema.getFieldNames()[indexTable.getColumnIndex()]);
					indexTable.indexTable.deleteAll();
				}
			}
			finally {
				nodeMgr.releaseNodes();
			}

			// Determine actual record count, max-key value and rebuild indexes
			monitor.setMessage("Rebuild Table " + getName());
			int actualCount = 0;
			LongField maxKey = null;
			try {
				RecordIterator recIter = iterator();
				while (recIter.hasNext()) {
					DBRecord rec = recIter.next();
					++actualCount;
					Field keyField = rec.getKeyField();
					if ((keyField instanceof LongField) &&
						(maxKey == null || maxKey.compareTo(rec.getKeyField()) > 0)) {
						maxKey = (LongField) keyField;
					}
					insertedRecord(rec);
				}
			}
			finally {
				nodeMgr.releaseNodes();
			}

			if (maxKey != null && maxKey.getLongValue() > tableRecord.getMaxKey()) {
				tableRecord.setMaxKey(maxKey.getLongValue());
			}
			tableRecord.setRecordCount(actualCount);

			if (!isConsistent(monitor)) {
				throw new IOException(
					"Consistency check failed after rebuilding table " + getName());
			}
		}
	}

	/**
	 * Check the consistency of this table and its associated index tables.
	 * @param monitor task monitor
	 * @return true if consistency check passed, else false
	 * @throws IOException thrown if IO error occurs 
	 * @throws CancelledException is task was cancelled
	 */
	public boolean isConsistent(TaskMonitor monitor) throws IOException, CancelledException {
		return isConsistent(null, monitor);
	}

	boolean isConsistent(String indexName, TaskMonitor monitor)
			throws IOException, CancelledException {
		synchronized (db) {

			if (rootBufferId < 0) {
				return true;
			}

			monitor.setMessage("Check Table " + getName());

			boolean consistent;
			try {
				BTreeNode rootNode = getBTreeNode(rootBufferId);
				consistent = rootNode.isConsistent(getName(), monitor);
			}
			catch (IOException t) {
				Msg.debug(this, "Consistency Error (" + getName() +
					"): failed to fetch root buffer: " + t.getMessage());
				return false;
			}
			finally {
				nodeMgr.releaseNodes();
			}

			// Check consistency of index tables
			for (int indexedColumn : indexedColumns) {
				IndexTable indexTable = secondaryIndexes.get(indexedColumn);
				monitor.setMessage("Check Table " + getName() + "." +
					schema.getFieldNames()[indexTable.getColumnIndex()]);
				consistent &= indexTable.isConsistent(monitor);
			}

			HashMap<Integer, Integer> missingIndexRecMap = new HashMap<>();
			int actualCount = 0;
			RecordIterator recIter = iterator();
			while (recIter.hasNext()) {
				DBRecord rec = recIter.next();
				++actualCount;

				// Check for bad index tables (missing or invalid entries)
				for (int indexedColumn : indexedColumns) {
					IndexTable indexTable = secondaryIndexes.get(indexedColumn);
					Field f = rec.getField(indexedColumn);
					if (indexTable.isSparseIndex && f.isNull()) {
						continue; // skip unindexed field
					}
					boolean found = false;
					Field[] keys = indexTable.findPrimaryKeys(f);
					for (Field key : keys) {
						if (key.equals(rec.getKeyField())) {
							found = true;
							break;
						}
					}
					if (!found) {
						consistent = false;
						Integer missing = missingIndexRecMap.get(indexTable.getColumnIndex());
						if (missing == null) {
							missingIndexRecMap.put(indexTable.getColumnIndex(), 1);
						}
						else {
							missingIndexRecMap.put(indexTable.getColumnIndex(), missing + 1);
						}
						logIndexConsistencyError(
							schema.getFieldNames()[indexTable.getColumnIndex()],
							"Index table does not reference record key: " +
								rec.getKeyField().getValueAsString());
					}
				}

			}
			if (actualCount != getRecordCount()) {
				consistent = false;
				logIndexConsistencyError(indexName,
					"Table record count inconsistent: iterator-count=" + actualCount +
						" stored-count=" + getRecordCount());
			}
			for (int indexCol : missingIndexRecMap.keySet()) {
				int missing = missingIndexRecMap.get(indexCol);
				logIndexConsistencyError(schema.getFieldNames()[indexCol],
					"Index is missing " + missing + " record references");
			}

			// Check for bad index tables (missing or invalid entries)
			for (int indexedColumn : indexedColumns) {
				IndexTable indexTable = secondaryIndexes.get(indexedColumn);

				monitor.setMessage("Check Index " + getName() + "." +
					schema.getFieldNames()[indexTable.getColumnIndex()]);

				HashSet<Field> keySet = new HashSet<>();
				int extra = 0;
				DBFieldIterator keyIterator = indexTable.keyIterator();
				while (keyIterator.hasNext()) {
					Field key = keyIterator.next();
					if (getRecord(key) == null) {
						++extra;
					}
					if (!keySet.add(key)) {
						logIndexConsistencyError(
							schema.getFieldNames()[indexTable.getColumnIndex()],
							"Index table references duplicate key: " + key.getValueAsString());
					}
				}
				if (extra != 0) {
					consistent = false;
					logIndexConsistencyError(schema.getFieldNames()[indexTable.getColumnIndex()],
						"Index table references " + extra + " nonexistent record keys");
				}
			}

			return consistent;
		}
	}

	void logIndexConsistencyError(String indexName, String msg) {
		Msg.debug(this, "Index Consistency Error (" + getName() +
			(indexName != null ? ("." + indexName) : "") + "): " + msg);
	}

	/**
	 * Delete all records within this table.
	 * @throws IOException if IO error occurs
	 */
	public void deleteAll() throws IOException {
		synchronized (db) {
			db.checkTransaction();
			if (rootBufferId < 0) {
				return;
			}
			try {
				BTreeNode rootNode = getBTreeNode(rootBufferId);
				try {
					// Delete all records
					rootNode.delete();

					// Delete all index entries
					for (int indexedColumn : indexedColumns) {
						IndexTable indexTable = secondaryIndexes.get(indexedColumn);
						indexTable.deleteAll();
					}
				}
				finally {
					tableRecord.setRootBufferId(rootBufferId = -1);
					tableRecord.setRecordCount(recordCount = 0);
					tableRecord.setMaxKey(maximumKey = Long.MIN_VALUE);
				}
			}
			finally {
				nodeMgr.releaseNodes();
			}

		}
	}

	/**
	 * Get the list of columns which are indexed
	 * @return list of indexed columns
	 */
	public int[] getIndexedColumns() {
		return indexedColumns;
	}

	/**
	 * Remove the index associated with the specified column.
	 * @param columnIndex column corresponding to the column index which 
	 * should be deleted.
	 * @throws IOException thrown if IO error occurs
	 */
	void removeIndex(int columnIndex) throws IOException {
		IndexTable indexTable = secondaryIndexes.get(columnIndex);
		if (indexTable != null) {
			indexTable.deleteAll();
			db.getMasterTable().deleteTableRecord(indexTable.getTableNum());
			secondaryIndexes.remove(columnIndex);
			indexedColumns = secondaryIndexes.getKeys();
		}
	}

	/**
	 * Get this tables schema.
	 * @return table schema
	 */
	public Schema getSchema() {
		return schema;
	}

	/**
	 * Get table name
	 * @return table name
	 */
	public String getName() {
		return tableRecord.getName();
	}

	/**
	 * Change the name of this table
	 * @param name new table name
	 * @return true if rename successful
	 * @throws DuplicateNameException if new table name already exists
	 */
	public boolean setName(String name) throws DuplicateNameException {
		return db.setTableName(getName(), name);
	}

	/**
	 * Get record count
	 * @return record count
	 */
	public int getRecordCount() {
		return (tableRecord == null ? 0 : tableRecord.getRecordCount());
	}

	/**
	 * Get the maximum record key which has ever been assigned within this table.
	 * This method is only valid for those tables which employ a long key and may
	 * not reflect records which have been removed (i.e., returned key may not 
	 * correspond to an existing record).
	 * @return maximum record key.
	 */
	public long getMaxKey() {
		return tableRecord.getMaxKey();
	}

	/**
	 * Get the next available key.
	 * This method is only valid for those tables which employ a long key.
	 * @return next available key.
	 */
	public long getKey() {
		long key = getMaxKey();
		if (key == Long.MIN_VALUE) {
			return 0;
		}
		return key + 1;
	}

//	/**
//	 * Sets the current root node for this table.
//	 * If the root changes the master table must be updated.
//	 * @param rootNode
//	 */
//	private void setRootNode(LongKeyNode rootNode) {
//		int id = rootNode.getBufferId();
//		if (rootBufferId != id) {
//			tableRecord.setRootBufferId(id);
//			rootBufferId = id;
//		}
//	}
//	
//	/**
//	 * Sets the current root node for this table.
//	 * If the root changes the master table must be updated.
//	 * @param rootNode
//	 */
//	private void setRootNode(VarKeyNode rootNode) {
//		int id = rootNode.getBufferId();
//		if (rootBufferId != id) {
//			tableRecord.setRootBufferId(id);
//			rootBufferId = id;
//		}
//	}

	/**
	 * Determine if this table contains a record with the specified key.
	 * @param key record key.
	 * @return true if record exists with key, else false.
	 * @throws IOException thrown if IO error occurs
	 */
	public boolean hasRecord(long key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return false;
			}
			boolean result = false;
			try {
				LongKeyRecordNode leaf = nodeMgr.getLongKeyNode(rootBufferId).getLeafNode(key);
				result = leaf.getKeyIndex(key) >= 0;
			}
			finally {
				nodeMgr.releaseNodes();
			}
			return result;
		}
	}

	/**
	 * Determine if this table contains a record with the specified key.
	 * @param key record key.
	 * @return true if record exists with key, else false.
	 * @throws IOException throw if an IO Error occurs
	 */
	public boolean hasRecord(Field key) throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				return hasRecord(key.getLongValue());
			}
			if (rootBufferId < 0) {
				return false;
			}
			boolean result = false;
			try {
				FieldKeyRecordNode leaf = getFieldKeyNode(rootBufferId).getLeafNode(key);
				result = leaf.getKeyIndex(key) >= 0;
			}
			finally {
				nodeMgr.releaseNodes();
			}
			return result;
		}
	}

	/**
	 * Get the record identified by the specified key value.
	 * @param key unique record key.
	 * @return Record the record identified by key, or null if record was not
	 * found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecord(long key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			try {
				LongKeyRecordNode leaf = nodeMgr.getLongKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecord(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record identified by the specified key value.
	 * @param key unique record key.
	 * @return Record the record identified by key, or null if record was not
	 * found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecord(Field key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			if (key instanceof LongField) {
				return getRecord(key.getLongValue());
			}
			FieldKeyRecordNode leaf;
			try {
				if (key instanceof FixedField) {
					leaf = nodeMgr.getFixedKeyNode(rootBufferId).getLeafNode(key);
					return leaf.getRecord(key, schema);
				}
				leaf = getFieldKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecord(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the maximum key value which is less than  
	 * the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value less than the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordBefore(long key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			try {
				LongKeyRecordNode leaf = nodeMgr.getLongKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordBefore(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the maximum key value which is less than  
	 * the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value less than the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordBefore(Field key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			if (key instanceof LongField) {
				return getRecordBefore(key.getLongValue());
			}
			try {
				FieldKeyRecordNode leaf = getFieldKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordBefore(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the minimum key value which is greater than 
	 * the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value greater than the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordAfter(long key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			try {
				LongKeyRecordNode leaf = nodeMgr.getLongKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordAfter(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the minimum key value which is greater than 
	 * the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value greater than the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordAfter(Field key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			if (key instanceof LongField) {
				return getRecordAfter(key.getLongValue());
			}
			try {
				FieldKeyRecordNode leaf = getFieldKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordAfter(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the maximum key value which is less than or equal 
	 * to the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value less than or equal to the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordAtOrBefore(long key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			try {
				LongKeyRecordNode leaf = nodeMgr.getLongKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordAtOrBefore(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the maximum key value which is less than or equal 
	 * to the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value less than or equal to the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordAtOrBefore(Field key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			if (key instanceof LongField) {
				return getRecordAtOrBefore(key.getLongValue());
			}
			try {
				FieldKeyRecordNode leaf = getFieldKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordAtOrBefore(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the minimum key value which is greater than or equal 
	 * to the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value greater than or equal to the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordAtOrAfter(long key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			try {
				LongKeyRecordNode leaf = nodeMgr.getLongKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordAtOrAfter(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Get the record with the minimum key value which is greater than or equal 
	 * to the specified key.
	 * @param key unique key which may or may not exist within the table.
	 * @return the first record which has a key value greater than or equal to the 
	 * specified key, or null if no record was found.
	 * @throws IOException throw if an IO Error occurs
	 */
	public DBRecord getRecordAtOrAfter(Field key) throws IOException {
		synchronized (db) {
			if (rootBufferId < 0) {
				return null;
			}
			if (key instanceof LongField) {
				return getRecordAtOrAfter(key.getLongValue());
			}
			try {
				FieldKeyRecordNode leaf = getFieldKeyNode(rootBufferId).getLeafNode(key);
				return leaf.getRecordAtOrAfter(key, schema);
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}
	}

	/**
	 * Put the specified record into the stored BTree.
	 * @param record the record to be stored.
	 * @throws IOException throw if an IO Error occurs
	 */
	public void putRecord(DBRecord record) throws IOException {
		synchronized (db) {
			db.checkTransaction();
			if (schema.useLongKeyNodes()) {
				putLongKeyRecord(record);
			}
			else {
				putFieldKeyRecord(record);
			}

		}
	}

	/**
	 * Store a record which uses a long key (requires DBHandle lock)
	 * @param record recore to be inserted or updated
	 * @throws IOException throw if an IO Error occurs
	 */
	private void putLongKeyRecord(DBRecord record) throws IOException {

//		boolean inserted = false;
		try {

// ?? Do we need to validate record against schema

			// Establish root node
			++modCount;
			LongKeyNode rootNode = null;
			if (rootBufferId < 0) {
				rootNode = LongKeyRecordNode.createRecordNode(nodeMgr, schema);
			}
			else {
				rootNode = nodeMgr.getLongKeyNode(rootBufferId);
			}

			// Put record and update root buffer ID
			long recKey = record.getKey();
			LongKeyRecordNode leaf = rootNode.getLeafNode(recKey);
			rootNode = leaf.putRecord(record, isIndexed ? this : null);
			int id = rootNode.getBufferId();
			if (rootBufferId != id) {
				rootBufferId = id;
				tableRecord.setRootBufferId(rootBufferId);
			}

			// Update maximum key
			if (maximumKey < recKey) {
				maximumKey = recKey;
				tableRecord.setMaxKey(maximumKey);
			}
		}
		finally {
			// Release node buffers and update record count
			int delta = nodeMgr.releaseNodes();
			if (delta != 0) {
//				inserted = true;
				recordCount += delta;
				tableRecord.setRecordCount(recordCount);
			}
		}
	}

	/**
	 * Store a record which uses a Field key (requires DBHandle lock)
	 * @param record record to be inserted or updated
	 * @throws IOException throw if an IO Error occurs
	 */
	private void putFieldKeyRecord(DBRecord record) throws IOException {

//		boolean inserted = false;
		try {

// ?? Do we need to validate record against schema

			// Establish root node
			++modCount;
			FieldKeyNode rootNode = null;
			if (rootBufferId < 0) {
				rootNode = schema.useFixedKeyNodes() ? FixedKeyRecordNode.createRecordNode(nodeMgr)
						: new VarKeyRecordNode(nodeMgr, schema.getKeyFieldType());
			}
			else {
				rootNode = getFieldKeyNode(rootBufferId);
			}

			// Put record and update root buffer ID
			Field recKey = record.getKeyField();
			FieldKeyRecordNode leaf = rootNode.getLeafNode(recKey);
			rootNode = leaf.putRecord(record, isIndexed ? this : null);
			int id = rootNode.getBufferId();
			if (rootBufferId != id) {
				rootBufferId = id;
				tableRecord.setRootBufferId(rootBufferId);
			}

			// NOTE: Maximum key is not tracked

		}
		finally {
			// Release node buffers and update record count
			int delta = nodeMgr.releaseNodes();
			if (delta != 0) {
//				inserted = true;
				recordCount += delta;
				tableRecord.setRecordCount(recordCount);
			}
		}
	}

	/**
	 * Delete a record identified by the specified key value.
	 * @param key unique record key.
	 * @return true if record was deleted successfully.
	 * @throws IOException throw if an IO Error occurs
	 */
	public boolean deleteRecord(long key) throws IOException {
		synchronized (db) {
			db.checkTransaction();
			boolean result = false;

			if (rootBufferId < 0) {
				return false;
			}
			if (!schema.useLongKeyNodes()) {
				throw new IllegalArgumentException("Field key required");
			}
			try {
				++modCount;
				LongKeyNode rootNode = nodeMgr.getLongKeyNode(rootBufferId);
				LongKeyRecordNode leaf = rootNode.getLeafNode(key);
				rootNode = leaf.deleteRecord(key, isIndexed ? this : null);

				if (rootNode != null) {
					int id = rootNode.getBufferId();
					if (rootBufferId != id) {
						rootBufferId = id;
						tableRecord.setRootBufferId(rootBufferId);
					}
				}
				else {
					rootBufferId = -1;
					tableRecord.setRootBufferId(rootBufferId);
				}

			}
			finally {
				// Release node buffers and update record count
				int delta = nodeMgr.releaseNodes();
				if (delta != 0) {
					result = true;
					recordCount += delta;
					tableRecord.setRecordCount(recordCount);
				}
			}
			return result;
		}
	}

	/**
	 * Delete a record identified by the specified key value.
	 * @param key unique record key.
	 * @return true if record was deleted successfully.
	 * @throws IOException throw if an IO Error occurs
	 */
	public boolean deleteRecord(Field key) throws IOException {
		synchronized (db) {
			db.checkTransaction();
			boolean result = false;

			if (rootBufferId < 0) {
				return false;
			}
			if (key instanceof LongField) {
				return deleteRecord(key.getLongValue());
			}
			try {
				++modCount;
				FieldKeyNode rootNode = getFieldKeyNode(rootBufferId);
				FieldKeyRecordNode leaf = rootNode.getLeafNode(key);
				rootNode = leaf.deleteRecord(key, isIndexed ? this : null);

				if (rootNode != null) {
					int id = rootNode.getBufferId();
					if (rootBufferId != id) {
						rootBufferId = id;
						tableRecord.setRootBufferId(rootBufferId);
					}
				}
				else {
					rootBufferId = -1;
					tableRecord.setRootBufferId(rootBufferId);
				}

			}
			finally {
				// Release node buffers and update record count
				int delta = nodeMgr.releaseNodes();
				if (delta != 0) {
					result = true;
					recordCount += delta;
					tableRecord.setRecordCount(recordCount);
				}
			}
			return result;
		}
	}

	/**
	 * Delete all records whose keys fall within the specified range, inclusive.
	 * @param startKey minimum key value
	 * @param endKey maximum key value
	 * @return true if one or more records were deleted.
	 * @throws IOException thrown if an IO error occurs
	 */
	public boolean deleteRecords(long startKey, long endKey) throws IOException {
		synchronized (db) {
			db.checkTransaction();
			if (startKey > endKey) {
				throw new IllegalArgumentException();
			}
			if (!schema.useLongKeyNodes()) {
				throw new IllegalArgumentException("Long key required");
			}

			boolean result = false;
			if (rootBufferId < 0) {
				return result;
			}

			try {
				++modCount;
				LongKeyNode rootNode = nodeMgr.getLongKeyNode(rootBufferId);
				LongKeyRecordNode leaf = rootNode.getLeafNode(startKey);

				try {
					// Handle partial first leaf where leftmost key is not deleted
					int index = leaf.getKeyIndex(startKey);
					long lastKey = 0;
					if (index < 0) {
						index = -index - 1;
					}
					if (index > 0) {
						int lastIndex = leaf.getKeyIndex(endKey);
						if (lastIndex < 0) {
							lastIndex = -lastIndex - 2;
						}
						// delete individual records within first leaf
						while (index <= lastIndex--) {
							if (isIndexed) {
								deletedRecord(leaf.getRecord(schema, index));
							}
							leaf.remove(index);
						}
						result = true;
						if (index < leaf.keyCount) {
							return result;
						}
						LongKeyRecordNode nextLeaf = leaf.getNextLeaf();
						if (nextLeaf == null) {
							return result;
						}
						lastKey = nextLeaf.getKey(nextLeaf.keyCount - 1);
						leaf = rootNode.getLeafNode(lastKey);
						index = 0;
					}
					else {
						lastKey = leaf.getKey(leaf.keyCount - 1);
					}

					// Handle additional whole leaves
					while (lastKey <= endKey) {
						if (isIndexed) {
							for (int n = 0; n < leaf.keyCount; n++) {
								deletedRecord(leaf.getRecord(schema, n));
							}
						}
						LongKeyRecordNode nextLeaf = leaf.getNextLeaf();
						rootNode = leaf.removeLeaf();
						result = true;
						if (nextLeaf == null) {
							return result;
						}
						lastKey = nextLeaf.getKey(nextLeaf.keyCount - 1);
						leaf = rootNode.getLeafNode(lastKey);
					}

					// Handle final leaf
					// delete individual records within first leaf
					int lastIndex = leaf.getKeyIndex(endKey);
					if (lastIndex < 0) {
						lastIndex = -lastIndex - 2;
					}
					long key = leaf.getKey(0);
					while (index <= lastIndex--) {
						if (isIndexed) {
							deletedRecord(leaf.getRecord(schema, index));
						}
						leaf.remove(index);
						result = true;
					}
					if (index == 0 && leaf.parent != null) {
						leaf.parent.keyChanged(key, leaf.getKey(0));
					}
				}
				finally {
					// Update root node
					if (rootNode != null) {
						int id = rootNode.getBufferId();
						if (rootBufferId != id) {
							rootBufferId = id;
							tableRecord.setRootBufferId(rootBufferId);
						}
					}
					else {
						rootBufferId = -1;
						tableRecord.setRootBufferId(rootBufferId);
					}
				}

			}
			finally {
				// Release node buffers and update record count
				int delta = nodeMgr.releaseNodes();
				if (delta != 0) {
					result = true;
					recordCount += delta;
					tableRecord.setRecordCount(recordCount);
				}
			}

			return result;
		}
	}

	/**
	 * Delete all records whose keys fall within the specified range, inclusive.
	 * @param startKey minimum key value
	 * @param endKey maximum key value
	 * @return true if one or more records were deleted.
	 * @throws IOException thrown if an IO error occurs
	 */
	public boolean deleteRecords(Field startKey, Field endKey) throws IOException {
		synchronized (db) {
			db.checkTransaction();
			if (startKey.compareTo(endKey) > 0) {
				throw new IllegalArgumentException();
			}
			if (schema.useLongKeyNodes()) {
				throw new IllegalArgumentException("Field key required");
			}

			boolean result = false;
			if (rootBufferId < 0) {
				return result;
			}

			try {
				++modCount;
				FieldKeyNode rootNode = getFieldKeyNode(rootBufferId);
				FieldKeyRecordNode leaf = rootNode.getLeafNode(startKey);

				try {
					// Handle partial first leaf where leftmost key is not deleted
					int index = leaf.getKeyIndex(startKey);
					Field lastKey = null;
					if (index < 0) {
						index = -index - 1;
					}
					if (index > 0) {
						int lastIndex = leaf.getKeyIndex(endKey);
						if (lastIndex < 0) {
							lastIndex = -lastIndex - 2;
						}
						// delete individual records within first leaf
						while (index <= lastIndex--) {
							if (isIndexed) {
								deletedRecord(leaf.getRecord(schema, index));
							}
							leaf.remove(index);
						}
						result = true;
						if (index < leaf.getKeyCount()) {
							return result;
						}
						RecordNode nextLeaf = leaf.getNextLeaf();
						if (nextLeaf == null) {
							return result;
						}
						lastKey = nextLeaf.getKeyField(nextLeaf.getKeyCount() - 1);
						leaf = rootNode.getLeafNode(lastKey);
						index = 0;
					}
					else {
						lastKey = leaf.getKeyField(leaf.getKeyCount() - 1);
					}

					// Handle additional whole leaves
					while (lastKey.compareTo(endKey) <= 0) {
						if (isIndexed) {
							int count = leaf.getKeyCount();
							for (int n = 0; n < count; n++) {
								deletedRecord(leaf.getRecord(schema, n));
							}
						}
						RecordNode nextLeaf = leaf.getNextLeaf();
						rootNode = leaf.removeLeaf();
						result = true;
						if (nextLeaf == null) {
							return result;
						}
						lastKey = nextLeaf.getKeyField(nextLeaf.getKeyCount() - 1);
						leaf = rootNode.getLeafNode(lastKey);
					}

					// Handle final leaf
					// delete individual records within first leaf
					int lastIndex = leaf.getKeyIndex(endKey);
					if (lastIndex < 0) {
						lastIndex = -lastIndex - 2;
					}
					Field key = leaf.getKeyField(0);
					while (index <= lastIndex--) {
						if (isIndexed) {
							deletedRecord(leaf.getRecord(schema, index));
						}
						leaf.remove(index);
						result = true;
					}
					if (index == 0 && leaf.getParent() != null) {
						leaf.getParent().keyChanged(key, leaf.getKeyField(0), leaf);
					}
				}
				finally {
					// Update root node
					if (rootNode != null) {
						int id = rootNode.getBufferId();
						if (rootBufferId != id) {
							rootBufferId = id;
							tableRecord.setRootBufferId(rootBufferId);
						}
					}
					else {
						rootBufferId = -1;
						tableRecord.setRootBufferId(rootBufferId);
					}
				}

			}
			finally {
				// Release node buffers and update record count
				int delta = nodeMgr.releaseNodes();
				if (delta != 0) {
					result = true;
					recordCount += delta;
					tableRecord.setRecordCount(recordCount);
				}
			}

			return result;
		}
	}

	/**
	 * Find the primary keys corresponding to those records which contain the
	 * specified field value in the specified record column.  The table must
	 * have been created with long keys and a secondary index on the specified 
	 * column index.
	 * @param field the field value
	 * @param columnIndex the record schema column which should be searched.
	 * @return list of primary keys
	 * @throws IOException if a secondary index does not exist for the specified
	 * column, or the wrong field type was specified, or an I/O error occurs.
	 */
	public Field[] findRecords(Field field, int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.findPrimaryKeys(field);
		}
	}

	/**
	 * Get the number of records which contain the
	 * specified field value in the specified record column.  The table must
	 * have been created with a secondary index on the specified column index.
	 * @param field the field value
	 * @param columnIndex the record schema column which should be searched.
	 * @return number of records which match the specified field value.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column, or the wrong field type was specified, or an I/O error occurs.
	 */
	public int getMatchingRecordCount(Field field, int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.getKeyCount(field);
		}
	}

	/**
	 * Determine if a record exists with the specified value within the specified
	 * column.  The table must have been created with a secondary index on the 
	 * specified column index.
	 * @param field the field value
	 * @param columnIndex the record schema column which should be searched.
	 * @return true if one or more records exis with the specified value.
	 * @throws IOException thrown if IO error occurs
	 */
	public boolean hasRecord(Field field, int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.hasRecord(field);
		}
	}

	/**
	 * Iterate over all the unique index field values.  Index values are
	 * returned in an ascending sorted order with the initial iterator position
	 * set to the minimum index value.
	 * @param columnIndex identifies an indexed column.
	 * @return index field iterator.
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexFieldIterator(int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.indexIterator();
		}
	}

	/**
	 * Iterate over all the unique index field values within the specified range identified
	 * by minField and maxField.  Index values are returned in an ascending sorted order.
	 * @param minField minimum index column value, if null absolute minimum is used
	 * @param maxField maximum index column value, if null absolute maximum is used
	 * @param before if true initial position is before minField, else position
	 * is after maxField
	 * @param columnIndex identifies an indexed column.
	 * @return index field iterator.
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexFieldIterator(Field minField, Field maxField, boolean before,
			int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.indexIterator(minField, maxField, before);
		}
	}

	/**
	 * Iterate over all the unique index field values within the specified range identified
	 * by minField and maxField.  Index values are returned in an ascending sorted order with the 
	 * initial iterator position corresponding to the startField.
	 * @param minField minimum index column value, if null absolute minimum is used
	 * @param maxField maximum index column value, if null absolute maximum is used
	 * @param startField index column value corresponding to initial position of iterator
	 * @param before if true initial position is before startField value, else position
	 * is after startField value
	 * @param columnIndex identifies an indexed column.
	 * @return index field iterator.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column or an I/O error occurs.
	 */
	public DBFieldIterator indexFieldIterator(Field minField, Field maxField, Field startField,
			boolean before, int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.indexIterator(minField, maxField, startField, before);
		}
	}

	/**
	 * Iterate over the records using a secondary index.  Sorting occurs on the
	 * specified schema column.  This table must have been constructed with a secondary
	 * index on the specified column.
	 * @param columnIndex schema column to sort on.
	 * @return RecordIterator record iterator.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column or an I/O error occurs.
	 */
	public RecordIterator indexIterator(int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return new KeyToRecordIterator(this, indexTable.keyIterator());
		}
	}

	/**
	 * Iterate over a range of records using a secondary index.  Sorting occurs on the
	 * specified schema column. The iterator is initially positioned before the startValue.
	 * This table must have been constructed with a secondary index on the specified column.
	 * @param columnIndex schema column to sort on.
	 * @param startValue the starting and minimum value of the secondary index field.
	 * @param endValue the ending and maximum value of the secondary index field.
	 * @param atStart if true, position the iterator before the start value. 
	 * Otherwise, position the iterator after the end value.
	 * 
	 * @return record iterator.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column, or the wrong field type was specified, or an I/O error occurs.
	 */
	public RecordIterator indexIterator(int columnIndex, Field startValue, Field endValue,
			boolean atStart) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return new KeyToRecordIterator(this,
				indexTable.keyIterator(startValue, endValue, atStart));
		}
	}

	/**
	 * Iterate over the records using a secondary index.  Sorting occurs on the
	 * specified schema column.  The iterator's initial position immediately follows 
	 * the specified startValue. If this value does not exist, the initial position corresponds
	 * to where it would exist.
	 * This table must have been constructed with a secondary index on the specified column.
	 * @param columnIndex schema column to sort on.
	 * @param startValue the starting value of the secondary index field.
	 * @return RecordIterator record iterator.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column, or the wrong field type was specified, or an I/O error occurs.
	 */
	public RecordIterator indexIteratorAfter(int columnIndex, Field startValue) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return new KeyToRecordIterator(this, indexTable.keyIteratorAfter(startValue));
		}
	}

	/**
	 * Iterate over the records using a secondary index.  Sorting occurs on the
	 * specified schema column.  The iterator's initial position immediately precedes 
	 * the specified startValue. If this value does not exist, the initial position corresponds
	 * to where it would exist.
	 * This table must have been constructed with a secondary index on the specified column.
	 * @param columnIndex schema column to sort on.
	 * @param startValue the starting value of the secondary index field.
	 * @return RecordIterator record iterator.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column, or the wrong field type was specified, or an I/O error occurs.
	 */
	public RecordIterator indexIteratorBefore(int columnIndex, Field startValue)
			throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return new KeyToRecordIterator(this, indexTable.keyIteratorBefore(startValue));
		}
	}

	/**
	 * Iterate over the records using a secondary index.  Sorting occurs on the
	 * specified schema column.  The iterator's initial position immediately follows 
	 * the specified startValue and primaryKey. If no such entry exists, the initial position 
	 * corresponds to where it would exist.
	 * <p>
	 * This table must have been constructed with a secondary index on the specified column.
	 * 
	 * @param columnIndex schema column to sort on.
	 * @param startValue the starting value of the secondary index field.
	 * @param primaryKey the primary key associated with the startField.
	 * @return RecordIterator record iterator.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column, or the wrong field type was specified, or an I/O error occurs.
	 */
	public RecordIterator indexIteratorAfter(int columnIndex, Field startValue, Field primaryKey)
			throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return new KeyToRecordIterator(this,
				indexTable.keyIteratorAfter(startValue, primaryKey));
		}
	}

	/**
	 * Iterate over the records using a secondary index.  Sorting occurs on the
	 * specified schema column.  The iterator's initial position immediately precedes 
	 * the specified startValue and primaryKey. If no such entry exists, the initial position 
	 * corresponds to where it would exist.
	 * <p>
	 * This table must have been constructed with a secondary index on the specified column.
	 * 
	 * @param columnIndex schema column to sort on.
	 * @param startValue the starting value of the secondary index field.
	 * @param primaryKey the primary key associated with the startField.
	 * @return RecordIterator record iterator.
	 * @throws IOException if a secondary index does not exist for the specified
	 * column, or the wrong field type was specified, or an I/O error occurs.
	 */
	public RecordIterator indexIteratorBefore(int columnIndex, Field startValue, Field primaryKey)
			throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return new KeyToRecordIterator(this,
				indexTable.keyIteratorBefore(startValue, primaryKey));
		}
	}

	/**
	 * Iterate over all primary keys sorted based upon the associated index key.
	 * @param columnIndex schema column to sort on.
	 * @return primary key iterator
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexKeyIterator(int columnIndex) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.keyIterator();
		}
	}

	/**
	 * Iterate over all primary keys sorted based upon the associated index key.
	 * The iterator is initially positioned before the first index buffer whose index key 
	 * is greater than or equal to the specified startField value.
	 * @param columnIndex schema column to sort on
	 * @param startField index column value which determines initial position of iterator
	 * @return primary key iterator
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexKeyIteratorBefore(int columnIndex, Field startField)
			throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.keyIteratorBefore(startField);
		}
	}

	/**
	 * Iterate over all primary keys sorted based upon the associated index key.
	 * The iterator is initially positioned after the index buffer whose index key 
	 * is equal to the specified startField value or immediately before the first 
	 * index buffer whose index key is greater than the specified startField value.
	 * @param columnIndex schema column to sort on
	 * @param startField index column value which determines initial position of iterator
	 * @return primary key iterator
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexKeyIteratorAfter(int columnIndex, Field startField)
			throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.keyIteratorAfter(startField);
		}
	}

	/**
	 * Iterate over all primary keys sorted based upon the associated index key.
	 * The iterator is initially positioned before the primaryKey within the index buffer 
	 * whose index key is equal to the specified startField value or immediately before the first 
	 * index buffer whose index key is greater than the specified startField value.
	 * @param columnIndex schema column to sort on
	 * @param startField index column value which determines initial position of iterator
	 * @param primaryKey initial position within index buffer if index key matches startField value.
	 * @return primary key iterator
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexKeyIteratorBefore(int columnIndex, Field startField,
			Field primaryKey) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.keyIteratorBefore(startField, primaryKey);
		}
	}

	/**
	 * Iterate over all primary keys sorted based upon the associated index key.
	 * The iterator is initially positioned after the primaryKey within the index buffer 
	 * whose index key is equal to the specified startField value or immediately before the first 
	 * index buffer whose index key is greater than the specified startField value.
	 * @param columnIndex schema column to sort on
	 * @param startField index column value which determines initial position of iterator
	 * @param primaryKey initial position within index buffer if index key matches startField value.
	 * @return primary key iterator
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexKeyIteratorAfter(int columnIndex, Field startField,
			Field primaryKey) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.keyIteratorAfter(startField, primaryKey);
		}
	}

	/**
	 * Iterate over all primary keys sorted based upon the associated index key.
	 * The iterator is limited to range of index keys of minField through maxField, inclusive.
	 * If atMin is true, the iterator is initially positioned before the first index 
	 * buffer whose index key is greater than or equal to the specified minField value. 
	 * If atMin is false, the iterator is initially positioned after the first index 
	 * buffer whose index key is less than or equal to the specified maxField value. 
	 * @param columnIndex schema column to sort on
	 * @param minField minimum index column value
	 * @param maxField maximum index column value
	 * @param atMin if true, position iterator before minField value, 
	 * Otherwise, position iterator after maxField value.
	 * @return primary key iterator
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexKeyIterator(int columnIndex, Field minField, Field maxField,
			boolean atMin) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.keyIterator(minField, maxField, atMin);
		}
	}

	/**
	 * Iterate over all primary keys sorted based upon the associated index key.
	 * The iterator is limited to range of index keys of minField through maxField, inclusive.
	 * The iterator is initially positioned before or after the specified startField index value. 
	 * @param columnIndex schema column to sort on
	 * @param minField minimum index column value
	 * @param maxField maximum index column value
	 * @param startField starting indexed value position
	 * @param before if true positioned before startField value, else positioned after maxField
	 * @return primary key iterator
	 * @throws IOException thrown if IO error occurs
	 */
	public DBFieldIterator indexKeyIterator(int columnIndex, Field minField, Field maxField,
			Field startField, boolean before) throws IOException {
		synchronized (db) {
			IndexTable indexTable = secondaryIndexes.get(columnIndex);
			if (indexTable == null) {
				throw new IOException("Index required (" + getName() + "," + columnIndex + ")");
			}
			return indexTable.keyIterator(minField, maxField, startField, before);
		}
	}

	/**
	 * Iterate over the records in ascending sorted order.  Sorting occurs on the primary key value.
	 * @return record iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public RecordIterator iterator() throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				return new LongKeyRecordIterator();
			}
			return new FieldKeyRecordIterator(null, null, null);
		}
	}

	/**
	 * Iterate over the records in ascending sorted order.  Sorting occurs on the primary key value
	 * starting at the specified startKey.
	 * @param startKey the first primary key.
	 * @return record iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public RecordIterator iterator(long startKey) throws IOException {
		synchronized (db) {
			if (!schema.useLongKeyNodes()) {
				throw new IllegalArgumentException("Field key required");
			}
			return new LongKeyRecordIterator(Long.MIN_VALUE, Long.MAX_VALUE, startKey);
		}
	}

	/**
	 * Iterate over the records in ascending sorted order.  Sorting occurs on the primary key value
	 * starting at the specified startKey.
	 * @param minKey the minimum primary key.
	 * @param maxKey the maximum primary key.
	 * @param startKey the initial iterator position.
	 * @return record iterator
	 * @throws IOException if an I/O error occurs.
	 * @throws IllegalArgumentException if long keys are not in use or startKey 
	 * is less than minKey or greater than maxKey.
	 */
	public RecordIterator iterator(long minKey, long maxKey, long startKey) throws IOException {
		synchronized (db) {
			if (!schema.useLongKeyNodes()) {
				throw new IllegalArgumentException("Field key required");
			}
			return new LongKeyRecordIterator(minKey, maxKey, startKey);
		}
	}

	/**
	 * Iterate over the records in ascending sorted order.  Sorting occurs on the primary key value
	 * starting at the specified startKey.
	 * @param startKey the first primary key.
	 * @return record iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public RecordIterator iterator(Field startKey) throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				return new LongKeyRecordIterator(Long.MIN_VALUE, Long.MAX_VALUE,
					startKey.getLongValue());
			}
			return new FieldKeyRecordIterator(null, null, startKey);
		}
	}

	/**
	 * Iterate over the records in ascending sorted order.  Sorting occurs on the primary key value
	 * starting at the specified startKey.
	 * @param minKey the minimum primary key, may be null.
	 * @param maxKey the maximum primary key, may be null.
	 * @param startKey the initial iterator position, if null minKey is also start.
	 * @return record iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public RecordIterator iterator(Field minKey, Field maxKey, Field startKey) throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				long min = minKey != null ? minKey.getLongValue() : Long.MIN_VALUE;
				long max = maxKey != null ? maxKey.getLongValue() : Long.MAX_VALUE;
				long start = startKey != null ? startKey.getLongValue() : min;
				return new LongKeyRecordIterator(min, max, start);
			}
			return new FieldKeyRecordIterator(minKey, maxKey, startKey);
		}
	}

	/**
	 * Iterate over all long primary keys in ascending sorted order.
	 * @return long key iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public DBLongIterator longKeyIterator() throws IOException {
		synchronized (db) {
			if (!schema.useLongKeyNodes()) {
				throw new AssertException();
			}
			return new LongKeyIterator();
		}
	}

	/**
	 * Iterate over the long primary keys in ascending sorted order
	 * starting at the specified startKey.
	 * @param startKey the first primary key.
	 * @return long key iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public DBLongIterator longKeyIterator(long startKey) throws IOException {
		synchronized (db) {
			if (!schema.useLongKeyNodes()) {
				throw new AssertException();
			}
			return new LongKeyIterator(Long.MIN_VALUE, Long.MAX_VALUE, startKey);
		}
	}

	/**
	 * Iterate over the long primary keys in ascending sorted order
	 * starting at the specified startKey.
	 * @param minKey the minimum primary key.
	 * @param maxKey the maximum primary key.
	 * @param startKey the initial iterator position.
	 * @return long key iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public DBLongIterator longKeyIterator(long minKey, long maxKey, long startKey)
			throws IOException {
		synchronized (db) {
			if (!schema.useLongKeyNodes()) {
				throw new AssertException();
			}
			return new LongKeyIterator(minKey, maxKey, startKey);
		}
	}

	/**
	 * Iterate over all primary keys in ascending sorted order.
	 * @return Field type key iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public DBFieldIterator fieldKeyIterator() throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				throw new AssertException();
			}
			return new FieldKeyIterator(null, null, null);
		}
	}

	/**
	 * Iterate over the primary keys in ascending sorted order
	 * starting at the specified startKey.
	 * @param startKey the first primary key.  If null the minimum key value will be assumed.
	 * @return Field type key iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public DBFieldIterator fieldKeyIterator(Field startKey) throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				throw new AssertException();
			}
			return new FieldKeyIterator(null, null, startKey);
		}
	}

	/**
	 * Iterate over the records in ascending sorted order
	 * starting at the specified startKey.
	 * @param minKey minimum key value.  Null corresponds to minimum key value.
	 * @param maxKey maximum key value.  Null corresponds to maximum key value.
	 * @param startKey the initial iterator position.  If null minKey will be assumed,
	 * if still null the minimum key value will be assumed.
	 * @return Field type key iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public DBFieldIterator fieldKeyIterator(Field minKey, Field maxKey, Field startKey)
			throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				throw new AssertException();
			}
			return new FieldKeyIterator(minKey, maxKey, startKey);
		}
	}

	/**
	 * Iterate over the records in ascending sorted order
	 * starting at the specified startKey.
	 * @param minKey minimum key value.  Null corresponds to minimum key value.
	 * @param maxKey maximum key value.  Null corresponds to maximum key value.
	 * @param before if true initial position is before minKey, else position
	 * is after maxKey.
	 * @return Field type key iterator
	 * @throws IOException if an I/O error occurs.
	 */
	public DBFieldIterator fieldKeyIterator(Field minKey, Field maxKey, boolean before)
			throws IOException {
		synchronized (db) {
			if (schema.useLongKeyNodes()) {
				throw new AssertException();
			}
			return new FieldKeyIterator(minKey, maxKey, before);
		}
	}

	/**
	 * A RecordIterator class for use with table data contained within LeafNode's.
	 */
	private class LongKeyRecordIterator implements RecordIterator {

		private int bufferId = -1; // current record buffer ID
		private int recordIndex; // current record index
		private boolean isNext; // recover position is next record
		private boolean isPrev; // recover position is previous record

		private DBRecord record; // current record
		private long curKey; // copy of record key (record may get changed by consumer)
		private DBRecord lastRecord;

		private boolean hasPrev; // current record is previous
		private boolean hasNext; // current record is next

		private long minKey;
		private long maxKey;

		private int expectedModCount;

		/**
		 * Construct a record iterator over all records. (requires DBHandle lock)
		 * @throws IOException thrown if IO error occurs
		 */
		private LongKeyRecordIterator() throws IOException {
			this(Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE);
			hasPrev = false;
		}

		/**
		 * Construct a record iterator. (requires DBHandle lock)
		 * @param minKey minimum allowed primary key.
		 * @param maxKey maximum allowed primary key.
		 * @param startKey the first primary key value.
		 * @throws IOException thrown if IO error occurs
		 */
		private LongKeyRecordIterator(long minKey, long maxKey, long startKey) throws IOException {

			expectedModCount = modCount;

			this.minKey = minKey;
			this.maxKey = maxKey;

			if (rootBufferId < 0) {
				return;
			}

			if (minKey > maxKey) {
				return;
			}

			try {
				LongKeyNode rootNode = nodeMgr.getLongKeyNode(rootBufferId);
				LongKeyRecordNode leaf = rootNode.getLeafNode(startKey);
				recordIndex = leaf.getKeyIndex(startKey);

				// Start key was found
				if (recordIndex >= 0) {
					hasPrev = true;
					hasNext = true;
				}

				// Start key was not found
				else {
					recordIndex = -(recordIndex + 1);
					if (recordIndex == leaf.keyCount) {
						--recordIndex;
						hasPrev = leaf.getKey(recordIndex) >= minKey;
						if (!hasPrev) {
							leaf = leaf.getNextLeaf();
							if (leaf == null) {
								return;
							}
							recordIndex = 0;
							hasNext = leaf.getKey(recordIndex) <= maxKey;
						}
					}
					else {
						hasNext = leaf.getKey(recordIndex) <= maxKey;
						if (!hasNext) {
							// position to previous record
							if (recordIndex == 0) {
								leaf = leaf.getPreviousLeaf();
								if (leaf == null) {
									return;
								}
								recordIndex = leaf.keyCount - 1;
							}
							else {
								--recordIndex;
							}
							hasPrev = leaf.getKey(recordIndex) >= minKey;
						}
					}

				}

				if (hasPrev || hasNext) {
					bufferId = leaf.getBufferId();
					record = leaf.getRecord(schema, recordIndex);
					curKey = record.getKey();
				}
			}
			finally {
				nodeMgr.releaseNodes();
			}
		}

		/**
		 * Get the current record leaf.  If the current record can not be found, attempt to 
		 * recover the record position.
		 * @param recoverPrev if true and the current record no longer exists,
		 * the current position will be set to the previous record and isPrev set to true; 
		 * else if false and the current record no longer exists, the current position
		 * will be set to the next record and isNext set to true.
		 * @return LongKeyRecordNode the leaf node containing the current record position
		 * identified by bufferId and recordIndex.  If null, the current record was not found
		 * or the position could not be set to a next/previous record position based upon the
		 * recoverPrev value specified.
		 * @throws IOException thrown if IO error occurs
		 */
		private LongKeyRecordNode getRecordLeaf(boolean recoverPrev) throws IOException {

			if (rootBufferId < 0 || record == null) {
				return null;
			}

			LongKeyRecordNode leaf = null;
			isNext = false;
			isPrev = false;

			if (expectedModCount == modCount) {
				leaf = (LongKeyRecordNode) nodeMgr.getLongKeyNode(bufferId);
				if (recordIndex >= leaf.keyCount || leaf.getKey(recordIndex) != curKey) {
					leaf = null; // something changed - key search required
				}
			}

			if (leaf == null) {

				// Something changed - try to relocate record using key
				LongKeyNode rootNode = nodeMgr.getLongKeyNode(rootBufferId);
				leaf = rootNode.getLeafNode(curKey);
				int index = leaf.getKeyIndex(curKey);
				if (index < 0) {
					// Record was deleted - position on next key
					index = -index - 1;
					if (recoverPrev) {
						--index;
						if (index < 0) {
							leaf = leaf.getPreviousLeaf();
							index = leaf != null ? (leaf.keyCount - 1) : 0;
						}
						isPrev = true;
					}
					else {
						if (index == leaf.keyCount) {
							leaf = leaf.getNextLeaf();
							index = 0;
						}
						isNext = true;
					}
				}
				if (leaf != null) {
					bufferId = leaf.getBufferId();
					recordIndex = index;
				}
				expectedModCount = modCount;
			}
			return leaf;
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {

				if (!hasNext && nodeMgr != null) {

					try {
						// Check for modification to storage of previous record
						LongKeyRecordNode leaf = getRecordLeaf(false);
						if (leaf == null) {
							return false;
						}

						// Position to next record
						int nextIndex = recordIndex;
						if (!isNext) {
							++nextIndex;
						}
						int nextBufferId = bufferId;
						if (nextIndex == leaf.keyCount) {
							leaf = leaf.getNextLeaf();
							if (leaf == null) {
								return false;
							}
							nextBufferId = leaf.getBufferId();
							nextIndex = 0;
						}

						// Load next record
						DBRecord nextRecord = leaf.getRecord(schema, nextIndex);
						hasNext = nextRecord.getKey() <= maxKey;
						if (hasNext) {
							bufferId = nextBufferId;
							recordIndex = nextIndex;
							record = nextRecord;
							curKey = record.getKey();
							hasPrev = false;
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
				return hasNext;
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {

				if (!hasPrev && nodeMgr != null) {

					try {
						// Check for modification to storage of next record
						LongKeyRecordNode leaf = getRecordLeaf(true);
						if (leaf == null) {
							return false;
						}

						// Position to previous record
						int prevIndex = recordIndex;
						if (!isPrev) {
							--prevIndex;
						}
						int prevBufferId = bufferId;
						if (prevIndex < 0) {
							leaf = leaf.getPreviousLeaf();
							if (leaf == null) {
								return false;
							}
							prevBufferId = leaf.getBufferId();
							prevIndex = leaf.keyCount - 1;
						}

						// Load previous record
						DBRecord prevRecord = leaf.getRecord(schema, prevIndex);
						hasPrev = prevRecord.getKey() >= minKey;
						if (hasPrev) {
							bufferId = prevBufferId;
							recordIndex = prevIndex;
							record = prevRecord;
							curKey = record.getKey();
							hasNext = false;
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
				return hasPrev;
			}
		}

		@Override
		public DBRecord next() throws IOException {
			if (hasNext || hasNext()) {
				hasNext = false;
				hasPrev = true;
				lastRecord = record;
				return record;
			}
			return null;
		}

		@Override
		public DBRecord previous() throws IOException {
			if (hasPrev || hasPrevious()) {
				hasNext = true;
				hasPrev = false;
				lastRecord = record;
				return record;
			}
			return null;
		}

		@Override
		public boolean delete() throws IOException {
			if (lastRecord == null) {
				return false;
			}
			deleteRecord(lastRecord.getKey());
			lastRecord = null;
			return true;
		}

	}

	/**
	 * A RecordIterator class for use with table data contained within LeafNode's.
	 */
	private class FieldKeyRecordIterator implements RecordIterator {

		private int bufferId = -1; // current record buffer ID
		private int recordIndex; // current record index
		private boolean isNext; // recover position is next record
		private boolean isPrev; // recover position is previous record

		private DBRecord record; // current record
//		private Field curKey;			// copy of record key (record may get changed by consumer)
		private DBRecord lastRecord;

		private boolean hasPrev; // current record is previous
		private boolean hasNext; // current record is next

		private Field minKey;
		private Field maxKey;

		private int expectedModCount;

		/**
		 * Construct a record iterator.
		 * @param minKey minimum allowed primary key.
		 * @param maxKey maximum allowed primary key.
		 * @param startKey the first primary key value. If null, minKey will be used.
		 * @throws IOException thrown if IO error occurs
		 */
		FieldKeyRecordIterator(Field minKey, Field maxKey, Field startKey) throws IOException {

			expectedModCount = modCount;

			this.minKey = minKey;
			this.maxKey = maxKey;

			if (rootBufferId < 0) {
				return;
			}

			if (minKey != null && maxKey != null && minKey.compareTo(maxKey) > 0) {
				return;
			}

			if (startKey != null) {
//				if (minKey != null && startKey.compareTo(minKey) < 0)
//					return;
//				if (maxKey != null && startKey.compareTo(maxKey) > 0)
//					return;
			}
			else {
				startKey = minKey;
			}

			try {
				FieldKeyNode rootNode = getFieldKeyNode(rootBufferId);

				// If startKey not specified, start with leftmost record
				if (startKey == null) {
					FieldKeyRecordNode leaf = rootNode.getLeftmostLeafNode();
					bufferId = leaf.getBufferId();
					recordIndex = 0;
					record = leaf.getRecord(schema, 0);
//					curKey = record.getKeyField();
					hasNext = true;
				}

				// else, start with specified startKey
				else {

					FieldKeyRecordNode leaf = rootNode.getLeafNode(startKey);
					recordIndex = leaf.getKeyIndex(startKey);

					// Start key was found
					if (recordIndex >= 0) {
						hasPrev = true;
						hasNext = true;
					}

					// Start key was not found
					else {
						recordIndex = -(recordIndex + 1);
						if (recordIndex == leaf.getKeyCount()) {
							--recordIndex;
							hasPrev = minKey == null ? true
									: (leaf.getKeyField(recordIndex).compareTo(minKey) >= 0);
							if (!hasPrev) {
								leaf = leaf.getNextLeaf();
								if (leaf == null) {
									return;
								}
								recordIndex = 0;
								hasNext = maxKey == null ? true
										: (leaf.getKeyField(recordIndex).compareTo(maxKey) <= 0);
							}
						}
						else {
							hasNext = maxKey == null ? true
									: (leaf.getKeyField(recordIndex).compareTo(maxKey) <= 0);
							if (!hasNext) {
								// position to previous record
								if (recordIndex == 0) {
									leaf = leaf.getPreviousLeaf();
									if (leaf == null) {
										return;
									}
									recordIndex = leaf.getKeyCount() - 1;
								}
								else {
									--recordIndex;
								}
								hasPrev = minKey == null ? true
										: (leaf.getKeyField(recordIndex).compareTo(minKey) >= 0);
							}
						}
					}

					if (hasPrev || hasNext) {
						bufferId = leaf.getBufferId();
						record = leaf.getRecord(schema, recordIndex);
//						curKey = record.getKeyField();
					}

				}

			}
			finally {
				nodeMgr.releaseNodes();
			}
		}

		/**
		 * Get the current record leaf.  If the current record can not be found, attempt to 
		 * recover the record position.
		 * @param recoverPrev if true and the current record no longer exists,
		 * the current position will be set to the previous record and isPrev set to true; 
		 * else if false and the current record no longer exists, the current position
		 * will be set to the next record and isNext set to true.
		 * @return FieldKeyRecordNode the leaf node containing the current record position
		 * identified by bufferId and recordIndex.  If null, the current record was not found
		 * or the position could not be set to a next/previous record position based upon the
		 * recoverPrev value specified.
		 * @throws IOException thrown if IO error occurs
		 */
		private FieldKeyRecordNode getRecordLeaf(boolean recoverPrev) throws IOException {

			if (rootBufferId < 0 || record == null) {
				return null;
			}

			Field key = record.getKeyField();
			FieldKeyRecordNode leaf = null;
			isNext = false;
			isPrev = false;

			if (expectedModCount == modCount) {
				leaf = (FieldKeyRecordNode) getFieldKeyNode(bufferId);
				if (recordIndex >= leaf.getKeyCount() ||
					!leaf.getKeyField(recordIndex).equals(key)) {
					leaf = null; // something changed - key search required
				}
			}

			if (leaf == null) {

				// Something changed - try to relocate record using key
				FieldKeyNode rootNode = getFieldKeyNode(rootBufferId);
				leaf = rootNode.getLeafNode(key);
				int index = leaf.getKeyIndex(key);
				if (index < 0) {
					// Record was deleted - position on next key
					index = -index - 1;
					if (recoverPrev) {
						--index;
						if (index < 0) {
							leaf = leaf.getPreviousLeaf();
							index = leaf != null ? (leaf.getKeyCount() - 1) : 0;
						}
						isPrev = true;
					}
					else {
						if (index == leaf.getKeyCount()) {
							leaf = leaf.getNextLeaf();
							index = 0;
						}
						isNext = true;
					}
				}
				if (leaf != null) {
					bufferId = leaf.getBufferId();
					recordIndex = index;
				}
				expectedModCount = modCount;
			}
			return leaf;
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {

				if (!hasNext && nodeMgr != null) {

					try {
						// Check for modification to storage of previous record
						FieldKeyRecordNode leaf = getRecordLeaf(false);
						if (leaf == null) {
							return false;
						}

						// Position to next record
						int nextIndex = recordIndex;
						if (!isNext) {
							++nextIndex;
						}
						int nextBufferId = bufferId;
						if (nextIndex == leaf.getKeyCount()) {
							leaf = leaf.getNextLeaf();
							if (leaf == null) {
								return false;
							}
							nextBufferId = leaf.getBufferId();
							nextIndex = 0;
						}

						// Load next record
						DBRecord nextRecord = leaf.getRecord(schema, nextIndex);
						hasNext = maxKey == null ? true
								: (nextRecord.getKeyField().compareTo(maxKey) <= 0);
						if (hasNext) {
							bufferId = nextBufferId;
							recordIndex = nextIndex;
							record = nextRecord;
//							curKey = record.getKeyField();
							hasPrev = false;
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
				return hasNext;
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {

				if (!hasPrev && nodeMgr != null) {

					try {
						// Check for modification to storage of next record
						FieldKeyRecordNode leaf = getRecordLeaf(true);
						if (leaf == null) {
							return false;
						}

						// Position to previous record
						int prevIndex = recordIndex;
						if (!isPrev) {
							--prevIndex;
						}
						int prevBufferId = bufferId;
						if (prevIndex < 0) {
							leaf = leaf.getPreviousLeaf();
							if (leaf == null) {
								return false;
							}
							prevBufferId = leaf.getBufferId();
							prevIndex = leaf.getKeyCount() - 1;
						}

						// Load previous record
						DBRecord prevRecord = leaf.getRecord(schema, prevIndex);
						hasPrev = minKey == null ? true
								: (prevRecord.getKeyField().compareTo(minKey) >= 0);
						if (hasPrev) {
							bufferId = prevBufferId;
							recordIndex = prevIndex;
							record = prevRecord;
//							curKey = record.getKeyField();
							hasNext = false;
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
				return hasPrev;
			}
		}

		@Override
		public DBRecord next() throws IOException {
			if (hasNext || hasNext()) {
				hasNext = false;
				hasPrev = true;
				lastRecord = record;
				return record;
			}
			return null;
		}

		@Override
		public DBRecord previous() throws IOException {
			if (hasPrev || hasPrevious()) {
				hasNext = true;
				hasPrev = false;
				lastRecord = record;
				return record;
			}
			return null;
		}

		@Override
		public boolean delete() throws IOException {
			if (lastRecord == null) {
				return false;
			}
			deleteRecord(lastRecord.getKeyField());
			lastRecord = null;
			return true;
		}

	}

	/**
	 * A long key iterator class.
	 */
	private class LongKeyIterator implements DBLongIterator {

		private static final int SHORT_ITER_THRESHOLD = 10;

		private DBLongIterator keyIter;
		private int iterCnt = 0;

		/**
		 * Construct a record iterator over all records. 
		 * Long-running iterator used (all keys in buffer read at once)
		 * @throws IOException thrown if IO error occurs
		 */
		LongKeyIterator() throws IOException {
			keyIter = new LongDurationLongKeyIterator(); // optimized for long iterations
			iterCnt = Integer.MAX_VALUE; // disable LongKeyIterator2-to-LongKeyIterator1 change-over logic
		}

		/**
		 * Construct a record iterator. The underlying iterator is optimized for
		 * short iterations.  If it determined that the iterator is to be used 
		 * for a large number of iterations, the underlying iterator is switched
		 * to one optimized for longer iterations.
		 * @param minKey minimum allowed primary key.
		 * @param maxKey maximum allowed primary key.
		 * @param startKey the first primary key value.
		 * @throws IOException thrown if IO error occurs
		 */
		LongKeyIterator(long minKey, long maxKey, long startKey) throws IOException {
			keyIter = new ShortDurationLongKeyIterator(minKey, maxKey, startKey);
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {
				if (iterCnt <= SHORT_ITER_THRESHOLD && ++iterCnt > SHORT_ITER_THRESHOLD) {
					// Switch to long-running iterator
					keyIter =
						new LongDurationLongKeyIterator((ShortDurationLongKeyIterator) keyIter);
				}
				return keyIter.hasNext();
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {
				if (iterCnt <= SHORT_ITER_THRESHOLD && ++iterCnt > SHORT_ITER_THRESHOLD) {
					// Switch to long-running iterator
					keyIter =
						new LongDurationLongKeyIterator((ShortDurationLongKeyIterator) keyIter);
				}
				return keyIter.hasPrevious();
			}
		}

		@Override
		public long next() throws IOException {
			return keyIter.next();
		}

		@Override
		public long previous() throws IOException {
			return keyIter.previous();
		}

		@Override
		public boolean delete() throws IOException {
			return keyIter.delete();
		}
	}

	/**
	 * A long key iterator class - optimized for long iterations since
	 * all keys are read for each record node.
	 */
	private class LongDurationLongKeyIterator implements DBLongIterator {

		private int bufferId;
		private int keyIndex;
		private long[] keys;
		private long key;
		private long lastKey;
		private boolean hasLastKey;

		private int expectedModCount;

		private boolean hasPrev;
		private boolean hasNext;

		private long minKey;
		private long maxKey;

		/**
		 * Construct a record iterator over all records. 
		 * @throws IOException thrown if IO error occurs
		 */
		LongDurationLongKeyIterator() throws IOException {
			this(Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE);
			hasPrev = false;
		}

		/**
		 * Iterator hand-off constructor.  Transition from short-running to 
		 * long-running iterator.
		 * @param keyIter partially used short-running iterator
		 * @throws IOException if IO error occurs
		 */
		LongDurationLongKeyIterator(ShortDurationLongKeyIterator keyIter) throws IOException {

			this.bufferId = keyIter.bufferId;
			this.keyIndex = keyIter.keyIndex;
			this.key = keyIter.key;
			this.lastKey = keyIter.lastKey;
			this.hasLastKey = keyIter.hasLastKey;
			this.expectedModCount = keyIter.expectedModCount;
			this.hasPrev = keyIter.hasPrev;
			this.hasNext = keyIter.hasNext;
			this.minKey = keyIter.minKey;
			this.maxKey = keyIter.maxKey;

			if (bufferId >= 0) {
				if (modCount != expectedModCount) {
					reset();
				}
				else {
					try {
						LongKeyRecordNode leaf =
							(LongKeyRecordNode) nodeMgr.getLongKeyNode(bufferId);
						getKeys(leaf);
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
			}
			else {
				keys = new long[0];
			}
		}

		/**
		 * Construct a record iterator.
		 * @param minKey minimum allowed primary key.
		 * @param maxKey maximum allowed primary key.
		 * @param startKey the first primary key value.
		 * @throws IOException thrown if IO error occurs
		 */
		LongDurationLongKeyIterator(long minKey, long maxKey, long startKey) throws IOException {

//			if (startKey < minKey || startKey > maxKey || minKey > maxKey)
//				throw new IllegalArgumentException();

			this.minKey = minKey;
			this.maxKey = maxKey;
			this.key = startKey;

			initialize(startKey);
		}

		/**
		 * Initialize (or re-initialize) iterator state.
		 * An empty or null keys array will force a complete initialization.
		 * Otherwise, following the deletethe keys array and keyIndex should reflect the state
		 * following a delete.
		 * @param targetKey the initial key.  For construction this is the startKey, 
		 * following a delete this is the deleted key.
		 * @throws IOException thrown if IO error occurs
		 */
		private void initialize(long targetKey) throws IOException {

			expectedModCount = modCount;
			hasPrev = false;
			hasNext = false;

			if (rootBufferId < 0) {
				bufferId = -1;
				keys = new long[0];
				return;
			}

			try {
				LongKeyRecordNode leaf = null;
				if (keys == null || keys.length == 0) {
					LongKeyNode rootNode = nodeMgr.getLongKeyNode(rootBufferId);
					leaf = rootNode.getLeafNode(targetKey);

					// Empty leaf node - special case
					int leafRecCount = leaf.keyCount;
					if (leafRecCount == 0) {
						return;
					}

					keyIndex = leaf.getKeyIndex(targetKey);
					getKeys(leaf);
				}

				// Start key was found
				if (keyIndex >= 0) {
					key = targetKey;
					hasPrev = true;
					hasNext = true;
				}

				// Start key was not found
				else {
					keyIndex = -(keyIndex + 1);
					if (keyIndex == keys.length) {
						--keyIndex;
						hasPrev = keys[keyIndex] >= minKey;
						if (!hasPrev) {
							if (leaf == null) {
								keys = null;
								initialize(targetKey);
								return;
							}
							leaf = leaf.getNextLeaf();
							if (leaf == null) {
								keys = new long[0];
								bufferId = -1;
								return;
							}
							keyIndex = 0;
							getKeys(leaf);
							hasNext = keys[keyIndex] <= maxKey;
						}
					}
					else {
						hasNext = keys[keyIndex] <= maxKey;
						if (!hasNext) {
							// position to previous record
							if (keyIndex == 0) {
								if (leaf == null) {
									keys = null;
									initialize(targetKey);
									return;
								}
								leaf = leaf.getPreviousLeaf();
								if (leaf == null) {
									keys = new long[0];
									bufferId = -1;
									return;
								}
								keyIndex = leaf.keyCount - 1;
								getKeys(leaf);
							}
							else {
								--keyIndex;
							}
							hasPrev = keys[keyIndex] >= minKey;
						}
					}
					if (hasNext || hasPrev) {
						key = keys[keyIndex];
					}
				}
			}
			finally {
				nodeMgr.releaseNodes();
			}

		}

		private void reset() throws IOException {
			boolean hadNext = hasNext;
			boolean hadPrev = hasPrev;
			keys = null;
			initialize(key);

			if (hasNext && hasPrev) {
				hasNext = hadNext;
				hasPrev = hadPrev;
			}
		}

		private void getKeys(LongKeyRecordNode node) {
			bufferId = node.getBufferId();
			if (keys == null || keys.length != node.keyCount) {
				keys = new long[node.keyCount];
			}
			for (int i = 0; i < node.keyCount; i++) {
				keys[i] = node.getKey(i);
			}
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasNext) {

					// Check next key index
					int nextIndex = keyIndex + 1;

					// Process next leaf if needed
					if (nextIndex >= keys.length) {
						try {
							if (bufferId == -1) {
								return false;
							}
							LongKeyRecordNode leaf = ((LongKeyRecordNode) nodeMgr.getLongKeyNode(
								bufferId)).getNextLeaf();
							if (leaf == null || leaf.getKey(0) > maxKey) {
								return false;
							}
							getKeys(leaf);
							key = keys[0];
							keyIndex = 0;
							hasNext = true;
							hasPrev = false;
						}
						finally {
							nodeMgr.releaseNodes();
						}
					}

					// else, use keys cache
					else {
						hasNext = keys[nextIndex] <= maxKey;
						if (hasNext) {
							key = keys[nextIndex];
							keyIndex = nextIndex;
							hasPrev = false;
						}
					}

				}
				return hasNext;
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasPrev) {

					// Check previous key index
					int prevIndex = keyIndex - 1;

					// Process previous leaf if needed
					if (prevIndex < 0 || keys.length == 0) {
						try {
							if (bufferId == -1) {
								return false;
							}
							LongKeyRecordNode leaf = ((LongKeyRecordNode) nodeMgr.getLongKeyNode(
								bufferId)).getPreviousLeaf();
							if (leaf == null) {
								return false;
							}
							prevIndex = leaf.keyCount - 1;
							if (leaf.getKey(prevIndex) < minKey) {
								return false;
							}
							getKeys(leaf);
							key = keys[prevIndex];
							keyIndex = prevIndex;
							hasNext = false;
							hasPrev = true;
						}
						finally {
							nodeMgr.releaseNodes();
						}
					}

					// else, use keys cache
					else {
						hasPrev = keys[prevIndex] >= minKey;
						if (hasPrev) {
							key = keys[prevIndex];
							keyIndex = prevIndex;
							hasNext = false;
						}
					}
				}
				return hasPrev;
			}
		}

		@Override
		public long next() throws IOException {
			if (hasNext || hasNext()) {
				hasNext = false;
				hasPrev = true;
				lastKey = key;
				hasLastKey = true;
				return key;
			}
			throw new NoSuchElementException();
		}

		@Override
		public long previous() throws IOException {
			if (hasPrev || hasPrevious()) {
				hasNext = true;
				hasPrev = false;
				lastKey = key;
				hasLastKey = true;
				return key;
			}
			throw new NoSuchElementException();
		}

		@Override
		public boolean delete() throws IOException {
			if (hasLastKey) {
				synchronized (db) {
					long deleteKey = lastKey;
					hasLastKey = false;
					boolean success = deleteRecord(deleteKey);
					int newLen = keys.length - 1;
					if (deleteKey == key && keys.length > 1 /* && keyIndex < newLen */) {
						long[] newKeys = new long[newLen];
						System.arraycopy(keys, 0, newKeys, 0, keyIndex);
						System.arraycopy(keys, keyIndex + 1, newKeys, keyIndex, newLen - keyIndex);
						keys = newKeys;
						keyIndex = -(keyIndex + 1); // reflects non-existent key to initialize method
					}
					else {
						keys = null;
					}
					initialize(deleteKey);
					return success;
				}
			}
			return false;
		}

	}

	/**
	 * A long key iterator class - optimized for short iterations since
	 * the number of keys read from each record node is minimized.
	 */
	private class ShortDurationLongKeyIterator implements DBLongIterator {

		private int bufferId;
		private int keyIndex;
		private long key;
		private long lastKey;
		private boolean hasLastKey = false;

		private int expectedModCount;

		private boolean hasPrev;
		private boolean hasNext;

		private long minKey;
		private long maxKey;

		/**
		 * Construct a record iterator.
		 * @param minKey minimum allowed primary key.
		 * @param maxKey maximum allowed primary key.
		 * @param startKey the first primary key value.
		 * @throws IOException thrown if IO error occurs
		 */
		ShortDurationLongKeyIterator(long minKey, long maxKey, long startKey) throws IOException {

			this.minKey = minKey;
			this.maxKey = maxKey;
			this.key = startKey;

			initialize(startKey);
		}

		/**
		 * Initialize (or re-initialize) iterator state.
		 * An empty or null keys array will force a complete initialization.
		 * Otherwise, following the deletethe keys array and keyIndex should reflect the state
		 * following a delete.
		 * @param targetKey the initial key.  For construction this is the startKey, 
		 * following a delete this is the deleted key.
		 * @throws IOException thrown if IO error occurs
		 */
		private void initialize(long targetKey) throws IOException {

			expectedModCount = modCount;
			hasPrev = false;
			hasNext = false;
			bufferId = -1;

			if (rootBufferId < 0) {
				return;
			}

			try {
				LongKeyRecordNode leaf = null;
				LongKeyNode rootNode = nodeMgr.getLongKeyNode(rootBufferId);

				leaf = rootNode.getLeafNode(targetKey);
				bufferId = leaf.getBufferId();

				// Empty leaf node - special case
				if (leaf.keyCount == 0) {
					keyIndex = -1;
					return;
				}

				keyIndex = leaf.getKeyIndex(targetKey);

				// Start key was found
				if (keyIndex >= 0) {
					key = leaf.getKey(keyIndex);
					hasPrev = true;
					hasNext = true;
				}

				// Start key was not found
				else {
					keyIndex = -(keyIndex + 1);
					if (keyIndex == leaf.keyCount) {
						--keyIndex;
						key = leaf.getKey(keyIndex);
						hasPrev = key >= minKey;
					}
					else {
						key = leaf.getKey(keyIndex);
						hasNext = key <= maxKey;
					}
				}
			}
			finally {
				nodeMgr.releaseNodes();
			}

		}

		private void reset() throws IOException {
			boolean hadNext = hasNext;
			boolean hadPrev = hasPrev;
			initialize(key);
			if (hasNext && hasPrev) {
				hasNext = hadNext;
				hasPrev = hadPrev;
			}
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasNext) {

					if (bufferId < 0 || keyIndex < 0) {
						return false;
					}

					// Check next key index
					int nextIndex = keyIndex + 1;

					try {
						// Process next leaf if needed
						LongKeyRecordNode leaf =
							(LongKeyRecordNode) nodeMgr.getLongKeyNode(bufferId);
						if (nextIndex >= leaf.keyCount) {
							leaf = leaf.getNextLeaf();
							if (leaf == null) {
								return false;
							}
							long nextKey = leaf.getKey(0);
							if (nextKey > maxKey) {
								return false;
							}
							bufferId = leaf.getBufferId();
							key = nextKey;
							keyIndex = 0;
							hasNext = true;
							hasPrev = false;
						}

						// else, use keys cache
						else {
							long nextKey = leaf.getKey(nextIndex);
							hasNext = (nextKey <= maxKey);
							if (hasNext) {
								key = nextKey;
								keyIndex = nextIndex;
								hasPrev = false;
							}
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}

				}
				return hasNext;
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasPrev) {

					if (bufferId < 0 || keyIndex < 0) {
						return false;
					}

					// Check previous key index
					int prevIndex = keyIndex - 1;

					try {
						// Process previous leaf if needed
						LongKeyRecordNode leaf =
							(LongKeyRecordNode) nodeMgr.getLongKeyNode(bufferId);
						if (prevIndex < 0) {
							leaf = leaf.getPreviousLeaf();
							if (leaf == null) {
								return false;
							}
							prevIndex = leaf.keyCount - 1;
							long prevKey = leaf.getKey(prevIndex);
							if (prevKey < minKey) {
								return false;
							}
							bufferId = leaf.getBufferId();
							key = prevKey;
							keyIndex = prevIndex;
							hasNext = false;
							hasPrev = true;
						}

						// else, use keys cache
						else {
							long prevKey = leaf.getKey(prevIndex);
							hasPrev = prevKey >= minKey;
							if (hasPrev) {
								key = prevKey;
								keyIndex = prevIndex;
								hasNext = false;
							}
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
				return hasPrev;
			}
		}

		@Override
		public long next() throws IOException {
			if (hasNext || hasNext()) {
				hasNext = false;
				hasPrev = true;
				lastKey = key;
				hasLastKey = true;
				return key;
			}
			throw new NoSuchElementException();
		}

		@Override
		public long previous() throws IOException {
			if (hasPrev || hasPrevious()) {
				hasNext = true;
				hasPrev = false;
				lastKey = key;
				hasLastKey = true;
				return key;
			}
			throw new NoSuchElementException();
		}

		@Override
		public boolean delete() throws IOException {
			if (hasLastKey) {
				hasLastKey = false;
				return deleteRecord(lastKey);
			}
			return false;
		}

	}

	/**
	 * A Field key iterator class.  The initial iterator is optimized for
	 * short iterations.  If it determined that the iterator is to be used 
	 * for a large number of iterations, the underlying iterator is switched
	 * to one optimized for longer iterations.
	 */
	private class FieldKeyIterator implements DBFieldIterator {

		private static final int SHORT_ITER_THRESHOLD = 10;

		private DBFieldIterator keyIter;
		private int iterCnt = 0;

		/**
		 * Construct a record iterator. (requires DBHandle lock)
		 * @param minKey minimum key value.  Null corresponds to minimum key value.
		 * @param maxKey maximum key value.  Null corresponds to maximum key value.
		 * @param startKey the first primary key value.  If null minKey will be assumed,
		 * if still null the minimum indexed value will be assumed.
		 * @throws IOException thrown if IO error occurs
		 */
		FieldKeyIterator(Field minKey, Field maxKey, Field startKey) throws IOException {
			keyIter = new ShortDurationFieldKeyIterator(minKey, maxKey, startKey);
		}

		/**
		 * Construct a record iterator. (requires DBHandle lock)
		 * @param minKey minimum key value.  Null corresponds to minimum key value.
		 * @param maxKey maximum key value.  Null corresponds to maximum key value.
		 * @param before true if initial position is before range, else after range
		 * @throws IOException thrown if IO error occurs
		 */
		FieldKeyIterator(Field minKey, Field maxKey, boolean before) throws IOException {

			Field startKey = before ? minKey : maxKey;

			if (startKey == null && !before && rootBufferId != -1) {
				try {
					FieldKeyNode rightmostLeaf =
						getFieldKeyNode(rootBufferId).getRightmostLeafNode();
					startKey = rightmostLeaf.getKeyField(rightmostLeaf.getKeyCount() - 1);
				}
				finally {
					nodeMgr.releaseNodes();
				}
			}

			keyIter = new ShortDurationFieldKeyIterator(minKey, maxKey, startKey);
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {
				if (iterCnt <= SHORT_ITER_THRESHOLD) {
					if (++iterCnt > SHORT_ITER_THRESHOLD) {
						// Switch to long-running iterator
						keyIter = new LongDurationFieldKeyIterator((ShortDurationFieldKeyIterator) keyIter);
					}
				}
				return keyIter.hasNext();
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {
				if (iterCnt <= SHORT_ITER_THRESHOLD) {
					if (++iterCnt > SHORT_ITER_THRESHOLD) {
						// Switch to long-running iterator
						keyIter = new LongDurationFieldKeyIterator((ShortDurationFieldKeyIterator) keyIter);
					}
				}
				return keyIter.hasPrevious();
			}
		}

		@Override
		public Field next() throws IOException {
			return keyIter.next();
		}

		@Override
		public Field previous() throws IOException {
			return keyIter.previous();
		}

		@Override
		public boolean delete() throws IOException {
			return keyIter.delete();
		}
	}

	/**
	 * A Field key iterator class - optimized for long iterations since
	 * all keys are read for each record node.
	 */
	private class LongDurationFieldKeyIterator implements DBFieldIterator {

		private int bufferId;
		private int keyIndex;
		private Field[] keys;
		private Field key;
		private Field lastKey;

		private int expectedModCount;

		private boolean hasPrev;
		private boolean hasNext;

		private Field minKey;
		private Field maxKey;

		/**
		 * Iterator hand-off constructor.  Transition from short-running to 
		 * long-running iterator.
		 * @param keyIter partially used short-running iterator
		 * @throws IOException if IO error occurs
		 */
		LongDurationFieldKeyIterator(ShortDurationFieldKeyIterator keyIter) throws IOException {

			this.bufferId = keyIter.bufferId;
			this.keyIndex = keyIter.keyIndex;
			this.key = keyIter.key;
			this.lastKey = keyIter.lastKey;
			this.expectedModCount = keyIter.expectedModCount;
			this.hasPrev = keyIter.hasPrev;
			this.hasNext = keyIter.hasNext;
			this.minKey = keyIter.minKey;
			this.maxKey = keyIter.maxKey;

			if (bufferId >= 0) {

				if (modCount != expectedModCount) {
					reset();
				}
				else {
					try {
						FieldKeyRecordNode leaf = (FieldKeyRecordNode) getFieldKeyNode(bufferId);
						getKeys(leaf);
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}

			}
		}

		/**
		 * Initialize (or re-initialize) iterator state. (require DBHandle lock)
		 * An empty or null keys array will force a complete initialization.
		 * Otherwise, following the delete the keys array and keyIndex should reflect the state
		 * following a delete.
		 * @param targetKey the initial key.  For construction this is the startKey, 
		 * following a delete this is the deleted key.
		 * @throws IOException thrown if IO error occurs
		 */
		private void initialize(Field targetKey) throws IOException {

			expectedModCount = modCount;
			hasNext = false;
			hasPrev = false;

			if (rootBufferId < 0) {
				keys = Field.EMPTY_ARRAY;
				bufferId = -1;
				return;
			}

			try {

				FieldKeyRecordNode leaf = null;
				if (keys == null || keys.length == 0) {

					FieldKeyNode rootNode = getFieldKeyNode(rootBufferId);

					if (targetKey == null) {
						targetKey = minKey;
					}

					// If startKey not specified, start with leftmost record
					if (targetKey == null) {
						leaf = rootNode.getLeftmostLeafNode();
						getKeys(leaf);
						key = keys[0];
						keyIndex = 0;
						hasNext = true;
						return;
					}
					leaf = rootNode.getLeafNode(targetKey);
					getKeys(leaf);

					// Empty leaf node - special case
					if (keys.length == 0) {
						return;
					}

					keyIndex = leaf.getKeyIndex(targetKey);
				}

				// Start key was found
				if (keyIndex >= 0) {
					hasPrev = true;
					hasNext = true;
				}

				// Start key was not found
				else {
					keyIndex = -(keyIndex + 1);
					if (keyIndex == keys.length) {
						--keyIndex;
						hasPrev = minKey == null ? true : (keys[keyIndex].compareTo(minKey) >= 0);
						if (!hasPrev) {
							if (leaf == null) {
								keys = null;
								initialize(targetKey);
								return;
							}
							leaf = leaf.getNextLeaf();
							if (leaf == null) {
								keys = Field.EMPTY_ARRAY;
								bufferId = -1;
								return;
							}
							keyIndex = 0;
							getKeys(leaf);
							hasNext =
								maxKey == null ? true : (keys[keyIndex].compareTo(maxKey) <= 0);
						}
					}
					else {
						hasNext = maxKey == null ? true : (keys[keyIndex].compareTo(maxKey) <= 0);
						if (!hasNext) {
							// position to previous record
							if (keyIndex == 0) {
								if (leaf == null) {
									keys = null;
									initialize(targetKey);
									return;
								}
								leaf = leaf.getPreviousLeaf();
								if (leaf == null) {
									keys = Field.EMPTY_ARRAY;
									bufferId = -1;
									return;
								}
								keyIndex = leaf.getKeyCount() - 1;
								getKeys(leaf);
							}
							else {
								--keyIndex;
							}
							hasPrev =
								minKey == null ? true : (keys[keyIndex].compareTo(minKey) >= 0);
						}
					}
					if (hasNext || hasPrev) {
						key = keys[keyIndex];
					}
				}

			}
			finally {
				nodeMgr.releaseNodes();
			}
		}

		/**
		 * Reset iterator (require DBHandle lock)
		 * @throws IOException if IO error occurs
		 */
		private void reset() throws IOException {
			boolean hadNext = hasNext;
			boolean hadPrev = hasPrev;
			keys = null;
			initialize(key);
			if (hasNext && hasPrev) {
				hasNext = hadNext;
				hasPrev = hadPrev;
			}
		}

		private void getKeys(FieldKeyRecordNode node) throws IOException {
			bufferId = node.getBufferId();
			int keyCount = node.getKeyCount();
			if (keys == null || keys.length != keyCount) {
				keys = new Field[keyCount];
			}
			for (int i = 0; i < keyCount; i++) {
				keys[i] = node.getKeyField(i);
			}
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasNext) {

					if (bufferId < 0) {
						return false;
					}

					// Check next key index
					int nextIndex = keyIndex + 1;

					// Process next leaf if needed
					if (nextIndex >= keys.length) {
						try {
							FieldKeyRecordNode leaf =
								((FieldKeyRecordNode) getFieldKeyNode(bufferId)).getNextLeaf();
							if (leaf == null ||
								(maxKey != null && leaf.getKeyField(0).compareTo(maxKey) > 0)) {
								return false;
							}
							getKeys(leaf);
							key = keys[0];
							keyIndex = 0;
							hasNext = true;
							hasPrev = false;
						}
						finally {
							nodeMgr.releaseNodes();
						}
					}

					// else, use keys cache
					else {
						hasNext = maxKey == null || keys[nextIndex].compareTo(maxKey) <= 0;
						if (hasNext) {
							key = keys[nextIndex];
							keyIndex = nextIndex;
							hasPrev = false;
						}
					}

				}
				return hasNext;
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasPrev) {

					if (bufferId < 0) {
						return false;
					}

					// Check previous key index
					int prevIndex = keyIndex - 1;

					// Process previous leaf if needed
					if (prevIndex < 0) {
						try {
							FieldKeyRecordNode leaf =
								((FieldKeyRecordNode) getFieldKeyNode(bufferId)).getPreviousLeaf();
							if (leaf == null) {
								return false;
							}
							prevIndex = leaf.getKeyCount() - 1;
							if (minKey != null &&
								leaf.getKeyField(prevIndex).compareTo(minKey) < 0) {
								return false;
							}
							getKeys(leaf);
							key = keys[prevIndex];
							keyIndex = prevIndex;
							hasNext = false;
							hasPrev = true;
						}
						finally {
							nodeMgr.releaseNodes();
						}
					}

					// else, use keys cache
					else {
						hasPrev = minKey == null || keys[prevIndex].compareTo(minKey) >= 0;
						if (hasPrev) {
							key = keys[prevIndex];
							keyIndex = prevIndex;
							hasNext = false;
						}
					}
				}
				return hasPrev;
			}
		}

		@Override
		public Field next() throws IOException {
			if (hasNext || hasNext()) {
				hasNext = false;
				hasPrev = true;
				lastKey = key;
				return key;
			}
			return null;
		}

		@Override
		public Field previous() throws IOException {
			if (hasPrev || hasPrevious()) {
				hasNext = true;
				hasPrev = false;
				lastKey = key;
				return key;
			}
			return null;
		}

		@Override
		public boolean delete() throws IOException {
			if (lastKey != null) {
				synchronized (db) {
					Field deleteKey = lastKey;
					lastKey = null;
					boolean success = deleteRecord(deleteKey);
					int newLen = keys.length - 1;
					if (deleteKey.equals(key) && keys.length > 1 && keyIndex < newLen) {
						Field[] newKeys = new Field[newLen];
						System.arraycopy(keys, 0, newKeys, 0, keyIndex);
						System.arraycopy(keys, keyIndex + 1, newKeys, keyIndex, newLen - keyIndex);
						keys = newKeys;
						keyIndex = -(keyIndex + 1); // reflects non-existent key to initialize method
					}
					else {
						keys = null;
					}
					initialize(deleteKey);
					return success;
				}
			}
			return false;
		}

	}

	/**
	 * A Field key iterator class - optimized for short iterations since
	 * the number of keys read from each record node is minimized.
	 */
	private class ShortDurationFieldKeyIterator implements DBFieldIterator {

		private int bufferId;
		private int keyIndex;
		private Field lastKey;
		private Field key;

		private int expectedModCount;

		private boolean hasPrev;
		private boolean hasNext;

		private Field minKey;
		private Field maxKey;

		/**
		 * Construct a record iterator. (requires DBHandle lock)
		 * @param minKey minimum key value.  Null corresponds to minimum key value.
		 * @param maxKey maximum key value.  Null corresponds to maximum key value.
		 * @param startKey the first primary key value.  If null minKey will be assumed,
		 * if still null the minimum indexed value will be assumed.
		 * @throws IOException if IO error occurs
		 */
		ShortDurationFieldKeyIterator(Field minKey, Field maxKey, Field startKey) throws IOException {

			this.minKey = minKey;
			this.maxKey = maxKey;
			this.key = startKey;

			initialize(startKey);
		}

		/**
		 * Initialize (or re-initialize) iterator state.
		 * An empty or null keys array will force a complete initialization.
		 * Otherwise, following the delete the keys array and keyIndex should reflect the state
		 * following a delete.
		 * @param targetKey the initial key.  For construction this is the startKey, 
		 * following a delete this is the deleted key.
		 * @throws IOException thrown if IO error occurs
		 */
		private void initialize(Field targetKey) throws IOException {

			expectedModCount = modCount;
			hasNext = false;
			hasPrev = false;
			bufferId = -1;

			if (rootBufferId < 0) {
				return;
			}

			try {

				FieldKeyRecordNode leaf;
				FieldKeyNode rootNode = getFieldKeyNode(rootBufferId);

				if (targetKey == null) {
					targetKey = minKey;
				}

				// If startKey not specified, start with leftmost record
				if (targetKey == null) {
					leaf = rootNode.getLeftmostLeafNode();
					bufferId = leaf.getBufferId();
					key = leaf.getKeyField(0);
					keyIndex = 0;
					hasNext = true;
					return;
				}
				leaf = rootNode.getLeafNode(targetKey);
				bufferId = leaf.getBufferId();

				// Empty leaf node - special case
				if (leaf.getKeyCount() == 0) {
					keyIndex = -1;
					return;
				}

				keyIndex = leaf.getKeyIndex(targetKey);

				// Start key was found
				if (keyIndex >= 0) {
					key = leaf.getKeyField(keyIndex);
					hasPrev = true;
					hasNext = true;
				}

				// Start key was not found
				else {
					keyIndex = -(keyIndex + 1);
					if (keyIndex == leaf.getKeyCount()) {
						--keyIndex;
						key = leaf.getKeyField(keyIndex);
						hasPrev = minKey == null ? true : (key.compareTo(minKey) >= 0);
					}
					else {
						key = leaf.getKeyField(keyIndex);
						hasNext = maxKey == null ? true : (key.compareTo(maxKey) <= 0);
					}

				}

			}
			finally {
				nodeMgr.releaseNodes();
			}
		}

		/**
		 * Reset iterator (requires DBHandle lock)
		 * @throws IOException if IO error occurs
		 */
		private void reset() throws IOException {
			boolean hadNext = hasNext;
			boolean hadPrev = hasPrev;
			initialize(key);
			if (hasNext && hasPrev) {
				hasNext = hadNext;
				hasPrev = hadPrev;
			}
		}

		@Override
		public boolean hasNext() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasNext) {

					if (bufferId < 0 || keyIndex < 0) {
						return false;
					}

					// Check next key index
					int nextIndex = keyIndex + 1;

					try {
						// Process next leaf if needed
						FieldKeyRecordNode leaf = (FieldKeyRecordNode) getFieldKeyNode(bufferId);
						if (nextIndex >= leaf.getKeyCount()) {
							leaf = leaf.getNextLeaf();
							if (leaf == null) {
								return false;
							}
							Field nextKey = leaf.getKeyField(0);
							if (maxKey != null && nextKey.compareTo(maxKey) > 0) {
								return false;
							}
							bufferId = leaf.getBufferId();
							key = nextKey;
							keyIndex = 0;
							hasNext = true;
							hasPrev = false;
						}

						// else, use keys cache
						else {
							Field nextKey = leaf.getKeyField(nextIndex);
							hasNext = maxKey == null ? true : (nextKey.compareTo(maxKey) <= 0);
							if (hasNext) {
								key = nextKey;
								keyIndex = nextIndex;
								hasPrev = false;
							}
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
				return hasNext;
			}
		}

		@Override
		public boolean hasPrevious() throws IOException {
			synchronized (db) {
				if (modCount != expectedModCount) {
					reset();
				}
				if (!hasPrev) {

					if (bufferId < 0 || keyIndex < 0) {
						return false;
					}

					// Check previous key index
					int prevIndex = keyIndex - 1;

					try {
						// Process previous leaf if needed
						FieldKeyRecordNode leaf = (FieldKeyRecordNode) getFieldKeyNode(bufferId);
						if (prevIndex < 0) {
							leaf = leaf.getPreviousLeaf();
							if (leaf == null) {
								return false;
							}
							prevIndex = leaf.getKeyCount() - 1;
							Field prevKey = leaf.getKeyField(prevIndex);
							if (minKey != null && prevKey.compareTo(minKey) < 0) {
								return false;
							}
							bufferId = leaf.getBufferId();
							key = prevKey;
							keyIndex = prevIndex;
							hasNext = false;
							hasPrev = true;
						}

						// else, use keys cache
						else {
							Field prevKey = leaf.getKeyField(prevIndex);
							hasPrev = minKey == null ? true : (prevKey.compareTo(minKey) >= 0);
							if (hasPrev) {
								key = prevKey;
								keyIndex = prevIndex;
								hasNext = false;
							}
						}
					}
					finally {
						nodeMgr.releaseNodes();
					}
				}
				return hasPrev;
			}
		}

		@Override
		public Field next() throws IOException {
			if (hasNext || hasNext()) {
				hasNext = false;
				hasPrev = true;
				lastKey = key;
				return key;
			}
			return null;
		}

		@Override
		public Field previous() throws IOException {
			if (hasPrev || hasPrevious()) {
				hasNext = true;
				hasPrev = false;
				lastKey = key;
				return key;
			}
			return null;
		}

		@Override
		public boolean delete() throws IOException {
			if (lastKey != null) {
				Field deleteKey = lastKey;
				lastKey = null;
				return deleteRecord(deleteKey);
			}
			return false;
		}

	}

	/**
	 * @return true if table is valid and has not been invalidated
	 */
	public boolean isInvalid() {
		return nodeMgr == null;
	}

	@Override
	public String toString() {
		return getName() + "(" + getRecordCount() + ")";
	}
}