BPlusTree

abstract class BPlusTree[K, +V] extends AnyRef

Provides for interaction (searching, insertion, update, deletion) with a B+ tree that can be stored anywhere (in memory, on disk). It is the implementation's responsability to create the empty B+ tree initially. An empty B+ tree consists of a single empty leaf node as the root. Also the first and last should refer to the root leaf node, and the lastlen variable should be 0. For on-disk implementations it should be possible to open an existing B+ tree or optionally create a new one.

A B+ tree is composed of nodes that are linked to one another using pointers. The exact way in which the nodes are layed out and stored is left to the implementation. Also, node pointers are left to the implementation through the abstract node type. There is a very important implementation requirement that comparing two nodes for equality return true when they point to the same node. All nodes have

a parent pointer
a next pointer to the right sibling
a prev pointer to the left sibling
an array of keys

There are two kinds nodes:

leaf nodes, containing an array of values each corresponding to it's associated key in the keys array.
internal nodes, containing an array of branch pointers. This array always has one element more than the number of keys.

K: the type of the keys contained in this map.
V: the type of the values associated with the keys.

Linear Supertypes

AnyRef, Any

Known Subclasses

FileBPlusTree, MemoryBPlusTree

Ordering

Alphabetic
By Inheritance

Inherited

BPlusTree
AnyRef
Any

Hide All
Show All

Visibility

Public
All

Instance Constructors

new BPlusTree()(implicit arg0: (K) ⇒ Ordered[K])
creates an object providing access to a B+ tree with a branching factor of order and possibly creating an empty tree.

Type Members

abstract type N
Abstract node type.
Abstract node type. For in-memory implementations this would probably be the actual node class and for on-disk it would likely be the file pointer where the node is stored.

Attributes
protected
Note
Comparing two nodes for equality is required to be true when they point to the same node.

Abstract Value Members

abstract def addBranch(node: N, branch: N): Unit
Adds a new branch to (internal) node.
Adds a new branch to (internal) node. branch is placed at an index equal to the length of node, given that the length of a node is the number of keys.

Attributes
protected
abstract def addKey(node: N, key: K): Unit
Adds a new key to node.
Adds a new key to node. The length of node will increase by one as a result. This method should be called before either addBranch or addValue since those methods use the current node length to determine placemenet.

Attributes
protected
abstract val first: N
First leaf node.
First leaf node. Implementations are required to set this as well as to create/update the in-storage copy of this if needed (only really applies to on-disk implementations) within the implementation's newRoot method. The methods in this class will take care of updating this variable, implementations only need to worry about the in-storage copy.

Attributes
protected
abstract def freeKey(node: N, index: Int): Unit
Free the storage previously allocated for the key at index in node.
Free the storage previously allocated for the key at index in node. For in-memory implementations, this method probably won't do anything.

Attributes
protected
abstract def freeNode(node: N): Unit
Free the storage previously allocated for node.
Free the storage previously allocated for node. For in-memory implementations, this method probably won't do anything.

Attributes
protected
abstract def freeValue(node: N, index: Int): Unit
Free the storage previously allocated for the value at index in node.
Free the storage previously allocated for the value at index in node. For in-memory implementations, this method probably won't do anything.

Attributes
protected
abstract def getBranch(node: N, index: Int): N
Returns a branch pointer from an internal node at a given index.
Returns a branch pointer from an internal node at a given index. There is always one more branch pointer than there are keys in an internal node so the highest index is equal to nodeLength( node ).

Attributes
protected
abstract def getBranches(node: N): Seq[N]
Returns the branches of node as a non-strict immutable sequence.
Returns the branches of node as a non-strict immutable sequence.

Attributes
protected
abstract def getKey(node: N, index: Int): K
Returns a key from a leaf node at a given index.
Returns a key from a leaf node at a given index.

Attributes
protected
abstract def getKeys(node: N): Seq[K]
Returns the keys of node as a non-strict immutable sequence.
Returns the keys of node as a non-strict immutable sequence.

