MIN_DEGREE
MIN_DEGREE
Default value of minimum degree. The minimum degree determines the minimum and maximum number of keys and child nodes, for nodes other than root node
This class implements the B-Tree data structure for storing int key based key-value pairs based on the algorithms in Introduction To Algorithms, by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Second Edition, 2001, The MIT Press
__construct(string $dir, integer $min_degree = self::MIN_DEGREE)
Creates/Loads B-Tree having specified directory and minimum_degree. The default minimum_degree is 501.
string | $dir | is the directory for storing the B-Tree files |
integer | $min_degree | minimum degree of a B-tree node |
search(object $node, integer $key)
Searches for key-value pair for a given key in a node. If key value pair is not found in the node, recursively searches in the root node of the sub-tree till the pair is found. Search stops at leaf nodes.
object | $node | is the B-Tree node from where the search starts |
integer | $key | is the key for which the key-value pair is to be searched |
insertNodeNotFull(object $node, array $pair)
Inserts a key-value pair in a leaf node that is not full. Searches for the appropriate leaf node, splitting full nodes before descending down the tree recursively.
object | $node | is the node from where the search for the leaf node begins |
array | $pair | is the key-value pair |
bTreeSplitChild(object $parent, integer $i, object $child)
Splits a full node into two child node. The median key-value pair is added to the parent node of the node being split.
object | $parent | is the parent node |
integer | $i | is the link to child node |
object | $child | is the child node |
binarySearch(array $keys, integer $key) : array
Performs binary search for a integer key on an array of integer key based key-value pairs
array | $keys | is an array containing key-value pairs |
integer | $key | is the key |
containing flag indicating it the value was found or not, and the position equal to, or nearest to the position of the key being searched
delete(object $node, integer $key)
Deletes a key-value pair from the B-Tree from a node.
Handles deletion from leaf node and internal node. If the key-value pair is not found in an internal node. The recrusion descends to the root of the sub-tree until a leaf node is encoutered that does not have the key-value pair to be deleted.
object | $node | is from where the key search starts |
integer | $key | is the key to be deleted |
reArrange(object $node, integer $pos)
Shifts a key from a non-leaf root to it's child node using nodes preceding and next to the key-value pair to be deleted. If the preceding child node has atleast minimum MIN_DEGREE keys, a the last key-value pair from the preceding node is moved to the position of the key-value pair that is to be deleted. Otherwise the same process is done using the first key-value pair of the child node next to the key-value pair to be deleted.
object | $node | is the internal node containing the key-value pair to be deleted |
integer | $pos | is the position of the key-value pair within $pos. |
getDescendant(object $parent, integer $pos) : object
If the key to be deleted is not found in an internal node, finds the root of the sub-tree that might contain the key to be deleted. If the node contains atleast $min_degree number of keys, the node is returned.
Otherwise, the node is adjusted using one of its sibling nodes and the parent node so that the resultant node has $min_degree keys.
object | $parent | is the parent node |
integer | $pos | is the link to the root of the sub-tree |
$child is the child node to which the recursion will descend
adjustChildUsingLeftSiblingAndParent(object $parent, object $child, object $pred, $pos)
Gives a child node an extra key by moving a key from the parent to the child node, and by moving a key from the child's left sibling to the parent node
object | $parent | is the parent node |
object | $child | is the child node |
object | $pred | is the $child's left sibling node |
$pos | is the link from $parent to $child |
adjustChildUsingRightSiblingAndParent(\seekquarry\yioop\library\object& $parent, \seekquarry\yioop\library\object& $child, \seekquarry\yioop\library\object& $next, integer $pos)
Gives a child node an extra key by moving a key from the parent to the child node, and by moving a key from the child's right sibling to the parent node
\seekquarry\yioop\library\object& | $parent | is the parent node |
\seekquarry\yioop\library\object& | $child | is the child node |
\seekquarry\yioop\library\object& | $next | is the $child's right sibling node |
integer | $pos | is the link from $parent to $child |
mergeChildWithParentKeyAndRightSibling(object $parent, object $child, object $next, $pos)
Merges the child node with it's right sibling. The separating key in the parent node is added as the median key to the newly formed node
object | $parent | is the parent node |
object | $child | is the child node |
object | $next | is the $child's right sibling node |
$pos | is the link from $parent to $child |