com.bigdata.btree
Class AbstractNode<T extends AbstractNode>

java.lang.Object
  com.bigdata.btree.PO
      com.bigdata.btree.AbstractNode<T>

All Implemented Interfaces:

IAbstractNodeData, IKeysData, IAbstractNode, IDirty, IIdentityAccess, IDataRecordAccess

Direct Known Subclasses:

Leaf, Node

public abstract class AbstractNode<T extends AbstractNode>
extends PO
implements IAbstractNode, IAbstractNodeData, IKeysData

Abstract node supporting incremental persistence and copy-on-write semantics.

Version:

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

Author:

Bryan Thompson

Field Summary

protected AbstractBTree	btree The BTree.
protected static boolean	INFO True iff the log level is INFO or less.
protected static org.apache.log4j.Logger	log Log for node and leaf operations.
protected Reference<Node>	parent The parent of this node.
protected int	referenceCount The #of times that this node is present on the HardReferenceQueue .
protected Reference<? extends AbstractNode<T>>	self A Reference to this Node.

Fields inherited from class com.bigdata.btree.PO

deleted, dirty, identity

Fields inherited from interface com.bigdata.btree.IIdentityAccess

NULL

Constructor Summary

protected	AbstractNode(AbstractBTree btree, boolean dirty) All constructors delegate to this constructor to set the btree and branching factor and to compute the minimum and maximum #of keys for the node.
protected	AbstractNode(AbstractNode<T> src) Copy constructor.

Method Summary

