JP2874810B2 - キーの記憶割り当て方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データベース検索のた
め、二次記憶装置上に木構造インデックスを構築する際
のキーの記憶割り当て方法に係り、特にインデックスノ
ードのキー格納効率向上、ひいてはデータベース検索の
高速化に好適なキー記憶割り当て方法に関する。

【０００２】

【従来の技術】ここでは、ＶＳＡＭデータベースを例に
説明する。ＶＳＡＭ（ＶirtualＳtorage Ａccess Ｍeth
od；仮想記憶アクセス方式）は、データ管理プログラム
の内の一つのアクセス技法であり、外部記憶装置である
磁気ディスク装置と仮想記憶装置内のプログラムとのデ
ータのやり取りを行うもので、外部記憶装置の物理的属
性から独立するように、その記憶形式が設計されてい
る。図５に示すように、ＶＳＡＭでは、複数個のレコー
ドからなるコントロールインタバル（ＣＩ）を単位とし
て、磁気ディスク装置とメモリ間で入出力データの転送
が行われる。更に、ＶＳＡＭでは、連続した領域にある
複数個のＣＩの集合であるコントロールエリア（ＣＡ）
を単位にして管理し、ＣＡは磁気ディスク装置上の連続
した領域（エクステント）に割り付けられる。ＶＳＡＭ
データセットはＶＳＡＭを介して処理するレコードの集
合である。

【０００３】ＶＳＡＭデータセットの編成法の一つにキ
ー順データセット（Ｋey ＳeqencedＤata Ｓet；ＫＳＤ
Ｓ）がある。このデータセットは、キー（例えば、社員
番号、年齢等）の昇順にレコードが順序付けられてい
て、レコードの取りだしを高速に行うためのインデック
スを持っている。

【０００４】インデックスは、木構造を用いて作成され
る。木構造とは、図６に示すように、根を上に葉を下に
して構成され、Ａ，Ｂ，Ｃ，．．．Ｊ，Ｋをノード
（節）といい、根以外のノードは上位のノードに接続さ
れ、末端のノード（Ｃ，Ｅ，Ｆ，Ｇ，Ｉ，Ｊ，Ｋ）を葉
という。

【０００５】図７は、ＶＳＡＭにおける木構造インデッ
クスを示し、最下位のインデックスレコードの集まりで
あるシーケンスセットと、それよりも一つ上のレベルの
インデックスレコードの集まりであるインデックスセッ
トからなる階層構造となっている。図中における各箱は
前述したＣＩを示している。

【０００６】図８は、ＫＳＤＳのデータセット構成図で
ある。シーケンスセットにおけるインデックスレコード
は、一つのＣＡ対応に作成され、ＣＡを構成する各ＣＩ
内のレコードの最高キーと、それに対応する各ＣＩへの
ポインタ（垂直ポインタ）が格納されている。この最高
キーと垂直ポインタのペアをインデックスエントリとい
う。一方、インデックスセット内のインデックスレコー
ドは、一つ下位にある複数のインデックスレコードを管
理し、それらのインデックスレコード内の最高キーと、
それに対応する各インデックスレコードへのポインタ
（垂直ポインタ）を持っている。さらに、シーケンスセ
ット、インデックスセットとも、同レベルの次につづく
インデックスレコードへのポインタ（水平ポインタ）を
持っている。

【０００７】キーによってレコードを検索する場合に
は、最上位のインデックスから垂直ポインタをたどって
シーケンスセットのＣＩを探す。このＣＩは一つのＣＡ
内のレコードを指しているので、そのポインタをたどる
ことによってレコードを検索する。また、キー順処理の
場合は、シーケンスセットを使用し、ＣＡ内の最高キー
を処理した後、次のＣＡに移るとき、シーケンスセット
の水平ポインタをたどっ次のシーケンスセットを読み込
み、キー順にレコードをアクセスする。

