ブロックアルゴリズムとB-Treeアルゴリズム

ファイルサーチを高速化するB-Treeアルゴリズム ext2、ext3がベースとするブロックアルゴリズムは、ブロック数が対応するディスクのジオメトリ数に制限されること、ファイルサーチにO（n）かかる（注）こと、ファイルサイズに関係するパフォーマンス低下など、いくつかの問題があった。 注：「O（n）」とは、実行時間が入力の大きさ「n」に比例するアルゴリズムである。O（n）は「nのオーダー」または「オーダーn」と読む。後述する「O（log n）」は、アルゴリズムの計算量に関する議論の場合logの底は常に2で、O（log n）の方がO（n）よりも効率が良い。例えばn＝8の場合、O（log n）は入力8に対して3回の実行で済むが、O（n）は8回の実行となる。 ReiserFS、JFS、XFSといったファイルシステムでは、こうしたブロックアルゴリズムの限界に対して、早い段階からデータベースの技術をフ

[dogusare]

dbというかソフトウェア門外漢としてはバランス木とB木とB-TreeとBalance-TreeとB*木とB+木が違うのか違わないのか何なのかから混乱していたところ（赤面、丁寧な解説に感謝

[yass]

" B+-Treeはデータとキーを完全に分けて管理 / ノードの下位層をインデックス部とデータ部に分けて構成し、「データ」は常にリーフノードに保存する。インデックス部の各ノードは4つのキー値と5つのポインタのみを保持 "

[Kshi_Kshi]

B-tree

[katryo]

ブクマしておこう

[muramasaosx]

b-tree

[zionic]

B木のアルゴリズム概説

[rero]

B-Tree (Bayer Tree，B 木) とその派生系である B*-Tree と B+-Tree

[jjzak]

B-Treeアルゴリズム

[mogwaing]

B-tree B+-tree B*-tree