Convenience alias for the implementation
Convenience alias for the key type
Convenience alias for the element type
Searches the tree for the element with the given key and returns the associated value.
Constructor.
Inserts the (key, value) in the tree. This is passing the copy of the value into the tree, so it's not necessary to manually create copy of it. Note that for the reference types, this will just copy the reference.
Inserts the (key, value) in the tree. This is passing the copy of the value into the tree, so it's not necessary to manually create copy of it. Note that for the reference types, this will just copy the reference.
Recursive inorder iteration over keys and values. Note that, in case the tree is changed during the iteration, iteration will halt.
Recursive inorder iteration over values only. Note that, in case the tree is changed during the iteration, iteration will halt.
Searches the tree for the element with the given key and returns the pointer to the associated value.
Deletes the element from the BTreeMap.
Private implementation
type of the key.
type of the element to store.
degree of the tree (refer to the documentation)
BTree is a rooted tree, with the following properties:
- A BTree has characteristic called "degree". This indicates branching factor of the tree, so that maximum number of the subtrees for a single node is 2 * degree. Having a high degree makes the tree shorter, and, because the node contains large number of elements, it allows prefetching many elements from the memory in one go.
- The layout of one node of the tree is as follows:
| p1 | element1 | p2 | element2 | ... | pn-1 | element n-1 | pn |
Every element (a key/value pair) in the node (for the non-leaf nodes) is surrounded by two pointers. We call these pointers child nodes.
- Each pointer is a root of a subtree, for which the following holds true: all the elements' keys in a tree pointed by p(i-1) (pointer left of the elements) are smaller (in respect to the ordering defined by the key's type) of the element(i), and all the elements' keys in a subtree pointed by p(i) are larger than a element(i).
- Every node may contain at most 2*degree - 1 elements. Therefore, an internal node may be root for at most 2*degree subtrees.
- Every node other than root must have at least (degree-1) elements.
- Every internal node other than the root has at least degree children.
- Every node has the following attributes:
node.number_of_elements = number of elements node currently contains (as nodes are statically allocated block, the number of the elements may not necessarily be maximal). node.elements = the elements themselves node.is_leaf = indicator if the node is a leaf. node.child_nodes = number_of_elements+1 pointers to the subtrees whose roots are this node. We refer to these nodes as child-nodes (this node is a direct parent of them).
- All leaves have the same depth
Other than insert and delete operations, inorder traversal method is provided, which traverses the tree in inorder order (left subtree is visited first, then the element separating these subtrees, then the right subtree, then the next element, etc.). This provides sequential access to the tree. There's a recursive and range-based implementation of the inorder traversal.
Range-based traversal is supported through BTreeMapRange structure, found in in ocean.util.container.btree.BTreeMapRange.
CPU complexity of the operations (n is number of the elements, t is degree, h is the tree height):
- Searching: O(th) = O(t * log_t(n)) - Inserting: O(th) = O(t * log_t(n)) - Deleting: O(th) = O(t * log_t(n))
Complexity of the memory access (to read/write the node from/in memory):
- Searching O(h) = O(log_t(n)) - Inserting O(h) = O(log_t(n)) - Deleting: O(h) = O(log_t(n))
References: - https://en.wikipedia.org/wiki/B-tree - Thomas H. Cormen et al. "Introduction to Algorithms, 3rd edition"
BTree structure.