JP4139613B2

JP4139613B2 - データ処理方法

Info

Publication number: JP4139613B2
Application number: JP2002073540A
Authority: JP
Inventors: 信之山下; 幸生中野
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2002-03-18
Filing date: 2002-03-18
Publication date: 2008-08-27
Anticipated expiration: 2022-03-18
Also published as: US20080320494A1; US7818749B2; JP2003271436A; US20030177131A1

Description

【０００１】
【発明の属する技術分野】
本発明は、ポインタにより複数のオブジェクトが関連づけられるデータ構造を持ち、オブジェクトの参照、更新、挿入および削除を行なう処理が複数並行して動作するシステムのデータ処理に関する。
【０００２】
【従来の技術】
（従来技術１）
本発明に関するインデックスにより高速にデータにアクセスする機能を持ったデータ管理システムは基本的なデータへのアクセス方法として次の４つの機能を提供するものとする；
（１）参照機能：指定したキー値に関連するデータの参照
（２）挿入機能：指定したキー値およびそれに関連する指定したデータの挿入
（３）削除機能：指定したキー値およびそれに関連するデータの削除
（４）更新機能：指定したキー値に関連するデータを指定したデータへの更新
これらの機能は、複数並列して処理要求されるものとする。以下、それぞれの機能を実現する処理方法を参照処理、挿入処理、削除処理そして更新処理と呼ぶものとする。
【０００３】
これらの機能を実現する従来技術を図１および図２を用いて説明する。
図１、１０１にデータ構造の一例を示す。３つのオブジェクトＡ、ＢおよびＣから構成されるオブジェクトグループＴを示す。オブジェクトはデータの単位であり、領域の確保および解放はオブジェクト単位で行なわれるものとする。またひとつのデータはひとつのオブジェクトに格納されるものとする。
【０００４】
オブジェクトＢにはキー値１０とそれに関連するデータが格納されているものとする。同様にオブジェクトＣにはキー値２０とそれに関連するデータが格納されているものとする。オブジェクトＡには、オブジェクトＢが保持するキー（すなわちキー値１０）とオブジェクトＢの格納位置情報（以下、ポインタと呼ぶ）およびオブジェクトＣが保持するキー（すなわちキー値２０）とオブジェクトＣのポインタが格納されている。
【０００５】
ここで、前記の４機能の実現方法について説明する。以上の機能を複数の処理が並列実行することを可能とするため、ロックの設定・解除が必要となる。ロックについては例えば、「Gray, J., Reuter, A., TRANSACTION PROCESSING:CONCEPTS AND TECHNIQUES, Morgan Kaufmann Publishers, Inc., 1993, p449-484」に実現方法が述べられている。ここでは前記文献にある、Ｓ、Ｘ、ＩＳ、ＩＸ各モードのロックを利用する。ＳモードのロックはＳおよびＩＳモードのロックと並列実行可能であり、Ｘモードはすべてのモードのロックと並列実行はできず、ＩＳモードのロックはＳ、ＩＳおよびＩＸモードのロックと並列実行可能であり、ＩＸモードのロックはＩＳおよびＩＸモードのロックと並列実行可能である。ロック設定の方針は、参照処理の場合はオブジェクトグループＴにＩＳモードのロックを、挿入、削除および更新処理の場合はオブジェクトグループＴにＩＸモードのロックを設定し、その後アクセスするオブジェクトに対し、参照する場合はＳモード、更新する（可能性がある）場合はＸモードでロックを設定するといったように階層的にロックを設定するものである。即ち、オブジェクトグループに対してロックを設定した後、特定のオブジェクトにロックを設定する。
【０００６】
オブジェクトグループに対しロックを設定する場合のリソース名称は、各処理が共通して知っている名称を指定するものとする。また、オブジェクトに対しロックを設定する場合、オブジェクトの格納位置に対応するリソース名称（リソース名称をオブジェクトが格納されている位置情報、例えば、ポインタの値とする）を指定するものとする。つまり、格納位置がわかればオブジェクトにロックを設定可能である。また、オブジェクトグループ内の基点となるオブジェクト（図１ではオブジェクトＡ）の格納位置はすべての処理が知っており、かつ格納位置が移動したりしないものとする。
【０００７】
各処理のタイムチャートを図２に示す。タイムチャートにおける時間は左から右方向に流れるものとする。両端が黒丸で示される線分は、線分の左側に示されるオブジェクトにロックを設定している期間を表し、線分の上にロックのモードを示し、線分の下に処理を示す。両端が白丸で示される線分は、線分の左側に示されるオブジェクトに対し（ロックを設定せずに）アクセスを行なっていることを表し、線分の下に処理を示す。図２（ａ）は参照処理のフローチャートを示す。ここでは、キー値が１０のオブジェクトを参照する例を示している。図２（ｂ）は挿入処理のフローチャートを示す。ここでは、キー値が３０のオブジェクトをグループＴに挿入する例を示している。図２（ｃ）は削除処理のフローチャートを示す。ここでは、キー値が２０のオブジェクトを削除する例を示している。図２（ｄ）は更新処理のフローチャートを示す。ここでは、キー値が１０のオブジェクトを更新する例を示している。
【０００８】
並列処理での状況を示すために、仮にキー値３０の挿入処理と、キー値２０の削除処理が、ほぼ同時に動作している状況での場合について説明する。挿入処理２０２は、まずオブジェクトグループＴに対し、ＩＸモードでロックを設定する。そして新規のデータを格納するためのオブジェクト領域を確保（オブジェクトＤとする）して、その領域にキー値３０および関連するデータを設定する。一方、削除処理２０３も、同様にオブジェクトグループＴに対し、ＩＸモードでロックを設定するが、このロックは挿入処理におけるＩＸと競合しても並列実行可能であり、いずれかが待たされることはない。次は、挿入処理２０２、削除処理２０３ともにオブジェクトＡに対してＸモードのロックを設定する処理であり、先行してロック設定した処理がロックを解除するまで他方は待たされることになる。
【０００９】
まず、削除処理２０３が挿入処理２０２に先立ってロックの設定に成功した場合について説明する。挿入処理２０２は削除処理２０３がオブジェクトＡのロックを解除するまで待たされることになる。削除処理２０３はオブジェクトＡをアクセスしてキー値２０に対応するオブジェクトＢへのポインタを取得して、オブジェクトＣに対しＸモードでロックを設定し、オブジェクトＡ内のキー値２０およびオブジェクトＣへのポインタを削除（以下、ポインタの切り離しと呼ぶ）して、オブジェクトＡに対するロックを解除して（この時点で挿入処理２０２の待ちは解除される）、オブジェクトＣを格納していたオブジェクト領域を解放し、オブジェクトＣのロックを解除し、最後にオブジェクトグループＴのロックを解除する。この状態を図１の１０２に示す。
【００１０】
削除処理２０３によるオブジェクトＡのロックの解除を受けて、挿入処理２０２はオブジェクトＡへのロックの設定に成功する。挿入処理２０２では、オブジェクトＡにアクセスして、オブジェクトＡにキー値３０とオブジェクトＤの格納位置を設定し、オブジェクトＡに設定したロックを解除し、オブジェクトグループＴに設定したロックを解除する。この状態を図１、１０４に示す。
【００１１】
一方、挿入処理２０２が削除処理２０３に先立ってロックの設定に成功した場合は、削除処理２０３は挿入処理２０２がオブジェクトＡのロックを解除するまで待たされることになる。挿入処理２０２は前記同様に処理を行い、図１、１０３の状態となる。その後、削除処理２０３が実行され、図１、１０４に示す状態となる。
【００１２】
参照処理(キー値１０)については図２、２０１に、更新処理（キー値１０）については図２、２０４に示す。参照処理２０１や更新処理２０４でオブジェクトＡに対するロックを解除する前にオブジェクトＢのロックを設定しているのは、並列してオブジェクトＢの削除処理が動作していた場合に、誤動作を防止するためである。つまり、仮に、オブジェクトＡに対するロックを解除した後にオブジェクトＢのロックを設定するようになっていると、その間に削除処理によってオブジェクトＢの領域解放が可能であり、さらにこの解放領域が別用途に再割当てされて設定されたデータをオブジェクトＢのデータと見てしまい誤動作する可能性がある。
【００１３】
また、より平易な方法として、参照処理の場合はオブジェクトグループＴにＳモードのロックを、挿入、削除および更新処理の場合はオブジェクトグループＴにＸモードのロックを設定するという方法もある。この方法では参照処理同士以外は、並列処理実行はできないため、上記の例より更にディスクやプロセッサといった資源を有効に活用できず、スループットおよびレスポンスタイムが低くなる。
【００１４】
このように、従来技術１では、オブジェクトＡに対してロックをかけた状態でオブジェクトＢにもロックをかけるなど同時に２つのオブジェクトにかける。このことによりオブジェクトの削除処理で削除したオブジェクトの領域を解放することが出来るという利点があるが、並列実行性能がやや低いという特性がある。
【００１５】
（従来技術２）
ＤＢ管理システムにおける、Ｂツリーインデクスは、従来技術１を拡張したデータ構造になっている。図７、７０１にその一例として、７つのページ（従来技術１のオブジェクトに相当）からなる３段のＢツリーインデクスを示す。図７、７０１の下方に位置するページＰ４、Ｐ５、Ｐ６およびＰ７はリーフページと呼ばれ、それぞれ１個以上のキー（ページ内の下方に記した値。例えばページＰ６ではキー値５０およびキー値７０）とそれに対応するデータの格納位置情報の組、右側のページのポインタ（一番右側のページＰ７は除く）、ページ内ＭＡＸキー値（リーフページ内の右上に記した値。ページ内に格納されているデータが持つ最大のキー値。例えばページＰ４ではキー値２０がページ内Ｍａｘキー値である）が格納されている。各リーフページは格納を担当するキーの範囲が設定されており、該当ページおよびその左側に位置するページのページ内Ｍａｘキー値によって示される。例えばページＰ５が格納を担当するキーの範囲は、ページＰ５の左側のページＰ４のページ内Ｍａｘキー値２０より大きく、ページＰ５のページ内Ｍａｘキー値４０以下のキーである。同様にページＰ６、Ｐ７が担当するキーの範囲はそれぞれ４０より大きく７０以下のキー、および７０より大きいキーである。左側に位置するページがないページＰ４は、ページ内Ｍａｘキー値以下（２０以下）のキーを担当する。
【００１６】
リーフページの上方には上位ページ（図７，７０１のページＰ１、ページＰ２およびページＰ３、ノードとも呼ばれる）と呼ばれるページが配置される。上位ページには、１個以上の直下のページへのポインタおよびキー値の組、（存在すれば）右側のページへのポインタが格納される。ここでのキー値は組になっているポインタで指されるページのページ内Ｍａｘキー値と一致する。特にページＰ１はルートページと呼ばれる。あるキー値が格納されているリーフページをサーチするためには、ルートページからアクセスして目的のキー値以上の最小のキー値と組になるポインタを辿っていけばよい。領域の確保はページ単位で行なわれる。
【００１７】
ここで、キー値２０〜４０の範囲のキー値を指定した削除処理について図８、８０１を用いて説明する。まずＢツリーインデクス全体Ｔに対し、ＩＸモードのロックを設定して、ルートページＰ１に対し、Ｓモードでロックを設定して、指定範囲の下限であるキー値２０以上であってページＰ１内の最小のキー値であるキー値４０と組になっているページＰ２へのポインタを取得して、ページＰ１のロックを解除する。ページＰ２に対しＳモードでロックを設定し、同様にキー値２０以上であってページＰ２内の最小のキー値であるキー値２０と組になっているページＰ４へのポインタを取得して、ページＰ２のロックを解除する。そしてページＰ４に対しＸモードでロックを設定し、ページＰ４内の削除対象であるキー値２０〜４０の範囲にあるキー値すべて削除する。
【００１８】
このときページＰ４には、キー値２０しか存在しないため、ページ内にキー値が残らなくなるが、ページＰ４の領域解放は行なわない。その大きな理由は、領域解放するには、解放対象ページへのポインタを適当なロックを設定しながら、設定し直す必要があり、並列実行性の劣化につながるからである。
【００１９】
またページＰ４のページ内Ｍａｘキー値が２０であることから、削除対象であるキー値２０〜４０の範囲のうち、２０より大きいキー値は右側のページに格納されていることがわかるので、右ページへのポインタ（ページＰ５へのポインタ）を取得して、ページＰ４のロックを解除する。ページＰ５に対するＸモードのロックを設定して、ページＰ５内の削除対象であるキー値２０〜４０の範囲にあるキー値すべて削除する。このときページＰ５には、キー値４０しか存在しないため、ページ内にキー値が残らなくなるが、ページＰ５の領域解放は行なわない。ページＰ５のページ内Ｍａｘキー値が４０であることよりキー値２０〜４０の範囲のキーすべてを削除できたことになる。ページＰ５のロックを解除し、最後にＢツリーインデクス全体Ｔのロックを解除し削除処理を完了する。削除処理が完了した状態を図７、７０２に示す。
【００２０】
また、図７、７０２の状態から、挿入処理（キー値６０）を行なう手順について図８、８０２を用いて説明する。Ｂツリーインデクス全体Ｔに対し、ＩＸモードのロックを設定して、前記記述の手順と同様にページＰ１、ページＰ３とページをアクセスしていき、ページＰ６に対してＸモードのロックを設定してページＰ６にアクセスする。ページＰ６には既にキー値５０および７０のデータが格納されており、キー値６０のデータを格納するのに十分なスペースがないものとする。この場合スプリット呼ばれる、ページ分割処理を行なう。まず、新規にページを確保（ページＰ８とする）する。ここでは分割キー値が５０であったものとする。つまり、キー値５０のデータをページＰ６に残し、キー値７０のデータおよび挿入するキー値６０のデータを新規に確保するページ領域に移動するものとする。ページＰ８に必要な設定を行い、ページＰ６のページ内Ｍａｘキー値を５０に設定し直し、右ページのポインタをページＰ８に設定し直すなどの処理を行なった後、ページＰ６のロックを解除して、ページＰ３に対しＸモードでロックを設定して、ポインタを設定し直し、ページＰ３のロックを解除し、最後にＢツリーインデクス全体Ｔのロックを解除し挿入処理を完了する。挿入処理が完了した状態を図７、７０３に示す。
【００２１】
前述したように、Ｂツリーインデクスにおいて、並列実行性を高く保つために、データの削除によりページ内にデータが一件もない状態になっても、ページの領域解放を行なわない。そのため、一般にデータの挿入・削除を繰り返すうちに格納効率が低下し、それに伴いアクセス性能が劣化していく。その性能劣化を抑えるために、適当な時期にインデクスのアクセスを禁止して、インデクスに格納されたデータを一時領域に出力して、データを詰め込み直す処理（再編成処理）が一般に行なわれている。
【００２２】
このように、従来技術２では同時に２つのページにロックをかけることがない。従って、並行実行可能性は高い。一方、従来技術１で述べたような誤ったページの参照が生じる可能性があるので、データを削除しても引き続いてその領域を解放することが出来ない。
【００２３】
【発明が解決しようとする課題】
以上のような従来技術１、従来技術２の説明から分かるように、データの削除処理でのその領域の解放処理が可能であることと、並列実行性が高いことはトレードオフの関係にあるものと考えられていた。
【００２４】
本発明の目的は、ポインタにより複数のオブジェクトが関連づけられるデータ構造を持ち、オブジェクトの参照、更新、挿入および削除を行なう処理が複数並行して動作するシステムにおいて、参照、更新および挿入の並列実行性が高く、かつ削除処理を参照、更新および挿入処理と並列実行可能とすることである。
【００２５】
さらに、データの挿入および削除の繰り返しにより格納効率・アクセス効率が低下（削除されたがその領域が解放されないオブジェクトが増えることや、目的のオブジェクトにアクセスするために不必要なオブジェクトを経由することになること）したＢトリーインデクスに対し、データ参照、更新および挿入を抑止することなく空きとなっているオブジェクトの領域の回収し、格納効率、アクセス効率を向上させることである。
【００２６】
【課題を解決するための手段】
参照、更新および挿入処理において、ポインタを辿ってのオブジェクト間の移動に際し、移動前のオブジェクトに対するロックを解除した後に、移動後のオブジェクトに対するロックを設定することにより、参照、更新および挿入の並列実行性を高くする。この際、処理の始めにオブジェクトグループに対しＩＳモード（参照処理の場合）またはＩＸモード（更新および挿入処理の場合）を設定し、処理完了時にロックを解除する。
一方、削除処理において、削除対象へのポインタを切り離し、あるいは付け替えた後、オブジェクトグループに対してロックを取得している全処理が完了した後に、削除対象オブジェクトの領域を解放する。
【００２７】
【発明の実施の形態】
（実施の形態１）
本発明を実現するシステム構成例を図９に示す。ここに示すシステム構成例は実施の形態１〜３において共通である。本システムは、プロセッサ２とメモリ３とを有するコンピュータシステム１と、それに接続された外部記憶装置４と、コンピュータシステム１にネットワーク６を介して接続された複数の端末７を備えている。
【００２８】
メモリ３内にはプロセッサ２で解釈可能なプログラムの形で表現されたデータ管理システム１０が配置され、プロセッサ２によって命令が読み込まれ演算処理がなされる。データ管理システム１０は、システム制御部１１、オブジェクト管理部１２、ロック管理部１３から構成される。システム制御部１１は、端末７からの参照、挿入、更新および削除要求を受け取り、要求内容を解析してオブジェクト管理部１２に制御を渡し、処理結果をネットワーク６を通じて端末７へ応答する。オブジェクト管理部１２はシステム制御部１１から渡された指示に従って、外部記憶装置４内に格納されたオブジェクト５の管理を行なう。ロック管理部１２は、指定されたリソースに対するロック機能をオブジェクト管理部１２に提供する。
【００２９】
従来技術１における説明に使用した図１において、参照、更新および挿入の並列実行性がより高く、かつ削除処理を参照、更新および挿入処理と並列実行可能な方法の例を図３および図４により開示する。
【００３０】
図３、３０１は本実施形態における参照処理を示すタイムチャートである。図２、２０１と比較して、オブジェクトＡに対するロックの解除時期とオブジェクトＢに対するＳモードのロックの設定時期が入れ替わっている。即ち、従来はオブジェクトＡについてロックを設定して、オブジェクトＢへのポインタの値を記憶し、その後、オブジェクトＢについてロックを設定し、それからオブジェクトＡについてのロックを解放していた。これに対し本実施形態ではオブジェクトＡについてロックを設定し、オブジェクトＢへのポインタの値を記憶したならば、オブジェクトＡについてのロックを解放する。それからオブジェクトＢについてロックを設定する。図３、３０２は本実施形態における挿入処理を示すタイムチャートである。これは図２、２０１と同じものである。
【００３１】
図３、３０４は本発明における更新処理を示すタイムチャートである。図２、２０４と比較して、オブジェクトＡに対するロックの解除時期とオブジェクトＢに対するＸモードのロックの設定時期が入れ替わっている。
【００３２】
図３、３０３は本発明における削除処理を示すタイムチャートである。図２、２０４とは、大きく変わっており、比較しながら説明する。オブジェクトグループＴに対するＩＸモードのロックの設定およびオブジェクトＡに対するＸモードのロックの設定は同様であるが、その後オブジェクトグループＴに対してロックを取得している全処理を記憶する。その後、オブジェクトＡから削除対象のオブジェクトＣに対するポインタを切り離すが、この実施形態ではここで前記記憶した全処理の完了を待つ。完了の待ち方として、ロックの解除時点でオブジェクトグループＴに対してロックを設定している処理側から削除処理へ完了を通知する方法と、削除処理が一定間隔で他の処理の処理完了をチェックする方法とがある。いずれかの方法を用いて前記記憶した全処理の完了を検知できた後、オブジェクトＣの領域を解放する。
【００３３】
解放した領域に他処理がアクセスする可能性はないので、オブジェクトＣに対するロックを設定する必要はない。その理由について、図４に例で説明する。図４では、削除処理４０１、参照処理４０２、挿入処理４０３、更新処理４０４および更新処理４０５が並列して処理が行なわれていることを示す。４０６時点、つまり削除処理４０１においてオブジェクトＡに対しＸモードでロックを設定した直後の時点でオブジェクトグループＴに対しロックを設定していない処理（ここでは更新処理４０４および更新処理４０５）は、オブジェクトＣにアクセスし得ない。なぜならばオブジェクトＣにアクセスする前にオブジェクトＣへのポインタを設定してある時点でのオブジェクトＡにアクセスする必要があるが削除処理４０１がＸモードで押さえているため、更新処理４０４および更新処理４０５でオブジェクトＡを見られるときにはオブジェクトＣへのポインタは切り離されている。また、参照処理４０２や更新処理４０３はオブジェクトＣを見てデータを取得することがあるが、それらの処理はすべてが完了したことを検知できているからである。
【００３４】
前記ＩＳモードおよびＩＸモードは例であって、その代わりに、それらの組と等価な、あるいはより並列実行性の低いロックモードを用いることも出来る。
【００３５】
前記処理方法により、従来処理に比べ、参照、挿入および更新処理の並列実行性を高くして、かつ削除処理によって解放された領域を誤って他処理がアクセスすることも回避している。更に詳しくは、上記実施形態では参照、挿入および更新処理において、一つの処理が同時に２つのオブジェクトをロックすることがないため、従来技術と同等の高い並列実行性を実現出来る。また、削除処理において、ポインタを切り離した後、削除処理の対象となっているオブジェクトグループにロックをかけている他の処理の完了を待って削除されたオブジェクトの領域を解放することにより、安全かつ他の処理の実行を阻害することなく領域の解放も実行出来る。
【００３６】
（実施の形態２）
図５および図６を用いて第２の実施の形態を開示する。
図５、５０１はあるハッシュ値に対応するデータをチェーンにより管理する場合などに典型的に用いられるデータ構造である（ここでは、ハッシュ関数がキー値を１０で割った余りと定義されていて、ハッシュ値＝２のキーおよびデータを管理する部分であると想定している）。この状態のデータ構造に対し、キー値３２の削除処理とキー値１２の挿入処理が要求された場合の手順について、図６に示す各処理のタイムチャートと合わせ説明する。
【００３７】
図６の削除処理６０１では、オブジェクトＢについて削除要求がなされる。まずオブジェクトグループＴに対し、ＩＸモードのロックを設定し、オブジェクトＡに対しＸモードでロックが設定する。オブジェクトＡに格納されているオブジェクトＢへのポインタを取得して、（オブジェクトＡに対するロックを保持したまま）オブジェクトＢに対しＸモードのロックを設定し、オブジェクトＢをアクセスする。オブジェクトＢ、即ち、キー値が３２のオブジェクトがあったことを確認し、この時点でオブジェクトグループＴに対しロックを設定しているすべての処理を記憶する（この時点で挿入処理６０２も並行して処理していてオブジェクトグループＴに対しロックを設定しているものとする）。オブジェクトＡに格納されているオブジェクトＢへのポインタをオブジェクトＢに格納されているポインタ（オブジェクトＣへのポインタ）に設定し直して（ポインタの付け替え）、オブジェクトＡおよびＢのロックを解除し（図５、５０２）、記憶した処理の完了待ちとなる。
【００３８】
一方、挿入処理６０２ではオブジェクトグループＴに対し、ＩＸモードのロックを設定し、挿入用のオブジェクト領域確保を行い（オブジェクトＤとする）、キー値１２および関連するデータの設定を行なう。続いてオブジェクトＡに対しＸモードでロックを設定（削除処理がロック保持中であれば、解除まで待つことになる）し、オブジェクトＡに格納されているポインタをオブジェクトＤへのポインタに設定し、オブジェクトＡからのポインタを、オブジェクトＤを指すように付け替え、オブジェクトＡのロックを解除し、最後にオブジェクトグループＴのロックを解除し、挿入処理を完了する（図５、５０３）。
【００３９】
挿入処理６０２のオブジェクトグループＴのロックを解除により、削除処理６０１はオブジェクトＢの領域を（ロックを設定することなく）解放し、オブジェクトグループＴのロックを解除して、削除処理を完了する（図５、５０４）。
【００４０】
次に、参照処理（キー値６２）６０３の処理手順について説明する。まず、オブジェクトグループＴに対しＩＳモードのロックを設定し、オブジェクトＡから順にポインタを辿っていってキー値が６２であるオブジェクトを探す。オブジェクト間を移動する際には、移動元のオブジェクトのロックを解除してから移動先のオブジェクトに対し、Ｓモードでロックを設定するものとする。なお、前記の削除処理６０１と並行して動作している場合は、オブジェクトＡにアクセスした際の状態が図５、５０２の状態であれば、オブジェクトＢへアクセスすることはなくポインタはオブジェクトＣへのものが記憶される。従って、図６、６０３の点線に囲まれた処理は行なわれない。６０３の点線で囲まれた処理はオブジェクトＢがまだ５０１の状態にあるときに実行される。このとき、オブジェクトＡのアクセスでオブジェクトＢへのポインタが記憶され、点線で囲まれた処理でオブジェクトＣへのポインタが記憶される。このように参照のタイミングにより処理が変わって来る。
【００４１】
続いて、更新処理（キー値６２）６０４の処理手順について説明する。まず、オブジェクトグループＴに対しＩＸモードのロックを設定し、オブジェクトＡから順にポインタを辿っていってキー値が６２であるオブジェクトを探し、見つけたら関連付けられているデータを更新する。オブジェクト間を移動する際には、移動元のオブジェクトのロックを解除してから移動先のオブジェクトに対し、Ｘモードでロックを設定するものとする。なお、前記の削除処理６０１と並行して動作している場合、オブジェクトＡにアクセスした際の状態が図５、５０２の状態あれば、オブジェクトＢへアクセスすることはなく、図６、６０４の点線に囲まれた処理は行なわれない。
【００４２】
前記処理方法により、削除処理によって解放された領域を誤ってアクセスすることなく、参照、挿入および更新処理の高い並列実行性を実現できる。更に述べれば、ハッシュ関数を用いたデータの管理においても実施の形態１と同様に、参照、挿入、および更新処理において、１つの処理が同時に２つのオブジェクトのロックを設定することがなく高い並列実行性を持つと共に、削除処理において、削除対象となるオブジェクトへのポインタを切り離した後にそのオブジェクトグループにロックをかけている他の処理の完了を待って領域の解放を実行することにより他の処理の実行を阻害することなく、かつ誤ったデータが使われることなく領域の解放が出来る。
【００４３】
（実施の形態３）
従来技術２で説明したＢツリーインデクスにおいて、データ削除やデータ挿入処理と並列実行可能な空きページ回収処理方法を図７および図８を用いて開示する。空きページ回収処理は、データの挿入・削除を繰り返すうちに格納効率が低下し、それに伴いアクセス性能が劣化している適当な時期に再編成に代わり実行することを想定している。
【００４４】
図７、７０３の状態において、空きページ回収処理が実行された場合の処理手順を図８、８０３に示す。まず、Ｂツリーインデクス全体Ｔに対しＩＸモードでロックを設定する。以降の説明において、ページに対するロックのモードについては[]内に記すものとする。次にルートページから一番左のリーフページに向かってページを辿る（ページＰ１[Ｓ]、Ｐ２[Ｓ]およびＰ４[Ｘ]）。リーフページＰ４においてデータ件数が０件であることを確認し、回収予定であることを示すフラグ（図７、７０４ページＰ４内の丸枠に「回」を記した記号）を設定する。続いてページＰ４の上位ページであるページＰ２にアクセス[Ｘ]して、ページＰ４へのポインタを切り離す（図７、７０４）。そして、ページＰ４の右側のページであるページＰ５にアクセス[Ｘ]して、データ件数が０件であることを確認し、回収予定であることを示すフラグを設定する。次に、上位ページであるページＰ２にアクセス[Ｘ]して、ページＰ５へのポインタを切り離すとページＰ２内にはキーが残らないことを確認して、ページ２に回収予定であることを示すフラグを設定する。続いてページＰ２の上位ページであるページＰ１にアクセス[Ｘ]して、ページＰ２へのポインタを切り離す（図７、７０５）。ページＰ５の右側のページであるページＰ６にアクセス[Ｘ]してデータ件数が１件以上であることを確認しページＰ６の右側のページであるページＰ８にアクセス[Ｘ]してデータ件数が１件以上であることを確認し、ページＰ８の右側のページであるページＰ７にアクセス[Ｘ]してデータ件数が１件以上であることを確認し、回収可能なページのフラグ設定およびポインタの切り離しが完了する。この時点でＢツリーインデクス全体Ｔに対しロックを設定している処理を記憶し、それらの処理の完了を待つ。記憶した処理がすべて完了したら、回収予定としたページＰ２、Ｐ４およびＰ５の領域を解放し、最後にＢツリーインデクス全体Ｔのロックを解除して空きページ回収処理を完了する（図７、７０６）。
【００４５】
前述した空き回収処理方法で得られた最終的な形では、領域解放を行なったページが格納を担当していたキーは、その右側のページが担当を引き継ぐ形となる。例えば、ページＰ６はキー値が５０以下のデータを担当する。それに伴い、参照、挿入および更新処理において、アクセスしたページに回収予定フラグが設定されているのを検知した場合、右側のページへ移動してアクセスするように処理を一部変更する。
【００４６】
ここまでに示した処理方法により、Ｂツリーインデクスにおいても参照、挿入および更新処理の並列実行性を大きく損なうことなく、かつデータ参照、更新および挿入を抑止することなく空きとなっているページの領域を回収し、格納効率、アクセス効率を向上させることが可能である。
【００４７】
以上述べた実施の形態で説明したように、ポインタにより複数のオブジェクトが関連づけられるデータ構造を持ち、オブジェクトの参照、更新、挿入および削除を行なう処理が複数並行して動作するシステムにおいて、参照、更新および挿入の並列実行性が高く、かつ削除処理を参照、更新および挿入処理と並列実行可能な処理が可能である。
【００４８】
さらに、データの挿入および削除の繰り返しにより格納効率・アクセス効率が低下したＢトリーインデクスに対し、データ参照、更新および挿入を抑止したり、一時リソースを使用したりすることなく空きとなっているページの領域の回収し、格納効率、アクセス効率を向上させることが可能である。
【００４９】
【発明の効果】
本発明によれば、参照、挿入および更新処理の並列実行性を持ち、かつ削除処理によって解放された領域を誤って他処理がアクセスすることも回避して削除処理後の解放(回収)も可能としている。
【図面の簡単な説明】
【図１】従来技術１および実施の形態１におけるデータ構造を示す図である。
【図２】従来技術１におけるタイムチャートを示す図である。
【図３】本発明の実施の形態１におけるタイムチャートを示す図である。
【図４】本発明の実施の形態１における並列処理の様子を示す図である。
【図５】本発明の実施の形態２におけるデータ構造を示す図である。
【図６】本発明の実施の形態２におけるタイムチャートを示す図である。
【図７】従来技術２および本発明の実施の形態３におけるデータ構造を示す図である。
【図８】従来技術２および本発明の実施の形態３におけるタイムチャートを示す図である。
【図９】本発明を実現するシステム構成の例を示す図である。
【符号の説明】
１…コンピュータシステム、２…プロセッサ、３…メモリ、４…外部記憶装置、５…オブジェクト、６…ネットワーク、７…端末、１０…データ管理システム、１１…システム制御部、１２…オブジェクト管理部、１３…ロック管理部

