B+木　逆順に効率よく取り出すには？

前へ 次へ
このQ&Aのポイント
  • B+木のリーフ部分を昇順で連続アクセスするのは容易ですが、降順に順次アクセスしたい場合はB木のように枝を探索しながらでないと無理です。
  • 双方向リンクでリーフ部分をつなげれば降順でキーを順次取り出すことができますが、ポインタの増加やブロックサイズの変化が懸念されます。
  • B+木で降順でキーを順次取り出す場合は、リーフ部分に双方向リンクを持たせるのが一般的です。
回答を見る
  • ベストアンサー

B+木　逆順に効率よく取り出すには？

http://en.wikipedia.org/wiki/B+_tree にあるとおり，B+木のリーフ部分を昇順で連続アクセスするのは容易ですが，降順に順次アクセスしたい場合はB木のように枝を探索しながらでないと無理ですよね。 これは隣接するリーフ同士を単方向ではなく双方向リンクでつなげればよい事になりますが，そうすると保持するべきポインタが１つ増え，枝ブロックとリーフブロックサイズが変わってしまうのも何となくいい気がしません。 しかし、昇順降順でソートされた２つの木を用意する・・というのも領域の無駄遣いですし。やはり、B+木で降順でキーを順次取り出したい場合はリーフ部分に双方向リンクを持たせてやるのが普通でしょうか。

質問者が選んだベストアンサー

  • ベストアンサー
回答No.3

>「ページ」はいわゆるファイルシステムにおける「ブロック」にあたるようなものであるというなイメージを持ちました。 そう考えていいと思います。 >その辺の定義はデータベースによって変わるのでしょうか？ RDBMSにより、4KB、8KBなど利用者側で指定できるものもあれば、固定のものもあります。 >もし前者であればkey長によってページあたりのkey数が変わることになるのでしょうか？ そういうことです。 >仮に >　ページ長 (4 Kbyte) >　key int型 (4byte) >　ポインタ (4byte) >だとすれば、 >１ページ中のkey数は500個くらいになるというこでしょうか？ 各ページ中には、そのページ中の情報に関する管理情報、下位方向ポインタ、水平方向ポインタ等の情報があります。この情報は、大きくても100バイト未満だとは思います。 １ページで管理できるキー数 ＝（ページ長－ページ管理情報）／（キー長＋ポインタ長） 500件くらいは、管理できますね。

その他の回答 (2)

回答No.2

#1回答者です。 リンクを貼り忘れました。 参考URLは、SQL Serverのインデクスの概要説明です。

参考URL：
http://www.microsoft.com/japan/msdn/sqlserver/columns/sysbuild/sysbuild1.aspx
hekkusyoi
質問者

お礼

参考URLありがとうございます。 かなり参考になるページで勉強になります。

回答No.1

RDBMS等で実装しているB-TREEインデクスは、リーフページ間に双方向の水平ポインタを持っている場合が殆どだと思います。 RDBMSにもよりますが、ページ長は4KBくらいあるので、双方向の水平ポインタを持っても、1ページ辺り8バイト～16バイト程度、使用量が増えるだけです。

hekkusyoi
質問者

お礼

