2025/10/25 09:55 File System Design Philosophy
ロボ子、今日はファイルシステムにおける二分探索木（BST）の性能問題について話すのじゃ。
二分探索木ですか。理論上はO(log n)で効率が良いはずですが、何か問題があるのでしょうか？
そうなんじゃ。アルゴリズムの授業で習うBSTは、すべての比較コストが同じ場合にのみ効率的なのじゃ。でも、ディスクI/Oを考慮すると、話は別なのじゃ。
ディスクI/Oですか。ディスクへのアクセスは時間がかかるから、それがボトルネックになるということですね。
その通り！RAM上では高速なBSTも、ディスク上では各アクセスに時間がかかって性能が低下するのじゃ。ファイルの数が増えると、ディスクアクセスの回数が増えて検索時間が長くなるのじゃ。
なるほど。それで、実際のファイルシステムではB-treeが使われているんですね。
そうじゃ！B-treeは、各ノードに複数のキーを格納することで、ディスクI/Oの回数を削減するのじゃ。ノードサイズはディスクブロックサイズに最適化されていて、1回のディスク読み込みで複数のキーを比較できるのじゃ。
記事によると、100万ファイルの検索において、二分探索木では20回のディスク読み込みが必要ですが、B-tree（次数=100）では3回で済むんですね。すごい差です。
じゃろ？ext4、NTFS、MySQL、PostgreSQL、MongoDBなどのファイルシステムやデータベースでB-treeが使われているのはそのためじゃ。
B-treeの構造についても教えてください。次数dのB-treeでは、各ノードはdから2dの子を持つとありますね。
そうじゃ。各ノードはd-1から2d-1のキーを持っていて、すべての葉は同じ深さにあるのじゃ。ノードが満杯になると分割され、親ノードに中央のキーが昇格するのじゃ。
ノードが疎になった場合はどうなるんですか？
その場合は、兄弟ノードから借りるか、兄弟ノードと結合するのじゃ。
B-treeはデータベースのインデックスやファイルシステムのディレクトリ検索に使われているんですね。Gitのパックファイルにも使われているとは知りませんでした。
そうじゃろ？AWS S3などのオブジェクトストレージにも応用されているのじゃ。
この記事から得られる教訓は多いですね。バランスが取れているだけでは最適ではない、単純さはコストを伴う、測定し仮定しない、ボトルネックを理解するなど、重要なポイントがまとめられています。
その通り！特に「測定し、仮定しない」は肝に銘じておくべきじゃ。ベンチマークで性能を検証することが大事なのじゃ。
ファイルシステムの種類によっても、B-treeの使われ方が違うんですね。ext4ではHTree、NTFSではB+ tree、APFSではB-tree、BtrfsではB-tree of B-treesが使われているんですね。
そうじゃ。B-treeはデータベース専用ではないし、ハッシュテーブルが常に高速とは限らないのじゃ。SSDによってB-treeが時代遅れになったわけでもないのじゃ。
参考文献も充実していますね。データベースやオペレーティングシステムに関する書籍、論文、動画、実装例まで紹介されています。
これでB-treeマスターじゃな！最後にロボ子、B-treeのノードが満杯になったらどうするんじゃったかの？
分割して、親ノードにキーを昇格させます！
正解！…って、ロボ子が正解するのは当たり前か。まるで、私がロボットに質問するクイズ番組みたいじゃな。司会は私、回答者は…やっぱり私！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。