Attributes
protected
abstract def getNext(node: N): N
Returns the next pointer of (leaf) node.
Returns the next pointer of (leaf) node.

Attributes
protected
abstract def getParent(node: N): N
Returns the parent pointer of node.
Returns the parent pointer of node.

Attributes
protected
abstract def getPrev(node: N): N
Returns the previous leaf node link pointer of (leaf) node.
Returns the previous leaf node link pointer of (leaf) node.

Attributes
protected
abstract def getValue(node: N, index: Int): V
Returns a value from a leaf node at a given index.
Returns a value from a leaf node at a given index.

Attributes
protected
abstract def getValues(node: N): Seq[V]
Returns the values of node as a non-strict immutable sequence.
Returns the values of node as a non-strict immutable sequence.

Attributes
protected
abstract def insertInternal(node: N, keyIndex: Int, key: K, branchIndex: Int, branch: N): Unit
Inserts key and branch into (internal) node at keyIndex and branchIndex, respectively.
Inserts key and branch into (internal) node at keyIndex and branchIndex, respectively.

Attributes
protected
abstract def insertLeaf[V1 >: V](node: N, index: Int, key: K, value: V1): Unit
Inserts key and value into (leaf) node at index.
Inserts key and value into (leaf) node at index.

Attributes
protected
abstract def isLeaf(node: N): Boolean
Returns true if node is a leaf node
Returns true if node is a leaf node

Attributes
protected
abstract val last: N
Last leaf node.
Last leaf node. Implementations are required to set this as well as to create/update the in-storage copy of this if needed (only really applies to on-disk implementations). The methods in this class will take care of updating this variable, implementations only need to worry about the in-storage copy.

Attributes
protected
abstract val lastlen: Int
Length of the last leaf node.
Length of the last leaf node. This just speeds up bulk loading (the load method). Implementations are required to set this.

Attributes
protected
abstract def moveInternal(src: N, begin: Int, end: Int, dst: N, index: Int): Unit
Moves key/branch pairs from node src beginning at index begin up to but not including index end to node dst at index.
Moves key/branch pairs from node src beginning at index begin up to but not including index end to node dst at index.

Attributes
protected
abstract def moveLeaf(src: N, begin: Int, end: Int, dst: N, index: Int): Unit
Moves key/value pairs from node src to node dst beginning at index begin and ending up to but not including index end.
Moves key/value pairs from node src to node dst beginning at index begin and ending up to but not including index end.

Attributes
protected
abstract def newInternal(parent: N): N
Creates a new internal node with parent as its parent pointer.
Creates a new internal node with parent as its parent pointer.

Attributes
protected
abstract def newLeaf(parent: N): N
Creates a new leaf node with parent as its parent pointer.
Creates a new leaf node with parent as its parent pointer.

Attributes
protected
abstract def newRoot(branch: N): N
Creates a new root (internal) node with branch as its leftmost branch pointer and null parent pointer.
Creates a new root (internal) node with branch as its leftmost branch pointer and null parent pointer. Implementations are require to update the in-storage copy of the root pointer if needed (only really applies to on-disk implementations).

Attributes
protected
abstract def nodeLength(node: N): Int
Returns the length (number of keys) of node.
Returns the length (number of keys) of node. For internal nodes, the number of branch pointers will one more than the length.

Attributes
protected
abstract def nul: N
Returns the null node pointer.
Returns the null node pointer. For in-memory implementations this will usually be a Scala null value. For on-disk it would make sense for this to be 0L.

Attributes
protected
abstract val order: Int
Order or branching factor of the tree.
Order or branching factor of the tree. The order is the maximum number of branches that an internal node can have. The maximum number of elements in a leaf node is order - 1.
abstract def removeInternal(node: N, keyIndex: Int, branchIndex: Int): Int
Removes the key and branch pair from internal node at keyIndex and branchIndex, respectively.
Removes the key and branch pair from internal node at keyIndex and branchIndex, respectively. This method is perhaps poorly named: it does not remove an internal node from the tree.
returns
length of node after removal

