基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

アイテック 2020基本情報技術者午前の解説について質問させてください。p280の平成26 秋 FE 問27の解説になります。

 B +木データベースの図の内容がしっくりこないので、質問させていただきました。

3点ごさいます。

1点目は図の1番上の15はインデックス番号のことだと思いますが、下段のマス2つが15の範囲よりも少し右にはみ出しているのが、どういう意味なのか、気になります。

2点目は15の下の箱には、配下のインデックス番号が格納されているのでしょうか？

3点目は中段のインデックス番号7が、再び下段の下に出でくるのかがよくわからないです。

どなたか、教えていただけないでしょうか？

私はアイテックの書籍を持っていませんので、当該の図は正確には分かりませんが、
他の参考書やWebページに出てくる図と類似していると思いますので、推測で説明します。
もし違っているところや不明な点があればまた質問してください。

まず、用語に多少混乱がありますからそれについて述べます。
「インデックス」というのは、（FE試験ドットコムのH26秋問27の解説にあるように）
「データベースに格納されているデータの取出しや並べ替えを高速で行うための仕組み」
のことです（なお、配列の要素を指定する添え字（例えば a[5] における 5）なども
インデックスと呼ぶことがありますが、これとは意味が違います）。
書籍の索引や英語の辞書もまさにインデックスであり、この場合、キーワードである
単語がアルファベット順に並べられているので、手作業でも（二分探索のような要領で）
比較的素早く引くことができます。
英語の個々の単語や上記質問中の 15 などは、インデックスという仕組みを用いて
データ（関係データベースの場合はレコード）を検索するための「キー」または
「キー値」であり、インデックス番号とは呼ばれません。

> 1点目は図の1番上の15はインデックス番号のことだと思いますが、下段のマス2つが
> 15の範囲よりも少し右にはみ出しているのが、どういう意味なのか、気になります。

推測される図の一番上の段にある「まとまり」は B+木の「根」に相当します。
根であるこの節点がキー値 15 を持ち、その下に2つのマスがあるのですから、それら
のマスから下方に向かって矢印が2本出ているはずです。
このことは、データベース中に15未満のキー値を持つデータがいくつかと、15以上の
キー値のデータがいくつかあることを意味します。
このとき、15未満のキー値を持ついくつかのデータは左側の矢印によって指し示され
ている節点を根とする部分木によって表現され、15以上のデータは右側の矢印によって
指し示されている節点を根とする部分木により表現されています。
（なお、ここではちょうど15のキー値は右側の部分木に含めると決めたのですが、
左側に含めても特に差し支えはありません。但し統一しないといけません。）
さて、キー値 15 直下のマス2つが 15のマスの範囲よりも少し右にはみ出しているのが
気になるということですが、この理由はキー値を2つ以上持つ節点を考えると明確に
なります。
例えば、この節点が 15 と 36 という2つのキー値を持っている場合には、その下に
3つのマスを用意します。
これら3つのマスは、15未満のキー値を持つデータ、15以上36未満のキー値のデータ、
36以上のキー値のデータ、をそれぞれ指し示すのに使われます。
つまり、この節点からは3つに枝分かれするということです。
このとき、特に真ん中のマスを 15 の真下ではなしに 15 と 36 にまたがるように
配置するのですが、そうしておけば、真ん中のマスが15以上36未満に対応している
ことが分かりやすくなるということです。

> 2点目は15の下の箱には、配下のインデックス番号が格納されているのでしょうか？

15のすぐ下の2つの箱（マス）には、インデックス番号（正確にはキー値）ではなく、
配下の節点への「ポインタ」すなわち「アドレス」が格納されています。
コンピュータは、アドレスが分かれば配下の節点に即座にアクセスできるからです。
例えば、根からその左の子の節点へのポインタをたどる（つまり矢印の方向に進む）
ことにより、15未満のキー値を持つデータの集まりにアクセスできます。

> 3点目は中段のインデックス番号7が、再び下段の下に出でくるのかがよくわからないです。

B+木では、中段や上段などの節点に出てきたキー値も再び最下段（つまり木の「葉」）
に現れるように構成します（古典的なB木ではそのようにはしませんが）。
さらに、隣接する葉をポインタで順にリンクさせます。
この結果、一連の葉の中に全データがキー値の昇順にソートされた形で蓄えられます。
このようなデータ構造にしておけば、「キー値がちょうど15のデータを探せ」と
いうような検索要求だけでなく、「キー値が15以上33以下の全データを探せ」という
「範囲検索」にも容易かつ高速に対応でき、便利だからです。

詳細説明ありがとうございます、内容を確認させていただきます。

画面ショットをアップロードさせていただきました。何かお気づきの点あれば追記ください。

Bツリー：htt  ps://yahoo.jp  
     /box/Yyr7ug

urlは投稿出来るように空白を意図的に入れてます！

図を確認しました。
基本的には前回説明したことに変わりはありませんが、少し補足をしておきます。

> 下段のマス2つが15の範囲よりも少し右にはみ出しているのが、どういう意味・・・
については前回述べた通りですが、この図のように、キー値の並びを上段に、子への
ポインタ（●で表現）を下段に書く流儀以外に、これらを横に並べて (●, 15, ●) 
のように書く表現法もあるようで、後者の方が分かりやすいかもしれません。
（もし 15 と 36 の2つのキー値を持つ場合には、(●, 15, ●, 36, ●) です。）
つまり左の黒丸が15以下のキー値を持つ（インデックス付きの）データ集合への、
右の黒丸が15より大きいキー値をもつデータ集合へのポインタとなります。
（なお、キー値がちょうど15であるデータは、この図の場合、左部分木に属します。
前回の説明とは逆です。）

各節点が持っているポインタの数（出ている矢印の数）はその節点がもつキー値の数
プラス 1 になりますから、この図の流儀のように1つの節点を長方形で表すとすれば、
上段と下段のます目は必然的にずれてきます。
前回述べたように、葉（リーフ）でない節点ではそれが好都合です。
しかし、葉ではこのために逆に分かりにくくなっていますね。
図の左下の葉に含まれる3つの◯は、それぞれキー値 3, 5, 7 に対応するレコード
へのポインタを表しますから、 3, 5, 7 の真下に書くのが適切なのでしょうが、
この図では、ずれてしまっています。

ありがとうございます！葉の部分がなぜ、ズレてるのかモヤモヤしてましたが、有識者の方がおっしゃるのであれば、適切な図ではないんでしょうね。本当にありがとうございます！