!!!B-TREEの考察
B-TREEを理解する為に[viz3/btree.c|https://gist.github.com/viz3/3486656](c)を[perl|https://github.com/john-smith-7701/mmt/commit/cb2da2ea70ed26e95463bbc912d789a1e878f294]に写経してみた。とりえず動く物を作ってから考えようと。【[デモ|http://www21051ue.sakura.ne.jp:3003/api/btree/btree/]】←クリック

 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|https://ja.wikipedia.org/wiki/B%E6%9C%A8]より
!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|http://www21051ue.sakura.ne.jp:3003/api/btree/btree/]

 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 ]