Attributes
protected
abstract def removeLeaf(node: N, index: Int): Int
Removes the key/value pair from leaf node at index.
Removes the key/value pair from leaf node at index. This method is perhaps poorly named: it does not remove a leaf node from the tree.
returns
length of node after removal

Attributes
protected
abstract val root: N
Root node.
Root node. Implementations are required to set this as well as to create/update the in-storage copy of this if needed (only really applies to on-disk implementations). The methods in this class will take care of updating this variable, implementations only need to worry about the in-storage copy.

Attributes
protected
abstract def setFirst(leaf: N): Unit
Sets the in-storage copy of the first leaf node pointer.
Sets the in-storage copy of the first leaf node pointer. This method is not responsable for setting the first variable.

Attributes
protected
abstract def setKey(node: N, index: Int, key: K): Unit
Sets the key at index of node to key.
Sets the key at index of node to key.

Attributes
protected
abstract def setLast(leaf: N): Unit
Sets the in-storage copy of the last leaf node pointer.
Sets the in-storage copy of the last leaf node pointer. This method is not responsable for setting the last variable nor the lastlen variable.

Attributes
protected
abstract def setNext(node: N, p: N): Unit
Sets the next pointer of (leaf) node to p.
Sets the next pointer of (leaf) node to p.

Attributes
protected
abstract def setParent(node: N, p: N): Unit
Sets the parent pointer of node to p.
Sets the parent pointer of node to p.

Attributes
protected
abstract def setPrev(node: N, p: N): Unit
Sets previous leaf node link pointer of (leaf) node to p.
Sets previous leaf node link pointer of (leaf) node to p.

Attributes
protected
abstract def setRoot(node: N): Unit
Sets the in-storage copy of the root node pointer.
Sets the in-storage copy of the root node pointer. This method is not responsable for setting the root variable.

Attributes
protected
abstract def setValue[V1 >: V](node: N, index: Int, v: V1): Unit
Sets the value at index of node to v.
Sets the value at index of node to v.

Attributes
protected

Concrete Value Members

final def !=(arg0: Any): Boolean

Definition Classes
AnyRef → Any
final def ##(): Int

Definition Classes
AnyRef → Any
final def ==(arg0: Any): Boolean

Definition Classes
AnyRef → Any
final def asInstanceOf[T0]: T0

Definition Classes
Any
def binarySearch(node: N, target: K): Int
Performs a binary search for key target within node (tail recursively).
Performs a binary search for key target within node (tail recursively).
returns
the index of target within node if it exists, or (-insertionPoint - 1) where insertionPoint is the index of the correct insertion point for key target.

Attributes
protected
def boundedIterator(bounds: (Symbol, K)*): Iterator[(K, V)]
Returns a bounded iterator over a range of key/value pairs in the tree in ascending sorted key order.
Returns a bounded iterator over a range of key/value pairs in the tree in ascending sorted key order. The range of key/value pairs in the iterator is specified by bounds. bounds must contain one or two pairs where the first element in the pair is a symbol corresponding to the type of bound (i.e. '<, '<=, '>, '>=) and the second element is a key value.
An example of a bounded iterator over all elements in a tree (with String keys) that will include all keys that sort greater than or equal to "a" and up to but not including "e" is boundedIterator( ('>=, "a"), ('<, "e") ).
def boundedKeysIterator(bounds: (Symbol, K)*): Iterator[K]
Returns a bounded iterator over a range of keys in the tree in ascending sorted key order.
Returns a bounded iterator over a range of keys in the tree in ascending sorted key order. The bounds parameter is the same as for boundedIterator.
def boundedPositionIterator(bounds: (Symbol, K)*): Iterator[(N, Int)]
Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in ascending sorted key order.
Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in ascending sorted key order. The bounds parameter is the same as for boundedIterator.

