goldman.collection.ordered
Class BPlusTree<E>
java.lang.Object
goldman.collection.AbstractCollection<E>
goldman.collection.ordered.AbstractSearchTree<E>
goldman.collection.ordered.BTree<E>
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 classes/interfaces inherited from class goldman.collection.ordered.BTree |
BTree.Marker |
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.AbstractCollection |
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize |
Methods inherited from interface goldman.collection.Collection |
accept, add, addAll, checkRep, contains, ensureCapacity, getCapacity, getComparator, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize |
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 elementst
- the order of the B+-tree
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>