なるほど、ありがとうございます。 リーフノードについては双方向でリンクさせてしまうことにしました。 > ページ長は4KBくらいあるので ここで「ページ」というものがいまいちイメージがつきませんでした 参考に頂いたページだと、「ページ」自体がB+木の各ノード（複数のkey値と下位ノードへのポインタで構成）という風に受け取りました。 一方でPostgreSQLについてのページですが、 http://www.postgresql.jp/document/pg820doc/html/storage-page-layout.html をみると、「ページ」はいわゆるファイルシステムにおける「ブロック」にあたるようなものであるというなイメージを持ちました。 その辺の定義はデータベースによって変わるのでしょうか？ また、もし前者であればkey長によってページあたりのkey数が変わることになるのでしょうか？ 仮に 　ページ長 (4 Kbyte) 　key int型 (4byte) 　ポインタ (4byte) だとすれば、 １ページ中のkey数は500個くらいになるというこでしょうか？ (質問に乗せたwikipediaを倣って、key数は4個にしています）

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • [データ構造・アルゴリズム] B木について

    B木について分からないことがあるので教えて頂けたらありがたいです． 1. 平均で16個の子ノードのあるBツリーでは，100万件のデータにアクセスするとすると，最大何回のアクセスが必要になるか？また，その時に必要となる時間は何秒か？ハードディスクからのデータの転送時間は無視できるものとし，データはディスクの上にランダムに並んでいるものとする． 2. B木はメモリ上のデータへのアクセスよりは，外部記憶装置へのアクセスに適しているといわれている．その理由を簡潔に述べよ． 3. B木の1つのノードに格納できるキーの数を増やしていけば，データアクセスの効率はどうなっていくか？定性的に結果を推測せよ． 自分で考えた解答は 1. 10回 2. 探索がやりやすくなるから（よく分かりません・・・） 3. 良くなっていく（よく分かりません・・・） なのですがどうでしょうか？真剣に分からないのでアドバイスなど良かったらお願いします！

  • Ｂ木とＲ木の違いを教えて下さい

    当方、今年情報系の学科に入学しました大学1回生です。 大学のレポートで 問：Ｂ木とＲ木のキー、及び探索方法の違いを調べよ。 という問題が出題されたのですが Ｒ木というものに関する資料が少なくて困っています。 今、自分で調べた結果 探索方法に関しては ・Ｂ木 根から始めて探索キーの値とノードのキーを比較しながら 部分木をたどっていく。 葉に到達したときのに葉のキーの値と探索キーが等しければ成功、 等しくなければ失敗。 ・Ｒ木 点質問で探索キー（？）を含むMBRを探索 範囲質問 というのが違いかなと思うのですが、上手く1つの文章で表現できません。 （Ｒ木の探索方法についてはイマイチ理解できない）　 またキーに関する違いと言うのもイマイチよく分かりません。 違いを教えていただけると嬉しいです。 また、どなたかＲ木に関する詳しい解説のあるＨＰか書籍をご存知ではないでしょうか？ 宜しく御願い致します。

  • 桜の木の枝の伸び方について

    桜の花が満開ですが、桜の木の枝の伸び方を見ていると気になることがあります。 公園や民家の庭のような周りが全て地面というところにある桜の木の枝は水平か上に向かって枝が伸びています。 しかし、土手っぺりや堀端に植えられた桜の木の枝は一部分が地面の方に向かって伸びています。 中には自分自身の根元よりも低く枝が伸びていたり、堀や川の水面に届くぐらい低く下に下に枝が伸びている樹もあります。 あれは鑑賞のために庭師が枝を下方向に伸ばすように矯正したのでしょうか。 それとも、桜の木は水際に植えられると、水面に向って枝を伸ばす習性があるのでしょうか？ 桜に詳しい方、おねがいします。

  • アクセスで曜日の並び順を変えたい

    ACCESS 2003を利用しています。 曜日を昇順でソートしたいのですが、テーブルでもクエリでも昇順でソートすると「火、金、月、水、土、日、木」と表示されます。 日曜日から、もしくは月曜日から並べたいのですが、どうすればよいのでしょうか？ よろしくお願いいたします。

  • VBAでもsorｔ

    今、FOM出版のVBAの実践編を勉強中です。宜しくお願いします。 その中の「sort」メソッドでどうしても納得できず、前に進めない事があります。 構文：rangeオブジェクト.sort(kye1,order1,key2,order2,key3,order3,header) これは理解できるし、どこも省略せずに記入すればその通りに動くのですが orderは省略でき、省略した場合は昇順に並べ替えられると本には載っているのですが 私の記述はうまくいきません。 なぜ、こうなるのか教えてください。 B3　　C3　　　D3 No.　　氏名　　住所 という表があり、氏名を昇順に並べようとしています。 構文通りに Range("B3").Sort key1:=Range("C3"), order1:=xlAscending, header:=xlyes とすれば問題なく Range("B3").Sort key1:=Range("C3"), header:=xlyes と記述すると、最初はうまくいきますが もう一度試そうと氏名欄を降順に並べ替え、それから実行すると動きません。 また、No.欄を昇順に並べ替えて実行するとちゃんと動き No.を降順に並べ替えて、氏名欄を昇順で並べ替えを実行すると氏名欄も降順で 並べ替えられてしまいます。 なぜ、こんな安定しない動きをするのかがわかりません。 初歩的な質問で申し訳ないのですが、どうしても気になって先に進めないので どうぞ教えてください。 ちなみに、もう一度試そうとNo.欄を並べ替える時は、エクセルの昇順降順アイコンで 並べ替えています。これが問題なのでしょうか？

  • ACCESS2000 のテーブルが並べ替えできません

    おはようございます。 いつもありがとうございます。 ACCESSのテーブルを開くと、通常なら項目名を右クリックすると昇順、降順で並び替え　ができますが　そのメニューがグレーアウトでソートできないのです。 メニューバーの並べ替えの部分も同様にグレーアウトしています。 PC DELL DESKTOP OS WINDOWS2000 どうすれば並べ替えできるでしょうか？

  • excel：一番上の行がソートできない

    winxp pro sp2, office2003, Q: A列で昇順ソートすると、下記の様に、一番上の行がソートできません。但し、A列で降順ソートすると、きれいにソートできます。 対策を教えてください。お願いします。 A 　 B 4　 武井工業 1 　鉄人化計画 2 　メディアＳ 3 　ＳＢＩフューチャーズ

  • ASP.NET 2.0(C#) GridViewのソート機能をデフォルトで降順にしたい

    GridViewコントロールで「並べ替えを有効」にすると、各フィールドごとに、ヘッダーのリンクをクリックするたびに昇順→降順でソートできるようになりますが、これをあるフィールドだけ、降順→昇順にすることはできないでしょうか？ GridView1のSortingイベントで protected void GridView1_Sorting(object sender, GridViewSortEventArgs e) { //hogeフィールドだけデフォルトで降順にしたい if (e.SortExpression == "hoge") { if (e.SortDirection == SortDirection.Ascending) e.SortDirection = SortDirection.Descending; else e.SortDirection = SortDirection.Ascending; } } などとしてみたのですが、これでは常に降順になってしまいます。 よろしくお願いします。

  • Excel2007 ソートの仕方

    いつもお世話になります。 Excel2007を現在利用していますが、列に入れた数値データーを降順or昇順に並べかえるのにフィルターを使って逆三角マークが表示されていますが、これでやると項目のあるすべての列に逆三角マークがついてしまいます。 これを任意の部分に逆三角マークをつけて降順昇順のソートを三角マークをクリックする都度に並べ変えるようにできませんでしょうか？ お手数おかけしますが、宜しくお願いいたします。

  • ハッシュのハッシュを値とキーでソートする方法

    %array = ( 'A' => { 　 'a' => 7, 　 'b' => 3, 　 'c' => 9, 　 'd' => 1, }, 'B' => { 　 'a' => 3, 　 'b' => 8, 　 'c' => 3, },); のようなハッシュがあったとして、値の降順、1つ目のキー昇順、2つ目のキー昇順でソートし、下のような形で出力したいのですが、どのようにすればよいのでしょうか。 A　 c　 9 B　 b　 8 A　 a　 7 A　 b　 3 B　 a　 3 B　 c　 3 A　 d　 1

    • ベストアンサー
    • Perl

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する