【０００８】上記したデータセット編成法は、レコード
の挿入、削除処理が頻繁に行われても、インデックスを
動的に再配置することで、データセットのどのレコード
に対しても平均的な処理効率が保証される（つまり、イ
ンデックスセットからシーケンスセットを経てレコード
に至るどのルートにおいても、そのアクセス時間にバラ
ツキがない）。このような木構造インデックスをＢ＋‐
treeという。

【０００９】

【発明が解決しようとする課題】上述のような木構造イ
ンデックス（Ｂ＋‐tree）を磁気ディスク装置等の二次
記憶装置上に構築する場合、通常、ノードの大きさと、
キーを格納する領域の大きさを固定長としている。この
ため、データ中に一つでも長いキーがある場合、ノード
内の各キー格納領域の大きさをそれに合わせて確保しな
ければならず、短いキーが格納される領域については、
その記憶領域が無駄になってしまうという問題があっ
た。

【００１０】また、１ノード中に格納されるキーの数
は、ノード内に確保されるキー格納領域の大きさで決ま
り、一つでも長いキーがあると、１ノードに格納される
キー数は削減される。一方、インデックスの階層数は、
１ノードに格納されるキー数が減少すると、逆に増加す
る（一般にインデックスの階層数は１ノードのキー格納
エントリ数を底とした対数で表わされる）。一般に、イ
ンデックスを持つデータベースの検索においては、イン
デックスが最も頻繁にアクセスされるものである。そし
て、このインデックスへのアクセス回数の多少はインデ
ックスの階層数に依存するため、階層数が増加すると、
データベース検索の高速化の点で問題がある。

【００１１】更に、１ノード中に格納されるキーの数
は、前述したように木の分岐数となるので、ノードの大
きさに対してキーの格納領域をあまり大きく確保するこ
とができず、このためノード長を越えるような長さのキ
ーを処理することができないという問題があった。

【００１２】本発明の目的は、二次記憶装置上に多分岐
の木構造インデックスを構築する際、インデックスノー
ドのキー格納効率の向上を図り、その結果としてデータ
ベース検索の高速化も可能になるキーの記憶割り当て方
法を提供することにある。

【００１３】

【課題を解決するための手段】前記目的を達成するため
に、本発明は、それぞれが垂直ポインタ部とキー部とか
らなる複数のキー格納部をインデックスノードとして、
二次記憶装置上に木構造インデックスを構築する際、イ
ンデックスノードのキー部には、キー先頭から所定長ま
でのキー部分（キー先頭部分）と、該キー先頭部分以外
の部分（キー後尾部分）を格納する領域の位置を示すポ
インタと、該キー先頭部分とキー後尾部分とからなるキ
ー全体の長さを示すキー長とを格納し、インデックスノ
ード以外の前記ポインタが示す領域に、キー後尾部分を
格納するようにしたことを特徴とする。

【００１４】

【実施例】以下、本発明の一実施例を図面を用いて具体
的に説明する。図２は、本発明が適用されるデータ処理
装置のブロック構成図を示し、キーボード、マウス等か
らなる入力装置２１、中央処理装置２２Ａと主記憶装置
２２Ｂからなるデータ処理装置２２、後述する入出力ブ
ロックが記憶されている二次記憶装置２３、処理された
情報を表示するための表示装置２４、処理された情報を
記憶印刷するためのプリンタ２５から構成されている。

【００１５】図１は、本発明に係る二次記憶装置２３上
に木構造インデックスを構築する際のキーの記憶割り当
てを説明する図である。Ｂ＋‐treeのノード（ＶＳＡＭ
のコントロールインタバル，ＣＩ）１４は、複数のキー
格納部からなり、それぞれがキー１やキー２と垂直ポイ
ンタ１５からなり、各キーは、キー長１６と、ポインタ
１７とキー先頭部１８からなっている。キー長１６に
は、キー全体の長さが格納され、キー先頭部１８は、ノ
ードに格納されたキーの先頭部分を表し、ノードに格納
されないキーの後尾部分は、ポインタ１７で指示された
入出力ブロックに格納される。

