Package org.apache.jackrabbit.commons.flat

Class BTreeManager

  • All Implemented Interfaces:
    TreeManager
    public class BTreeManager
extends 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");