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

長らく標準ファイルシステムとしてLinuxを支えてきたext2の仕組みを明らかにするとともに、ext2の問題点を克服するための諸技術について解説する。（編集局）

[菅谷みどり，＠IT]

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

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

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

	基本アルゴリズム	拡張機能	ジャーナリング機能
ext2	ブロック	―	―
ext3	（ベースはext2）	―	あり
ReiserFS	B*-Tree	v4より動的iノード スパースファイル	あり
JFS	B+-Tree	動的iノード エクステント スパースファイル	あり
XFS	B+-Tree	動的iノード エクステント スパースファイル	あり
表1　各ローカルファイルシステムの特徴

　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ノード」「ジャーナリング」といったファイルシステムの実装の基本的な仕組みを紹介する。