【００１６】入出力ブロックは、前（低位のアドレス）
からブロック管理領域１０、キースロット領域１１、空
き領域１２、キー記憶領域１３の順に配列構成されてい
る。ブロック管理領域１０には、入出力ブロックの空き
領域１２の長さを表す空き長さデータ記憶領域１０Ａ
と、空き領域１２の先頭位置を表す空き先頭アドレス記
憶領域１０Ｂと、空き最終位置を表す空き最終スロット
領域１０Ｃからなっている。キースロット領域１１に
は、ノードに全てを格納できない各キーについて、入出
力ブロック中に格納されるキー後尾部分のキーの長さ
（第１キー長、第２キー長等）とその格納位置（第１キ
ー位置、第２キー位置等）が記憶されている。この第１
キー長と第１キー位置を合わせた長さをスロット長とい
う。そして、キー記憶領域１３には、入出力ブロックの
最後（高位のアドレス）から前の方に順に、それぞれキ
ー後尾部分の第１キー１３Ａ、第２キー１３Ｂ，第３キ
ー１３Ｃが記憶されている。このように、本実施例で
は、一つの入出力ブロック中には複数個のキーが格納さ
れる。

【００１７】このように構成された本発明の入出力ブロ
ックは、以下のようにして管理される。すなわち、 （１）キーは入出力ブロックの最後から順に、可変長領
域に割り当てられて格納される。 （２）スロットは、オーバーフローしたキー後尾部分の
キー長とキー位置（つまり入出力ブロックの先頭からの
オフセット）のペアからなり、各キーが管理される。 （３）スロットは入出力ブロックの先頭から確保され
る。 （４）レコードが削除されてそのレコードのキーを削除
する場合は、スロットは空きスロットとなり（空きスロ
ットマークを付ける）、キー記憶領域１３は後につめら
れる。 （５）ノードからキーを指すために張るポインタ１７
は、キーを直接指さずに、そのキーを管理しているスロ
ットを指しているので、削除処理によってキーを削除し
てもスロットを空きスロットにするだけで、キーを指す
ポインタを張り変える必要がない。 （６）Ｂ＋‐treeは、一つの木の中に同じキーが複数回
現われるが、これらの同一のキーは１ヶ所に格納共用さ
れ、重複することはない。

【００１８】図３は、本実施例のキー格納領域確保の処
理を表すフローチャートである。すなわち、この処理
は、Ｂ＋‐treeに新しくレコードを挿入する際に、キー
の長さがノード内の固定長領域より長い場合に、キー格
納用のブロックに領域を確保して、ノードに格納できな
いオーバーフローしたキーの後尾部分を該領域中に入れ
る処理である。

【００１９】ブロック管理領域１０のデータ記憶領域１
０Ａに示される空き長さが、“オーバーフロー部分のキ
ー長＋スロット長”以上あるか否かをステップ３０１で
判断し、“オーバーフロー部分のキー長＋スロット長”
以上ある場合は、ステップ３０２に、そうでない場合
は、ステップ３０５に進む。“オーバーフロー部分のキ
ー長＋スロット長”以上ある場合は、ステップ３０２
で、空きスロットマークの付いたスロットが調べられ、
空きスロットマークの付いたスロットがないときには、
ブロック管理領域１０の最終スロット領域１０Ｃを変更
してスロットを確保し、次いでステップ３０３で、ブロ
ック管理領域１０の空き先頭アドレス記憶領域１０Ｂを
変更して、キー格納領域を確保し、ステップ３０４で入
出力ブロックの空き領域１２を変更する。

【００２０】ステップ３０１で、ブロック管理領域１０
のデータ記憶領域１０Ａに示される空き長さが、“オー
バーフロー部分のキー長＋スロット長”に満たない場合
は、ステップ３０５で、他の入出力ブロックを生成し
て、前記したステップ３０１からステップ３０４と同様
にしてキー格納領域を確保する。

