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

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

» 2003年06月24日 00時00分 公開
[菅谷みどり@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ノード」「ジャーナリング」といったファイルシステムの実装の基本的な仕組みを紹介する。

       1|2|3 次のページへ

Copyright © ITmedia, Inc. All Rights Reserved.

RSSについて

アイティメディアIDについて

メールマガジン登録

@ITのメールマガジンは、 もちろん、すべて無料です。ぜひメールマガジンをご購読ください。