B-Tree

B-TREEの考察

B-TREEを理解する為にviz3/btree.c(c)をperlに写経してみた。とりえず動く物を作ってから考えようと。【デモ】←クリック

sub btree{
    my $s = shift;
    $s->M(int(rand(8)+2));
    $s->debugtext($s->debugtext . " (M:" . $s->M . ")"); 
    $s->insert($_ * 2) for (11 .. 15);
    $s->insert($_ * 2 - 1) for (1 .. 6);
    $s->insert($_) for (1 .. 20);
    $s->insert($_) for (30 .. 100);
    $s->insert(7);
    $s->delete($_) for (92 .. 99);
    $s->delete(11);
    $s->delete(51);
    $s->insert(11);
    $s->insert(51);
    $s->delete(75);

    $s->level(0);
    $s->tree_dump($s->root);
    $s->render(template => 'btree/btree','message'=> $s->message,
           'treetext'=>$s->debugtext);
}

wikiより

B木

B木（びーき）は、コンピュータサイエンスにおけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。実システムでも多用されており、データベース管理システムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木やB*木を使うことが多い）。

構造

多分岐の平衡木(バランス木)である。1 ノードから最大 m 個の枝が出るとき、これをオーダー m のB木という。後述する手順に従って操作すると、根と葉を除く「内部ノード」は最低でも m /2 の枝を持つことを保証できる。各ノードは、枝の数 - 1 のキーを持つ。枝1 〜 枝m と キー1 〜 キーm -1 を持つとき、枝i には キーi -1 より大きく キーi より小さいキーだけを保持する（キーの重複を許す場合はどちらかに等号をつける）。葉ノードの定義は文献によって違いが見られる。木の終端をヌルポインタのような特殊な値で表す場合、枝がすべて終端記号となっているノードを葉とする。これに対して一部の文献では、終端を表すためにキーが0個のノードを連結し、このノードを葉と定義している。すなわち、後者の定義における葉ノードの親が、前者の定義における葉ノードとなる。後者の定義をとる文献では「葉ノードはキーを持たない」ということになる。以下の記述では、前者の定義に従うものとする。ノードはページと呼ばれることもある。特にハードディスクドライブなどの外部記憶装置を使ってB木を実現する場合によく見られる。この場合、各ノード（ページ）のサイズが、外部記憶装置のブロックサイズの整数倍になるようにオーダーを調整することが多い。B木の中でも特に、オーダー3のものを2-3木、オーダー4のものを2-3-4木と呼ぶ。

B-TREE

B-TREE

削除しました
Debug TREE (M:9)
N -> 7ー [ 10, 20, 35, 45, 55, 65, 76 ]
N -> 9ーー [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
N -> 9ーー [ 11, 12, 13, 14, 15, 16, 17, 18, 19 ]
N -> 9ーー [ 22, 24, 26, 28, 30, 31, 32, 33, 34 ]
N -> 9ーー [ 36, 37, 38, 39, 40, 41, 42, 43, 44 ]
N -> 9ーー [ 46, 47, 48, 49, 50, 51, 52, 53, 54 ]
N -> 9ーー [ 56, 57, 58, 59, 60, 61, 62, 63, 64 ]
N -> 9ーー [ 66, 67, 68, 69, 70, 71, 72, 73, 74 ]
N -> 16ーー [ 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 100 ]