com.bigdata.btree
Class IndexSegment

java.lang.Object
  com.bigdata.btree.AbstractBTree
      com.bigdata.btree.IndexSegment

All Implemented Interfaces:

IAutoboxBTree, IBTreeStatistics, IIndex, IIndexLocalCounter, ILinearList, ILocalBTreeView, IRangeQuery, ISimpleBTree, ICounterSetAccess

public class IndexSegment
extends AbstractBTree

An index segment is read-only btree corresponding to some key range of a potentially distributed index. The file format of the index segment includes a metadata record, the leaves of the segment in key order, and the nodes of the segment in an arbitrary order. It is possible to map or buffer the part of the file containing the index nodes or the entire file depending on application requirements.

Note: iterators returned by this class do not support removal (the nodes and leaves will all refuse mutation operations).

Version:

$Id: IndexSegment.java 5897 2012-01-27 17:45:20Z thompsonbry $

Author:

Bryan Thompson

Nested Class Summary

class	IndexSegment.ImmutableLeafCursor Cursor using the double-linked leaves for efficient scans.
protected static class	IndexSegment.ImmutableNodeFactory Factory for immutable nodes and leaves used by the NodeSerializer.
static class	IndexSegment.IndexSegmentTupleCursor<E> Implementation for an immutable IndexSegment.

Nested classes/interfaces inherited from class com.bigdata.btree.AbstractBTree

AbstractBTree.IBTreeCounters

Field Summary

Fields inherited from class com.bigdata.btree.AbstractBTree

branchingFactor, debug, DEBUG, dumpLog, ERROR_CLOSED, ERROR_LESS_THAN_ZERO, ERROR_READ_ONLY, ERROR_TOO_LARGE, ERROR_TRANSIENT, INFO, log, metadata, ndistinctOnWriteRetentionQueue, nodeSer, readOnly, root, store, storeCache, writeRetentionQueue

Fields inherited from interface com.bigdata.btree.IRangeQuery

ALL, CURSOR, DEFAULT, DELETED, FIXED_LENGTH_SUCCESSOR, KEYS, NONE, PARALLEL, READONLY, REMOVEALL, REVERSE, VALS

Constructor Summary

IndexSegment(IndexSegmentStore fileStore)
Open a read-only index segment.

Method Summary

protected void	_reopen() This method is responsible for setting up the root leaf (either new or read from the store), the bloom filter, etc.
void	close() Extended to also close the backing file.
protected void	finalize() Extended to explicitly close the IndexSegment and the backing IndexSegmentStore.
IndexSegment.ImmutableNodeFactory.ImmutableLeaf	findLeaf(byte[] key)
long	findLeafAddr(byte[] key) Find the address of the leaf that would span the key.
BloomFilter	getBloomFilter() Return the optional IBloomFilter, transparently AbstractBTree.reopen()ing the index if necessary.
ICounter	getCounter() Operation is disallowed - the counter is only stored in the mutable BTree.
long	getEntryCount() The #of entries (aka tuples) in the AbstractBTree.
int	getHeight() The height of the btree.
long	getLastCommitTime() The value of the IndexSegmentCheckpoint.commitTime field.
long	getLeafCount() The #of leaf nodes in the AbstractBTree.
BTree	getMutableBTree() The BTree that is absorbing writes for the view.
long	getNodeCount() The #of non-leaf nodes in the AbstractBTree.
long	getRevisionTimestamp() The timestamp associated with unisolated writes on this index.
int	getSourceCount() The #of AbstractBTrees sources for the view.
AbstractBTree[]	getSources() An array containing the ordered sources in the view.
IndexSegmentStore	getStore() Overridden to a more constrained type.
IndexSegment.ImmutableLeafCursor	newLeafCursor(byte[] key) Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree.
IndexSegment.ImmutableLeafCursor	newLeafCursor(SeekEnum where) Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree.
IndexSegment.ImmutableNodeFactory.ImmutableLeaf	readLeaf(long addr) Type-safe method reads the leaf from the backing file given the address of that leaf.
protected AbstractNode<?>	readNodeOrLeaf(long addr) Extended to transparently re-open the backing IndexSegmentStore.
void	removeAll() Remove all entries in the B+Tree.
String	toString() Fast summary information about the B+Tree.

Methods inherited from class com.bigdata.btree.AbstractBTree

