ブロックアルゴリズムとB-Treeアルゴリズム：Linuxファイルシステム技術解説（2）（1/3 ページ）

　前回はVFSの管理機構やファイルシステムの基本的な仕組みについて解説した。今回は、ファイルシステムがファイルを管理する仕組みを中心に各種の技術を解説する。

各ファイルシステムの特徴

　今回紹介する技術内容は、次に挙げるローカルファイルシステムで主に用いられている手法である。

　ext2とext3は、「ブロックアルゴリズム」を採用している。ブロックアルゴリズムとは、例えばディスクを4Kbytesなどの単位（ブロック）に分けて管理する方法である。ext2にジャーナリング機能を追加したものがext3である。ext2、ext3以外のファイルシステムで用いられているB-Treeとそのバリエーションは、バランス木（Balanced Tree）をベースとしたアルゴリズムである。

　拡張機能としては、今回紹介する「動的iノード」と「エクステント」方式が挙げられる。「エクステント」は、ブロックアドレスの代わりに「論理セット」と呼ばれる「開始アドレス」「サイズ」「オフセット」を渡すことでアドレッシングを効率化する方式である。「動的iノード」はiノードを動的に付与する方法で、これまで存在していたiノード数の制約を解決するものとして期待されている。ReiserFSやJFS、XFSはこれらの拡張を実装している。「ジャーナリング」機能は、信頼性を高める方法としてすでに定着しつつある。

　これらの拡張機能は、伝統的に用いられてきた「ブロックアルゴリズム」の制限や問題を解決するものとして期待されている。今回はこうした経緯も踏まえつつ、従来型のファイルシステムであるext2を中心に「ブロックアルゴリズム」を解説し、次いで「B-Tree」とその派生形である「B*-Tree」と「B+-Tree」について説明する。次回は、その続きとして「エクステント」「動的iノード」「ジャーナリング」といったファイルシステムの実装の基本的な仕組みを紹介する。