Claims

コンピュータシステムのメモリ内にプログラムとして保持され、プロセッサにより実行されるデータ管理システムを演算処理するデータ処理方法において、
前記データ管理システムは、
オブジェクト管理部と、
ロック管理部とを有し、
領域の確保および開放が一つのものとしておこなわれるデータ単位であるオブジェクトと、複数のオブジェクトより構成されるオブジェクトグループと、あるオブジェクトと次のオブジェクトを指し示し、あるオブジェクトから次のオブジェクトをアクセスすることができるようにするポインタとよりなるデータ構造を有し、
オブジェクトの参照、更新、挿入および削除の処理をおこなうときに、前記オブジェクトグループに対して、ロックを設定し、その後に、前記オブジェクトグループ内の特定のオブジェクトから、処理対象のオブジェクトまでの前記ポインタによって関連付けられたオブジェクトに対して、前記オブジェクトのロックを設定して、オブジェクトの参照、更新、挿入および削除の処理を複数並行して、前記データ管理システムにより動作させるデータ処理方法であって、
前記ロック管理部のプログラムが前記プロセッサにより演算処理されることによって実行されて、削除処理をおこなうときに、前記オブジェクトグループに第１のロックを設定する第１のステップと、
前記ロック管理部のプログラムが前記プロセッサにより演算処理されることによって実行されて、前記オブジェクトグループ内の特定のオブジェクトから、削除処理をおこなう削除対象オブジェクトまでの前記ポインタによって関連付けられたオブジェクトに対して、第２のロックを設定する第２のステップと、
前記オブジェクト管理部のプログラムが前記プロセッサにより演算処理されることによって実行されて、削除処理をおこなう削除対象オブジェクトの属する前記オブジェクトグループのオブジェクトにロックを取得している前記削除処理以外の全ての処理の情報を記憶する第３のステップと、
前記オブジェクト管理部のプログラムが前記プロセッサにより演算処理されることによって実行されて、削除処理をおこなう削除対象オブジェクトをポインタするオブジェクトから、前記削除対象オブジェクトをポイントしないようにする第４のステップと、
前記オブジェクト管理部のプログラムが前記プロセッサにより演算処理されることによって実行されて、前記オブジェクトグループに対してロックを取得している前記削除処理以外の全ての処理が完了したことを判断する第５のステップと、
前記オブジェクト管理部のプログラムが前記プロセッサにより演算処理されることによって実行されて、前記全ての処理が完了したと判断したときに、前記削除対象オブジェクトの領域を解放する第６のステップとを具備することを特徴とするデータ処理方法。
前記第５のステップにおいて、前記オブジェクト管理部のプログラムが、前記オブジェクトグループにロックを取得している前記削除処理以外の処理から処理完了通知を受けることを特徴とする請求項１記載のデータ処理方法。
前記オブジェクト管理部のプログラムが前記プロセッサにより演算処理されることによって実行されて、あるオブジェクトに対して、参照、更新、挿入および削除の処理を実行する場合に、前記オブジェクトグループの基点となる特定のオブジェクトから、前記ポインタを順次たどって、処理を実行するオブジェクトを検索することを特徴とする請求項１記載のデータ処理方法。