\seekquarry\yioop\libraryBTree

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

Summary

Methods
Properties
Constants
__construct()
readNode()
writeNode()
writeRoot()
deleteNodeFile()
saveNodeCount()
deleteCount()
findValue()
search()
insert()
insertNodeNotFull()
bTreeSplitChild()
swap()
createEmptyParentNode()
binarySearch()
remove()
delete()
reArrange()
deleteFromLeaf()
deleteFromNonLeaf()
getDescendant()
adjustChildUsingLeftSiblingAndParent()
adjustChildUsingRightSiblingAndParent()
mergeChildWithParentKeyAndRightSibling()
getSiblings()
$min_degree
$root
$id_count
$dir
MIN_DEGREE
No protected methods found
No protected properties found
N/A
No private methods found
No private properties found
N/A

Constants

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

Properties

$min_degree

$min_degree : integer

Minimum degree of the B-Tree. Used in determining the minimum/maximum keys and links a B-Tree node may have.

minimum_keys = minimum_degree - 1 minimum_links = minimum_keys + 1 maximum_keys = 2 * minimum_degree - 1 maximum_links = maximum_keys + 1

Type

integer

$root

$root : object

Storage for root node of the B-Tree

Type

object

$id_count

$id_count : integer

Counter for node Ids

Type

integer

$dir

$dir : string

Directory for storing the B-Tree files

Type

string

Methods

__construct()

__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.

Parameters

string $dir

is the directory for storing the B-Tree files

integer $min_degree

minimum degree of a B-tree node

readNode()

readNode(integer  $id) : object

Reads node from file saved on disk

Parameters

integer $id

is the Id of the node to be read

Returns

object —

$node is the node

writeNode()

writeNode(object  $node) 

Writes node to disk

Parameters

object $node

is the node to be written to disk

writeRoot()

writeRoot() 

Writes the root node of this btree to disk

deleteNodeFile()

deleteNodeFile(integer  $id) 

Deletes file associated with given node from disk

Parameters

integer $id

is the id of the node whose file is to be deleted

saveNodeCount()

saveNodeCount() 

Saves value of node id counter

deleteCount()

deleteCount() 

Deletes the node id count file

findValue()

findValue(integer  $key) : array

Returns key-value pair in the B-Tree based on key

Parameters

integer $key

is the key for whicht the key-value pair is to be found

Returns

array —

key-value pair associated with $key or null if the key-value pair is not found in the tree.

search()

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.

Parameters

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

insert()

insert(array  $pair) 

Inserts a key-value pair in the B-Tree

Parameters

array $pair

is the key-value pair to be inserted

insertNodeNotFull()

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.

Parameters

object $node

is the node from where the search for the leaf node begins

array $pair

is the key-value pair

bTreeSplitChild()

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.

Parameters

object $parent

is the parent node

integer $i

is the link to child node

object $child

is the child node

swap()

swap(  $x,   $y) 

Swaps value of two variables

Parameters

$x

is the first variable

$y

is the second variable

createEmptyParentNode()

createEmptyParentNode() : object

Creates an empty non-leaf node

Returns

object —

$node is the non-leaf node

binarySearch()

binarySearch(array  $keys, integer  $key) : array

Performs binary search for a integer key on an array of integer key based key-value pairs

Parameters

array $keys

is an array containing key-value pairs

integer $key

is the key

Returns

array —

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

remove()

remove(integer  $key) 

Removes a key-value pair from the B-Tree

Parameters

integer $key

associated with the key-value pair to be deleted

delete()

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.

Parameters

object $node

is from where the key search starts

integer $key

is the key to be deleted

reArrange()

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.

Parameters

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.

deleteFromLeaf()

deleteFromLeaf(\seekquarry\yioop\library\object&  $node, integer  $pos) 

Deletes key-value pair from a leaf node in a B-Tree

Parameters

\seekquarry\yioop\library\object& $node

is the leaf node containing the key-value pair

integer $pos

in node to delete

deleteFromNonLeaf()

deleteFromNonLeaf(\seekquarry\yioop\library\object&  $node, integer  $pos) 

Deletes key-value pair from a non-leaf node in a B-Tree

Parameters

\seekquarry\yioop\library\object& $node

is the non-leaf node containing the key-value pair

integer $pos

link position in node to delete

getDescendant()

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.

Parameters

object $parent

is the parent node

integer $pos

is the link to the root of the sub-tree

Returns

object —

$child is the child node to which the recursion will descend

adjustChildUsingLeftSiblingAndParent()

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

Parameters

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()

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

Parameters

\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()

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

Parameters

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

getSiblings()

getSiblings(object  $parent, integer  $pos) 

Gets the siblings ids based on link in parent node

Parameters

object $parent

is the parent node

integer $pos

is the link for which the siblings are to be found