【００２１】図４は、本実施例のキー格納領域解放処理
のフローチャートである。レコードが削除されてそのレ
コードのキーを削除するときは、ステップ４０１で削除
されるキー（例えば、図１の第２キーとする）より前に
あるキー（図１の第３キー）を全て後に移動することに
よって、当該キーを削除し、ステップ４０２に進む。ス
テップ４０２では、移動したキーを管理するスロットの
キー位置を変更し、次いでステップ４０３では、空き領
域１２の長さを表す空き長さデータ記憶領域１０Ａの長
さを、削除したオーバーフロー部分のキー長分だけ増加
し、ステップ４０４では、削除されたキーのスロットに
空きスロットマークを付けて処理を終了する。

【００２２】

【発明の効果】本発明のキーの記憶割り当て方法によれ
ば、次のような効果が得られる。 (１) 長さが異なるキーをインデックスノードへ高効率
に格納でき、インデックスノード内に空き領域が生じる
のを防止できると同時に、インデックス階層数が削減で
きるため、インデックスノードのアクセス回数が減少
し、データベース検索の高速化が実現する。 (２) キーを任意の位置で分割し、ノード外の領域に動
作することにより、可変長キーに対して、システムに最
適な分割キー長をもつインデックスを作成できる。ま
た、インデックスノードに格納できないような長いキー
が存在する場合でも、インデックスを作成できるため、
インデックスノード長をシステムに最適な長さとするこ
とができる。 (３) キー先頭部は必ずインデックスノード内にあるた
め、このインデックスノード内のキー先頭部だけを参照
することによって検索することも可能である。このた
め、二次記憶アクセスにおけるデータベース検索の高速
化を更に図ることができる。 (４) 任意の１ケのキーＫｊが、あるインデックスノー
ド内で最高キーの場合、当該ノードから最下位置までの
各階層に必ずキーＫｊが１ケ現れるが、これらＫｊ出現
ノードにおいても「キーＫｊ分割後後尾部分長×キーＫ
ｊ出現回数」すなわち「全キーについて、Σ（キーＫｊ
分割後後尾部分長×キーＫｊ出現回数）」の領域削減が
でき、さらにインデックスノードへの格納効率向上が図
れる。

【図面の簡単な説明】

【図１】本発明に係るキーの記憶割り当て方法を説明す
る図である。

【図２】本発明が適用されるデータ処理装置のブロック
構成図である。

【図３】本実施例のキー格納領域確保処理のフローチャ
ートである。

【図４】本実施例のキー格納領域解放処理のフローチャ
ートである。

【図５】ＶＳＡＭにおけるファイル構成図である。

【図６】木構造の例を示す図である。

【図７】ＶＳＡＭにおける木構造インデックスを示す図
である。

【図８】ＫＳＤＳのデータセット構成図である。

【符号の説明】

１０ ブロック管理領域 １１ キースロット領域 １２ 空き領域 １３ キー記憶領域 １４ Ｂ＋‐treeのノード １５ 垂直ポインタ １６ キー長 １７ ポインタ １８ キー先頭部１３Ａ、１３Ｂ、１３Ｃ キー後尾部

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭60−24657（ＪＰ，Ａ) 特開 昭60−129852（ＪＰ，Ａ) 特開 平１−315843（ＪＰ，Ａ) 特開 平２−161541（ＪＰ，Ａ) 特開 平２−216552（ＪＰ，Ａ) 特開 平３−44746（ＪＰ，Ａ) 特開 平３−100742（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁶，ＤＢ名) G06F 12/00

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】 それぞれが垂直ポインタ部とキー部とか
   らなる複数のキー格納部をインデックスノードとして、
   二次記憶装置上に木構造インデックスを構築する際のキ
   ーの記憶割り当て方法において、 前記インデックスノードのキー部に、キーの先頭から所
   定長までのキー部分であるキー先頭部分と、該キー先頭
   部分以外の部分であるキー後尾部分を格納する領域の位
   置を示すポインタと、前記キー先頭部分と前記キー後尾
   部分とからなるキー全体の長さを示すキー長とを格納
   し、 前記ポインタが示す領域に、前記キー後尾部分を格納す
   る、 ことを特徴とするキーの記憶割り当て方法。