The BpNode class defines nodes of size order that that may be stored in a B+tree. Keys have type ValueType and may reference values of Any type.
Value parameters
- DLINK
-
whether the leaf nodes support linkage in both directions (ref(0) & pre)
- isLeaf
-
whether this node is a leaf
- keys
-
number of active keys
Attributes
- Companion
- object
- Graph
-
- Supertypes
-
trait Serializableclass Objecttrait Matchableclass Any
Members list
Value members
Constructors
Concrete methods
Add the new key k and value v into this node at the to be found insertion position (ip). If a duplicate key is entered, return the OLD VALUE stored with the key, otherwise return None (meaning no duplicate was found)..
Add the new key k and value v into this node at the to be found insertion position (ip). If a duplicate key is entered, return the OLD VALUE stored with the key, otherwise return None (meaning no duplicate was found)..
Value parameters
- k
-
the new key
- v
-
the new value (or node for internal nodes)
Attributes
Return the key at index position i.
Return the key at index position i.
Value parameters
- i
-
the index position in this node
Attributes
Find and return the first position where 'k < key_i' in this node. If none, return keys (corresponds to last ref).
Find and return the first position where 'k < key_i' in this node. If none, return keys (corresponds to last ref).
Value parameters
- k
-
the key whose index position is sought
Attributes
Find and return the first position where 'k == key_i' in this node. If none, return -1 meaning not found.
Find and return the first position where 'k == key_i' in this node. If none, return -1 meaning not found.
Value parameters
- k
-
the key whose index position is sought
Attributes
Merge this LEAF node with its right sibling node (rt).
Merge this LEAF node with its right sibling node (rt).
Value parameters
- rt
-
the right sibling node
Attributes
Merge this INTERNAL node with its right sibling node (rt).
Merge this INTERNAL node with its right sibling node (rt).
Value parameters
- dk
-
the divider key from parent
- rt
-
the right sibling node
Attributes
Return whether this node has overflowed (too many keys).
Return whether this node has overflowed (too many keys).
Attributes
Remove key at dp and its reference from this node and check for underflow.
Remove key at dp and its reference from this node and check for underflow.
Value parameters
- dp
-
the deletion index position (may use findEq to find it)
Attributes
Remove key at dp and its reference from this INTERNAL node and check for underflow.
Remove key at dp and its reference from this INTERNAL node and check for underflow.
Value parameters
- dp
-
the deletion index position (may use findEq to find it)
Attributes
Return whether this node is rich (i.e., has surplus keys).
Return whether this node is rich (i.e., has surplus keys).
Attributes
Shift keys from ip to keys one position to the RIGHT (make room for insertion). Also shift all references to the right of key ip.
Shift keys from ip to keys one position to the RIGHT (make room for insertion). Also shift all references to the right of key ip.
Value parameters
- ip
-
the future insertion position
Attributes
Show the node's data structure.
Show the node's data structure.
Attributes
Show the node's references.
Show the node's references.
Attributes
Split this LEAF node by creating a right sibling node (rt) and moving half the keys and references to that new node, leaving halfp. Return the divider key and the right sibling node.
Split this LEAF node by creating a right sibling node (rt) and moving half the keys and references to that new node, leaving halfp. Return the divider key and the right sibling node.
Attributes
Split this INTERNAL node by creating a right sibling rt and moving half the keys and references to that new node, leaving halfp - 1. Return the divider key and the right sibling node.
Split this INTERNAL node by creating a right sibling rt and moving half the keys and references to that new node, leaving halfp - 1. Return the divider key and the right sibling node.
Attributes
Convert this node to a string.
Convert this node to a string.
Attributes
- Definition Classes
-
Any
Return whether this node has underflowed (too few keys).
Return whether this node has underflowed (too few keys).