protected void	assertInvariants() Invariants: A node with nkeys + 1 children. A node must have between [m/2:m] children (alternatively, between [m/2-1:m-1] keys since nkeys + 1 == nchildren for a node). A leaf has no children and has between [m/2:m] key-value pairs (the same as the #of children on a node). The root leaf may be deficient (may have less than m/2 key-value pairs). where m is the branching factor and a node is understood to be a non-leaf node in the tree.
protected void	assertKeysMonotonic() Verify keys are monotonically increasing.
protected void	copyKey(int dstpos, IRaba srckeys, int srcpos) Copy a key from the source node into this node.
protected AbstractNode<?>	copyOnWrite() Return this leaf iff it is dirty (aka mutable) and otherwise return a copy of this leaf.
protected AbstractNode<T>	copyOnWrite(long triggeredByChildId) Return this node or leaf iff it is dirty (aka mutable) and otherwise return a copy of this node or leaf.
void	delete() Deletes the persistence capable object.
boolean	dump(org.apache.log4j.Level level, PrintStream out) Dump the data onto the PrintStream.
abstract boolean	dump(org.apache.log4j.Level level, PrintStream out, int height, boolean recursive) Dump the data onto the PrintStream.
boolean	dump(PrintStream out) Dump the data onto the PrintStream (non-recursive).
ITupleIterator	entryIterator() Traversal of index values in key order.
int	getBranchingFactor()
Node	getParent() The parent iff the node has been added as the child of another node and the parent reference has not been cleared.
abstract long	indexOf(byte[] searchKey) Recursive search locates the appropriate leaf and returns the index position of the entry.
abstract Tuple	insert(byte[] key, byte[] val, boolean delete, long timestamp, Tuple tuple) Insert or update a value.
abstract boolean	isLeaf() True iff this is a leaf node.
protected boolean	isLeftMostNode() Return true if this node is the left-most node at its level within the tree.
protected boolean	isRightMostNode() Return true if this node is the right-most node at its level within the tree.
protected void	join() Join this node (must be deficient) with either its left or right sibling.
protected static String	keyAsString(byte[] key) Return a human readable representation of the key.
abstract byte[]	keyAt(long index) Recursive search locates the entry at the specified index position in the btree and returns the key for that entry.
abstract Tuple	lookup(byte[] searchKey, Tuple tuple) Lookup a key.
protected abstract int	maxKeys() The maximum #of keys.
protected abstract void	merge(AbstractNode sibling, boolean isRightSibling) Merge the sibling into this node.
protected abstract int	minKeys() The minimum #of keys.
abstract Iterator<AbstractNode>	postOrderIterator(byte[] fromKey, byte[] toKey) Post-order traversal of nodes and leaves in the tree with a key range constraint.
Iterator<AbstractNode>	postOrderNodeIterator() Post-order traveral of nodes and leaves in the tree.
Iterator<AbstractNode>	postOrderNodeIterator(boolean dirtyNodesOnly) Post-order traversal of nodes and leaves in the tree.
abstract Iterator<AbstractNode>	postOrderNodeIterator(boolean dirtyNodesOnly, boolean nodesOnly) Post-order traversal of nodes and leaves in the tree.
ITupleIterator	rangeIterator(byte[] fromKey, byte[] toKey, int flags) Return an iterator that visits the entries in a half-open key range but filters the values.
protected abstract void	redistributeKeys(AbstractNode sibling, boolean isRightSibling) Redistribute the one key from the sibling into this node.
abstract Tuple	remove(byte[] searchKey, Tuple tuple) Recursive search locates the appropriate leaf and removes the entry for the key.
protected abstract IAbstractNode	split() Split a node or leaf that is over capacity (by one).
abstract void	valueAt(long index, 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.PO

getIdentity, indent, isDeleted, isDirty, isPersistent, setDirty, setIdentity, toShortString, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.bigdata.btree.data.IAbstractNodeData

data, getMaximumVersionTimestamp, getMinimumVersionTimestamp, hasVersionTimestamps, isCoded, isReadOnly

Methods inherited from interface com.bigdata.btree.data.IKeysData

getKeyCount, getKeys

Field Detail

log

protected static final org.apache.log4j.Logger log

Log for node and leaf operations.

info

A high level trace of insert, split, joint, and remove operations. You MUST test on Category.isInfoEnabled() before generating log messages at this level to avoid string concatenation operations would otherwise kill performance.

A low level trace including a lot of dumps of leaf and node state. * You MUST test on Category.isDebugEnabled() before generating log messages at this level to avoid string concatenation operations would otherwise kill performance.

See Also:

AbstractBTree.log, AbstractBTree.dumpLog

INFO

protected static final boolean INFO

True iff the log level is INFO or less.

btree

protected final transient AbstractBTree btree

The BTree. Note: This field MUST be patched when the node is read from the store. This requires a custom method to read the node with the btree reference on hand so that we can set this field.

parent

protected transient Reference<Node> parent

The parent of this node. This is null for the root node. The parent is required in order to set the persistent identity of a newly persisted child node on its parent. The reference to the parent will remain strongly reachable as long as the parent is either a root (held by the BTree) or a dirty child (held by the Node). The parent reference is set when a node is attached as the child of another node.

Note: When a node is cloned by copyOnWrite() the parent references for its clean children are set to the new copy of the node. This is referred to in several places as "stealing" the children since they are no longer linked back to their old parents via their parent reference.

self

protected final transient Reference<? extends AbstractNode<T extends AbstractNode>> self

A Reference to this Node. This is created when the node is created and is reused by a children of the node as the Reference to their parent. This results in few Reference objects in use by the B+Tree since it effectively provides a canonical Reference object for any given Node.

referenceCount

protected transient int referenceCount

The #of times that this node is present on the HardReferenceQueue . This value is incremented each time the node is added to the queue and is decremented each time the node is evicted from the queue. On eviction, if the counter is zero(0) after it is decremented then the node is written on the store. This mechanism is critical because it prevents a node entering the queue from forcing IO for the same node in the edge case where the node is also on the tail on the queue. Since the counter is incremented before it is added to the queue, it is guaranteed to be non-zero when the node forces its own eviction from the tail of the queue. Preventing this edge case is important since the node can otherwise become immutable at the very moment that it is touched to indicate that we are going to update its state, e.g., during an insert, split, or remove operation. This mechanism also helps to defer IOs since IO can not occur until the last reference to the node is evicted from the queue.

Note that only mutable BTrees may have dirty nodes and the BTree is NOT thread-safe for writers so we do not need to use synchronization or an AtomicInteger for the referenceCount field.

Constructor Detail

AbstractNode

protected AbstractNode(AbstractBTree btree,
                       boolean dirty)

All constructors delegate to this constructor to set the btree and branching factor and to compute the minimum and maximum #of keys for the node. This isolates the logic required for computing the minimum and maximum capacity and encapsulates it as final data fields rather than permitting that logic to be replicated throughout the code with the corresponding difficulty in ensuring that the logic is correct throughout.

Parameters:

btree - The btree to which the node belongs.

branchingFactor - The branching factor for the node. By passing the branching factor rather than using the branching factor declared on the btree we are able to support different branching factors at different levels of the tree.

dirty - Used to set the PO.dirty state. All nodes and leaves created by non-deserialization constructors begin their life cycle as dirty := true All nodes or leaves de-serialized from the backing store begin their life cycle as clean (dirty := false). This we read nodes and leaves into immutable objects, those objects will remain clean. Eventually a copy-on-write will create a mutable node or leaf from the immutable one and that node or leaf will be dirty.

AbstractNode

protected AbstractNode(AbstractNode<T> src)

Copy constructor.

Note: The copy constructor steals the state of the source node, creating a new node with the same state but a distinct (and not yet assigned) address on the backing store. If the source node has immutable data for some aspect of its state, then a mutable copy of that data is made.

Note: The caller MUST delete() the source node after invoking this copy constructor. If the backing store supports the operation, the source node will be reclaimed as free space at the next commit.

The source node must be deleted since it is no longer accessible and various aspects of its state have been stolen by the copy constructor. If the btree is committed then both the delete of the source node and the new tree structure will be made restart-safe atomically and all is well. If the operation is aborted then both changes will be undone and all is well. In no case can we access the source node after this operation unless all changes have been aborted, in which case it will simply be re-read from the backing store.

Parameters:

src - The source node.

Method Detail

minKeys

protected abstract int minKeys()

The minimum #of keys. For a Node, the minimum #of children is minKeys + 1. For a Leaf, the minimum #of values is minKeys.

maxKeys

protected abstract int maxKeys()

The maximum #of keys. This is branchingFactor - 1 for a Node and branchingFactor for a Leaf. For a Node, the maximum #of children is maxKeys + 1. For a Leaf, the maximum #of values is maxKeys.

delete

public void delete()

Description copied from interface: IIdentityAccess

Deletes the persistence capable object. Both transient and persistent objects may be logically deleted. If the object is persistent then its space on the store is deallocated.

Specified by:

delete in interface IIdentityAccess

getParent

public final Node getParent()

The parent iff the node has been added as the child of another node and the parent reference has not been cleared.

Returns:

The parent or null if (a) this is the root node or (b) the WeakReference to the parent has been cleared.

copyOnWrite

protected AbstractNode<?> copyOnWrite()

Return this leaf iff it is dirty (aka mutable) and otherwise return a copy of this leaf. If a copy is made of the leaf, then a copy will also be made of each immutable parent up to the first mutable parent or the root of the tree, which ever comes first. If the root is copied, then the new root will be set on the BTree. This method must MUST be invoked any time an mutative operation is requested for the leaf.

Note: You can not modify a node that has been written onto the store. Instead, you have to clone the node causing it and all nodes up to the root to be dirty and transient. This method handles that cloning process, but the caller MUST test whether or not the node was copied by this method, MUST delegate the mutation operation to the copy iff a copy was made, and MUST result in an awareness in the caller that the copy exists and needs to be used in place of the immutable version of the node.

Returns:

Either this leaf or a copy of this leaf.

copyOnWrite

protected AbstractNode<T> copyOnWrite(long triggeredByChildId)

Return this node or leaf iff it is dirty (aka mutable) and otherwise return a copy of this node or leaf. If a copy is made of the node, then a copy will also be made of each immutable parent up to the first mutable parent or the root of the tree, which ever comes first. If the root is copied, then the new root will be set on the BTree. This method must MUST be invoked any time an mutative operation is requested for the leaf.

Note: You can not modify a node that has been written onto the store. Instead, you have to clone the node causing it and all nodes up to the root to be dirty and transient. This method handles that cloning process, but the caller MUST test whether or not the node was copied by this method, MUST delegate the mutation operation to the copy iff a copy was made, and MUST be aware that the copy exists and needs to be used in place of the immutable version of the node.

Parameters:

triggeredByChildId - The persistent identity of child that triggered this event if any.

Returns:

Either this node or a copy of this node.

postOrderNodeIterator

public final Iterator<AbstractNode> postOrderNodeIterator()

Description copied from interface: IAbstractNode

Post-order traveral of nodes and leaves in the tree. For any given node, its children are always visited before the node itself (hence the node occurs in the post-order position in the traveral). The iterator is NOT safe for concurrent modification.

Specified by:

postOrderNodeIterator in interface IAbstractNode

Returns:

Iterator visiting IAbstractNodes.

postOrderNodeIterator

public final Iterator<AbstractNode> postOrderNodeIterator(boolean dirtyNodesOnly)

Post-order traversal of nodes and leaves in the tree. For any given node, its children are always visited before the node itself (hence the node occurs in the post-order position in the traversal). The iterator is NOT safe for concurrent modification.

Parameters:

dirtyNodesOnly - When true, only dirty nodes and leaves will be visited

Returns:

Iterator visiting AbstractNodes.

postOrderNodeIterator

public abstract Iterator<AbstractNode> postOrderNodeIterator(boolean dirtyNodesOnly,
                                                             boolean nodesOnly)

Post-order traversal of nodes and leaves in the tree. For any given node, its children are always visited before the node itself (hence the node occurs in the post-order position in the traversal). The iterator is NOT safe for concurrent modification.

Parameters:

dirtyNodesOnly - When true, only dirty nodes and leaves will be visited

nodesOnly - When true, the leaves will not be visited.

Returns:

Iterator visiting AbstractNodes.

entryIterator

public ITupleIterator entryIterator()

Description copied from interface: IAbstractNode

Traversal of index values in key order.

Specified by:

entryIterator in interface IAbstractNode

rangeIterator

public ITupleIterator rangeIterator(byte[] fromKey,
                                    byte[] toKey,
                                    int flags)

Return an iterator that visits the entries in a half-open key range but filters the values.

Parameters:

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.

flags - indicating whether the keys and/or values will be materialized.

postOrderIterator

public abstract Iterator<AbstractNode> postOrderIterator(byte[] fromKey,
                                                         byte[] toKey)

Post-order traversal of nodes and leaves in the tree with a key range constraint. For any given node, its children are always visited before the node itself (hence the node occurs in the post-order position in the traversal). The iterator is NOT safe for concurrent modification.

Parameters:

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.

Returns:

Iterator visiting AbstractNodes.

assertInvariants

protected final void assertInvariants()

Invariants:

• A node with nkeys + 1 children.
• A node must have between [m/2:m] children (alternatively, between [m/2-1:m-1] keys since nkeys + 1 == nchildren for a node).
• A leaf has no children and has between [m/2:m] key-value pairs (the same as the #of children on a node).
• The root leaf may be deficient (may have less than m/2 key-value pairs).

where m is the branching factor and a node is understood to be a non-leaf node in the tree.

In addition, all leaves are at the same level (not tested by this assertion).

assertKeysMonotonic

protected final void assertKeysMonotonic()

Verify keys are monotonically increasing.

keyAsString

protected static final String keyAsString(byte[] key)

Return a human readable representation of the key. The key is a variable length unsigned byte[]. The returned string is a representation of that unsigned byte[]. This is use a wrapper for Object.toString().

Parameters:

key - The key.

copyKey

protected final void copyKey(int dstpos,
                             IRaba srckeys,
                             int srcpos)

Copy a key from the source node into this node. This method does not modify the source node. This method does not update the #of keys in this node.

Note: Whenever possible the key reference is copied rather than copying the data. This optimization is valid since we never modify the contents of a key.

Parameters:

dstpos - The index position to which the key will be copied on this node.

srckeys - The source keys.

srcpos - The index position from which the key will be copied.

isLeaf

public abstract boolean isLeaf()

Description copied from interface: IAbstractNodeData

True iff this is a leaf node.

Specified by:

isLeaf in interface IAbstractNodeData

getBranchingFactor

public final int getBranchingFactor()

split

protected abstract IAbstractNode split()

Split a node or leaf that is over capacity (by one).

Returns:

The high node (or leaf) created by the split.

join

protected void join()

Join this node (must be deficient) with either its left or right sibling. A join will either cause a single key and value (child) to be redistributed from a sibling to this leaf (node) or it will cause a sibling leaf (node) to be merged into this leaf (node). Both situations also cause the separator key in the parent to be adjusted.

Join is invoked when a leaf has become deficient (too few keys/values). This method is never invoked for the root leaf therefore the parent of this leaf must be defined. Further, since the minimum #of children is two (2) for the smallest branching factor three (3), there is always a sibling to consider.

Join first considers the immediate siblings. if either is materialized and has more than the minimum #of values, then it redistributes one key and value (child) from the sibling into this leaf (node). If either sibling is materialized and has only the minimum #of values, then it merges this leaf (node) with that sibling.

If no materialized immediate sibling meets these criteria, then first materialize and test the right sibling. if the right sibling does not meet these criteria, then materialize and test the left sibling.

Note that (a) we prefer to merge a materialized sibling with this leaf to materializing a sibling; and (b) merging siblings is the only way that a separator key is removed from a parent. If the parent becomes deficient through merging then join is invoked on the parent as well. Note that join is never invoked on the root node (or leaf) since it by definition has no siblings.

Note that we must invoked copy-on-write before modifying a sibling. However, the parent of the leaf MUST already be mutable (aka dirty) since that is a precondition for removing a key from the leaf. This means that copy-on-write will not force the parent to be cloned.

isLeftMostNode

protected boolean isLeftMostNode()

Return true if this node is the left-most node at its level within the tree.

Returns:

true iff the child is the left-most node at its level within the tree.

isRightMostNode

protected boolean isRightMostNode()

Return true if this node is the right-most node at its level within the tree.

Returns:

true iff the child is the right-most node at its level within the tree.

redistributeKeys

protected abstract void redistributeKeys(AbstractNode sibling,
                                         boolean isRightSibling)

Redistribute the one key from the sibling into this node.

Parameters:

sibling - The sibling.

isRightSibling - True iff the sibling is the rightSibling of this node.

TODO:

redistribution should proceed until the node and the sibling have an equal #of keys (or perhaps more exactly until the node would have more keys than the sibling if another key was redistributed into the node from the sibling). this takes advantage of the fact that the node and the sibling are known to be in memory to bring them to the point where they are equally full. along the same lines when both siblings are resident we could actually redistribute keys from both siblings into the node until the keys were equally distributed among the node and its siblings., a b*-tree variant simply uses redistribution of keys among siblings during insert to defer a split until the node and its siblings are all full.

merge

protected abstract void merge(AbstractNode sibling,
                              boolean isRightSibling)

Merge the sibling into this node.

Parameters:

sibling - The sibling.

isRightSibling - True iff the sibling is the rightSibling of this node.

insert

public abstract Tuple insert(byte[] key,
                             byte[] val,
                             boolean delete,
                             long timestamp,
                             Tuple tuple)

Insert or update a value.

Parameters:

key - The key (non-null).

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

Returns:

The tuple iff there was a pre-existing entry under that key and null otherwise.

remove

public abstract Tuple remove(byte[] searchKey,
                             Tuple tuple)

Recursive search locates the appropriate leaf and removes the entry for the key.

Note: It is an error to call this method if delete markers are in use.

Parameters:

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

Returns:

The tuple iff there was a pre-existing entry under that key and null otherwise.

lookup

public abstract Tuple lookup(byte[] searchKey,
                             Tuple tuple)

Lookup a key.

Parameters:

searchKey - The search key.

tuple - A tuple that may be used to obtain the data and metadata for the pre-existing index entry (required).

Returns:

The tuple iff there was a pre-existing entry under that key and null otherwise.

indexOf

public abstract long indexOf(byte[] searchKey)

Recursive search locates the appropriate leaf and returns the index position of the entry.

Parameters:

searchKey - The search 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.

keyAt

public abstract byte[] keyAt(long index)

Recursive search locates the entry at the specified index position in the btree and returns the key for that entry.

Parameters:

index - The index position of the entry (origin zero and relative to this node or leaf).

Returns:

The key at that index position.

Throws:

IndexOutOfBoundsException - if index is less than zero.

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

valueAt

public abstract void valueAt(long index,
                             Tuple tuple)

Recursive search locates the entry at the specified index position in the btree and returns the value for that entry.

Parameters:

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

Throws:

IndexOutOfBoundsException - if index is less than zero.

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

dump

public boolean dump(PrintStream out)

Dump the data onto the PrintStream (non-recursive).

Parameters:

out - Where to write the dump.

Returns:

True unless an inconsistency was detected.

dump

public boolean dump(org.apache.log4j.Level level,
                    PrintStream out)

Dump the data onto the PrintStream.

Parameters:

level - The logging level.

out - Where to write the dump.

Returns:

True unless an inconsistency was detected.

dump

public abstract boolean dump(org.apache.log4j.Level level,
                             PrintStream out,
                             int height,
                             boolean recursive)

Dump the data onto the PrintStream.

Parameters:

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.

Returns:

True unless an inconsistency was detected.