MemoryBPlusTree
Related Doc:
package btree
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.
Comparing two nodes for equality is required to be true when they point to the same node.
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.
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.
Performs a binary search for key target within node (tail recursively).
Performs a binary search for key target within node (tail recursively).
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.
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") ).
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.
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.
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.
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.
( [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]
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.
true if key was found (and therefore removed), false otherwise
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.
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.
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.
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.
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.
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 ).
Returns the branches of node as a non-strict immutable sequence.
Returns the branches of node as a non-strict immutable sequence.
Returns a key from a leaf node at a given index.
Returns a key from a leaf node at a given index.
Returns the key/value pair at index within leaf.
Returns the key/value pair at index within leaf.
Returns the keys of node as a non-strict immutable sequence.
Returns the keys of node as a non-strict immutable sequence.
Returns the next pointer of (leaf) node.
Returns the next pointer of (leaf) node.
Returns the parent pointer of node.
Returns the parent pointer of node.
Returns the previous leaf node link pointer of (leaf) node.
Returns the previous leaf node link pointer of (leaf) node.
Returns a value from a leaf node at a given index.
Returns a value from a leaf node at a given index.
Returns the values of node as a non-strict immutable sequence.
Returns the values of node as a non-strict immutable sequence.
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.
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.
Returns the key/value pair whose key is greatest less than key.
Returns the key/value pair whose key is greatest less than key.
Returns the key/value pair whose key is greatest less than or equal to key.
Returns the key/value pair whose key is greatest less than or equal to key.
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.
true if key exists
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.
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.
true if key exists
Inserts key and branch into (internal) node at keyIndex and branchIndex, respectively.
Inserts key and branch into (internal) node at keyIndex and branchIndex, respectively.
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.
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.
Inserts key and value into (leaf) node at index.
Inserts key and value into (leaf) node at index.
Returns true is the tree is empty.
Returns true is the tree is empty.
Returns true if node is a leaf node
Returns true if node is a leaf node
Returns an iterator over all key/value pairs in the tree in ascending sorted key order.
Returns an iterator over all key/value pairs in the tree in ascending sorted key order.
Returns a non-strict Iterable containing the keys in the tree.
Returns a non-strict Iterable containing the keys in the tree.
Returns an iterator over all keys in the tree in ascending sorted order.
Returns an iterator over all keys in the tree in ascending sorted order.
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.
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.
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.
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.
Returns the key/value pair whose key is least greater than key.
Returns the key/value pair whose key is least greater than key.
Returns the key/value pair whose key is least greater than or equal to key.
Returns the key/value pair whose key is least greater than or equal to key.
Returns the left most or least key within or under node.
Returns the left most or least key within or under node.
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.
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.
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.
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.
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.
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.
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.
Returns the maximum key and it's associated value.
Returns the maximum key and it's associated value.
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.
Returns the maximum key.
Returns the maximum key.
Returns the minimum key and it's associated value.
Returns the minimum key and it's associated value.
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.
Returns the minimum key.
Returns the minimum key.
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.
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.
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.
Creates a new internal node with parent as its parent pointer.
Creates a new internal node with parent as its parent pointer.
Creates a new leaf node with parent as its parent pointer.
Creates a new leaf node with parent as its parent pointer.
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).
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.
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.
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.
the branching factor (maximum number of branches in an internal node) of the tree
the branching factor (maximum number of branches in an internal node) of the tree
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.
Prints (to stdout) a readable representation of the structure and contents of the tree.
Prints (to stdout) a readable representation of the structure and contents of the tree.
Prints (to stdout) a readable representation of the structure and contents of the tree, omitting the values and only printing the keys.
Prints (to stdout) a readable representation of the structure and contents of the tree, omitting the values and only printing the keys.
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.
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.
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.
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.
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.
length of node after removal
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.
length of node after removal
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") ).
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.
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.
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.
Returns an iterator over all key/value pairs in the tree in descending sorted key order.
Returns an iterator over all key/value pairs in the tree in descending sorted key order.
Returns a reverse iterator over all keys in the tree in descending sorted order.
Returns a reverse iterator over all keys in the tree in descending sorted order.
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.
Returns the right most or greatest key within or under node.
Returns the right most or greatest key within or under node.
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.
Searches for key returning it's associated value if key exists.
Searches for key returning it's associated value if key exists.
Some( value ) where value is the value associated to key if it exists, or None otherwise
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.
string to be prepended to the serialization
string to be place before each line of the serialization that includes internal and leaf nodes
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
function to generate leaf node serializations using two parameters: the current node, a function to return a string id of a node
string to be appended to the serialization
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.
Sets the key at index of node to key.
Sets the key at index of node to key.
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.
Sets the next pointer of (leaf) node to p.
Sets the next pointer of (leaf) node to p.
Sets the parent pointer of node to p.
Sets the parent pointer of node to p.
Sets previous leaf node link pointer of (leaf) node to p.
Sets previous leaf node link pointer of (leaf) node to p.
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.
Sets the value at index of node to v.
Sets the value at index of node to v.
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.
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.
Returns an iterator over all values in the tree in the order corresponding to ascending keys.
Returns an iterator over all values in the tree in the order corresponding to ascending keys.
Analyzes the tree to determine if it is well constructed.
Analyzes the tree to determine if it is well constructed.
"true" (as a string) if the tree is a well constructed B+ tree, a string description of the flaw otherwise.
An in-memory B+ Tree implementation.
the type of the keys contained in this map.
the type of the values associated with the keys.