昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ

Linux は fork で子プロセスを作成した場合、親の仮想メモリ空間の内容を子へコピーする必要があります。しかしまともに全空間をコピーしていたのでは fork のコストが高くなってしまいますし、子が親と同じようなプロセスとして動作し続ける場合は、内容の重複したページが多数できてしまい、効率がよくありません。 そこで、Linux の仮想メモリは、メモリ空間を舐めてコピーするのではなく、はじめは親子でメモリ領域を共有しておいて、書き込みがあった時点で、その書き込みのあったページだけを親子で個別に持つという仕組みでこの問題を回避します。Copy-On-Write (CoW) と呼ばれる戦略です。共有メモリページは、親子それぞれの仮想メモリ空間を同一の物理メモリにマッピングすることで実現されます。より詳しくは コピーオンライト - Wikipedia などを参照してください。 この CoW に