com.bigdata.btree.PO
com.bigdata.btree.AbstractNode<Leaf>
com.bigdata.btree.Leaf
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Object
public class Leaf
A B+-Tree leaf.
When tuple revision timestamps are maintained, they must be propagated to the
parents if we insert or remove a tuple, but also need to be propagated if we
update a tuple in a manner which changes the min/max version timestamp. This
is done either by Node.updateEntryCount(AbstractNode, int), when the
#of tuples in the leaf was changed, or by
Node.updateMinMaxVersionTimestamp(AbstractNode) when the #of tuples
in the leaf is unchanged.
The getMinimumVersionTimestamp() and
getMaximumVersionTimestamp() can be used to efficiently filter
iterators so as to only visit those nodes and leaves which have updates for
some revision timestamp range. This filtering is effective because if we
reject a node has not having data for the revision range of interest, then we
do not need to consider any of the nodes or leaves spanned by that node.
Note that revision timestamps ARE NOT commit timestamps. See
ITransactionService and IsolatedFusedView for more about
this and how to obtain and work with revision timestamps.
| Nested Class Summary | |
|---|---|
static interface |
Leaf.ILeafListener
An interface that may be used to register for and receive events when the state of a Leaf is changed. |
| Field Summary |
|---|
| Fields inherited from class com.bigdata.btree.AbstractNode |
|---|
btree, INFO, log, parent, referenceCount, self |
| Fields inherited from class com.bigdata.btree.PO |
|---|
deleted, dirty, identity |
| Fields inherited from interface com.bigdata.btree.IIdentityAccess |
|---|
NULL |
| Constructor Summary | |
|---|---|
protected |
Leaf(AbstractBTree btree)
Creates a new mutable leaf. |
protected |
Leaf(AbstractBTree btree,
long addr,
ILeafData data)
De-serialization constructor. |
protected |
Leaf(Leaf src)
Copy constructor. |
| Method Summary | |
|---|---|
void |
addLeafListener(Leaf.ILeafListener l)
Register an Leaf.ILeafListener with this Leaf. |
protected void |
copyDown(int entryIndex,
int count)
Copies all keys and values from the specified start index down by one in order to make room to insert a key and value at that index. |
AbstractFixedByteArrayBuffer |
data()
The coded (aka compressed) data. |
void |
delete()
Deletes the persistence capable object. |
boolean |
dump(org.apache.log4j.Level level,
PrintStream out,
int height,
boolean recursive)
Dump the data onto the PrintStream. |
ITupleIterator |
entryIterator()
Iterator visits the tuples in this leaf in key order. |
protected void |
fireInvalidateLeafEvent()
Fire an Leaf.ILeafListener.invalidateLeaf() event to any registered
listeners. |
ILeafData |
getDelegate()
Return the delegate IAbstractNodeData object. |
boolean |
getDeleteMarker(int index)
Return true iff the entry at the specified index is marked
as deleted. |
int |
getKeyCount()
Return the #of keys in the node or leaf. |
IRaba |
getKeys()
The object used to contain and manage the keys. |
long |
getMaximumVersionTimestamp()
The most recent tuple revision timestamp associated with any tuple spanned by this node or leaf. |
long |
getMinimumVersionTimestamp()
The earliest tuple revision timestamp associated with any tuple spanned by this node or leaf. |
long |
getNextAddr()
The address of the next leaf in key order, 0L if it is known
that there is no next leaf, and -1L if either: (a) it is not
known whether there is a next leaf; or (b) it is known but the address of
that leaf is not known to the caller. |
long |
getPriorAddr()
The address of the previous leaf in key order, 0L if it is
known that there is no previous leaf, and -1L if either: (a)
it is not known whether there is a previous leaf; or (b) it is known but
the address of that leaf is not known to the caller. |
int |
getSpannedTupleCount()
The #of tuples spanned by this node or leaf. |
int |
getValueCount()
The #of values in the leaf (this MUST be equal to the #of keys for a leaf). |
IRaba |
getValues()
Return the object storing the logical byte[][] containing the values for the leaf. |
long |
getVersionTimestamp(int index)
The version timestamp for the entry at the specified index. |
boolean |
hasDeleteMarkers()
Return true iff the leaf maintains delete markers. |
boolean |
hasVersionTimestamps()
Return true iff the leaf maintains version timestamps. |
int |
indexOf(byte[] key)
Recursive search locates the appropriate leaf and returns the index position of the entry. |
Tuple |
insert(byte[] searchKey,
byte[] newval,
boolean delete,
long timestamp,
Tuple tuple)
Insert or update an entry in the leaf as appropriate. |
boolean |
isCoded()
true iff this is a coded data structure. |
boolean |
isDoubleLinked()
Return true if the leaf data record supports encoding of the
address of the previous and next leaf in the B+Tree order. |
boolean |
isLeaf()
Always returns true. |
boolean |
isReadOnly()
The result depends on the implementation. |
byte[] |
keyAt(int entryIndex)
Recursive search locates the entry at the specified index position in the btree and returns the key for that entry. |
Tuple |
lookup(byte[] searchKey,
Tuple tuple)
Lookup a key. |
protected int |
maxKeys()
Return branchingFactor, which is the maximum #of keys for a
Leaf. |
protected void |
merge(AbstractNode sibling,
boolean isRightSibling)
Merge the keys and values from the sibling into this leaf, delete the sibling from the store and remove the sibling from the parent. |
protected int |
minKeys()
Return (branchingFactor + 1) << 1 |
Iterator<AbstractNode> |
postOrderIterator(byte[] fromKey,
byte[] toKey)
Visits this leaf. |
Iterator<AbstractNode> |
postOrderNodeIterator(boolean dirtyNodesOnly)
Visits this leaf if unless it is not dirty and the flag is true, in which case the returned iterator will not visit anything. |
protected void |
redistributeKeys(AbstractNode sibling,
boolean isRightSibling)
Redistributes a key from the specified sibling into this leaf in order to bring this leaf up to the minimum #of keys. |
Tuple |
remove(byte[] key,
Tuple tuple)
Recursive search locates the appropriate leaf and removes the entry for the key. |
protected IAbstractNode |
split()
Split an over-capacity leaf (a leaf with maxKeys+1 keys),
creating a new rightSibling. |
String |
toString()
Human readable representation of the ILeafData plus transient
information associated with the Leaf. |
void |
valueAt(int entryIndex,
Tuple tuple)
Recursive search locates the entry at the specified index position in the btree and returns the value for that entry. |
| Methods inherited from class com.bigdata.btree.AbstractNode |
|---|
assertInvariants, assertKeysMonotonic, copyKey, copyOnWrite, copyOnWrite, dump, dump, getBranchingFactor, getParent, indent, isLeftMostNode, isRightMostNode, join, keyAsString, postOrderNodeIterator, rangeIterator |
| Methods inherited from class com.bigdata.btree.PO |
|---|
getIdentity, isDeleted, isDirty, isPersistent, setDirty, toShortString |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
| Constructor Detail |
|---|
protected Leaf(AbstractBTree btree,
long addr,
ILeafData data)
Note: The de-serialization constructor (and ONLY the de-serialization
constructor) ALWAYS creates a clean leaf. Therefore the PO.dirty
flag passed up from this constructor has the value false.
btree - The tree to which the leaf belongs.addr - The address of this leaf.data - The data record.protected Leaf(AbstractBTree btree)
btree - A mutable B+Tree.protected Leaf(Leaf src)
src - The source node (must be immutable).AbstractNode.copyOnWrite()| Method Detail |
|---|
protected final int minKeys()
(branchingFactor + 1) << 1
minKeys in class AbstractNode<Leaf>protected final int maxKeys()
branchingFactor, which is the maximum #of keys for a
Leaf.
maxKeys in class AbstractNode<Leaf>public final ILeafData getDelegate()
AbstractNodeIAbstractNodeData object.
public final boolean isLeaf()
true.
isLeaf in interface IAbstractNodeDataisLeaf in class AbstractNode<Leaf>public final boolean isReadOnly()
Leaf will be
mutable when it is first created and is made immutable when it is
persisted. If there is a mutation operation, the backing
ILeafData is automatically converted into a mutable instance.
isReadOnly in interface IAbstractNodeDatapublic final boolean isCoded()
IAbstractNodeDatatrue iff this is a coded data structure.
isCoded in interface IAbstractNodeDatapublic final AbstractFixedByteArrayBuffer data()
IAbstractNodeData
data in interface IAbstractNodeDatadata in interface IDataRecordAccesspublic final boolean getDeleteMarker(int index)
ILeafDatatrue iff the entry at the specified index is marked
as deleted.
getDeleteMarker in interface ILeafDatapublic final int getKeyCount()
IAbstractNodeDatankeys+1
children. A leaf has nkeys keys and values. The maximum #of
keys for a node is one less than the branching factor of the B+Tree. The
maximum #of keys for a leaf is the branching factor of the B+Tree.
getKeyCount in interface IAbstractNodeDatapublic final IRaba getKeys()
IAbstractNodeData
getKeys in interface IAbstractNodeDatapublic final int getSpannedTupleCount()
IAbstractNodeData
getSpannedTupleCount in interface IAbstractNodeDataINodeData#getChildEntryCounts()public final int getValueCount()
ILeafData
getValueCount in interface ILeafDatapublic final IRaba getValues()
ILeafData
getValues in interface ILeafDataILeafData.hasDeleteMarkers(),
ILeafData.getDeleteMarker(int)public final long getVersionTimestamp(int index)
ILeafData
getVersionTimestamp in interface ILeafDatapublic final boolean hasDeleteMarkers()
ILeafDatatrue iff the leaf maintains delete markers.
hasDeleteMarkers in interface ILeafDatapublic final boolean hasVersionTimestamps()
ILeafDatatrue iff the leaf maintains version timestamps.
hasVersionTimestamps in interface IAbstractNodeDatahasVersionTimestamps in interface ILeafDatapublic final long getMinimumVersionTimestamp()
IAbstractNodeDataLong.MAX_VALUE since the initial value of the minimum
version timestamp is always the largest possible long integer.
getMinimumVersionTimestamp in interface IAbstractNodeDatapublic final long getMaximumVersionTimestamp()
IAbstractNodeDataLong.MIN_VALUE since the initial value of the
maximum version timestamp is always the smallest possible long integer.
getMaximumVersionTimestamp in interface IAbstractNodeDatapublic final boolean isDoubleLinked()
ILeafDatatrue if the leaf data record supports encoding of the
address of the previous and next leaf in the B+Tree order.
isDoubleLinked in interface ILeafDatapublic final long getPriorAddr()
ILeafData0L if it is
known that there is no previous leaf, and -1L if either: (a)
it is not known whether there is a previous leaf; or (b) it is known but
the address of that leaf is not known to the caller.
getPriorAddr in interface ILeafDatapublic final long getNextAddr()
ILeafData0L if it is known
that there is no next leaf, and -1L if either: (a) it is not
known whether there is a next leaf; or (b) it is known but the address of
that leaf is not known to the caller.
getNextAddr in interface ILeafDatapublic void delete()
IIdentityAccess
delete in interface IIdentityAccessdelete in class AbstractNode<Leaf>
public Tuple insert(byte[] searchKey,
byte[] newval,
boolean delete,
long timestamp,
Tuple tuple)
insert in class AbstractNode<Leaf>searchKey - The key (non-null).newval - The value (may be null).delete - true iff the entry is to marked as deleted
(delete markers must be supported for if this is true).timestamp - The timestamp associated with the version (the value is
ignored unless version metadata is being maintained).tuple - A tuple that may be used to obtain the data and metadata for
the pre-existing index entry overwritten by the insert
operation (optional).
null otherwise.
public Tuple lookup(byte[] searchKey,
Tuple tuple)
AbstractNode
lookup in class AbstractNode<Leaf>searchKey - The search key.tuple - A tuple that may be used to obtain the data and metadata for
the pre-existing index entry (required).
null otherwise.public int indexOf(byte[] key)
AbstractNode
indexOf in class AbstractNode<Leaf>key - The search key.
(-(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.public byte[] keyAt(int entryIndex)
AbstractNode
keyAt in class AbstractNode<Leaf>entryIndex - The index position of the entry (origin zero and relative to
this node or leaf).
public void valueAt(int entryIndex,
Tuple tuple)
AbstractNode
valueAt in class AbstractNode<Leaf>entryIndex - The index position of the entry (origin zero and relative to
this node or leaf).tuple - A tuple that may be used to obtain the data and metadata for
the pre-existing index entry (required).protected IAbstractNode split()
Split an over-capacity leaf (a leaf with maxKeys+1 keys),
creating a new rightSibling. The splitIndex (the index of the first key
to move to the rightSibling) is (maxKeys+1)/2. The key at
the splitIndex is also inserted as the new separatorKey into the parent.
All keys and values starting with splitIndex are moved to the new
rightSibling. If this leaf is the root of the tree (no parent), then a
new root Node is created without any keys and is made the parent
of this leaf. In any case, we then insert( separatorKey, rightSibling )
into the parent node, which may cause the parent node itself to split.
split in class AbstractNode<Leaf>
protected void redistributeKeys(AbstractNode sibling,
boolean isRightSibling)
redistributeKeys in class AbstractNode<Leaf>sibling - A direct sibling of this leaf (either the left or right
sibling). The sibling MUST be mutable.isRightSibling - True iff the sibling is the rightSibling of this node.
protected void merge(AbstractNode sibling,
boolean isRightSibling)
AbstractNode.join() if the parent node is now
deficient. While this changes the #of entries spanned by the current node
it does NOT effect the #of entries spanned by the parent. Likewise, while
the min/max tuple revision timestamp may change for this Leaf, it
WILL NOT change for its parent Node (since this operation does
not remove any tuples).
merge in class AbstractNode<Leaf>sibling - A direct sibling of this leaf (does NOT need to be mutable).
The sibling MUST have exactly the minimum #of keys.
FIXME maintain min/max version timestamps.isRightSibling - True iff the sibling is the rightSibling of this node.
protected void copyDown(int entryIndex,
int count)
entryIndex - The index of the first key and value to be copied.
public Tuple remove(byte[] key,
Tuple tuple)
AbstractNodeNote: It is an error to call this method if delete markers are in use.
remove in class AbstractNode<Leaf>key - The search key.tuple - A tuple that may be used to obtain the data and metadata for
the pre-existing index entry that was either removed by the
remove operation (optional).
null otherwise.public Iterator<AbstractNode> postOrderNodeIterator(boolean dirtyNodesOnly)
postOrderNodeIterator in class AbstractNode<Leaf>dirtyNodesOnly - When true, only dirty nodes and leaves will be visited
AbstractNodes.
public Iterator<AbstractNode> postOrderIterator(byte[] fromKey,
byte[] toKey)
postOrderIterator in class AbstractNode<Leaf>fromKey - The first key that will be visited (inclusive). When
null there is no lower bound.toKey - The first key that will NOT be visited (exclusive). When
null there is no upper bound.
AbstractNodes.public ITupleIterator entryIterator()
entryIterator in interface IAbstractNodeentryIterator in class AbstractNode<Leaf>
public boolean dump(org.apache.log4j.Level level,
PrintStream out,
int height,
boolean recursive)
AbstractNodePrintStream.
dump in class AbstractNode<Leaf>level - The logging level.out - Where to write the dump.height - The height of this node in the tree or -1 iff you need to
invoke this method on a node or leaf whose height in the tree
is not known.recursive - When true, the node will be dumped recursively using a
pre-order traversal.
public String toString()
ILeafData plus transient
information associated with the Leaf.
toString in class POpublic final void addLeafListener(Leaf.ILeafListener l)
Leaf.ILeafListener with this Leaf. Listeners are
automatically removed by the JVM shortly after they become only weakly
reachable.
l - The listener.
IllegalStateException - if the owning AbstractBTree is read-only.protected final void fireInvalidateLeafEvent()
Leaf.ILeafListener.invalidateLeaf() event to any registered
listeners.
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||