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

質問

http://en.wikipedia.org/wiki/B+_tree

にあるとおり，B+木のリーフ部分を昇順で連続アクセスするのは容易ですが，降順に順次アクセスしたい場合はB木のように枝を探索しながらでないと無理ですよね。

これは隣接するリーフ同士を単方向ではなく双方向リンクでつなげればよい事になりますが，そうすると保持するべきポインタが１つ増え，枝ブロックとリーフブロックサイズが変わってしまうのも何となくいい気がしません。

しかし、昇順降順でソートされた２つの木を用意する・・というのも領域の無駄遣いですし。やはり、B+木で降順でキーを順次取り出したい場合はリーフ部分に双方向リンクを持たせてやるのが普通でしょうか。

回答No.3

chukenkenkou · ベストアンサー

>「ページ」はいわゆるファイルシステムにおける「ブロック」にあたるようなものであるというなイメージを持ちました。

そう考えていいと思います。

>その辺の定義はデータベースによって変わるのでしょうか？

RDBMSにより、4KB、8KBなど利用者側で指定できるものもあれば、固定のものもあります。

>もし前者であればkey長によってページあたりのkey数が変わることになるのでしょうか？

そういうことです。

>仮に
>　ページ長 (4 Kbyte)
>　key int型 (4byte)
>　ポインタ (4byte)
>だとすれば、
>１ページ中のkey数は500個くらいになるというこでしょうか？

各ページ中には、そのページ中の情報に関する管理情報、下位方向ポインタ、水平方向ポインタ等の情報があります。この情報は、大きくても100バイト未満だとは思います。

１ページで管理できるキー数
＝（ページ長－ページ管理情報）／（キー長＋ポインタ長）

500件くらいは、管理できますね。

回答No.2

chukenkenkou

#1回答者です。

リンクを貼り忘れました。

参考URLは、SQL Serverのインデクスの概要説明です。

参考URL：

http://www.microsoft.com/japan/msdn/sqlserver/columns/sysbuild/sysbuild1.aspx

お礼

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

回答No.1

chukenkenkou

RDBMS等で実装しているB-TREEインデクスは、リーフページ間に双方向の水平ポインタを持っている場合が殆どだと思います。

RDBMSにもよりますが、ページ長は4KBくらいあるので、双方向の水平ポインタを持っても、1ページ辺り8バイト～16バイト程度、使用量が増えるだけです。

お礼

なるほど、ありがとうございます。
リーフノードについては双方向でリンクさせてしまうことにしました。

> ページ長は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個にしています）