com.bigdata.btree
Class IndexSegment

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

All Implemented Interfaces:

IAutoboxBTree, IIndex, ILinearList, IRangeQuery, ISimpleBTree

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 2265 2009-10-26 12:51:06Z 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.

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, 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.
int	getEntryCount() The #of entries (aka values) in the AbstractBTree.
int	getHeight() The height of the btree.
long	getLastCommitTime() The value of the IndexSegmentCheckpoint.commitTime field.
int	getLeafCount() The #of leaf nodes in the AbstractBTree.
int	getNodeCount() The #of non-leaf nodes in the AbstractBTree.
IndexSegmentStore	getStore() Overridden to a more constrained type.
boolean	isReadOnly() Return true iff this B+Tree is read-only.
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() Note: This is synchronized in order to prevent a concurrent process from closing the IndexSegment during this method.

Methods inherited from class com.bigdata.btree.AbstractBTree

assertNotReadOnly, assertNotTransient, contains, contains, dump, dump, getBranchingFactor, getBtreeCounters, getContainsTuple, getCounters, getDynamicCounterSet, getIndexMetadata, getLookupTuple, getNodeSerializer, getResourceMetadata, getRightMostNode, getRoot, getRootOrFinger, getStaticCounterSet, getUtilization, getWriteTuple, indexOf, insert, insert, insert, isOpen, isTransient, keyAt, lookup, lookup, lookup, rangeCheck, rangeCopy, rangeCount, rangeCount, rangeCount, rangeCountExact, rangeCountExactWithDeleted, rangeIterator, rangeIterator, rangeIterator, rangeIterator, rangeIterator, 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 class: AbstractBTree

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 class AbstractBTree

getLeafCount

public final int getLeafCount()

Description copied from class: AbstractBTree

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

Specified by:

getLeafCount in class AbstractBTree

getNodeCount

public final int getNodeCount()

Description copied from class: AbstractBTree

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

Specified by:

getNodeCount in class AbstractBTree

getEntryCount

public final int getEntryCount()

Description copied from class: AbstractBTree

The #of entries (aka values) in the AbstractBTree. This is zero (0) for a new B+Tree. Note that this value is tracked explicitly so it requires no IOs.

Specified by:

getEntryCount in class AbstractBTree

toString

public String toString()

Note: This is synchronized in order to prevent a concurrent process from closing the IndexSegment during this method. In particular, getEntryCount() uses the IndexSegmentCheckpoint and that is only available while the IndexSegmentStore is open.

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 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).

isReadOnly

public final boolean isReadOnly()

Description copied from class: AbstractBTree

Return true iff this B+Tree is read-only.

Specified by:

isReadOnly in class AbstractBTree

getLastCommitTime

public final long getLastCommitTime()

The value of the IndexSegmentCheckpoint.commitTime field.

Specified by:

getLastCommitTime in class AbstractBTree

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).