assertNotReadOnly, assertNotTransient, contains, contains, decodeRecordAddr, dump, dump, encodeRecordAddr, getBranchingFactor, getBtreeCounters, getContainsTuple, getCounters, getIndexMetadata, getLookupTuple, getNodeSerializer, getResourceMetadata, getRightMostNode, getRoot, getRootOrFinger, getStatistics, getUtilization, getWriteTuple, indexOf, insert, insert, insert, isOpen, isReadOnly, isTransient, keyAt, lookup, lookup, lookup, rangeCheck, rangeCopy, rangeCount, rangeCount, rangeCount, rangeCountExact, rangeCountExactWithDeleted, rangeIterator, rangeIterator, rangeIterator, rangeIterator, rangeIterator, recycle, remove, remove, remove, reopen, setBTreeCounters, submit, submit, submit, touch, valueAt, valueAt, writeNodeOrLeaf, writeNodeRecursive

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

IndexSegment

public IndexSegment(IndexSegmentStore fileStore)

Open a read-only index segment.

Parameters:

fileStore - The store containing the IndexSegment.

See Also:

IndexSegmentStore.loadIndexSegment()

Method Detail

getHeight

public final int getHeight()

Description copied from interface: IBTreeStatistics

The height of the btree. The height is the #of levels minus one. A btree with only a root leaf has height := 0. A btree with a root node and one level of leaves under it has height := 1. Note that all leaves of a btree are at the same height (this is what is means for the btree to be "balanced"). Also note that the height only changes when we split or join the root node (a btree maintains balance by growing and shrinking in levels from the top rather than the leaves).

Specified by:

getHeight in interface IBTreeStatistics

Specified by:

getHeight in class AbstractBTree

getNodeCount

public final long getNodeCount()

Description copied from interface: IBTreeStatistics

The #of non-leaf nodes in the AbstractBTree. This is zero (0) for a new btree.

Specified by:

getNodeCount in interface IBTreeStatistics

Specified by:

getNodeCount in class AbstractBTree

getLeafCount

public final long getLeafCount()

Description copied from interface: IBTreeStatistics

The #of leaf nodes in the AbstractBTree. This is one (1) for a new btree.

Specified by:

getLeafCount in interface IBTreeStatistics

Specified by:

getLeafCount in class AbstractBTree

getEntryCount

public final long getEntryCount()

Description copied from interface: IBTreeStatistics

The #of entries (aka tuples) in the AbstractBTree. This is zero (0) for a new B+Tree. When the B+Tree supports delete markers, this value also includes tuples which have been marked as deleted.

Specified by:

getEntryCount in interface IBTreeStatistics

Specified by:

getEntryCount in class AbstractBTree

toString

public String toString()

Fast summary information about the B+Tree.

Overridden to be thread-safe without requiring any locks.

Overrides:

toString in class AbstractBTree

close

public void close()

Extended to also close the backing file.

Overrides:

close in class AbstractBTree

getStore

public final IndexSegmentStore getStore()

Overridden to a more constrained type.

Specified by:

getStore in class AbstractBTree

finalize

protected void finalize()
                 throws Throwable

Extended to explicitly close the IndexSegment and the backing IndexSegmentStore. A finalizer is necessary for this class because we maintain IndexSegments in a weak value cache and do not explicitly close then before their reference is cleared. This leads to the IndexSegmentStore being left open. The finalizer fixes that.

Overrides:

finalize in class Object

Throws:

Throwable

_reopen

protected void _reopen()

Description copied from class: AbstractBTree

This method is responsible for setting up the root leaf (either new or read from the store), the bloom filter, etc. It is invoked by AbstractBTree.reopen() once AbstractBTree.root has been show to be null with double-checked locking. When invoked in this context, the caller is guaranteed to hold a lock on this. This is done to ensure that at most one thread gets to re-open the index from the backing store.

Specified by:

_reopen in class AbstractBTree

getBloomFilter

public final BloomFilter getBloomFilter()

Description copied from class: AbstractBTree

Return the optional IBloomFilter, transparently AbstractBTree.reopen()ing the index if necessary.

Specified by:

getBloomFilter in interface ILocalBTreeView

Specified by:

getBloomFilter in class AbstractBTree

Returns:

The bloom filter -or- null if there is no bloom filter (including the case where there is a bloom filter but it has been disabled since the BTree has grown too large and the expected error rate of the bloom filter would be too high).

getLastCommitTime

public final long getLastCommitTime()

The value of the IndexSegmentCheckpoint.commitTime field.

Specified by:

getLastCommitTime in class AbstractBTree

getRevisionTimestamp

public final long getRevisionTimestamp()

