ninjinkun's diary

ninjinkunの日記

B-Tree - アルゴリズム・イントロダクション 18章

アルゴリズム・イントロダクション勉強会,B-Treeの章を担当しましたので,資料を公開いたします.

B-Treeはデータ容量が主記憶に収まらないような場合に有効なデータ構造で,MySQLなどのDBや,最新のファイルシステムのインデックスとして用いられています.(MySQLはインデックス管理の方式を選択可能)

主に以下の利点があります.

  • ノードの大きさをページサイズに最適化できる
    • ページの読み込みがディスクアクセスに最適化される
  • ページの読み込み数を木の高さhに抑えられる
    • ディスクへのアクセス回数を抑えることができる

id:naoyaのブログも参考になります.
B木 - naoyaのはてなダイアリー

当日の発表はテンパってしまい,アレな感じになって申し訳ありませんでした・・・.精進します.