public class Leaf extends AbstractNode<Leaf> implements ILeafData, IRawRecordAccess
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.
| Modifier and Type | Class and Description |
|---|---|
static interface |
Leaf.ILeafListener
An interface that may be used to register for and receive events when the
state of a
Leaf is changed. |
btree, DEBUG, log, parent, referenceCount, selfNULL| Modifier | Constructor and Description |
|---|---|
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.
|
| Modifier and Type | Method and Description |
|---|---|
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. |
long |
getRawRecord(int index)
Return the address of the raw record on the backing store of the value
stored in the tuple having the given index -or-
IAddressManager.NULL if
the value is the actual byte[] value associated with the key
in the leaf. |
byte[] |
getValue(int index)
Convenience method returns the byte[] for the given index in the 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 |
hasRawRecords()
Return
true iff the leaf promotes large byte[]
values to raw records on the backing store. |
boolean |
hasVersionTimestamps()
Return
true iff the leaf maintains version timestamps. |
long |
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,
boolean putIfAbsent,
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(long 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,
boolean nodesOnly)
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 boolean |
rangeCheck(int index)
Used for methods which have an index into the leaf.
|
protected boolean |
rangeCheck2(long index)
Used for the
ILinearList methods. |
ByteBuffer |
readRawRecord(long addr)
Read the raw record from the backing store.
|
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()
|
void |
valueAt(long entryIndex,
Tuple tuple)
Recursive search locates the entry at the specified index position in the
btree and returns the value for that entry.
|
assertInvariants, assertKeysMonotonic, copyKey, copyOnWrite, copyOnWrite, dump, dump, getBranchingFactor, getParent, isLeftMostNode, isRightMostNode, join, keyAsString, postOrderNodeIterator, postOrderNodeIterator, rangeIteratorgetIdentity, indent, isDeleted, isDirty, isPersistent, setDirty, setIdentity, toShortStringprotected 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()protected final int minKeys()
(branchingFactor + 1) << 1
Note: the root may have fewer keys.
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()
IAbstractNodeDatadata 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()
IKeysDatankeys+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. For a
hash bucket, this is the #of entries in the bucket.getKeyCount in interface IKeysDatapublic final IRaba getKeys()
IKeysDatapublic final int getValueCount()
ILeafDatagetValueCount in interface ILeafDatapublic final IRaba getValues()
ILeafData
Note: When the leaf maintains raw records you MUST check whether or not
the value was written onto a raw record before interpreting the data
returned by IRaba.get(int). If the length of the value exceeded
the configured maximum record length for the index, then the value was
written onto a raw record on the backing store and IRaba.get(int)
will return the encoded address of that record rather than its data.
getValues in interface ILeafDataILeafData.hasDeleteMarkers(),
ILeafData.getDeleteMarker(int)public byte[] getValue(int index)
leaf - The leaf.index - The index in the leaf.AbstractTuple#copy(int, Leaf)public final long getVersionTimestamp(int index)
ILeafDatagetVersionTimestamp in interface ILeafDatapublic final long getRawRecord(int index)
ILeafDataIAddressManager.NULL if
the value is the actual byte[] value associated with the key
in the leaf. When the value is the address of a raw record, the actual
byte[] value should be read from the backing store using the
decoded address.
Raw record addresses are created transparently when a large
byte[] is associated with a key in the leaf. They are
materialized transparently when the tuple associated with the leaf is
read. They are deleted when the tuple associated with the leaf is
deleted.
Note: Raw records are managed at the leaf, rather than the IRaba
level, because there is not always a backing store associated with an
IRaba object. This is similar to how deleted tuples are handled.
However, IRabaCoders are responsible for coding the
long address stored in the values raba.
Raw records are only used for large byte[] values. Highly specialized
IRabaCoders can avoid the potential for a conflict with their own
coding scheme by ensuring that the index either will not promote large
values to raw records or by refraining from inserting large values into
the index.
getRawRecord in interface ILeafDataIAddressManager.NULLpublic 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 hasRawRecords()
ILeafDatatrue iff the leaf promotes large byte[]
values to raw records on the backing store.hasRawRecords in interface ILeafDatapublic 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()
IIdentityAccessdelete in interface IIdentityAccessdelete in class AbstractNode<Leaf>public Tuple insert(byte[] searchKey, byte[] newval, boolean delete, boolean putIfAbsent, 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).putIfAbsent - When true, a pre-existing entry for the key will
NOT be replaced (unless it is a deleted tuple, which is the
same as if there was no entry under the key). This should ONLY
be true when the top-level method is putIfAbsent.
Historical code paths should specify false for an unconditional
mutation. See BLZG-1539.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)
AbstractNodelookup 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 long indexOf(byte[] key)
AbstractNodeindexOf 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(long entryIndex)
AbstractNodekeyAt in class AbstractNode<Leaf>entryIndex - The index position of the entry (origin zero and relative to
this node or leaf).public void valueAt(long entryIndex,
Tuple tuple)
AbstractNodevalueAt 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 final boolean rangeCheck2(long index)
throws IndexOutOfBoundsException
ILinearList methods.IndexOutOfBoundsExceptionprotected final boolean rangeCheck(int index)
throws IndexOutOfBoundsException
IndexOutOfBoundsExceptionprotected 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, boolean nodesOnly)
postOrderNodeIterator in class AbstractNode<Leaf>dirtyNodesOnly - When true, only dirty nodes and leaves will be visitednodesOnly - When true, the leaves will not 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 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.public final ByteBuffer readRawRecord(long addr)
IRawRecordAccessreadRawRecord in interface IRawRecordAccessaddr - The record address.Copyright © 2006–2019 SYSTAP, LLC DBA Blazegraph. All rights reserved.