org.apache.jackrabbit.commons.flat

Class BTreeManager

java.lang.Object

org.apache.jackrabbit.commons.flat.BTreeManager

All Implemented Interfaces:

TreeManager

public class BTreeManager
extends java.lang.Object
implements TreeManager

This TreeManager implementation provides B+-tree like behavior. That is items of a sequence (i.e. NodeSequence or PropertySequence) are mapped to a sub-tree in JCR in a way such that only leave nodes carry actual values, the sub-tree is always balanced and ordered. This implementation does in contrast to a full B+-tree implementation not join nodes after deletions. This does not affect the order of items and also leaves the tree balanced wrt. its depths. It might however result in a sparse tree. That is, the tree might get unbalanced wrt. its weights.

The nodes in the JCR sub tree are arranged such that any node named x only contains child nodes with names greater or equal to x. The implementation keeps the child nodes in the sub tree ordered if the respective node type supports ordering of child nodes. Ordering is always wrt. to a Comparator on the respective keys. For lexical order this arrangement corresponds to how words are arranged in a multi volume encyclopedia.

Example usage:

 // Create a new TreeManager instance rooted at node. Splitting of nodes takes place
 // when the number of children of a node exceeds 40 and is done such that each new
 // node has at least 40 child nodes. The keys are ordered according to the natural
 // order of java.lang.String.
 TreeManager treeManager = new BTreeManager(node, 20, 40, Rank.<String>comparableComparator(), true);

 // Create a new NodeSequence with that tree manager
 NodeSequence nodes = ItemSequence.createNodeSequence(treeManager);

 // Add nodes with key "jcr" and "day"
 nodes.addNode("jcr", NodeType.NT_UNSTRUCTURED);
 nodes.addNode("day", NodeType.NT_UNSTRUCTURED);

 // Iterate over the node in the sequence.
 // Prints "day jcr "
 for (Node n : nodes) {
     System.out.print(n.getName() + " ");
 }

 // Retrieve node with key "jcr"
 Node n = nodes.getItem("jcr");

 // Remove node with key "day"
 nodes.removeNode("day");
 

Constructor Summary

Constructors

Constructor and Description
BTreeManager(Node root, int minChildren, int maxChildren, java.util.Comparator<java.lang.String> order, boolean autoSave) Create a new BTreeManager rooted at Node root.

Method Summary

Modifier and Type	Method and Description
boolean	getAutoSave() Whether to automatically save changes of the current session occurring from adding/removing nodes and properties.
java.util.Set<java.lang.String>	getIgnoredProperties() Properties to ignore.
java.util.Comparator<java.lang.String>	getOrder() Comparator used for establishing the order of the keys in the sequence.
Node	getRoot()
boolean	isLeaf(Node node) Returns !node.hasNodes()
boolean	isRoot(Node node) Determined whether the given node is the root node of the JCR sub-tree.
void	join(ItemSequence itemSequence, Node node, Node cause) This implementation does not actually join any nodes.
void	join(ItemSequence itemSequence, Node node, Property cause) This implementation does not actually join any nodes.
void	split(ItemSequence itemSequence, Node node, Node cause) This implementations splits node when its number of child nodes exceeds the maximum number specified in the constructor.
void	split(ItemSequence itemSequence, Node node, Property cause) This implementations splits node when its number of properties exceeds the maximum number specified in the constructor.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BTreeManager

public BTreeManager(Node root,
                    int minChildren,
                    int maxChildren,
                    java.util.Comparator<java.lang.String> order,
                    boolean autoSave)
             throws RepositoryException

Create a new BTreeManager rooted at Node root.

Parameters:

root - the root of the JCR sub-tree where the items of the sequence are stored.

minChildren - minimal number of children for a node after splitting.

maxChildren - maximal number of children for a node after which splitting occurs.

order - order according to which the keys are stored

autoSave - determines whether the current session is saved after add/delete operations.

Throws:

RepositoryException

Method Detail

getIgnoredProperties

public java.util.Set<java.lang.String> getIgnoredProperties()

