トップ > テック > B木の構造の整理

B木の構造の整理

テック テック-その他

個人開発したアプリの宣伝
目的地が設定できる手帳のような使い心地のTODOアプリを公開しています。
Todo with Location

Todo with Location

  • Yoshiko Ichikawa
  • Productivity
  • Free

スポンサードリンク

ノードページの構造

ページバッファに整列済みのデータを配置

{ 40 }
{ 40, 63 }
{ 24, 40, 63 }
{ 24, 40, 58, 63 }

ページの分割

バッファが溢れた時、ページの分割を行う。

{ 24, (+ 31), 40, 58, 63 }
     ┏ {40} ┓
{ 24, 31} {58, 63 }

さらにデータを追加

B木では常に下のページから挿入を行う。

     ┏ {40} ┓ <- 8, 72
{ 24, 31} {58, 63 }
       ┏ {40} ┓
{ 8, 24, 31} {58, 63, 72 }

最下層ページを再び分割

       ┏ {40} ┓<- 42
{ 8, 24, 31} {58, 63, 72, 80}
       ┏ {40} ┓
{ 8, 24, 31} {(42), 58, 63, 72, 80}
           {40,      63} 
{ 8, 24, 31} {42, 58}, {72, 80}

親ページを分割

親、子共にページのバッファが溢れた場合、子->親の順で分割する。

{ 40,63, 80, 105}  <- 45
 ┗  { 8, 24, 31} 
 ┗  {42, 47, 50 58}, 
 ┗  {72, 79},
 ┗  {91, 97, 103}, 
 ┗  {113, 122}

子ページも満杯

{ 40, 63, 80, 105}
 ┗  { 8, 24, 31} ,
 ┗  {42, 47, 50 58},   <- 45
 ┗  {72, 79},
 ┗  {91, 97, 103}, 
 ┗  {113, 122}

子ページを分割

{ 40, (47), 63, 80, 105}
 ┗  { 8, 24, 31} ,
 ┗  {42, 45},
 ┗  {50, 58},
 ┗  {72, 79},
 ┗  {91, 97, 103}, 
 ┗  {113, 122}

親ページを分割

{63}
 ┗ {40, 47},
    ┗  { 8, 24, 31} ,
    ┗  {42, 45},
    ┗  {50 58}
 ┗ {80, 105}
    ┗  {72, 79},
    ┗  {91, 97, 103}, 
    ┗  {113, 122}
B+木について

B+木はすべてのデータが最下層のデータに格納されているようにする。