Description copied from class: AbstractBTree

The timestamp associated with unisolated writes on this index. This timestamp is designed to allow the interleaving of full transactions (whose revision timestamp is assigned by the transaction service) with unisolated operations on the same indices.

The revision timestamp assigned by this method is lastCommitTime+1. The reasoning is as follows. Revision timestamps are assigned by the transaction manager when the transaction is validated as part of its commit protocol. Therefore, revision timestamps are assigned after the transaction write set is complete. Further, the assigned revisionTimestamp will be strictly LT the commitTime for that transaction. By using lastCommitTime+1 we are guaranteed that the revisionTimestamp for new writes (which will be part of some future commit point) will always be strictly GT the revisionTimestamp of historical writes (which were part of some prior commit point).

Note: Unisolated operations using this timestamp ARE NOT validated. The timestamp is simply applied to the tuple when it is inserted or updated and will become part of the restart safe state of the B+Tree once the unisolated operation participates in a commit.

Note: If an unisolated operation were to execute concurrent with a transaction commit for the same index then that could produce inconsistent results in the index and could trigger concurrent modification errors. In order to avoid such concurrent modification errors, unisolated operations which are to be mixed with full transactions MUST ensure that they have exclusive access to the unisolated index before proceeding. There are two ways to do this: (1) take the application off line for transactions; (2) submit your unisolated operations to the IConcurrencyManager which will automatically impose the necessary constraints on concurrent access to the unisolated indices.

Specified by:

getRevisionTimestamp in class AbstractBTree

Returns:

The revision timestamp to be assigned to an unisolated write.

Throws:

UnsupportedOperationException - always since the IndexSegment is read-only.

getCounter

public final ICounter getCounter()

Operation is disallowed - the counter is only stored in the mutable BTree.

removeAll

public final void removeAll()

Description copied from class: AbstractBTree

Remove all entries in the B+Tree.

Note: The IIndexManager defines methods for registering (adding) and dropping indices vs removing the entries in an individual AbstractBTree.

Specified by:

removeAll in class AbstractBTree

Throws:

UnsupportedOperationException - always.

readLeaf

public IndexSegment.ImmutableNodeFactory.ImmutableLeaf readLeaf(long addr)

Type-safe method reads the leaf from the backing file given the address of that leaf. This method is suitable for ad-hoc examination of the leaf or for a low-level iterator based on the prior/next leaf addresses.

Note: The parent is NOT set on the leaf but it MAY be defined if the leaf was read from cache.

Parameters:

addr - The address of a leaf.

Returns:

That leaf.

readNodeOrLeaf

protected AbstractNode<?> readNodeOrLeaf(long addr)

Extended to transparently re-open the backing IndexSegmentStore.

Overrides:

readNodeOrLeaf in class AbstractBTree

Parameters:

addr - The address in the store.

Returns:

The node or leaf.

findLeaf

public IndexSegment.ImmutableNodeFactory.ImmutableLeaf findLeaf(byte[] key)

findLeafAddr

public long findLeafAddr(byte[] key)

Find the address of the leaf that would span the key.

Parameters:

key - The key

Returns:

The address of the leaf which would span that key.

Throws:

IllegalArgumentException - if the key is null.

RuntimeException - if the key does not lie within the optional key-range constraints for an index partition.

newLeafCursor

public IndexSegment.ImmutableLeafCursor newLeafCursor(SeekEnum where)

Description copied from class: AbstractBTree

Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree. The cursor will be initially positioned on the leaf identified by the symbolic constant.

Specified by:

newLeafCursor in class AbstractBTree

newLeafCursor

public IndexSegment.ImmutableLeafCursor newLeafCursor(byte[] key)

Description copied from class: AbstractBTree

Return a cursor that may be used to efficiently locate and scan the leaves in the B+Tree. The cursor will be initially positioned on the leaf that spans the given key.

Specified by:

newLeafCursor in class AbstractBTree

Parameters:

key - The key (required).

getMutableBTree

public BTree getMutableBTree()

Description copied from interface: ILocalBTreeView

The BTree that is absorbing writes for the view.

getSourceCount

public int getSourceCount()

Description copied from interface: ILocalBTreeView

The #of AbstractBTrees sources for the view. This will be ONE (1) if the view is a BTree.

getSources

public AbstractBTree[] getSources()

Description copied from interface: ILocalBTreeView

An array containing the ordered sources in the view. Changes to the array DO NOT affect the view. If the view is an AbstractBTree then the array will contain a single element which is that AbstractBTree.