Properties to ignore. The default set contains JcrConstants.JCR_PRIMARYTYPE and JcrConstants.JCR_MIXINTYPES.

Specified by:

getIgnoredProperties in interface TreeManager

Returns:

split

public void split(ItemSequence itemSequence,
                  Node node,
                  Node cause)
           throws RepositoryException

This implementations splits node when its number of child nodes exceeds the maximum number specified in the constructor. Splitting is done such that after the split each of the new child nodes contains at least as many nodes as specified in the constructor.

Specified by:

split in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the new node cause has been inserted.

node - the parent node of the newly inserted node

cause - the newly inserted node or null if not known.

Throws:

RepositoryException

See Also:

org.apache.jackrabbit.commons.flat.TreeManager#split(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Node)

split

public void split(ItemSequence itemSequence,
                  Node node,
                  Property cause)
           throws RepositoryException

This implementations splits node when its number of properties exceeds the maximum number specified in the constructor. Splitting is done such that after the split each of the new child nodes contains at least as many nodes as specified in the constructor.

Specified by:

split in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the new node cause has been inserted.

node - the parent node of the newly inserted node

cause - the newly inserted node or null if not known.

Throws:

RepositoryException

See Also:

org.apache.jackrabbit.commons.flat.TreeManager#split(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Property)

join

public void join(ItemSequence itemSequence,
                 Node node,
                 Node cause)
          throws RepositoryException

This implementation does not actually join any nodes. It does however delete node if getNodes(Node) returns an empty iterator. It does further recursively delete any parent of node which does not have any child node.

Specified by:

join in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the node cause has been deleted from.

node - the parent node from which cause has been deleted.

cause - the deleted node or null if not known. Note: cause might be stale.

Throws:

RepositoryException

See Also:

org.apache.jackrabbit.commons.flat.TreeManager#join(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Node)

join

public void join(ItemSequence itemSequence,
                 Node node,
                 Property cause)
          throws RepositoryException

This implementation does not actually join any nodes. It does however delete node if getProperties(Node) returns an empty iterator. It does further recursively delete any parent of node which does not have any child node.

Specified by:

join in interface TreeManager

Parameters:

itemSequence - the ItemSequence where the node cause has been deleted from.

node - the parent node from which cause has been deleted.

cause - the deleted node or null if not known. Note: cause might be stale.

Throws:

RepositoryException

See Also:

org.apache.jackrabbit.commons.flat.TreeManager#join(org.apache.jackrabbit.commons.flat.ItemSequence, javax.jcr.Node, javax.jcr.Property)

getRoot

public Node getRoot()

Specified by:

getRoot in interface TreeManager

Returns:

the root node of the JCR sub-tree where the items of the sequence are be mapped to.

isRoot

public boolean isRoot(Node node)
               throws RepositoryException

Description copied from interface: TreeManager

Determined whether the given node is the root node of the JCR sub-tree.

Specified by:

isRoot in interface TreeManager

Parameters:

node - Node to test for root

Returns:

getRoot().isSame(node).

Throws:

RepositoryException

isLeaf

public boolean isLeaf(Node node)
               throws RepositoryException

Returns !node.hasNodes()

Specified by:

isLeaf in interface TreeManager

Parameters:

node - Node to test for leaf

Returns:

true if node is a leaf node, false otherwise.

Throws:

RepositoryException

See Also:

org.apache.jackrabbit.commons.flat.TreeManager#isLeaf(javax.jcr.Node)

getOrder

public java.util.Comparator<java.lang.String> getOrder()

Description copied from interface: TreeManager

Comparator used for establishing the order of the keys in the sequence.

Specified by:

getOrder in interface TreeManager

Returns:

a Comparator<String> instance

getAutoSave

public boolean getAutoSave()

Description copied from interface: TreeManager

Whether to automatically save changes of the current session occurring from adding/removing nodes and properties.

Specified by:

getAutoSave in interface TreeManager

Returns:

true if changes should be automatically saved, false otherwiese.