goldman.collection.ordered
Class BPlusTree<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.AbstractSearchTree<E>
          extended by goldman.collection.ordered.BTree<E>
              extended by goldman.collection.ordered.BPlusTree<E>
All Implemented Interfaces:
Collection<E>, OrderedCollection<E>, Iterable<E>

public class BPlusTree<E>
extends BTree<E>

The B+-tree is variation of a B-tree in which the internal nodes are used only for navigation. The leaves (from left to right) form a sorted list of all elements in the ordered collection, and contain a pointer from each leaf to its successor to enable fast navigation within the sorted order. The B+-tree is also designed for collections so large that secondary storage is required. It aims to minimize the number of disk access required to both search for elements and find the set of elements that fall in a desired range of values. A B+-tree also supports efficient bulk loading which is important for real-time applications when a large number of insertions must be performed. If each element inserted is larger than all elements in the collection, then it can be inserted at the end of the leaf list and the rest of the structure can be built later. A B+-tree uses more space than a B-tree since the elements held in the internal nodes are duplicated in the leaves.


Nested Class Summary
 class BPlusTree.LeafNode
           
 
Nested classes/interfaces inherited from class goldman.collection.ordered.BTree
BTree.Marker
 
Nested classes/interfaces inherited from class goldman.collection.ordered.AbstractSearchTree
AbstractSearchTree.TreeNode
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
 
Fields inherited from class goldman.collection.ordered.AbstractSearchTree
root
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, NOT_FOUND, size, version
 
Constructor Summary
BPlusTree()
           
BPlusTree(Comparator<? super E> comp, int t)
           
BPlusTree(int t)
           
 
Method Summary
 void clear()
          Removes all elements from the collection
protected  void createRoot()
          Creates and initializes a new empty root node
protected  goldman.collection.ordered.BTree.BTreeNode find(E target)
          If there is no equivalent element the collection, then find returns the frontier node where the target would be inserted with the parent field set to the node that preceded it on the search path.
protected  void traverseForVisitor(Visitor<? super E> v)
          Traverses the collection applying v to each element
protected  void writeElements(StringBuilder sb)
          Appends to the string buffer a comma-separated string representation for the elements in the collection, in the iteration order.
 
Methods inherited from class goldman.collection.ordered.BTree
getLastNodeSearchIndex, getLocator, insert, iterator, iteratorAtEnd, predecessor, remove, successor
 
Methods inherited from class goldman.collection.ordered.AbstractSearchTree
add, contains, get, getEquivalentElement, max, min, remove
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.ordered.OrderedCollection
get, getEquivalentElement, max, min
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, contains, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize
 

Constructor Detail

BPlusTree

public BPlusTree()

BPlusTree

public BPlusTree(int t)
Parameters:
t - the order for the B+-tree

BPlusTree

public BPlusTree(Comparator<? super E> comp,
                 int t)
Parameters:
comp - the function used to compare two elements
t - the order of the B+-tree
Method Detail

createRoot

protected void createRoot()
Creates and initializes a new empty root node

Overrides:
createRoot in class BTree<E>

find

protected goldman.collection.ordered.BTree.BTreeNode find(E target)
If there is no equivalent element the collection, then find returns the frontier node where the target would be inserted with the parent field set to the node that preceded it on the search path. This method sets the global instance variable curIndex to hold the position for an occurrence of the target, if any, or otherwise the position where it would be inserted in the node

Overrides:
find in class BTree<E>
Parameters:
target - the target element
Returns:
a reference to the leaf node where the search ends (which would be FRONTIER when there is no equivalent element in the collection

traverseForVisitor

protected void traverseForVisitor(Visitor<? super E> v)
                           throws Exception
Traverses the collection applying v to each element

Overrides:
traverseForVisitor in class AbstractSearchTree<E>
Parameters:
v - a visitor
Throws:
Exception

writeElements

protected void writeElements(StringBuilder sb)
Description copied from class: AbstractSearchTree
Appends to the string buffer a comma-separated string representation for the elements in the collection, in the iteration order.

Overrides:
writeElements in class AbstractSearchTree<E>
Parameters:
sb - the string builder to fill with a comma-separated string of the elements in the collection in sorted order

clear

public void clear()
Removes all elements from the collection

Specified by:
clear in interface Collection<E>
Overrides:
clear in class BTree<E>