前回、XFSの技術上の特徴として、(1)複数ブロックにまたがるメタデータのB+ treeデータ構造、(2)エクステントを単位としたブロック管理、(3)遅延アロケーションによるブロック割り当て、(4)ジャーナリングによる障害からの高速な復旧、──の四つを挙げた。以下では、それぞれの特徴を詳しく解説していこう。

(1)複数ブロックにまたがるメタデータのB+ treeデータ構造

 B+ treeデータ構造は、ツリー状のインデックス情報を持つブロックと、リーフ(ツリーの末端)に対応するデータを格納するブロックからなる*3。このデータ構造は、ランダムアクセスとシーケンシャルアクセスの双方で良い性能を発揮する。ツリーの深さを増やすことでデータサイズの変更にも柔軟に対応する。このデータ構造はディスク上のデータ管理に優れており、多くのファイルシステムやRDBなどで採用されている。

*3 B+ treeデータ構造についてはhttps://en.wikipedia.org/wiki/B%2B_treeを参照

 ext系のファイルシステムでは、空きブロックの管理にビットマップを利用している。これは、1ビットを管理対象の1ブロックと対応付ける単純なデータ構造である。ビットマップによる管理はシンプルだが、非効率な面がある。最悪のケースを考えると、空き領域が最後の1ブロックしかない場合に、すべてのブロックをチェックしてようやく最後の空きブロックを発見することになる。

 一方XFSが採用するB+ treeなら、最悪の場合でもツリーの高さ分だけのブロックを確認することで空きブロックを発見することができる。ツリーの高さは、管理対象のブロック数の対数に比例する。

 XFSでは、空きブロックの管理のほか、inodeやディレクトリーエントリー、後述するエクステントの管理、といった多くの場所でB+ treeが使われている。

 ext2ではディレクトリーエントリーを単純なリストで構成している。そのため、1ディレクトリーに多数のファイルやディレクトリーが含まれると、参照が非常に遅くなる場合があった。ext3以降はhtreeというデータ構造が採用されて、参照の速度は改善されている。