(57)【要約】【課題】  単体ディスクブロックの空間に対して、単体内部ノードのデータ量が小さい場合に、単体ディスクブロック内の空間を効率的に利用する。【解決手段】  本発明は、整数列入力装置から入力された整数列からＢ＋木索引を生成し、複数の内部ノードを単体ディスクブロックに割り当て前記Ｂ＋木索引記憶手段に書き込む。このとき、Ｂ＋木索引を該Ｂ＋木索引の内部ノードの高さ毎に分割し、同じ高さｉに属する各内部ノードを複数の組ｊに分解し、データベース処理に必要な情報と複数のミニディスクブロックへのオフセット情報をディスクブロックの先頭にヘッダとして格納し、該ディスクブロック内のｋ番目のミニディスクブロックのヘッダに探索に必要な情報を書き込み、該ｋ番目の内部ノードの組の情報を該ｋ番目のミニディスクブロックに格納する。【選択図】  図７
2013149097.tif 000002
【特許請求の範囲】
【請求項１】
整数列から任意の整数を探索する処理を高速化するために構造化されたＢ＋木索引の内部ノードをディスクに格納するＢ＋木のディスク記録方法であって、
Ｂ＋木索引初期化手段、ディスクブロック書き出し手段、Ｂ＋木索引記憶手段、探索キー処理手段、ディスクブロック探索手段と、を有する装置において、
前記Ｂ＋木索引初期化手段が、整数列入力装置から入力された整数列からＢ＋木索引を生成するＢ＋木索引初期化ステップと、
前記ディスクブロック書き出し手段が、複数の内部ノードを単体ディスクブロックに割り当て、前記Ｂ＋木索引記憶手段に書き込むディスクブロック書き出しステップと、を行い、
前記Ｂ＋木索引初期化ステップにおいて、
前記Ｂ＋木索引を該Ｂ＋木索引の内部ノードの高さ毎に分割し、同じ高さｉに属する各内部ノードを複数の組ｊに分解し、
データベース処理に必要な情報と複数のミニディスクブロックへのオフセット情報をディスクブロックの先頭にヘッダとして格納し、該ディスクブロック内のｋ番目のミニディスクブロックのヘッダに探索に必要な情報を書き込み、該ｋ番目の内部ノードの組の情報を該ｋ番目のミニディスクブロックに格納する
ことを特徴とするＢ＋木のディスク記録方法。
【請求項２】
前記探索キー処理手段が、
探索キー入力装置から入力された探索キーが、前記整数列入力装置から入力された前記整数列に含まれているかを判定し、含まれている場合には、該探索キーの位置情報を出力する探索キー処理ステップと、
前記ディスクブロック探索手段が、前記Ｂ＋木索引記憶手段から前記位置情報に対応するディスクブロックを読み出し、該ディスクブロックのヘッダに基づいて、探索キーに対応する前記単体ディスクブロック内の複数のミニディスクブロックのオフセットまで移動し、
前記Ｂ＋木索引記憶手段から前記位置情報に対応するディスクブロックがない場合は、前記整数列が前記探索キーと同じ値か否かを調べその結果を出力するディスクブロック探索ステップと、
を更に行う請求項１記載のＢ＋木のディスク記録方法。
【請求項３】
コンピュータに、
請求項１または２に記載のＢ＋木のディスク記録方法の各ステップを実行させるためのＢ＋木のディスク記録プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｂ＋木のディスク記録方法及びプログラムに係り、特に、整数列から任意の整数（探索キー）を探索する処理を高速化するために構造化されたＢ＋木索引の内部ノードをディスクへ格納するためのＢ＋木のディスク記録方法及びプログラムに関する。
【背景技術】
【０００２】
探索キーを探索する処理において、探索対象となる整数列は昇順に並んでおり、その整数列から探索キーと同じキー値を持つ整数が存在するかの判定を行う。探索処理は、Ｂ＋木の最上位に位置するROOTノードから順にノード内の比較キーと探索キーの比較処理を繰り返し、木の中間位置に存在する内部ノードを通過し、探索キーに対応する整数列内への位置情報を計算し、最終的に探索キーの整数列内の有無を判定する。
【０００３】
Ｂ＋木索引の例を図１に示す。同図において、「３１」の探索キーが入力された場合を考える。まず、内部ノードａの中に含まれる比較キー集合（２３，７１，…）と探索キーを比較し、次に探索を行うべき内部ノードの決定を行う。ここでは、"２３＜３１＜７１"と判断され、「２３」と「７１」の間にあるポインタが選ばれ、次に探索を行うべき内部ノードは「ｃ」ということになる。内部ノードｃでも同様の処理が行われ、内部ノードがなくなるまでこの処理を続けることで整列列内への位置情報の計算を行う。
【０００４】
古くからディスクへの書き出しを前提に設計されたデータベースでは、その内部に含まれる論理的コンテンツ（表ファイル、索引、ユーザデータ等）は、ディスクへの読み書きの単位である「ディスクブロック」（一般的に４KiBや８KiB程度の連続領域のデータ）に格納される。整数列の中から目的の値を高速に探索するためのデータ構造であるＢ＋木索引（例えば、非特許文献１参照）も同様で、この単体ディスクブロックに内部ノードの１つが対応付けられることが一般的である（例えば、非特許文献２参照）。
【０００５】
上記の図１の内部ノードａを単一のディスクブロックに対応付けた場合の例を図２に示す。ディスクブロックのヘッダにはデータベースが利用するための情報（ロックや、ログ管理情報など）が格納され、その後続に内部ノードの比較キー集合を書き込む。比較キーは、可変長であることも考慮し（この例では整数であるため固定長）、可変長の比較キーをディスクブロックの後方位置から先頭位置に向けて連続的に書き出し、これらの比較キーへの（ディスクブロック先頭からの）固定長のオフセット情報を、ヘッダ情報の直後から連続的に格納する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】R. Bayer and E. M. McCreight: Organization and maintenance of large ordered indexes, SIGFIDET Workshop, p107-141, 1970.
【非特許文献２】G. Graefe: Modern B-tree techniques, p1-88, March 17, 2011, 8 PM.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、CPUの性能向上（キャッシュ効率やCPUアクセス効率など）の観点からＢ＋木索引の内部ノードに含まれる比較キーの個数が制限される場合がある。この際、図３に示すように、単体ディスクブロック内に空き領域が多く取られてしまい空間効率が非常に悪くなる。
【０００８】
本発明は、上記の点に鑑みなされたもので、B+木索引内部ノードの比較キー個数が制限され、単体ディスクブロックの空間に対して、単体内部ノードのデータ量が小さい場合に発生する空間効率の課題を解決し、単体ディスクブロック内の空間を効率的に利用することが可能なＢ＋木のディスク記録方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記の課題を解決するため、本発明（請求項１）は、整数列から任意の整数を探索する処理を高速化するために構造化されたＢ＋木索引の内部ノードをディスクに格納するＢ＋木のディスク記録方法であって、
Ｂ＋木索引初期化手段、ディスクブロック書き出し手段、Ｂ＋木索引記憶手段、探索キー処理手段、ディスクブロック探索手段と、を有する装置において、
前記Ｂ＋木索引初期化手段が、整数列入力装置から入力された整数列からＢ＋木索引を生成するＢ＋木索引初期化ステップと、
前記ディスクブロック書き出し手段が、複数の内部ノードを単体ディスクブロックに割り当て前記Ｂ＋木索引記憶手段に書き込むディスクブロック書き出しステップと、を行い、
前記Ｂ＋木索引初期化ステップにおいて、
前記Ｂ＋木索引を該Ｂ＋木索引の内部ノードの高さ毎に分割し、同じ高さｉに属する各内部ノードを複数の組ｊに分解し、
データベース処理に必要な情報と複数のミニディスクブロックへのオフセット情報をディスクブロックの先頭にヘッダとして格納し、該ディスクブロック内のｋ番目のミニディスクブロックのヘッダに探索に必要な情報を書き込み、該ｋ番目の内部ノードの組の情報を該ｋ番目のミニディスクブロックに格納する。
【００１０】
また、本発明（請求項２）は、前記探索キー処理手段において、
探索キー入力装置から入力された探索キーが、前記整数列入力装置から入力された前記整数列に含まれているかを判定し、含まれている場合には、該探索キーの位置情報を出力する探索キー処理ステップと、
前記ディスクブロック探索手段が、前記Ｂ＋木索引記憶手段から前記位置情報に対応するディスクブロックを読み出し、該ディスクブロックのヘッダに基づいて、探索キーに対応する前記単体ディスクブロック内の複数のミニディスクブロックのオフセットまで移動し、
前記Ｂ＋木索引記憶手段から前記位置情報に対応するディスクブロックがない場合は、前記整数列が前記探索キーと同じ値か否かを調べその結果を出力するディスクブロック探索ステップと、を更に行う。
【発明の効果】
【００１１】
本発明では、ディスクへの書き出しを前提とした固定長のディスクブロックを有効活用するために、このディスクブロックをＮ個の仮想的なミニブロックに分割し、単体ディスクブロックに格納可能なＢ＋木索引内の内部ノード数を拡大させることにより、CPU性能向上（キャッシュ効率やCPUアクセス効率など）の観点から内部ノードに含む比較キーの個数を少なくする（つまり単体ディスクブロックの余剰空間が大きくなる）場合において、単体ディスクブロック内の空間を効率的に利用することが可能となり、結果的にＢ＋索引の総サイズが小さくなる効果が得られる。
【図面の簡単な説明】
【００１２】
【図１】データベースシステムでよく用いられる索引Ｂ＋木を示す図である。
【図２】従来技術におけるディスクブロック内へのＢ＋木ノード格納方式を示す図である。
【図３】ディスクブロック内の余剰領域を示す図である。
【図４】本発明の一実施の形態における装置構成図である。
【図５】本発明の一実施の形態におけるディスクブロック内の仮想ディスクブロック（ミニブロック）である。
【図６】本発明の一実施の形態におけるミニブロック適用例である。
【図７】本発明の一実施の形態におけるＢ＋木索引初期化部のフローチャートである。
【図８】本発明の一実施の形態におけるＢ＋索引内のＮ個の内部ノード組への分解である。
【図９】本発明の一実施の形態におけるディスクブロック構成モジュールのフローチャートである。
【図１０】本発明の一実施の形態における探索キー処理部のフローチャートである。
【発明を実施するための形態】
【００１３】
以下、図面と共に本発明の実施の形態を説明する。
【００１４】
図４は、本発明の一実施の形態における装置構成図である。
【００１５】
同図に示す装置は、Ｂ＋木索引初期化部１１、ディスクブロック書き出し部１２、Ｂ＋木索引記憶部１３、ディスクブロック探索部１４、探索キー処理部１５から構成され、Ｂ＋木索引初期化部１１には、整数列入力装置２０が、探索キー処理部１５には探索キー入力装置３０及び結果出力装置４０が接続されている。
【００１６】
探索キーの高速な探索処理を行うために、B+索引初期化部１１は、入力された整数列に対してB+木索引の作成を行う。B+索引初期化部１１では、整数列入力装置２０から入力された、昇順並び替え済みのＢ＋木索引作成対象整数列に対して、まず、既存技術と同様の方法でＢ＋木索引の作成を実行する。
【００１７】
次に、ディクスブロック書き出し部１２は、B+木索引内の各内部ノードを単体ディスクブロック内に図２のように配置していく。この際、従来手法のように単体内部ノードを、単体ディスクブロックに割り当てるのではなく、図５、図６に示すように複数（Ｎ個）の内部ノードを単体ディスクブロックに割り当てることが本発明の特徴である。
【００１８】
これ以降、単体ディスクブロック内に含まれるＮ個の固定長の領域を「ミニディスクブロック」と呼ぶ。
【００１９】
探索キー処理部１５は、探索キー入力装置３０から入力された探索キーに基づいてＢ＋木索引記憶部３１を検索し、整数列入力装置２０から入力された整数列内に含まれているかどうかを判定し、その位置情報を返す。
【００２０】
探索の際には、Ｂ＋木索引記憶部１３のB+木索引内の内部ノードに含まれる比較キーと、探索キー入力装置３０から入力された探索キーを比較して、次に探索すべき内部ノードを判定し、"ポインタ"を辿り次の内部ノードへと移動する。この際、従来手法では、ポインタとして（ディスクブロック番号）を用いていたが、本発明では、単体ディスクブロック内に複数の内部ノードが含まれているため、ポインタとして｛ディスクブロック番号，ミニディスクブロック番号｝の組をポインタとして利用する。次に探索すべき内部ノードへのポインタが決定した後、ディスクブロック探索部１４は、当該ポインタが指し示すディスクブロックを読み出し、そのディスクブロックのヘッダに含まれる情報を利用して目的のミニディスクブロックに移動する。
【００２１】
この処理を繰り返すことで目的の整数の探索を行う。
【００２２】
次に、B＋木索引初期化部１１の処理を詳細説明する。
【００２３】
図７は、本発明の一実施の形態におけるＢ＋木索引初期化部の動作のフローチャートである。
【００２４】
ステップ１００）  Ｂ＋木索引初期化部１１は、整数列入力装置２０から昇順の整数列の入力を待機する。
【００２５】
ステップ１０５）  整数列入力装置２０から入力された整数値に対して、従来技術と同様の手法によりＢ＋木索引を作成する。
【００２６】
ステップ１１０）  作成したＢ＋木索引を図８に示すように、Ｂ＋木索引の内部ノードの高さ毎に分割し、同じ高さに所属する各内部ノードをＮ個（１つのディスクブロックに含まれる内部ノードの数）ずつの組に分解する。
【００２７】
ステップ１１５）  ｉを値１で初期化（ｉ＝０）する。
【００２８】
ステップ１２０）  高さｉに所属するＮ個ずつにまとめられた内部ノードを全て取得し、高さｉに所属する内部ノード集合を出力する。
【００２９】
ステップ１２５）  ｊを値１で初期化（ｊ＝０）する。
【００３０】
ステップ１３０）  高さｉに所属する内部ノード集合の中から、ｊ番目の内部ノードの組を取得し、ｊ番目のＮ個の内部ノードの組を出力する。
【００３１】
ステップ１３５）  ディスクブロック構成モジュールを利用することで、ｊ番目のＮ個の内部ノードの組を単体ディスクブロックに書き出す。Ｎ個の内部ノードでＮ個のミニブロックを構成し、それらのミニブロックをディスクブロック内に配置することで単体ディスクブロックを作成する。当該ディスクブロック構成モジュールについては、図８で詳述する。
【００３２】
ステップ１４０）  ｊに１を加算し（ｊ＝ｊ＋１）、ｊが高さｉに対する内部ノードの総数Ｓ以下である場合にはステップ１３０に移行する。
【００３３】
ステップ１４５）  ｉに１を加算（ｉ＝ｉ＋１）し、ｉがＢ＋木の高さＨ以下であればステップ１２０に移行する。ｉがＨより大きければ当該Ｂ＋木索引初期化部１１の処理を終了する。
【００３４】
次に、上記のステップ１３５のディスクブロック構成モジュールの処理について説明する。
【００３５】
図９は、本発明の一実施の形態におけるディスクブロック構成モジュールのフローチャートである。
【００３６】
ステップ２００）  B＋木索引初期化部１１内のディスクブロック構成モジュールは、高さｉのｊ番目の組の内部ノード集合を受け取る。
【００３７】
ステップ２０５）  データベース処理に必要な情報とＮ個のミニディスクブロックへのオフセット情報をディスクブロックの先頭にヘッダとして格納する。
【００３８】
ステップ２１０）  ｋを値１で初期化（ｋ＝１）する。
【００３９】
ステップ２１５）  ディスクブロック内のｋ番目のミニディスクブロックのヘッダに探索に必要な情報（内部ノードの比較キー数など）を書き込む。
【００４０】
ステップ２２０）  ｋ個目の内部ノードの組、ｋ番目のミニディスクブロックを入力とし、図２の従来の手法に併せて、ｋ個目の内部ノードの組の情報をｋ番目のミニディスクブロックに格納する。
【００４１】
ステップ２２５）  ｋに１を加算（ｋ＝ｋ＋１）する。
【００４２】
ステップ２３０）  ディスクブロック書き出し部１２は、上記の処理が完了したディスクブロックをＢ＋木索引記憶部１３に書き込む。
【００４３】
次に、探索キー処理部１５の処理について説明する。
【００４４】
図１０は、本発明の一実施の形態における探索キー処理部の動作のフローチャートである。
【００４５】
ステップ３００）  探索キー処理部１５は、探索キー入力装置３０からの探索キーの入力を待機する。
【００４６】
ステップ３０５）  ディスクブロック探索部１４は、Ｂ＋木索引記憶部１３からROOTノードを含むディスクブロックを読み出す。なお、ROOTノードと同じ高さには他にノードが存在しないため、ディスクブロック内には１つのミニディスクブロックしか存在しない。
【００４７】
ステップ３１０）  探索キー処理部１５は、探索キー入力装置３０から入力された探索キー及び、ディスクブロック探索部１４により探索されたディスクブロック（ミニディスクブロック）を取得し、ミニディスクブロック内に含まれる比較キーと、入力された探索キーを比較することで、次に探索を行うべき内部ノードを決定し、次に探索を行うミニディスクブロックへのポインタをディスクブロック探索部１４に出力する。
【００４８】
ステップ３１５）  ディスクブロック探索部１４は、探索キー処理部１５から渡されたポインタ内に含まれるディスクブロック番号に対応するディスクブロックをＢ＋木索引記憶部１３から読み出す。読み出すディスクブロックがない場合はステップ３２５に移行し、存在する場合はステップ３２０に移行する。
【００４９】
ステップ３２０）  ディスクブロック探索部１４は、Ｂ＋木索引記憶部１３から読み出されたディスクブロックのヘッダに含まれる情報を利用して、ポインタ内で指定された番号のミニディスクブロックまで移動し、ステップ３１０の処理に戻る。
【００５０】
ステップ３２５）  探索キー処理部１５は、探索された整数値が探索キーと同じ値かどうかを調べ、もし同じ値である場合は、その整数値に対応した列内のポインタを、結果出力装置４０に出力する。異なる値の場合には、『整数列に探索キーと同じ値はない』と出力し、ステップ３００に移行する。
【実施例】
【００５１】
以下に、上記の実施の形態の処理について具体的に説明する。
【００５２】
合計で２24個の整数列に対してＢ＋索引を構成する場合を前提に、CPU性能の観点から単体ノードに含むことのできる比較キーの数を２8個に限定する場合を考える。
【００５３】
この２8個の比較キーと、それらと対応するポインタから構成される内部ノードのサイズは約２KiBであるため、単体ディスクブロックのサイズを８KiBと考えた場合、Ｂ＋索引の総サイズは約514MiBである（２24個から構成される木構造を２8個ずつに分割した場合、その分割個数は総計65,793個であるため、65,793*8KiBで計算される）。ここで、本発明のミニディスクブロック（ｎ＝３）を適用した場合、その総サイズは約171MiBとなり、約66%の空間節約が可能となる。
【００５４】
上述のように、ディスクブロックをＮ個の仮想的なミニブロックに分割し、単体ディスクブロックに格納可能なＢ＋木索引内の内部ノード数を拡大させたことにより、ディスクへの書き出しを前提とした固定長のディスクブロックを有効活用することが可能となる。
【００５５】
上記の、図７、図９、図１０に示すフローチャートの動作をプログラムとして構築し、上記の処理を行うコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５６】
本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５７】
１０  マシン
１１  Ｂ＋木索引初期化部
１２  ディスクブロック書き出し部
１３  Ｂ＋木索引記憶部
１４  探索キー処理部
１５  ディスクブロック探索部
２０  整数列入力装置
３０  探索キー入力装置
４０  結果出力装置
【図１】
2013149097.tif 000003
【図２】
2013149097.tif 000004
【図３】
2013149097.tif 000005
【図４】
2013149097.tif 000006
【図５】
2013149097.tif 000007
【図６】
2013149097.tif 000008
【図７】
2013149097.tif 000009
【図８】
2013149097.tif 000010
【図９】
2013149097.tif 000011
【図１０】
2013149097.tif 000012