ブロックアルゴリズムと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といったファイルシステムでは、こうしたブロックアルゴリズムの限界に対して、早い段階からデータベースの技術をフ
http://1978th.net/tech/promenade.cgi?id=83