Attributes
protected
def boundedValuesIterator(bounds: (Symbol, K)*): Iterator[V]
Returns a bounded iterator over a range of values in the tree in ascending sorted key order.
Returns a bounded iterator over a range of values in the tree in ascending sorted key order. The bounds parameter is the same as for boundedIterator.
def build(s: String): BPlusTree[K, V]
Returns a B+ tree build from a string representation of the tree.
Returns a B+ tree build from a string representation of the tree. The syntax of the input string is simple: internal nodes are coded as lists of nodes alternating with keys (alpha strings with no quotation marks) using parentheses with elements separated by space, leaf nodes are coded as lists of alpha strings (no quotation marks) using brackets with elements separated by space.
Example:
1. ( [g] j [j t] u [u v] )
  produces a tree that pretty prints as
  [n0: (null, null, null) n1 | j | n2 | u | n3] [n1: (null, n0, n2) g] [n2: (n1, n0, n3) j t] [n3: (n2, n0, null) u v]
def clone(): AnyRef

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( ... )
def delete(key: K): Boolean
Performs the B+ tree deletion algorithm to remove key and it's associated value from the tree, rebalancing the tree if necessary.
Performs the B+ tree deletion algorithm to remove key and it's associated value from the tree, rebalancing the tree if necessary.
returns
true if key was found (and therefore removed), false otherwise
def diagram(name: String): Unit
Creates a PNG image file called name (with .png added) which visually represents the structure and contents of the tree, only showing the keys.
Creates a PNG image file called name (with .png added) which visually represents the structure and contents of the tree, only showing the keys. This method uses GraphViz (specifically the dot command) to produce the diagram, and ImageMagik (specifically the convert command) to convert it from SVG to PNG. dot can product PNG files directly but I got better results producing SVG and converting to PNG.
final def eq(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def equals(arg0: Any): Boolean

Definition Classes
AnyRef → Any
def finalize(): Unit

Attributes
protected[java.lang]
Definition Classes
AnyRef
Annotations
@throws( classOf[java.lang.Throwable] )
final def getClass(): Class[_]

Definition Classes
AnyRef → Any
def getKeyValue(leaf: N, index: Int): (K, V)
Returns the key/value pair at index within leaf.
Returns the key/value pair at index within leaf.

Attributes
protected
def greatestLT(key: K): (N, Int)
Returns the leaf position of the key that is greatest less than key.
Returns the leaf position of the key that is greatest less than key.

Attributes
protected
def greatestLTE(key: K): (N, Int)
Returns the leaf position of the key that is greatest less than or equal to key.
Returns the leaf position of the key that is greatest less than or equal to key.

Attributes
protected
def greatestLessThan(key: K): Option[(K, V)]
Returns the key/value pair whose key is greatest less than key.
def greatestLessThanOrEqual(key: K): Option[(K, V)]
Returns the key/value pair whose key is greatest less than or equal to key.
def hashCode(): Int

Definition Classes
AnyRef → Any
def insert[V1 >: V](key: K, value: V1 = null.asInstanceOf[V1]): Boolean
Inserts key with associated value into the tree.
Inserts key with associated value into the tree. If key exists, then it's new associated value will be value.
returns
true if key exists
def insertAt[V1 >: V](key: K, value: V1, leaf: N, index: Int): Unit
Performs the B+ tree insertion algorithm to insert key and associated value into the tree, specifically in leaf at index, rebalancing the tree if necessary.
Performs the B+ tree insertion algorithm to insert key and associated value into the tree, specifically in leaf at index, rebalancing the tree if necessary. If leaf and index is not the correct insertion point for key then this method will probably result in an invalid B+ tree.

Attributes
protected
def insertIfNotFound[V1 >: V](key: K, value: V1 = null.asInstanceOf[V1]): Boolean
Inserts key with associated value into the tree only if key does not exist.
Inserts key with associated value into the tree only if key does not exist.
returns
true if key exists
def insertKeys(keys: K*): Unit
Inserts keys into the tree each with an associated value of null.
Inserts keys into the tree each with an associated value of null. If a given key exists, then it's new associated value will be null.
def insertKeysAndCheck(keys: K*): String
Inserts keys into the tree each with an associated value of null, and checks that the tree is well constructed after each key is inserted.
Inserts keys into the tree each with an associated value of null, and checks that the tree is well constructed after each key is inserted. If a given key exists, then it's new associated value will be null. This method is used for testing.
def isEmpty: Boolean
Returns true is the tree is empty.
final def isInstanceOf[T0]: Boolean

Definition Classes
Any
def iterator: Iterator[(K, V)]
Returns an iterator over all key/value pairs in the tree in ascending sorted key order.
def keys: Iterable[K]
Returns a non-strict Iterable containing the keys in the tree.
def keysIterator: Iterator[K]
Returns an iterator over all keys in the tree in ascending sorted order.
def leastGT(key: K): (N, Int)
Returns the leaf position of the key that is least greater than key.
Returns the leaf position of the key that is least greater than key.

Attributes
protected
def leastGTE(key: K): (N, Int)
Returns the leaf position of the key that is least greater than or equal to key.
Returns the leaf position of the key that is least greater than or equal to key.

Attributes
protected
def leastGreaterThan(key: K): Option[(K, V)]
Returns the key/value pair whose key is least greater than key.
def leastGreaterThanOrEqual(key: K): Option[(K, V)]
Returns the key/value pair whose key is least greater than or equal to key.
def leftmost(node: N): K
Returns the left most or least key within or under node.
Returns the left most or least key within or under node.

Attributes
protected
def load[V1 >: V](kvs: (K, V1)*): Unit
Performs the B+ tree bulk loading algorithm to insert key/value pairs kvs into the tree efficiently.
Performs the B+ tree bulk loading algorithm to insert key/value pairs kvs into the tree efficiently. This method is more efficient than using insert because insert performs a search to determine the correct insertion point for the key whereas load does not. load can only work if the tree is empty, or if the minimum key to be inserted is greater than the maximum key in the tree.
def lookup(key: K): (Boolean, N, Int)
Performs the B+ tree lookup algorithm (tail recursively) beginning at the root, in search of the location (if found) or correct insertion point (if not found) of key.
Performs the B+ tree lookup algorithm (tail recursively) beginning at the root, in search of the location (if found) or correct insertion point (if not found) of key.
returns
a triple where the first element is true if key exists and false otherwise, the second element is the node containing key if found or the correct insertion point for key if not found, the third is the index within that node.

Attributes
protected
def lookupGTE(key: K): (Boolean, N, Int)
Searches for key returning a point in a leaf node that is the least greater than (if not found) or equal to (if found) key.
Searches for key returning a point in a leaf node that is the least greater than (if not found) or equal to (if found) key. The leaf node and index returned in case key does not exist is not necessarily the correct insertion point. This method is used by boundedIterator.
returns
a triple where the first element is true if key exists and false otherwise, and the second element is the leaf node containing the least greater than or equal key, and the third is the index of that key.

Attributes
protected
def lookupLTE(key: K): (Boolean, N, Int)
Searches for key returning a point in a leaf node that is the greatest less than (if not found) or equal to (if found) key.
Searches for key returning a point in a leaf node that is the greatest less than (if not found) or equal to (if found) key. The leaf node and index returned in case key does not exist is not necessarily the correct insertion point. This method is used by reverseBoundedIterator.
returns
a triple where the first element is true if key exists and false otherwise, and the second element is the leaf node containing the greatest less than or equal key, and the third is the index of that key.

Attributes
protected
def max: Option[(K, V)]
Returns the maximum key and it's associated value.
Returns the maximum key and it's associated value.
returns
Some( (key, value) ) where key is the maximum key and value is it's associated value if the tree is non-empty, or None if the tree is empty.
def maxKey: Option[K]
Returns the maximum key.
def min: Option[(K, V)]
Returns the minimum key and it's associated value.
Returns the minimum key and it's associated value.
returns
Some( (key, value) ) where key is the minimum key and value is it's associated value if the tree is non-empty, or None if the tree is empty.
def minKey: Option[K]
Returns the minimum key.
val minlen: Int
The minimum length (number of keys) that a non-root node (internal or leaf) may have is ceil(order/2) - 1.
The minimum length (number of keys) that a non-root node (internal or leaf) may have is ceil(order/2) - 1. The minimum length for a root leaf node is 0. The minimum length for a root internal node is 1.

Attributes
protected
final def ne(arg0: AnyRef): Boolean

Definition Classes
AnyRef
def nextPosition(leaf: N, index: Int): (N, Int)
Returns the node/index pair pointing to the location of the leaf node key following the one at index in leaf.
Returns the node/index pair pointing to the location of the leaf node key following the one at index in leaf.

Attributes
protected
final def notify(): Unit

Definition Classes
AnyRef
final def notifyAll(): Unit

Definition Classes
AnyRef
def optionalKey(pos: (N, Int)): Option[K]

Attributes
protected
def optionalKeyValue(pos: (N, Int)): Option[(K, V)]

Attributes
protected
def positionIterator: Iterator[(N, Int)]
Returns an iterator over all key positions (node/index pairs) in the tree in ascending sorted key order.
Returns an iterator over all key positions (node/index pairs) in the tree in ascending sorted key order.

Attributes
protected
def prettyPrint: Unit
Prints (to stdout) a readable representation of the structure and contents of the tree.
def prettyPrintKeysOnly: Unit
Prints (to stdout) a readable representation of the structure and contents of the tree, omitting the values and only printing the keys.
def prettySearch(key: K): String
Returns a string representing a search result for key that will be consistant with prettyPrint.
Returns a string representing a search result for key that will be consistant with prettyPrint. This method is used mainly for unit testing.
def prettyString: String
Returns a string containing a readable representation of the structure and contents of the tree, omitting the values and only printing the keys.
Returns a string containing a readable representation of the structure and contents of the tree, omitting the values and only printing the keys. This method is used mainly for unit testing.
def prettyStringWithValues: String
Returns a string containing a readable representation of the structure and contents of the tree.
Returns a string containing a readable representation of the structure and contents of the tree. This method is used mainly for unit testing.
def prevPosition(leaf: N, index: Int): (N, Int)
Returns the node/index pair pointing to the location of the leaf node key preceding the one at index in leaf.
Returns the node/index pair pointing to the location of the leaf node key preceding the one at index in leaf.

Attributes
protected
def reverseBoundedIterator(bounds: (Symbol, K)*): Iterator[(K, V)]
Returns a bounded iterator over a range of key/value pairs in the tree in descending sorted key order.
Returns a bounded iterator over a range of key/value pairs in the tree in descending sorted key order. The range of key/value pairs in the iterator is specified by bounds. bounds must contain one or two pairs where the first element in the pair is a symbol corresponding to the type of bound (i.e. '<, '<=, '>, '>=) and the second element is a key value.
An example of a reverse bounded iterator over all elements in a tree (with String keys) that will include all keys that sort greater than or equal to "a" and up to but not including "e", iterated over in reverse order, is reverseBoundedIterator( ('>=, "a"), ('<, "e") ).
def reverseBoundedKeysIterator(bounds: (Symbol, K)*): Iterator[K]
Returns a bounded iterator over a range of keys in the tree in descending sorted key order.
Returns a bounded iterator over a range of keys in the tree in descending sorted key order. The bounds parameter is the same as for boundedIterator.
def reverseBoundedPositionIterator(bounds: (Symbol, K)*): Iterator[(N, Int)]
Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in descending sorted key order.
Returns a bounded iterator over a range of key positions (node/index pairs) in the tree in descending sorted key order. The bounds parameter is the same as for boundedIterator.

Attributes
protected
def reverseBoundedValuesIterator(bounds: (Symbol, K)*): Iterator[V]
Returns a bounded iterator over a range of values in the tree in descending sorted key order.
Returns a bounded iterator over a range of values in the tree in descending sorted key order. The bounds parameter is the same as for boundedIterator.
def reverseIterator: Iterator[(K, V)]
Returns an iterator over all key/value pairs in the tree in descending sorted key order.
def reverseKeysIterator: Iterator[K]
Returns a reverse iterator over all keys in the tree in descending sorted order.
def reversePositionIterator: Iterator[(N, Int)]
Returns a reverse iterator over all key positions (node/index pairs) in the tree in descending sorted key order.
Returns a reverse iterator over all key positions (node/index pairs) in the tree in descending sorted key order.

Attributes
protected
def rightmost(node: N): K
Returns the right most or greatest key within or under node.
Returns the right most or greatest key within or under node.

Attributes
protected
def search(key: K): Option[V]
Searches for key returning it's associated value if key exists.
Searches for key returning it's associated value if key exists.
returns
Some( value ) where value is the value associated to key if it exists, or None otherwise
def serialize(before: String, prefix: String, internalnode: (N, (N) ⇒ String, (String) ⇒ Unit) ⇒ String, leafnode: (N, (N) ⇒ String) ⇒ String, after: String): String
Returns a serialization (string representation of the tree) using string and function arguments to specify the exact form of the serialization.
Returns a serialization (string representation of the tree) using string and function arguments to specify the exact form of the serialization. This method is used for pretty printing and to generate a DOT (graph description language) description of the tree so that it can be visualized.
before
string to be prepended to the serialization
prefix
string to be place before each line of the serialization that includes internal and leaf nodes
internalnode
function to generate internal node serializations using three parameters: the current node, a function to return a string id of a node, a function that allows a line of text to be appended after all nodes have been serialized
leafnode
function to generate leaf node serializations using two parameters: the current node, a function to return a string id of a node
after
string to be appended to the serialization

Attributes
protected
def str(node: N): String
Returns a string representation of the keys in node.
Returns a string representation of the keys in node. This method was used in debugging FileBPlusTree since the node type is Long.

Attributes
protected
final def synchronized[T0](arg0: ⇒ T0): T0

Definition Classes
AnyRef
def toString(): String

Definition Classes
AnyRef → Any
def traverseBreadthFirst(level: (List[N]) ⇒ Unit): Unit
Performs a breadth first traversal of the tree (tail recursively), applying level to each level of the tree beginning at the root.
Performs a breadth first traversal of the tree (tail recursively), applying level to each level of the tree beginning at the root.

Attributes
protected
def valuesIterator: Iterator[V]
Returns an iterator over all values in the tree in the order corresponding to ascending keys.
final def wait(): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long, arg1: Int): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
final def wait(arg0: Long): Unit

Definition Classes
AnyRef
Annotations
@throws( ... )
def wellConstructed: String
Analyzes the tree to determine if it is well constructed.
Analyzes the tree to determine if it is well constructed.
returns
"true" (as a string) if the tree is a well constructed B+ tree, a string description of the flaw otherwise.

Packages

Overview

BPlusTree

abstract class BPlusTree[K, +V] extends AnyRef

Instance Constructors

Type Members

Abstract Value Members

Concrete Value Members

Inherited from AnyRef

Inherited from Any

Ungrouped

Packages

Overview

BPlusTree 

abstract class BPlusTree[K, +V] extends AnyRef

Instance Constructors

Type Members

Abstract Value Members

Concrete Value Members

Inherited from AnyRef

Inherited from Any

Ungrouped

BPlusTree