質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.98%

  • MySQL

    5115questions

    MySQL(マイエスキューエル)は、TCX DataKonsultAB社などが開発するRDBMS(リレーショナルデータベースの管理システム)です。世界で最も人気の高いシステムで、オープンソースで開発されています。MySQLデータベースサーバは、高速性と信頼性があり、Linux、UNIX、Windowsなどの複数のプラットフォームで動作することができます。

  • PostgreSQL

    869questions

    PostgreSQLはオープンソースのオブジェクトリレーショナルデータベース管理システムです。 Oracle Databaseで使われるPL/SQLを参考に実装されたビルトイン言語で、Windows、 Mac、Linux、UNIX、MSなどいくつものプラットフォームに対応しています。

  • データベース

    627questions

    データベースとは、データの集合体を指します。また、そのデータの集合体の共用を可能にするシステムの意味を含めます

  • MongoDB

    227questions

    MongoDBはオープンソースのドキュメント指向データベースの1つです。高性能で、多くのリトルエンディアンシステムを利用することができます。

B+木の挿入について

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 180

hositaka

score 4

イメージ説明
↑の初期状態のB+木に[23 B]と[31 C]を挿入↓
イメージ説明
その後、[24 D]と[25 E]を挿入↓
イメージ説明
その後、[29 F]を挿入↓
イメージ説明
という問題があって、
①上記のように解いたのですがあっておりますでしょうか?
学校の教材やインターネットでB+木について調べても正誤判定が自分ではできないです。
また、②2番目の画像の中間ノードには31の隣に34を入れたほうがよろしいでしょうか?
③最後の画像の右側の中間ノードに34を入れたうえで根ノードには右側に34を入れるべきでしょうか?
ご回答ご回答宜しくお願い致します。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

0

結論から言いますと、正しくないようです。

参考:B+Tree Insertions

B+木は、索引部とデータ部が分かれているデータ構造で、データは末端ノードで管理されます。初期状態の図が課題の図だとすると、四角で表されているのがノードで、丸四角で表されているのがデータと思います。ここで、末端ノードと索引ノードの区別が必要と思います。

今回は、同じ構造を末端ノードと索引ノードとして使用しているようです。この四角の構造を見てみると、インデクス値を格納できる場所が2つ、ポインタを格納できる場所が3つの構造になっています。この構造の使われ方は、末端ノードと索引ノードで違っています。

末端ノードとして使うときは左から順に

  • 未使用、または1つ目のデータへのポインタ
  • 1つ目のデータのインデクス値
  • 未使用、または2つ目のデータへのポインタ
  • 2つ目のデータのインデクス値
  • 未使用、または次の末端ノードへのポインタ

索引ノードとして使うときは左から順に

  • 未使用、または1つ目の子ノードのインデクス値よりも小さい子ノードへのポインタ
  • 1つ目の子ノードの最小インデクス値
  • 未使用、または1つ目の子ノードへのポインタ
  • 2つ目の子ノードの最小インデクス値
  • 未使用、または2つ目の子ノードへのポインタ

おそらく、回答は以下のような形だろうと思います。たたし、分割時のロジックはいろいろ流派があるようです。ここではYouTubeの例のようにシンブルに1/2に分け、二つ目ノードのインデクス値で親ノードを作る方法にしました。
初期状態

[34,]


[23 B]を挿入(部屋が空いてるのでそのまま格納)

[23, 34]


[31 C]を挿入(オーバーしたので分割し、親ノードを生成)

   [31,]
[23,][31, 34]


[24 D]を挿入(部屋が空いてるのでそのまま格納)

    [31,]
[23,24][31, 34]


[25 E]を挿入(オーバーしたので分割し、親ノードにインデクス追加)

     [24,31]
[23,][24, 25][31, 34]


[29 F]を挿入(配置換えによるインデクス更新)

       [25,31]
[23,24][25, 29][31, 34]

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/23 11:31

    難しいですね。ご回答ありがとうございました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.98%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    xcodeでの画面サイズ変更方法

    swiftでサンプルコードを写しているのですが、参考書を今まで放置してたのでxcodeのバージョンが違うので画面サイズ変更の方法がわからないです。 simulatorでの表示画面

  • 解決済

    Blender Game Engineでマテリアルを透過したい

    Blenderでゲーム開発をしようとしているものです。 Blender Renderで透過処理したマテリアルをBlender Gameに反映させたいと思っているのですが、透過でき

  • 解決済

    ACCESS クエリでの一部重複?の除外方法について

    前提・実現したいこと こんにちは、質問タイトルが適格でないかもしれませんが宜しくお願いいたします。 通販事業をしており、商品の仕入から販売までのデータベースをACCESSの

  • 受付中

    この場合キャッシュが効くのか

    キャッシュが効いているのかわかりません headerにCache-Control=no-cacheを指定しているがETagやLast-Modifiedを指定しない場合、

  • 解決済

    GAS(google apps script)で一つのスプレッドシート内にある複数のスクリプトの挙動...

    GASに詳しい方、教えていただけますと助かります。 表題の件、一つのスプレッドシートに対してスクリプトが複数あってそれぞれに同じトリガーを設定している場合、そのトリガーが入っ

  • 受付中

    ER図について

    つぶやきアプリを作っているのですが、 ER図を作るとする例えばどんなものがありますか?? サンプル程度でいいので教えていただきたいです

  • 解決済

    pycharmのpython console部分の色の変更

    プログラムには関係ないんですが・・・ 長時間PCの画面を見てると目が疲れてしまうので、色を変えてみようと思って 色を変更してみたのですが、python consoleの部分の色

  • 解決済

    vb2017でexcel2016操作

    vb2017を使っています。 communityです。 excel2016を開いてセルのデータを読み込みたいと思っています。 参考にしているサイトです。 http://d.

同じタグがついた質問を見る

  • MySQL

    5115questions

    MySQL(マイエスキューエル)は、TCX DataKonsultAB社などが開発するRDBMS(リレーショナルデータベースの管理システム)です。世界で最も人気の高いシステムで、オープンソースで開発されています。MySQLデータベースサーバは、高速性と信頼性があり、Linux、UNIX、Windowsなどの複数のプラットフォームで動作することができます。

  • PostgreSQL

    869questions

    PostgreSQLはオープンソースのオブジェクトリレーショナルデータベース管理システムです。 Oracle Databaseで使われるPL/SQLを参考に実装されたビルトイン言語で、Windows、 Mac、Linux、UNIX、MSなどいくつものプラットフォームに対応しています。

  • データベース

    627questions

    データベースとは、データの集合体を指します。また、そのデータの集合体の共用を可能にするシステムの意味を含めます

  • MongoDB

    227questions

    MongoDBはオープンソースのドキュメント指向データベースの1つです。高性能で、多くのリトルエンディアンシステムを利用することができます。