com.bigdata.btree
Interface ILinearList

All Known Implementing Classes:

AbstractBTree, BTree, CommitRecordIndex, CommitTimeIndex, CounterSetBTree, EventReceiver.EventBTree, IndexSegment, IndexSegmentIndex, JournalIndex, MetadataIndex, Name2Addr, TxId2CommitTimeIndex

public interface ILinearList

Interface for methods that return or accept an ordinal index into the entries in the B+-Tree. The semantics of this interface are build over the #of spanned tuples for each child as recorded within each node of the B+Tree. This provides a fast means to compute the linear index into the B+Tree of any given tuple. However, this interface is only available for a local B+Tree object (versus scale-out) since the spanned tuple count metadata is not exact across shards. Further, when delete markers are used, the deleted tuples remain in the B+Tree and the ILinearList interface will continue to count them until they have been purged. Thus deleting a tuple does not change the indexOf(byte[]) keys after that tuple, keyAt(long) can return the key for a deleted tuple, and valueAt(long) will return null if the tuple at that index is marked as deleted within the B+Tree.

Version:

$Id: ILinearList.java 4523 2011-05-18 18:14:45Z thompsonbry $

Author:

Bryan Thompson

Method Summary

long	indexOf(byte[] key) Lookup the index position of the key.
byte[]	keyAt(long index) Return the key for the identified entry.
byte[]	valueAt(long index) Return the value for the identified entry.

Method Detail

indexOf

long indexOf(byte[] key)

Lookup the index position of the key.

Note that indexOf(byte[]) is the basis for implementing the IRangeQuery interface.

Parameters:

key - The key.

Returns:

The index of the search key, if found; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be found it it were inserted into the btree without intervening mutations. Note that this guarantees that the return value will be >= 0 if and only if the key is found. When found the index will be in [0:nentries). Adding or removing entries in the tree may invalidate the index.

pos = -(pos+1) will convert an insertion point to the index at which the key would be found if it were inserted - this is also the index of the predecessor of key in the index.

See Also:

keyAt(long), valueAt(long)

keyAt

byte[] keyAt(long index)

Return the key for the identified entry. This performs an efficient search whose cost is essentially the same as ISimpleBTree.lookup(byte[]).

Parameters:

index - The index position of the entry (origin zero).

Returns:

The key at that index position.

Throws:

IndexOutOfBoundsException - if index is less than zero.

IndexOutOfBoundsException - if index is greater than or equal to the #of entries.

See Also:

indexOf(byte[]), valueAt(long)

valueAt

byte[] valueAt(long index)

Return the value for the identified entry. This performs an efficient search whose cost is essentially the same as ISimpleBTree.lookup(byte[]).

Parameters:

index - The index position of the entry (origin zero).

Returns:

The value at that index position -or- null if there is a deleted entry at that index position then

Throws:

IndexOutOfBoundsException - if index is less than zero.

IndexOutOfBoundsException - if index is greater than or equal to the #of entries.

See Also:

indexOf(byte[]), keyAt(long)