(57)【要約】【課題】B+木索引における挿入処理中に発生する探索処理の同期待ち時間を除去する。【解決手段】B+木索引記憶部に格納されたB+木索引に対する処理を行うB+木索引処理装置が実行するB+木索引処理方法において、前記B+木索引におけるノードにキーを挿入する際に、前記キーを挿入する対象のノードとして特定される対象ノードのコピーである対象ノードコピーを作成し、当該対象ノードコピーに前記キーを挿入し、前記対象ノードの上位ノードのポインタを、一時的に当該対象ノードと同位階層で一方の側に隣接する隣接ノードを参照するようにATOMIC命令を用いて付け替え、前記隣接ノードから前記対象ノードへのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替え、一時的に前記隣接ノードを参照するように付けられた前記上位ノードのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替えるようにする。【選択図】図４
2013242677.tif 000002
【特許請求の範囲】
【請求項１】
B+木索引記憶部に格納されたB+木索引に対する処理を行うB+木索引処理装置が実行するB+木索引処理方法であって、
前記B+木索引におけるノードにキーを挿入する際に、
前記キーを挿入する対象のノードとして特定される対象ノードのコピーである対象ノードコピーを作成し、当該対象ノードコピーに前記キーを挿入し、
前記対象ノードの上位ノードのポインタを、一時的に当該対象ノードと同位階層で一方の側に隣接する隣接ノードを参照するようにATOMIC命令を用いて付け替え、
前記隣接ノードから前記対象ノードへのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替え、
一時的に前記隣接ノードを参照するように付けられた前記上位ノードのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替える
ことを特徴とするB+木索引処理方法。
【請求項２】
前記B+木索引に対して探索キーの探索を行う場合において、
探索処理中に前記B+木索引におけるノードを参照する際に、当該ノードの参照カウンタを加算し、参照を完了する際に当該参照カウンタを減算し、
参照しているノードが前記探索キーの探索のために通過するノードとして正しくないノードである場合に、当該ノードに対して前記一方の側と反対の側に隣接する隣接ノードを参照し、探索を行う
ことを特徴とする請求項１に記載のB+木索引処理方法。
【請求項３】
B+木索引記憶部に格納されたB+木索引に対する処理を行うB+木索引処理装置であって、
前記B+木索引に対して探索キーの探索を行う探索処理手段と、
前記B+木索引におけるノードにキーを挿入する挿入処理手段と、を備え、
前記挿入処理手段は、
前記キーを挿入する対象のノードとして前記探索処理手段により特定される対象ノードのコピーである対象ノードコピーを作成し、当該対象ノードコピーに前記キーを挿入し、
前記対象ノードの上位ノードのポインタを、一時的に当該対象ノードと同位階層で一方の側に隣接する隣接ノードを参照するようにATOMIC命令を用いて付け替え、
前記隣接ノードから前記対象ノードへのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替え、
一時的に前記隣接ノードを参照するように付けられた前記上位ノードのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替える
ことを特徴とするB+木索引処理装置。
【請求項４】
コンピュータを、請求項３に記載のB+木索引処理装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース表内のデータ列（例えばID値など）から特定の値（探索キー）を探す処理を高速化するために構造化されたB+木索引の探索と挿入処理間の同期方式に関するものである。
【背景技術】
【０００２】
B+木索引の探索処理では、最上位に位置するROOTノードから順にノード内の比較キーと探索キーの比較処理を繰り返し、中間位置に存在する内部のノードを通過し、探索キーに対応する最下端ノード（これ以降はリーフと表記）を見つけ、最終的に探索キーがデータ列内に存在するかを判定する。
【０００３】
図１に示すB+木索引の例を用いて、31の探索キーが入力された場合を考える。まずノード1の中に含まれる比較キー集合（27、71、…）と探索キーを比較し、次に探索を行うべきノードの決定を行う。ここでは"27＜31＜71"と判断され、27と71の間にあるポインタが選ばれ、次に探索を行うべきノードは3ということになる。ノード3でも同様の処理が行われ、リーフに到達するまでこの処理を続けることでデータベース表内に探索キーが存在するかを調べる。またデータベース表内のデータ列が挿入された場合、B+木索引も併せてデータを挿入する必要があるため、探索と挿入の処理間で不整合が起こらないように互いの処理を同期的に行う。
【０００４】
データベースで用いられるB+木索引は図１で示すように、リーフにのみデータベース表内のデータ列に対応した値が格納されていて（図１の例では、21、22、…）、それ以上に位置するノードには、それらのリーフまで正しく探索処理が完了できる比較キーを任意に選択した値が格納される。このようなデータ構造により、もしデータベースの表内のデータ列に更新があった場合に、対応するデータを挿入する処理が容易になる効果が得られる。まず挿入の前処理として、データを挿入するリーフの特定を、挿入キーを用いて探索することで行う。その後、特定されたリーフにキーの挿入を行うが、ここで挿入対象のリーフにデータが一杯でリーフの分割が必要である場合と、そうでない場合の処理に分けられる。
【０００５】
まずより簡単なリーフの分割が必要のない場合の挿入処理を図２を用いて説明する。まず、この例ではリーフ7が挿入対象であり、挿入中に他の探索処理が、このリーフを参照できないように排他的なロックを取得する。その後、（１）リーフ7に挿入キー（38）を挿入し、取得したロックを解放して完了となる。その際、（２）他の探索処理がリーフ7を参照した場合、挿入処理が完了するまで探索処理は保留される。
【０００６】
次に、挿入対象のリーフが一杯で分割する必要がある場合を図３を用いて説明する。まず挿入対象のリーフ7と、そのリーフをポイントしている上位のノード3の排他的ロックを取得する。その後、リーフ7を2つに分割（リーフ7とリーフ7′）し、データを2つの分割されたリーフに対して均等に振り分ける。そして、（１）分割して作成したリーフ7′（図３ではリーフ８と表記）に挿入キー（38）を挿入し、取得したロックを解放して完了となる。ここでも分割が発生しない場合と同様に、（２）挿入処理中のノードを参照した探索処理は、それらが完了するまで待ち状態に入る。現在主なデータベース製品（商用/オープンソースともに）は、上記で説明した同期方式を改良した手法を参考に実装されている（非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】P. L. Lehman, and B. Yao: Efficient locking for concurrent operation on B-trees, ACM Trans. Database Syst., Vol. 6, No. 4, pp. 650-670, 1981
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述したように、従来手法の同期方式では挿入処理中に他の探索処理が参照しようとした場合、それらの探索処理は挿入処理が完了するまで待ち状態に遷移してしまうため、挿入処理が発生するような状況でB+木索引に対する時間当たりの探索処理完了数が低下してしまう危険性がある。
【０００９】
本発明は上記の点に鑑みてなされたものであり、B+木索引における挿入処理中に発生する探索処理の同期待ち時間を除去し、B+木索引に対する時間当たりに完了可能な平均探索処理性能を向上させることを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するために、本発明は、B+木索引記憶部に格納されたB+木索引に対する処理を行うB+木索引処理装置が実行するB+木索引処理方法であって、
前記B+木索引におけるノードにキーを挿入する際に、
前記キーを挿入する対象のノードとして特定される対象ノードのコピーである対象ノードコピーを作成し、当該対象ノードコピーに前記キーを挿入し、
前記対象ノードの上位ノードのポインタを、一時的に当該対象ノードと同位階層で一方の側に隣接する隣接ノードを参照するようにATOMIC命令を用いて付け替え、
前記隣接ノードから前記対象ノードへのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替え、
一時的に前記隣接ノードを参照するように付けられた前記上位ノードのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替えることを特徴とするB+木索引処理方法として構成される。
【００１１】
上記B+木索引処理方法において、前記B+木索引に対して探索キーの探索を行う場合は、
探索処理中に前記B+木索引におけるノードを参照する際に、当該ノードの参照カウンタを加算し、参照を完了する際に当該参照カウンタを減算し、
参照しているノードが前記探索キーの探索のために通過するノードとして正しくないノードである場合に、当該ノードに対して前記一方の側と反対の側に隣接する隣接ノードを参照し、探索を行うようにする。
【００１２】
また、本発明は、B+木索引記憶部に格納されたB+木索引に対する処理を行うB+木索引処理装置であって、
前記B+木索引に対して探索キーの探索を行う探索処理手段と、
前記B+木索引におけるノードにキーを挿入する挿入処理手段と、を備え、
前記挿入処理手段は、
前記キーを挿入する対象のノードとして前記探索処理手段により特定される対象ノードのコピーである対象ノードコピーを作成し、当該対象ノードコピーに前記キーを挿入し、
前記対象ノードの上位ノードのポインタを、一時的に当該対象ノードと同位階層で一方の側に隣接する隣接ノードを参照するようにATOMIC命令を用いて付け替え、
前記隣接ノードから前記対象ノードへのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替え、
一時的に前記隣接ノードを参照するように付けられた前記上位ノードのポインタを、前記対象ノードコピーを参照するようにATOMIC命令を用いて付け替えることを特徴とするB+木索引処理装置として構成することもできる。
【００１３】
また、本発明は、上記B+木索引処理装置における各手段として機能させるためのプログラムとして構成することもできる。
【発明の効果】
【００１４】
本発明によれば、B+木索引における挿入処理中に発生する探索処理の同期待ち時間を除去し、B+木索引に対する時間当たりに完了可能な平均探索処理性能を向上させることが可能となる。
【図面の簡単な説明】
【００１５】
【図１】従来技術におけるB+木索引構造を示す図である。
【図２】従来技術におけるB+木索引の挿入処理（リーフが分割されない場合）を示す図である。
【図３】従来技術におけるB+木索引の挿入処理（リーフが分割される場合）を示す図である。
【図４】本発明の実施の形態に係るB＋木索引処理装置４０の機能構成図である。
【図５】本発明の実施の形態に係る挿入処理（１）（リーフが分割されない場合）を示す図である。
【図６】本発明の実施の形態に係る挿入処理（２）（リーフが分割されない場合）を示す図である。
【図７】本発明の実施の形態に係る挿入処理（３）（リーフが分割されない場合）を示す図である。
【図８】本発明の実施の形態に係る挿入処理（４）（リーフが分割されない場合）を示す図である。
【図９】本発明の実施の形態に係る挿入処理（１）（リーフが分割される場合）を示す図である。
【図１０】本発明の実施の形態に係る挿入処理（２）（リーフが分割される場合）を示す図である。
【図１１】本発明の実施の形態に係る挿入処理（３）（リーフが分割される場合）を示す図である。
【図１２】本発明の実施の形態に係る挿入処理（４）（リーフが分割される場合）を示す図である。
【図１３】B+木索引初期化部４１の処理を示すフローチャートである。
【図１４】探索処理部４２の処理を示すフローチャートである。
【図１５】探索処理モジュールの処理を示すフローチャートである。
【図１６】挿入処理部４３の処理を示すフローチャートである。
【図１７】挿入処理部４３の処理（リーフが分割されない場合）を示すフローチャートである。
【図１８】挿入処理部４３の処理（リーフが分割される場合）を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。また、本実施の形態において、リーフ上での探索処理は左リーフから右リーフへの方向でしか発生しないことを前提とするが、この方向は一例である。
【００１７】
（装置構成）
図４に、本発明の実施の形態に係るB＋木索引処理装置４０の機能構成図を示す。図４に示すように、本実施の形態に係るB＋木索引処理装置４０は、B+木索引初期化部４１、探索処理部４２、挿入処理部４３、ロック処理部４４、B+木索引記憶部４５を備える。また、B＋木索引処理装置４０には、DB表内データ列入力装置４６、探索キー入力装置４７、挿入キー入力装置４８、結果出力装置４９が接続される。まず、このように構成されたB＋木索引処理装置４０が実行する処理概要を説明する。
【００１８】
＜B+木索引作成処理概要＞
B+木索引初期化部４１は、探索キーの高速な探索処理に必要な索引を作るために、DB表内データ列入力装置４６から入力されたデータベース表内のデータ列（例えばID値など）に対してB+木索引の作成を行い、作成したB+木索引をB+木索引記憶部４５に記録する。B+木索引記憶部４５に記録されている各B+木ノードは、（挿入処理排他制御用ロック領域、探索処理用参照カウンタ領域、ノード内の比較キー集合領域）の3つのデータ領域を含む。
【００１９】
＜B+木索引探索処理概要＞
探索処理部４２は、作成されたB+木索引に対して、探索キー入力装置４７から入力された探索キーの探索を実行する。他の処理からB+木索引内のノードが参照されているかを判断できるようにするため、探索処理中にB+木索引内のノードを参照する際に参照カウンタに1を加算し、参照が完了する際に参照カウンタから1を減算する。この各ノード内参照カウンタの加減算処理や、この後説明する挿入処理中のノードの排他ロック処理は、B+木索引記憶部４５からノードを読みだす際にロック処理部４４がまとめて行う。なお、探索処理部４２は探索処理モジュールを有し、探索処理モジュールが探索キーの探索を実行する。
【００２０】
＜B+木索引挿入処理概要＞
挿入処理部４３では、挿入キー入力装置４８から入力された挿入キーをB+木索引のリーフに挿入をする。その際従来手法と同じように、リーフの挿入可能データ数を超えない場合、超える場合に分けて処理を行う。リーフの分割が起こらない場合の処理例を図５〜図８に示し、リーフの分割が起こる場合の処理例を図９〜図１２に示すが、これらの図についてはフローチャートを用いた処理詳細説明のところで適宜参照する。
【００２１】
本発明の実施の形態では、一般的なCPU上に実装されているATOMIC命令を利用することを前提としている。ATOMIC命令とは、CPU命令の一種で、他のCPU命令から見て不可分に実行される命令のことである。この命令を利用して、ノード間のポインタの付け替え処理を不可分に行い、探索処理が挿入処理の影響を受けないようすることが目的である。ただし、このATOMIC命令は2つ以上のポインタを同時に（不可分に）付け替えることができない制約があるため、本発明の実施の形態では一時的に上位ノードのポインタの参照先を1つ左のノードを参照する（TEMPORARY ATOMIC LINK UPDATE）ように（図６、図９、図１０等に例が示される）した後、左ノードから挿入対象のノードへのポインタをATOMIC命令で書き換える工夫をしている。
【００２２】
本実施の形態に係るB＋木索引処理装置４０は、CPU及びメモリ等を有するコンピュータに、本実施の形態で説明する処理に対応するプログラムを実行させることにより実現可能である。当該プログラムは、可搬メモリ等の記憶媒体に格納して配布し、上記コンピュータにインストールして用いてもよいし、ネットワーク上のサーバからダウンロードして上記コンピュータにインストールしてもよい。また、本実施の形態で説明する処理をハードウェア回路として実現し、当該ハードウェア回路を備える装置としてB＋木索引処理装置４０を実現してもよい。
【００２３】
なお、B＋木索引処理装置４０は、B+木索引初期化部４１とB+木索引記憶部４５を含まない構成としてもよい。その場合、B＋木索引処理装置４０は、外部に備えられたB+木索引記憶部にアクセスしてB+木索引に対する探索処理や挿入処理を行う。また、その場合の上記プログラムは、探索処理部４２、挿入処理部４３、ロック処理部４４に対応する処理を行うプログラムとなる。また、本実施の形態では、ロック処理部４４を備えるが、この機能を探索処理部４２、挿入処理部４３の各々の中に備えることとしてもよい。
【００２４】
（処理の詳細）
以下、フローチャートを参照しながら各機能部の処理を詳細に説明する。
【００２５】
＜B+木索引初期化部４１＞
まず、B+木索引初期化部４１により実行される処理について図１３のフローチャートを参照して説明する。
【００２６】
ステップS1300）DB表内データ列入力装置４６から昇順に並び替えられたデータベース表内のデータ列が入力されるまで待機する。DB表内データ列入力装置４６から昇順のデータ列が入力されたら当該昇順のデータ列を受け取る。
【００２７】
ステップS1305）DB表内データ列入力装置４６から入力された昇順のデータ列に対して、従来技術通りのB+木索引を作成する。
【００２８】
ステップS1310）入力されたデータ列から作成されたB+木索引をB+木索引記憶部４５に記録する。
【００２９】
＜探索処理部４２＞
次に、探索処理部４２により実行される処理について図１４のフローチャートを参照して説明する。
【００３０】
ステップS1400）探索キー入力装置４７から探索キーの入力があるまで待機し、入力があったらそれを受け取る。
【００３１】
ステップS1405）入力された探索キーを引数に、探索処理モジュールを実行することで、対応するデータベース表内のデータが存在するかの判定を行う。存在する場合、データベース表内のポインタが出力され、存在しない場合、NULLが出力される。
【００３２】
ステップS1410）探索処理モジュールの結果であるデータベース表内のポインタ（もしくはNULL）を結果出力装置４９に出力する。
【００３３】
ステップS1415）リーフ内に含まれている参照カウンタから1を減算する。
【００３４】
続いて、探索処理モジュールの処理を図１５のフローチャートを参照して説明する。
【００３５】
ステップS1500）B+木索引記憶部４５からROOTノードを取り出す。
【００３６】
ステップS1505）探索経路記録のため（挿入処理の際にリーフを参照しているノードを辿るために利用）のスタックを初期化し、入力されたROOTノードをスタックに積む。
【００３７】
ステップS1510）現在ROOTノードを参照していることを、他の処理に知らせるためにROOTノード内に含まれている参照カウンタに1を加算する。
【００３８】
ステップS1515）現在探索しているノード内の比較キーと入力された探索キーを利用して、次に探索を行うノードのポインタを取得する。
【００３９】
ステップS1520）ステップS1515により取得されたポインタに対応するノードをB+木索引記憶部４５から読み出す。
【００４０】
ステップS1523）挿入処理の影響で、探索処理の結果取得されるノードが左にずれることがあるため、これを正しいノードへ修正する必要がある。この影響が発生しているどうかの判定を、現在参照しているノード内に含まれている"判定用の比較キー"を利用して行う（非特許文献１参照）。
【００４１】
ステップS1525）上記の判定により、もしずれていると判定された場合は、右のノードへのポインタを返し、ステップS1520に戻る。
【００４２】
ステップS1530）ステップS1520において取得したノード（参照を開始するノードであり、次に探索を行うノード）をスタックに積み、参照カウンタに１を加算する。
【００４３】
ステップS1535）現在探索をしているノード内に含まれている参照カウンタから1を減算する。
【００４４】
ステップS1538）探索されたノード（上記次に探索を行うノード）が最下端かどうか、すなわち、探索されたノードがリーフかどうかを調べ、最下端でなければステップS1515に戻り、最下端であればステップS1540に進む。
【００４５】
ステップS1540）探索されたノードであるリーフ内に探索キーに対応するデータがあるかを調べ、ある場合はデータベース表内へのポインタを取得し、なければNULLを返却する。
【００４６】
ステップS1545）探索されたノードであるリーフをスタックに積み、リーフ内に含まれる参照カウンタに1を加算する。
【００４７】
＜挿入処理部４２＞
次に、図１６〜図１８を参照して、挿入処理部４３の処理を詳細に説明する。
【００４８】
図１６のステップS1600）挿入キー入力装置４８から挿入キーの入力があるまで待機し、挿入キーの入力があればそれを受け取る。
【００４９】
ステップS1605）入力された挿入キーを引数に、探索処理モジュールを実行することで、挿入を行うリーフの特定を行う。この処理により、探索経路のノードを含んだスタックが得られる。なお、上記探索処理モジュールは、挿入処理部４２が備えるものであってもよいし、探索処理部４２が備える探索処理モジュールを利用してもよい。
【００５０】
ステップS1610）ステップS1605で得られた探索経路のノードを含んだスタックからリーフを取り出す。このリーフが挿入を行うリーフである。
【００５１】
ステップS1615）ロック処理部４４を利用して、挿入を行うリーフ（挿入対象のリーフ）と、そのリーフの左に位置するリーフ（左リーフと表記）のロックを取得する。図５及び図９にこれらロックが取得されたことが示されている。なお、本実施の形態におけるロックは、他の処理からのデータ書き換えやデータ削除を防止するためのロックである。
【００５２】
ステップS1618）ロックが取得されたリーフにおいて、リーフ内の参照カウンタから1を減算する。
【００５３】
ステップS1619）挿入のためにリーフの分割が必要かどうかを判定し、必要であればステップS1620に進み（図１７へ）、必要でなければステップS1675に進む（図１８へ）。
【００５４】
まず、リーフの分割が必要ない場合の挿入処理を図１７のフローチャートを参照して説明する。
【００５５】
ステップS1620）挿入対象のリーフに対して挿入を行うために、リーフのCOPY（対象リーフCOPYと表記）の作成、対象リーフCOPYに対するロックの取得、対象リーフCOPYに対して挿入キーの挿入、対象リーフから対象リーフCOPYへのポインタの作成を行う。これらの処理例が図５に示されている。
【００５６】
ステップS1625）探索経路のノードを含んだスタックから1つ上のノードを取り出す。すなわち、挿入対象のリーフをポイントしているノードを取り出す（図５の例ではノード３）。
【００５７】
ステップS1630）ステップS1625で取得したノードのロックを取得する（図５のノード３におけるロック）。
【００５８】
ステップS1635）ステップS1630においてロックが取得されたノードから挿入対象のリーフへのポインタをATOMIC命令で、一時的に左リーフに付け替える（図６のTEMPORARY ATOMIC LINK UPDATE）。
【００５９】
ステップS1640）左リーフから挿入対象のリーフへのポインタをATOMIC命令で、対象リーフCOPYに付け替えることで、探索処理から挿入キーが挿入された後のB+木索引に見えるようにする（図６のリーフ６からリーフ７´へのポインタ）。
【００６０】
ステップS1645）挿入対象リーフの上位ノードにおいて一時的に付け替えられているノードのポインタ（図6のTEMPORARY ATOMIC LINK UPDATE）を対象リーフCOPYへのポインタに、ATOMIC命令を利用して付け替える（図７のノード３からリーフ７´へのポインタ）。
【００６１】
ステップS1650）ロックが取得されている全ノードについて、取得されたロックを全て解放する。
【００６２】
ステップS1655）挿入前の対象リーフを参照している処理が全てなくなるのを（参照カウンタが0になるまで）待つ。
【００６３】
ステップS1660）挿入前の対象リーフを参照している処理が全てなくなったら、挿入前の対象リーフの右のリーフ（右リーフと表記）へのロックを取得する（図８のリーフ８のロック）。
【００６４】
ステップS1665）ロックが取得された右リーフから挿入前の対象リーフへのポインタを最新の対象リーフCOPYにATOMIC命令で付け替える（図８のATOMIC LINK UPDATE）。
【００６５】
ステップS1670）挿入前の対象リーフを削除して、右リーフのロックを解放する。
【００６６】
以上で、リーフが分割されない場合の挿入処理が終了する。
【００６７】
次に、リーフが分割される場合における図１６から続く挿入処理を図１８のフローチャートを参照して説明する。
【００６８】
ステップS1675）対象リーフに対して挿入を行うために、対象リーフを分割して2つのCOPY（対象リーフCOPY1と対象リーフCOPY 2と表記）を作成する（図９のリーフ７´、リーフ７´´）。この際、挿入対象のリーフに含まれていたデータが分割された先の対象リーフCOPY1/2に均等になるように振り分ける。
【００６９】
ステップS1680）対象リーフCOPY1/2のロックを取得し、相互のポインタの作成、挿入キーの挿入を行う（図９）。
【００７０】
ステップS1685）探索経路のノードを含んだスタックから1つ上のノードを取り出す。最初は挿入対象のリーフをポイントしているノードを取り出すことになる。
【００７１】
ステップS1687）ステップS1685で取り出したノードの下位のノード（リーフを含む）が分割されているか否かを判定し、下位のノードが分割されていればステップS1689に進み、分割されていなければステップS16105に進む。
【００７２】
ステップS1689）ステップS1685で取り出したノードに比較キーを挿入するために、ノードの分割が必要か否かを判定し、ノードの分割が必要であればステップS1690に進み、必要でなければステップS16200に進む。なお、図９〜図１２は、ノード（リーフ以外のノード）の分割が必要でない場合を示している。
【００７３】
ノードの分割が必要な場合は以下の処理が行われる。
【００７４】
ステップS1690）処理中のノード（ステップS1685で取り出したノード）のロックを取得し、下位の分割されたノードへの分岐するための比較キーを挿入するために、ノードを分割して2つのCOPY（対象ノードCOPY1と対象ノードCOPY2と表記）を作成する。この際、挿入対象のノードに含まれていた比較キーが分割された先の対象ノードCOPY1/2で均等になるように振り分ける。
【００７５】
ステップS1695）対象ノードCOPY1/2と、挿入対象のノードの左のノード（左ノードと表記）のロックを取得し、相互のポインタの作成、下位の分割されたノードへの分岐するための比較キーの挿入を行う。
【００７６】
ステップS16100）対象ノードCOPY1/2のポインタを一時的に下位ノードの左ノードにATOMIC命令で付ける。処理はステップS1685に戻る。
【００７７】
ノードの分割が不要な場合は以下の処理が行われる。  
ステップS16200）処理中のノード（ステップS1685で取り出したノード）のロックを取得し、下位の分割されたノードへ分岐するための比較キーを挿入するために、COPY（対象ノードCOPY1と表記）を作成する（図９でのノード３´）。
【００７８】
ステップS16205）対象ノードCOPY1と、挿入対象のノードの左のノード（左ノードと表記）のロックを取得し、ポインタの作成、下位の分割されたノード（リーフを含む）へ分岐するための比較キーの挿入を行う（図９）。
【００７９】
ステップS16210）対象ノードCOPY1のポインタを一時的に下位ノードの左ノードにATOMIC命令で付ける（図9のTEMPORARY ATOMIC LINK UPDATE）。処理はステップS1685に戻る。たたし、現在の処理中ノードがROOTノードの場合は、ステップS16105に進む。
【００８０】
ステップS16105）ステップS1685で取得したノード（図１０の例ではノード１）から探索経路上の下位ノードに対するポインタを、ATOMIC命令を利用して、1つ下の高さの左ノード（図１０のノード２）に一時的に付け替える（図１０のTEMPORARY ATOMIC LINK UPDATE）。
【００８１】
ステップS16110）処理中のノードに対する1つ下の高さの左ノードから挿入対象のノードへのポインタを、ATOMIC命令を利用して、対象ノードCOPYに付け替える（図９、図１０、図１１）。
【００８２】
ステップS16113）処理中のノードにおいて、一時的に付け替えられているノードのポインタを対象ノードCOPYへのポインタに、ATOMIC命令を利用して付け替える（図１１）。
【００８３】
ステップS16115）処理中のノードから1つ下のノードへ移動する。
ステップS16117）ステップS16115で移動した先のノードが最下端かどうか（リーフかどうか）を判定し、最下端であればステップS16120に進み、最下端でなければステップS16110に戻る。
【００８４】
ステップS16120）ロックが取得されている全ノードに対し、取得されたロックを全て解放する。
【００８５】
ステップS16125）全ての挿入対象ノードについて、参照している処理がなくなるのを（参照カウンタが0になるまで）待つ。
【００８６】
ステップS16130）ロック処理部４４を利用して、全ての対象ノードの右のリーフ（右リーフと表記）へのロックを取得する。全ての対象ノードのロックが取得された右リーフ集合が得られる（図１２）。
【００８７】
ステップS16135）上記右リーフ集合における全ての右リーフから挿入前の対象ノードへのポインタを最新の対象ノードCOPY（図１２でのノード３´、リーフ７´´）にATOMIC命令で付け替える（図１２）。
【００８８】
ステップS16140）全ての対象ノードを削除し、取得した全てのロックを解放する。
【００８９】
（実施の形態のまとめ、効果）
上述したように、本実施の形態では、探索キーを利用した探索処理から常に一貫したB+木索引構造に見える（挿入処理の影響を全く受けない）ように、CPU上に実装されているATOMIC命令（他のCPU命令から見て不可分に実行される命令）を利用して、一時的に上位ノードのポインタの参照先を1つ左のノードを参照する（例：S1635、S16100/S16210/S16105）ようにした後、左ノードから挿入対象のノードへのポインタをATOMIC命令で書き換えている（S1640、S16110）。この一連の後処理として、最後に一時的に左ノードを参照させていたポインタを、正しいノードを指すように書き換える（S1645、S16113）。
【００９０】
このような処理を行う構成を採用したことにより、探索処理を行っている間に従来手法で発生していた挿入処理完了の待ち時間を完全に除去することが可能であるため、定期的にデータベース表内のデータ列に挿入が発生するような環境下において時間当たりに完了可能な平均探索処理性能が向上する効果が得られる。
【００９１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００９２】
４０  B＋木索引処理装置
４１  B+木索引初期化部
４２  探索処理部
４３  挿入処理部
４４  ロック処理部
４５  B+木索引記憶部
４６  DB表内データ列入力装置
４７  探索キー入力装置
４８  挿入キー入力装置
４９  結果出力装置
【図１】
2013242677.tif 000003
【図２】
2013242677.tif 000004
【図３】
2013242677.tif 000005
【図４】
2013242677.tif 000006
【図５】
2013242677.tif 000007
【図６】
2013242677.tif 000008
【図７】
2013242677.tif 000009
【図８】
2013242677.tif 000010
【図９】
2013242677.tif 000011
【図１０】
2013242677.tif 000012
【図１１】
2013242677.tif 000013
【図１２】
2013242677.tif 000014
【図１３】
2013242677.tif 000015
【図１４】
2013242677.tif 000016
【図１５】
2013242677.tif 000017
【図１６】
2013242677.tif 000018
【図１７】
2013242677.tif 000019
【図１８】
2013242677.tif 000020