Here follows an example of creating "Multiway B-Tree".
<
br />The implementation is in PHP:
// B-tree
function btree_search( $value, $a, &$higher, $v)
{
global $tree, $q, $u, $n, $nn;
static $v;
// create new elelemt
if( $tree[$a]['m'] == 0 )
{
$higher = true;
$v['value'] = $value;
$v['count'] = 1;
$v['p'] = null;
$u = $v;
}
else
{
$cur = $tree[$a];
$l = 1;
$r = $cur['m'];
do// binary search
{
$k = (int)( ($l + $r)/2);
if( $value <= $cur['el'][$k]['value'] )
{
$r = $k - 1;
}
if( $value >= $cur['el'][$k]['value'] )
{
$l = $k + 1;
}
}while( $r >= $l);
// found
if( $l - $r > 1)
{
$cur['el'][$k]['count']++;
$higher = false;
}
else
{
if( $r == 0 )
$q = $cur['p0'];
else
$q = $cur['el'][$r]['p'];
btree_search($value, $q, $higher, $u);
if( $higher )
{
/* $a !== null. Search key $value in B-tree with root $a;
insert new item with key $value. If an entry is to be passed up,
assign it to $v. $higher = "tree has become higher"
*/
$cur = &$tree[$a];
// !$higher
if( $cur['m'] < $n*2 )
{
$cur['m']++;
$higher = false;
for( $i=$cur['m']; $i >= $r+2; $i-- )
{
$cur['el'][$i] = $cur['el'][$i-1];
}
$cur['el'][$r+1] = $u;
}
// page $tree[$a]/$cur is full.
// It's partioned and the odd element is moved to v
else
{
// add new element to $tree and assign
// the last element's num to $b;
$b = array_push($tree, array());
if( $r <= $n ) // insert in left page $a
{
if( $r == $n )
$v = $u;
else
{
$v = $cur['el'][$n];
for( $i=$n; $i >= $r+2; $i-- )
$cur['el'][$i] = $cur['el'][$i-1];
$cur['el'][$r+1] = $u;
}
for( $i=1; $i <= $n; $i++ ){
$tree[$b]['el'][$i] = $cur['el'][$i+$n];
unset( $cur['el'][$i+$n] );
}
}
else // insert into right page $b
{
$r = $r-$n;
$v = $cur['el'][$n+1];
for( $i=1; $i <= $r-1; $i++ )
$tree[$b]['el'][$i] = $cur['el'][$i+$n+1];
$tree[$b]['el'][$r] = $u;
for( $i=$r+1; $i <= $n; $i++ )
$tree[$b]['el'][$i] = $cur['el'][$i+$n];
}
$cur['m'] = $n;
$tree[$b]['m'] = $n;
$tree[$b]['p0'] = $v['p'];
$v['p'] = $b;
$u = $v;
}
}
}
}
return 1;
}
$b_tree = array();
// you could create as many trees as you want
// but when you want to work with them use $tree = &$my_tree;
$tree = &$b_tree;
// array for B-tree insert test
// test steps bellow to see how the tree behaves
$values = array(20);
//$values = array(20, 40, 10, 30,15);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32);
//$values = array(20, 40, 10, 30,15, 35, 7, 26, 18, 22, 5, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25 );
$higher = false;
$root = null;
$n = 2;
foreach( $values as $val )
{
btree_search( $val, $root, $higher, $u);
if( $higher )
{
$q = $root;
if( count($tree) == 0 )
{
$tree = array(1=>array());
$root = 1;
}
else
$root = array_push($tree, array());
$tree[$root]['m'] = 1;
$tree[$root]['p0'] = $q;
$tree[$root]['el'][1] = $u;
}
}
