ファイルサーチを高速化する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といったファイルシステムでは、こうしたブロックアルゴリズムの限界に対して、早い段階からデータベースの技術をフ
![ブロックアルゴリズムとB-Treeアルゴリズム](https://cdn-ak-scissors.b.st-hatena.com/image/square/6e84fc6ab06f31b2e64248cbfc92fe06deb5bab5/height=288;version=1;width=512/https%3A%2F%2Fimage.itmedia.co.jp%2Fimages%2Flogo%2F1200x630_500x500_ait.gif)