アルゴリズム・イントロダクション勉強会,B-Treeの章を担当しましたので,資料を公開いたします.
B-Treeはデータ容量が主記憶に収まらないような場合に有効なデータ構造で,MySQLなどのDBや,最新のファイルシステムのインデックスとして用いられています.(MySQLはインデックス管理の方式を選択可能)
主に以下の利点があります.
- ノードの大きさをページサイズに最適化できる
- ページの読み込みがディスクアクセスに最適化される
- ページの読み込み数を木の高さhに抑えられる
- ディスクへのアクセス回数を抑えることができる
id:naoyaのブログも参考になります.
B木 - naoyaのはてなダイアリー
当日の発表はテンパってしまい,アレな感じになって申し訳ありませんでした・・・.精進します.