アルゴリズムとデータ構造勉強会 B＋tree.

Presentation on theme: "アルゴリズムとデータ構造勉強会 B＋tree."— Presentation transcript:

1 アルゴリズムとデータ構造勉強会 B＋tree

2 B+木 多量のデータの移動を避ける方法として、B木の内部節点にレコードのキーだけを格納することができる。
これらの節点には、別の場所に保存された実際のデータレコードを指すポインタだけを格納する。 プログラムによってバケットを再配列する場合でも、レコードのキーとポインタだけを移動すればよく、レコード全体を移動する必要がなくなる。 この種のB木をB+木と呼ぶ。 B木については前回の輪講資料を参考 子節点へのポインタ キー ポインタ データ データへのポインタ データ データ キー ポインタ キー ポインタ

3 B+木の利点 B+木の節点に格納される要素サイズを小さくすれば、プログラムは各節点にそれだけ多くのキーを格納することが可能になる。
同じサイズの節点に対して、木の次数を上げることができ、それによって木の高さを低くすることができる。 B+木は複数のキーをレコードのセットに関連付けることが容易にできる。

4 B+木のプログラム 別紙参照 挿入のみ、２次のB+木 根節点の分割が起こる時点で終了 構造
Key　（このプログラムではage をkeyとした） ポインタ Name　(名前） Age　（年齢） Address　（住所） キー（age) ポインタ Name(名前） Age　（年齢） Address　（住所）

5 プログラムの動作確認（１） <初期状態> saino@bass[~]%./b+tree2-24
Q:insert node ? yes: input 1 // no: input other 3 　　　　　　　　　　　　　　　　 ROOT<22#67# 0# 0> 　　　　 ________________________________________| 　　| 　 | 　 | 　 | 　　　 / 　　　　　　 _____________________________　| 　| 　| 　| 　　　 / 　　　　　 / 　　　　　　___________________| 　　| 　| 　　　 / 　　　　　 / 　　　　　　 / 　　　　 　 ________| 　 | 　 　　　 /B_ 　　　　 /B_ 　　　　　 /B_ 　　　 /B_4 　　　 |B_5 < 9#14#20# 0> <23#45# 0# 0> <77#112# 0# 0> < 0# 0# 0# 0> < 0# 0# 0# 0> Q:print ? yes: input 1 // no: input other 1 ROOT.b[0]:Daisuke,22,Fukuoka ROOT.b[1]:Mike,67,Hawaii B_1.[0]:Wong,9,HongKong B_1.[1]:Kent,14,London B_1.[2]:Youngman,20,Tokyo B_2.[0]:Ann,23,New York B_2.[1]:Bill,45,Paris B_3.[0]:Lucky,77,Rome B_3.[1]:Oldman,112,Okinawa

6 プログラムの動作確認（２） 挿入するデータ <データの挿入>
Q:insert node ? yes: input 1 // no: input other 1 name = Kitano age = 50 address = Cannes 　　　　　　　　　　　　　　　 ROOT<22#67# 0# 0> 　　　 　 ________________________________________| 　 | 　 | 　| 　| 　　 　　　 / 　　　　　　 _____________________________| 　| 　| 　 | 　　　 / 　　　　　 / 　　　　　 ___________________| 　 | 　| 　　　 / 　　　　　 / 　　　　　　 / 　　　　 ________| 　| 　　　 /B_ 　　　　 /B_ 　　　　　 /B_ 　　　 /B_ 　　　 |B_5 < 9#14#20# 0> <23#45#50# 0> <77#112# 0# 0> < 0# 0# 0# 0> < 0# 0# 0# 0> Q:print ? yes: input 1 // no: input other 1 ROOT.b[0]:Daisuke,22,Fukuoka ROOT.b[1]:Mike,67,Hawaii B_1.[0]:Wong,9,HongKong B_1.[1]:Kent,14,London B_1.[2]:Youngman,20,Tokyo B_2.[0]:Ann,23,New York B_2.[1]:Bill,45,Paris B_2.[2]:Kitano,50,Cannes B_3.[0]:Lucky,77,Rome B_3.[1]:Oldman,112,Okinawa 挿入するデータ

7 プログラムの動作確認（３） 挿入するデータ この時点で バケットが一杯 <バケットの分割> name = Rui
age = 13 address = Vienna　　　 　　　　　　　　　　　　　　　 ROOT<22#67# 0# 0> 　　　　________________________________________| 　 | 　| 　| 　| 　　　　 / 　　　　　 _____________________________| 　 | 　| 　| 　　　　 / 　　　　 / 　　　　　　 ___________________|　 | 　 | 　　　　 / 　　　　 / 　　　　　　 / 　　　　 　________|　 | 　　　　 /B_ 　　　 /B_ 　　　　　 /B_ 　　　 /B_4 　　　　 |B_5 < 9#13#14#20> <23#45#50# 0> <77#112# 0# 0> < 0# 0# 0# 0> < 0# 0# 0# 0> Q:print ? yes: input 1 // no: input other 1 ROOT.b[0]:Daisuke,22,Fukuoka ROOT.b[1]:Mike,67,Hawaii B_1.[0]:Wong,9,HongKong B_1.[1]:Rui,13,Vienna B_1.[2]:Kent,14,London B_1.[3]:Youngman,20,Tokyo B_2.[0]:Ann,23,New York B_2.[1]:Bill,45,Paris B_2.[2]:Kitano,50,Cannes B_3.[0]:Lucky,77,Rome B_3.[1]:Oldman,112,Okinawa 挿入するデータ この時点で バケットが一杯

8 プログラムの動作確認（４） 挿入するデータ 中間キーを新たに加える 分割 !! <バケットの分割> name = Shinji
age = 17 address = Amsterdam　　　　 　　　　　　　　　　　　　　 ROOT<14#22#67# 0> 　　　 ________________________________________| 　| 　 | 　| 　 | 　　　 / 　　　　　 _____________________________| 　| 　| 　 | 　　　 / 　　　　　 / 　　　　　 ___________________| 　| 　 | 　　 　　　 / 　　　　　 / 　　　　　 / 　　　　　 ________| 　 | 　　　 /B_ 　　　　 /B_2 　　　　 /B_3 　　　　 /B_ 　　　 |B_5 < 9#13# 0# 0> <17#20# 0# 0> <23#45#50# 0> <77#112# 0# 0> < 0# 0# 0# 0> Q:print ? yes: input 1 // no: input other 1 ROOT.b[0]:Kent,14,London ROOT.b[1]:Daisuke,22,Fukuoka ROOT.b[2]:Mike,67,Hawaii B_1.[0]:Wong,9,HongKong B_1.[1]:Rui,13,Vienna B_2.[0]:Shinji,17,Amsterdam B_2.[1]:Youngman,20,Tokyo B_3.[0]:Ann,23,New York B_3.[1]:Bill,45,Paris B_3.[2]:Kitano,50,Cannes B_4.[0]:Lucky,77,Rome B_4.[1]:Oldman,112,Okinawa 挿入するデータ 中間キーを新たに加える 分割　!!