Download presentation
Presentation is loading. Please wait.
1
B+Treeのバケットサイズ
2
ハードディスク読み込み時の特性 ハードディスクは適当なブロック単位でデータを読み込む。そのブロック単位は512バイトまたは1024バイト（または2の階乗で作られる適当なサイズ）である。 そのため、1バイトを読み込むのに要する時間とそのブロックを読み込むのに要する時間は変わらない。
3
バケットサイズの選択 ディスクの特性を利用するには、バケットのサイズをディスクの読み込み単位の整数倍にし、出来るだけ多くのレコードやキーをそのサイズに詰め込む。 （例）バケットサイズが2048バイトで、80バイトのキーを使ったB+Treeを構築する場合 24個のキーと25個のポインタ（ポインタは4バイトと過程）をバケットに詰め込むことが出来る。 24× ×4 = 2020バイト
4
B-TreeとB+Treeの比較 B-Treeでは、内部nodeにレコード全体を格納する nodeに格納される要素サイズが大きい
同じバケットサイズにデータを格納する場合、 B+Treeのほうが多くのキーを格納できる。 B+Treeの方が木の次数を高くすることができ、 ディスクアクセス回数は少なくなる。
Similar presentations
