ディレクトリ分散型記憶装置及びデータ処理要求移譲プログラム
【課題】データを木構造で管理する場合に、メッセージ伝送の負荷が大きいラッチカップリングを行わずに、並行性制御を行うことが可能なディレクトリ分散型記憶装置を提供する。
【解決手段】ディレクトリ分散型記憶装置ＰＥＡは、木構造を構成するページごとに、当該ページで管理する検索キーの境界値を設定する境界値設定手段２３２ａと、検索キーの値が境界値の範囲内であるか否かに基づいて、経路誤りを判定する経路誤り判定手段２２３と、誤りと判定された場合に再度上位のページから経路の探索を行う経路再探索手段２２４と、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段２２１と、移譲すると判定した場合に処理要求を他のディレクトリ分散型記憶装置へ送信する移譲手段２２２とを備えることを特徴とする。
【解決手段】ディレクトリ分散型記憶装置ＰＥＡは、木構造を構成するページごとに、当該ページで管理する検索キーの境界値を設定する境界値設定手段２３２ａと、検索キーの値が境界値の範囲内であるか否かに基づいて、経路誤りを判定する経路誤り判定手段２２３と、誤りと判定された場合に再度上位のページから経路の探索を行う経路再探索手段２２４と、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段２２１と、移譲すると判定した場合に処理要求を他のディレクトリ分散型記憶装置へ送信する移譲手段２２２とを備えることを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造を有するディレクトリ構造を分散環境下で実現するディレクトリ分散型記憶装置及びデータ処理要求移譲プログラムに関する。
【背景技術】
【０００２】
近年、ネットワーク上に並列に配置された計算機（ＰＥ：Processing Element）上にデータベース等のデータを分散して記憶することで、データにアクセスする際の負荷分散と並行性動作とを実現したシステム（分散データ格納システム）が存在する。
このようなシステムにおいては、アクセス集中による負荷の偏りが存在する場合、その負荷の大きいＰＥがボトルネックとなり、システム全体の処理能力が低下してしまう。そこで、各ＰＥに負荷を均等に分配するためのディレクトリ構造と、そのディレクトリ構造における並行性制御とが提案されている（例えば、非特許文献１参照）。
【０００３】
（Ｆａｔ−Ｂｔｒｅｅ構造）
ここで、図１４を参照して、従来の分散データ格納システムにおけるディレクトリ構造について、その概要を説明する。図１４は、従来の分散データ格納システムにおけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造の構成例を示す図である。
図１４に示すように、Ｆａｔ−Ｂｔｒｅｅ構造は、データを示す葉ページＰｄを各計算機ＰＥに均等に分配した構造となっている。また、Ｆａｔ−Ｂｔｒｅｅ構造は、葉ページＰｄ以外のインデックスを示すインデックスページＰｉを各計算機ＰＥに分配した構造となっている。
【０００４】
なお、各インデックスページＰｉに登録（エントリ）される下位層のインデックスページの数と、葉ページＰｄに登録されるデータ（データページ）の数とは、予め定められた数に制限されている。この制限された数を超過する場合は、各ページは分割され、木構造が更新されることになる。
【０００５】
このように、葉ページＰｄ及びインデックスページＰｉを分配することで、各計算機ＰＥの記憶部に記憶されるのは、全体の木構造に対して、ルートページＰｉＲから、均等に分配された葉ページＰｄまでの部分木となる。すなわち、計算機ＰＥ１には部分木Ｒ１が、計算機ＰＥ２には部分木Ｒ２が、計算機ＰＥ３には部分木Ｒ３が、計算機ＰＥ４には部分木Ｒ４がそれぞれ記憶されることになる。
これによって、各計算機ＰＥに対するアクセスの分散が行われる。また、各計算機ＰＥでは、記憶している葉ページＰｄの探索に必要のないインデックスページＰｉを保持していないため、高速に葉ページＰｄにアクセスすることができる。
【０００６】
ここで、並行性制御を説明するために必要な用語について説明しておく。
「木をたどる主体」…木構造において、木をたどる主体は、システムに格納されたある葉ページを取得するために、各ノード上で葉ページ処理要求（処理要求）を構成する一連のプロセス（プロセスの集合体）である。
【０００７】
「ページのラッチ」…ある葉ページ要求Ａｎを構成するプロセスによってラッチが設定されたページは、その他の葉ページ要求Ａｍ（ｍ≠ｎ）に属するプロセスからのアクセスが制限される。この制限の種類によって複数のラッチが存在する。例えば、他から読み込みも変更も破棄も行えないラッチ、変更や破棄は行えないが読み込みは行えるラッチ等がある。このラッチによりアクセスが制限されたプロセスは実行を一時停止し、当該ラッチが解除された後、再び当該ページへのラッチ獲得やアクセスを試みる。なお、ラッチは例えばセマフォを用いて実装される。
【０００８】
「木構造の一貫性」…木構造ごとに決められた手順に従って葉ページ要求を行う限り、木構造が変更している最中に、一部の葉ページへアクセスができない状況になっても、要求が正常に一時停止され、最終的に正しい葉ページを取得できる性質をいう。
「アクセスパス」…ルートページＰｉＲ及び要求する葉ページＰｄと、これらの各ページ間に含まれるページを意味する。
「ロック」…アクセスパスに対して、他の処理要求に属するプロセスからのアクセスを制御するもので、デットロック検出機能を持つ。
【０００９】
（並行性制御）
次に、従来の分散データ格納システムにおける並行性制御について説明する。図１４で説明したＦａｔ−Ｂｔｒｅｅ構造では、木構造の一貫性を保証するため、並行性制御が必須となる。この並行性制御においては、アクセスパスに対して、他のプロセスからのアクセスを制御するロックが用いられる。一般に、このロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（セマフォの一種）が用いられている。
このＦａｔ−Ｂｔｒｅｅ構造において、葉ページのデータが参照、更新等される場合、並列計算機は、まず、ルートページにラッチを設定する。その後、下位層のページ（子ページ）のポインタを取得し、子ページにラッチを設定し、ルートページ（親ページ）のラッチを解除する。この動作を、上位層から下位層に向けて葉ページまで繰り返すことで、並行性を保証しながら葉ページを更新等することが可能になる。このような上位層から下位層に向けてラッチの設定及び解除を順次繰り返す動作を「ラッチカップリング」という。
【００１０】
また、ある計算機（例えば、ＰＥ１）が、自身の記憶部には記憶されていない葉ページＰｄについての処理要求があった場合、その葉ページＰｄを管理している他の計算機（例えば、ＰＥ２）に処理要求を通知し、他の計算機がその処理要求を継続して実行する必要がある。このように、処理要求を他の計算機に継続して実行させることを、処理要求の移譲という。
【００１１】
ここで、図１５〜図１７を参照（適宜図１４参照）して、従来の並列計算機における処理要求の移譲動作について詳細に説明する。図１５は、従来の並列計算機における処理要求の移譲動作を示すフローチャートである。図１６は、計算機間で処理の移譲を伴わないラッチカップリングの動作例を示す模式図である。図１７は、計算機間で処理の移譲を伴うラッチカップリングの動作例を示す模式図である。
並列計算機は、データの処理要求（参照、更新等）があった各計算機ＰＥにおいて、以下の動作を実行する。ここでは、計算機ＰＥ１の動作を主に説明する。
【００１２】
まず、計算機ＰＥ１は、初期値として、親ページを“ｎｕｌｌ”、子ページをルートページに設定する（ステップＳ５０）。そして、計算機ＰＥ１は、要求に示されたデータのアクセスパスに基づいて、子ページへ降下が必要であるか否かを判定する（ステップＳ５１）。
ここで、降下が必要でない場合（ステップＳ５１でＮｏ）、そのページが要求のあった葉ページであるため、当該葉ページへの処理を実行し（ステップＳ５２）、動作を終了する。一方、降下が必要である場合（ステップＳ５１でＹｅｓ）、計算機ＰＥ１は、要求に示されたデータのアクセスパスに基づいて、他の計算機へ処理要求を移譲するか否かを判定する（ステップＳ５３）。
【００１３】
ここで、移譲が必要な場合（ステップＳ５３でＹｅｓ）、計算機ＰＥ１は、移譲先の計算機（ここでは、計算機ＰＥ２とする）へ処理要求の移譲を要求する（移譲要求メッセージ送信）。この段階で、移譲先への移譲処理が開始されたことになる。なお、処理要求の移譲を要求された計算機ＰＥ２は、計算機ＰＥ２において後記するステップＳ５４以降の動作を実行する。
【００１４】
一方、移譲が必要でない場合（ステップＳ５３でＮｏ）、計算機ＰＥ１は、子ページにラッチを設定し（ステップＳ５４）、その子ページに降下（子ページを新たな親ページに、孫ページを新たな子ページに設定）する（ステップＳ５５）。
なお、計算機ＰＥ１は、他の計算機におけるステップＳ５３の判定により、当該他の計算機（ここでは、計算機ＰＥ3とする）から、処理要求の移譲を要求された場合も、ステップＳ５４以降の動作を実行する。この段階で、移譲元からの移譲処理が開始されたことになる。
【００１５】
その後、計算機ＰＥ１は、移譲元の計算機（計算機ＰＥ３）からの移譲処理中である場合（ステップＳ５６でＹｅｓ）、計算機ＰＥ３へ要求に対する応答を通知する。一方、移譲元の計算機（計算機ＰＥ３）からの移譲処理中でない場合（ステップＳ５６でＮｏ）、親ページのラッチを解除する（ステップＳ５７）。
なお、計算機ＰＥ１は、移譲先の計算機（計算機ＰＥ２）から移譲の要求に対する応答を通知された場合（移譲応答メッセージ受信）も、ステップＳ５７の動作を実行する。
【００１６】
そして、計算機ＰＥ１は、移譲先の計算機（計算機ＰＥ２）への移譲処理中である場合（ステップＳ５８でＹｅｓ）、計算機ＰＥ２へ移譲の完了を通知し（移譲完了メッセージ送信）、動作を終了する。この段階で、移譲先への移譲処理が完了したことになる。
一方、移譲先の計算機（計算機ＰＥ２）への移譲処理中でない場合（ステップＳ５８でＮｏ）、計算機ＰＥ１は、ステップＳ５１に戻って、処理対象の葉ページに到達するまで動作を続ける。
なお、計算機ＰＥ１は、移譲元の計算機（計算機ＰＥ３）から移譲の完了を通知された場合も、ステップＳ５１に戻って動作を実行する。なお、この段階で、移譲元からの移譲処理が完了したことになる。
【００１７】
例えば、図１６（ａ）に示すように、ルートページＰ１から対象データの葉ページＰ４までが、同一の計算機ＰＥ１内で管理されている場合、図１６（ｂ）に示すように、葉ページＰ４までの処理要求を受け付けた計算機ＰＥ１は、他の計算機に参照先の葉ページＰ４に対する処理要求を移譲することなく、計算機ＰＥ１内で、各ページＰ１からＰ４まで、ラッチカップリングを行いながら、最下層の葉ページＰ４に対してラッチをかけ、参照、更新等の処理を行うことができる。なお、図１６（ｂ）中“Ｌ”は、ラッチが設定された状態を示している。
【００１８】
一方、図１７（ａ）に示すように、ルートページＰ１から参照先の葉ページＰ４までが、葉ページＰ４までの処理要求を受け付けた計算機ＰＥ１内で管理されていない場合、計算機間で処理要求の移譲が行われる。例えば、図１７（ａ）に示すように、ルートページＰ１から対象データの葉ページＰ４までにおいて、インデックスページＰ３及び葉ページＰ４が計算機ＰＥ２でしか管理されていない場合、計算機ＰＥ１にデータ（葉ページＰ４）の処理要求（参照、更新等）がなされると、インデックスページＰ３以下の子ノードへの降下処理は、計算機ＰＥ２に移譲されることになる。
【００１９】
これによって、図１７（ｂ）に示すように、異なる計算機間で、ラッチカップリングを行いながら、最下層の葉ページＰ４に対してラッチをかけ、参照、更新等の処理を行うことができる。なお、図１７（ｂ）中、破線で示した移譲処理は、図１７（ｃ）に示すように、計算機ＰＥ１及びＰＥ２間で、各メッセージが送受信されることで行われる。この各メッセージは、図１５のステップＳ５３でＹｅｓの場合に計算機ＰＥ２に送信される移譲要求メッセージ、ステップＳ５７の前に計算機ＰＥ２から受信する移譲応答メッセージ、ステップＳ５８でＹｅｓの場合に計算機ＰＥ２に送信される移譲完了メッセージである。
【非特許文献１】吉原朋宏、他４名，「並列ディレクトリ構造Ｆａｔ−Ｂｔｒｅｅの並行性制御とその評価」，［online］，平成１７年３月２７日，電子情報通信学会第１６回データ工学ワークショップ第３回日本データベース学会年次大会，［平成１８年８月４日検索］，インターネット＜URL:http://www.ieice.org/iss/de/DEWS/DEWS2005/procs/papers/2A-o4.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【００２０】
一般に、データをネットワーク上に分散して蓄積する分散データ格納システムにおいて、データを木構造で管理する場合、複数の計算機（ＰＥ）間でデータの一貫性を維持するため、並行性制御を行う必要がある。この並行性制御を行うために、従来の分散データ格納システムでは、木構造で管理されたデータに対して、更新、挿入、削除等の操作を行う場合、木構造の上位から下位の層に向かってラッチ（あるいはロック）カップリングを行っている。
しかし、ラッチカップリングにより、計算機（ＰＥ）間での処理要求の移譲が発生した場合、図１７（ｃ）に示したように、複数（３回）のメッセージがネットワーク上で伝送されることになるため、ネットワークレイテンシが増大する。また、分散データ格納システムでは、スループットの向上を目的として、システム規模を大きくする場合がある。このとき、システム規模の拡大に伴いネットワーク上のメッセージ伝送の頻度が多くなり、スループットの向上の効果が得られにくくなるという問題がある。
【００２１】
本発明は、以上のような問題点に鑑みてなされたものであり、データを木構造で管理する場合に、メッセージ伝送の負荷が大きいラッチカップリングを行わずに、並行性制御を行うことが可能なディレクトリ分散型記憶装置及びデータ処理要求移譲プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載のディレクトリ分散型記憶装置は、記憶手段と、木構造更新手段と、経路探索手段とを備え、ネットワーク環境下で木構造を有するディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記経路探索手段が、経路誤り判定手段と、経路復旧手段と、移譲判定手段と、移譲手段とを備える構成とした。
【００２３】
かかる構成において、ディレクトリ分散型記憶装置は、ページを順に子ページの方向にロックの設定と解除とを行いながら探索していく途中でページの分割が発生した場合、経路誤り判定手段によって、経路誤りを判定する。なお、ここでいうロックには、デッドロック検出機能を持たない高速かつ単純なラッチも含む。
そして、ディレクトリ分散型記憶装置は、経路復旧手段によって、経路誤り判定手段で経路誤りと判定された場合に、経路の復旧を行う。
【００２４】
また、ディレクトリ分散型記憶装置は、移譲判定手段によって、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する。そして、ディレクトリ分散型記憶装置は、移譲手段によって、移譲判定手段で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求（移譲要求メッセージ）を他のディレクトリ分散型記憶装置へ送信する。
なお、従来では、処理要求の移譲途中に経路誤りを発生させないようにページのロック制御を行うため、複数のメッセージを他のディレクトリ分散型記憶装置との間で送受信する必要があったが、このディレクトリ分散型記憶装置では、経路誤りを検出可能としたことで、処理要求の移譲を１回のメッセージ送信で行うことが可能になる。
【００２５】
また、請求項２に記載のディレクトリ分散型記憶装置は、記憶手段と、木構造更新手段と、経路探索手段とを備え、ネットワーク環境下で木構造を有するディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記木構造更新手段が境界値設定手段を備え、前記経路探索手段が、経路誤り判定手段と、経路再探索手段と、移譲判定手段と、移譲手段とを備える構成とした。
【００２６】
かかる構成において、ディレクトリ分散型記憶装置は、境界値設定手段によって、データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだページ内で、参照先の数が予め定めた制限値を超過して当該ページを分割する際に、その分割されたページごとに、当該ページで管理する検索キーの境界値を設定する。これによって、親ページを参照することなく、当該ページで管理されている子ページが、どの検索キーの範囲のページがあるのかを特定することができる。
【００２７】
そして、ディレクトリ分散型記憶装置は、ページを順に子ページの方向にロックの設定と解除とを行いながら探索していく途中でページの分割が発生した場合、経路誤り判定手段によって、境界値設定手段で設定された境界値に基づいて検索キーが該当するページに存在するか否かにより、経路誤りを判定する。なお、ここでいうロックには、デッドロック検出機能を持たない高速かつ単純なラッチも含む。
そして、ディレクトリ分散型記憶装置は、経路再探索手段によって、経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから経路の探索を行う。これによって、正しい経路が探索されることになる。
【００２８】
また、ディレクトリ分散型記憶装置は、移譲判定手段によって、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する。そして、ディレクトリ分散型記憶装置は、移譲手段によって、移譲判定手段で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求（移譲要求メッセージ）を他のディレクトリ分散型記憶装置へ送信する。
なお、従来では、処理要求の移譲途中に経路誤りを発生させないようにページのロック制御を行うため、複数のメッセージを他のディレクトリ分散型記憶装置との間で送受信する必要があったが、このディレクトリ分散型記憶装置では、経路誤りを検出可能としたことで、処理要求の移譲を１回のメッセージ送信で行うことが可能になる。
【００２９】
また、請求項３に記載のディレクトリ分散型記憶装置は、請求項２に記載のディレクトリ分散型記憶装置において、プロセスを管理するプロセス管理手段を備え、木構造更新手段が、前記ページを分割した際に、当該ディレクトリ分散型記憶装置以外の参照先のみからなるページを、当該ディレクトリ分散型記憶装置の管理対象外のページであると判定する管理対象ページ判定手段と、この管理対象ページ判定手段で管理対象外のページであると判定したページを削除するページ削除手段とを備え、前記ページ削除手段が、当該ページを参照するプロセスが存在しなくなった段階で、当該ページを削除する構成とした。
【００３０】
かかる構成において、ディレクトリ分散型記憶装置は、木構造更新手段がページを分割した際に、管理対象ページ判定手段によって、当該ディレクトリ分散型記憶装置以外の参照先のみからなるページを、当該ディレクトリ分散型記憶装置の管理対象外のページであると判定する。なお、この管理対象外のページより下位のページは、他のディレクトリ分散型記憶装置で管理されているため、当該ディレクトリ分散型記憶装置で管理する必要がないページである。
そして、ディレクトリ分散型記憶装置は、ページ削除手段によって、管理対象ページ判定手段で管理対象外のページであると判定したページを削除する。このとき、ページ削除手段は、削除対象のページを参照するプロセスが存在しなくなった段階で、当該ページを削除する。これによって、完全に不要になったページのみが削除されることになる。
【００３１】
さらに、請求項４に記載のディレクトリ分散型記憶装置は、請求項３に記載のディレクトリ分散型記憶装置において、木構造更新手段が、前記ページを分割した際に、親ページに参照先が記述されている一方のページが当該ディレクトリ分散型記憶装置以外の参照先のみからなるページである場合に、分割された他方のページの内容を前記一方のページに上書きするエントリ複製手段を備え、このエントリ複製手段により上書きされた後に、前記ページ削除手段が、前記他方のページを削除する構成とした。
【００３２】
かかる構成において、ディレクトリ分散型記憶装置は、エントリ複製手段によって、分割された他方のページの内容を、親ページに参照先が記述されている一方のページに上書きする。そして、ディレクトリ分散型記憶装置は、ページ削除手段によって、他方のページを削除する。このとき、他方のページを参照している親ページは存在しないため、上位のページからの参照の有無を確認することなく削除することができる。
【００３３】
また、請求項５に記載のデータ処理要求移譲プログラムは、データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページで構成されるディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記データへの処理要求を、ネットワークに接続された他のディレクトリ分散型記憶装置に移譲するために、コンピュータを、境界値設定手段、ロック設定手段、経路誤り判定手段、経路再探索手段、移譲判定手段、移譲手段、として機能させる構成とした。
【００３４】
かかる構成によれば、データ処理要求移譲プログラムは、境界値設定手段によって、ページ内の参照先の数が予め定めた制限値を超過して当該ページを分割する際に、分割されたページごとに、当該ページで管理する検索キーの境界値を設定する。これによって、親ページを参照することなく、当該ページで管理されている子ページが、どの検索キーの範囲のページがあるのかを特定することができる。
【００３５】
また、データ処理要求移譲プログラムは、ロック設定手段によって、データまでの経路を探索する経路において、上位のページにロックを設定し、下位ページへの参照先を取得した後に、ロックを解除し、下位のページにロックを設定する処理を繰り返す。
さらに、データ処理要求移譲プログラムは、経路誤り判定手段によって、データまでの経路を探索する経路途中のページにおいて、当該データの検索キーの値が、境界値設定手段で設定された境界値の範囲内であるか否かに基づいて、経路誤りを判定する。
そして、データ処理要求移譲プログラムは、経路再探索手段によって、経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから経路の探索を行う。これによって、正しい経路が探索されることになる。
【００３６】
また、データ処理要求移譲プログラムは、移譲判定手段によって、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する。そして、データ処理要求移譲プログラムは、移譲手段によって、移譲判定手段で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求（移譲要求メッセージ）を他のディレクトリ分散型記憶装置へ送信する。
【発明の効果】
【００３７】
本発明は、以下に示す優れた効果を奏するものである。
請求項１、請求項２又は請求項５に記載の発明によれば、ラッチカップリング処理を行わないため、処理要求を他のディレクトリ分散型記憶装置に移譲する場合に、ネットワークを介したメッセージの送受信回数を１回で処理することができる。これによって、システム規模の拡大を行った場合に、ネットワークへの負荷を抑えることができ、スループットを向上させることができる。
【００３８】
請求項３に記載の発明によれば、サービスを継続したまま、不要になったページを削除することが可能となり、メモリの効率的利用が可能で、データを探索する際の処理速度を高速化することができる。
請求項４に記載の発明によれば、親ページに参照先が記述されていないページを削除するため、経路再探索手段が行う再探索の回数を減らすことができ、データを探索する際の処理速度を高速化することができる。
【発明を実施するための最良の形態】
【００３９】
≪第１実施形態≫
［ディレクトリ分散型記憶装置の構成］
まず、図１を参照して、第１実施形態に係るディレクトリ分散型記憶装置の構成について説明する。図１は、本発明の第１実施形態に係るディレクトリ分散型記憶装置の構成を示すブロック図である。
【００４０】
図１に示したディレクトリ分散型記憶装置ＰＥＡは、ネットワークＮに接続された他のディレクトリ分散型記憶装置（図示せず）と協働し、データベース等のデータを分散して記憶するものである。このディレクトリ分散型記憶装置ＰＥＡは、図１４で説明したＦａｔ−Ｂｔｒｅｅ構造のディレクトリ構造によってデータを記憶管理する計算機ＰＥに相当する。ここでは、ディレクトリ分散型記憶装置ＰＥＡは、通信制御部１と、記憶部２と、制御部３とを備えている。
【００４１】
通信制御部１は、ネットワークＮを介して、クライアントコンピュータ（図示せず）や他のディレクトリ分散型記憶装置（図示せず）と、データや制御情報の送受信を行うものである。例えば、通信制御部１は、ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）の通信プロトコルによってデータ等の送受信を行う通信ボードである。
【００４２】
記憶部２は、データベース等のデータや、ディレクトリ構造を特定する木構造情報等を記憶しておくもので、一般的なハードディスク等の記憶装置である。この記憶部２には、データＤＴと、木構造情報ＴＲと、エントリ制限情報ＥＬとを記憶している。
【００４３】
データＤＴは、Ｆａｔ−Ｂｔｒｅｅ構造における葉ページであって、データの実体である。このデータＤＴは、記憶領域の予め定められたページ単位で管理され、所定のページ数（後記するエントリ制限情報ＥＬに含まれる）を超過する場合は分割される。
【００４４】
木構造情報ＴＲは、Ｆａｔ−Ｂｔｒｅｅ構造のデータ構造を示す情報である。ここでは、木構造情報ＴＲは、Ｆａｔ−Ｂｔｒｅｅ構造のルートページから、記憶部２に記憶されているデータ（葉ページ）ＤＴまでのアクセスパスを示すインデックスページを記憶している。
【００４５】
ここで、図２を参照して木構造情報ＴＲの内容について説明する。図２は、木構造情報を構成するインデックスページの構造を示すデータ構造図である。従来、Ｆａｔ−Ｂｔｒｅｅ構造のインデックスページは、インデックスページを検索する際のキーとなる「検索キー」と、下層のインデックスページ（又は葉ページ）の参照先を示す「ポインタ」とを対として、検索キーが昇順（又は降順）となるように複数連結したデータ構造を有している。
この木構造情報ＴＲでは、図２に示すように、「検索キー」と「ポインタ」との対の情報以外に、「削除ビットＤｂ」と、「始端検索キーＫｓ」と、「終端検索キーＫｅ」とを付加している。
【００４６】
「削除ビットＤｂ」は、当該インデックスページが有効なページであるか否かを示す情報である。この削除ビットＤｂに、インデックスページが削除対象のページとなっていることを示すビット（例えば、値“１”）を設定することで、無効なページであることを意味することとする。
【００４７】
「始端検索キーＫｓ」は、当該インデックページおいて管理される検索キーの始端の値を示す情報である。
「終端検索キーＫｅ」は、同じ階層で後続するインデックスページとの検索キーの境界値を示す情報である。この終端検索キーＫｅは、例えば、図２に示すように、インデックスページＰ２にインデックスページＰ３が続く場合、後続のインデックスページＰ３における先頭の検索キー（始端検索キー）の値“Ｋｉ”と、インデックスページＰ２の終端検索キーＫｅの値とを同一に設定しておく。これによって、インデックスページＰ２において、検索キーの値の範囲を明確にすることができる。なお、インデックスページが、ルートページである場合は、終端検索キーの値は、検索キーの値とはならない特殊な値、例えば“ｎｕｌｌ”を設定しておく。この場合、各階層の最終のインデックスページにおける終端検索キーの値も、“ｎｕｌｌ”が設定されることになる。
この「削除ビットＤｂ」、「始端検索キーＫｓ」及び「終端検索キーＫｅ」の具体的な利用方法については、後記することとする。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００４８】
エントリ制限情報ＥＬは、Ｆａｔ−Ｂｔｒｅｅ構造において、インデックスページに登録される子ページの数の最大値や、葉ページとして登録できるデータの数の最大値を示す情報である。このエントリ制限情報ＥＬは、後記する制御部３によって参照され、データの更新に伴う木構造の変化が発生するか否かを判定するために用いられる。
【００４９】
制御部３は、ディレクトリ分散型記憶装置ＰＥＡ全体の動作を制御するものであって、一般的なコンピュータにおけるＣＰＵ（Central Processing Unit：中央処理装置）を制御するものである。なお、制御部３は、一般的なＯＳ（Operating System）上で、クライアントコンピュータ（図示せず）や他のディレクトリ分散型記憶装置（図示せず）からの要求に基づいて、複数のプロセスにより動作するものである。ここでは、制御部３は、データ操作手段１０と、木構造管理手段２０と、制御情報送受信手段３０と、プロセス管理手段４０とを備えている。
【００５０】
データ操作手段１０は、通信制御部１を介して、データの送受信操作を行うものである。なお、データ操作手段１０は、木構造管理手段２０において、データへのアクセスパスが、当該ディレクトリ分散型記憶装置ＰＥＡが管理するデータＤＴへのアクセスパスである場合にのみ起動される。ここでは、データ操作手段１０は、データ送受信手段１１と、データ参照手段１２と、データ更新手段１３とを備えている。
【００５１】
データ送受信手段１１は、制御情報送受信手段３０から通知されるデータの送信元（例えば、クライアントコンピュータ等）から、通信制御部１を介してデータを受信したり、データの送信先（例えば、クライアントコンピュータ等）に、通信制御部１を介してデータを送信したりするものである。
このデータ送受信手段１１は、データ参照手段１２から出力されるデータを、通信制御部１を介して送信し、通信制御部１を介して受信したデータをデータ更新手段１３に出力する。
【００５２】
データ参照手段１２は、記憶部２に記憶されているデータＤＴを読み出すものである。このデータ参照手段１２は、木構造管理手段２０から通知される制御情報（記憶元のアドレス等のアクセスパス）に基づいて、データＤＴを記憶部２から読み出す。このデータ参照手段１２で読み出されたデータＤＴは、データ送受信手段１１に出力される。
【００５３】
データ更新手段１３は、データ送受信手段１１で受信したデータを、記憶部２に書き込むものである。このデータ更新手段１３は、木構造管理手段２０から通知される制御情報（記憶先のアドレス等のアクセスパス）に基づいて、データを記憶部２に書き込む。
また、データ更新手段１３は、木構造管理手段２０から通知される制御情報に基づいて、指示されたデータＤＴを記憶部２から削除する動作も行う。なお、データＤＴを削除する場合、親ページのインデックスページに設定されているポインタを削除する必要があるため、データＤＴを削除した旨を木構造管理手段２０に通知する。
【００５４】
木構造管理手段２０は、記憶部２に記憶されている木構造情報ＴＲとエントリ制限情報ＥＬとに基づいて、記憶部２に記憶されるデータＤＴを階層構造で管理するものである。また、木構造管理手段２０は、Ｆａｔ−Ｂｔｒｅｅ構造（図１４参照）のディレクトリ構造によりデータＤＴを管理するものとする。ここでは、木構造管理手段２０は、ラッチ設定手段２１と、経路探索手段２２と、木構造更新手段２３とを備えている。
【００５５】
ラッチ設定手段（ロック設定手段）２１は、後記する経路探索手段２２でページを探索する際に、経路探索手段２２からの要求に基づいて、要求されたページに対してラッチを設定したり、解除したりするものである。このラッチは、ロックの一種であり、デッドロック検出機能を持たないセマフォの一種である。なお、ここでは、ラッチを用いることにしているが、デッドロック検出機能を持つ一般的なロックを用いることとしてもよい。
【００５６】
経路探索手段２２は、木構造情報ＴＲを参照して、制御情報送受信手段３０から制御情報として通知される検索キーに基づいて、ルートページから子ページに向かって、順次インデックスページに対するラッチの設定及び解除を繰り返しながら、処理対象の葉ページを検索し、ラッチを設定するものである。ここでは、経路探索手段２２は、移譲判定手段２２１と、移譲手段２２２と、経路誤り判定手段２２３と、経路再探索手段２２４とを備えている。
【００５７】
移譲判定手段２２１は、要求された処理を自装置で継続するか、他のディレクトリ分散型記憶装置（図示せず）に移譲するか否かを判定するものである。ここでは、移譲判定手段２２１は、木構造情報ＴＲのインデックスページにおいて、検索キーに対応するポインタが、自装置の木構造情報ＴＲで管理されているインデックスページを指し示している場合に、自装置で処理を継続すると判定する。
一方、ポインタが他のディレクトリ分散型記憶装置（図示せず）で管理されているインデックスページを指し示している場合、移譲判定手段２２１は、他のディレクトリ分散型記憶装置に、要求された処理を移譲すると判定する。なお、移譲すると判定した場合、移譲判定手段２２１は、その旨を移譲手段２２２に通知する。
【００５８】
移譲手段２２２は、移譲判定手段２２１で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求を他のディレクトリ分散型記憶装置へ送信するものである。ここでは、移譲手段２２２は、移譲判定手段２２１から、移譲する旨を通知された段階で、制御情報送受信手段３０を介して、他のディレクトリ分散型記憶装置に、処理プロセスを特定する識別子であるトランザクションＩＤ、検索キーの値、インデックスページのポインタ、並びに、要求された処理内容（参照、挿入、更新、削除）を含んだ制御情報を移譲要求メッセージとして通知する。
【００５９】
ここで、図３を参照（適宜図１参照）して、経路探索手段２２により行うディレクトリ分散型記憶装置間の処理の移譲手順について説明する。図３は、ディレクトリ分散型記憶装置間で行う処理の移譲手順を示す模式図である。
なお、ここでは、図３（ａ）に示すように、ディレクトリ構造が図１４に示したＦａｔ−Ｂｔｒｅｅ構造において、ルートページＰ１から対象データの葉ページＰ４までが、異なるディレクトリ分散型記憶装置ＰＥＡ（ＰＥ１，ＰＥ２）で管理されているものとする。
【００６０】
このとき、ディレクトリ分散型記憶装置ＰＥ１は、図３（ｂ）に示すように、ディレクトリ分散型記憶装置ＰＥ１の内部で管理しているページＰ１にラッチを設定し、その子ページであるページＰ２を探索した後、親ページとなるページＰ１のラッチを解除する。その後、ディレクトリ分散型記憶装置ＰＥ１は、ページＰ２にラッチを設定し、その子ページであるページＰ３を探索する。このとき、ページＰ３は、ディレクトリ分散型記憶装置ＰＥ２で管理されているため、ディレクトリ分散型記憶装置ＰＥ１は、親ページとなるページＰ２のラッチを解除し、ディレクトリ分散型記憶装置ＰＥ２に対して、葉ページＰ４に対する処理を移譲する。
【００６１】
その後、ディレクトリ分散型記憶装置ＰＥ２が、ページＰ３にラッチを設定し、その子ページである葉ページＰ４を探索した後、親ページとなるページＰ３のラッチを解除する。そして、ディレクトリ分散型記憶装置ＰＥ２は、葉ページＰ４にラッチを設定し、葉ページＰ４に対する処理（参照、更新等）を行う。なお、図３（ｂ）中“Ｌ”は、ラッチが設定された状態を示している。
このとき、図３（ｂ）中、破線で示した移譲処理において、図３（ｃ）に示すように、ディレクトリ分散型記憶装置ＰＥ１から、ディレクトリ分散型記憶装置ＰＥ２に対して、移譲要求メッセージのみが送信される。
【００６２】
なお、この場合、図３（ｂ）に示すように、子ページにラッチを設定する前に親ページのラッチを解除するため、他のプロセスによる処理によって、木構造情報ＴＲが更新される場合があり、子ページに降下する際に経路誤りが発生することがある。
そこで、ディレクトリ分散型記憶装置ＰＥＡは、後記する経路誤り判定手段２２３により、経路誤りを判定し、正しい経路を補償することとしている。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００６３】
経路誤り判定手段２２３は、インデックスページを降下していく際に、その経路に誤りがあるか否かを判定するものである。ここでは、経路誤り判定手段２２３は、木構造情報ＴＲのインデックスページにおいて、処理対象の検索キーが当該インデックスページに属するものであるか否かを判定することで、経路の誤りを判定する。
具体的には、経路誤り判定手段２２３は、処理対象の検索キーの値が、インデックスページにおける「始端検索キーＫｓ」の領域（図２参照）に記述されている検索キーの値以上で、「終端検索キーＫｅ」の領域（図２参照）に記述されている検索キーの値未満であるときに、経路が正しいと判定し、それ以外のときに、経路が誤っていると判定する。なお、経路が誤っていると判定した場合、経路誤り判定手段２２３は、その旨を経路再探索手段２２４に通知する。
【００６４】
なお、ここでは、経路誤り判定手段２２３が、検索キーの始端及び終端に基づいて経路誤りを判定することとしたが、既存の技術であるＡＲＩＥＳ／ＩＭ（Algorithm for Recovery and Isolation Exploiting Semantics for Index Management）という方式で用いられている方法を応用して用いてもよい。
このＡＲＩＥＳ／ＩＭ方式の方法を応用すると、まず、ＳＭ＿ｂｉｔというビットを各ページに設け、初期値として“０”に設定しておく。そして、ページを更新する際には、木ラッチと呼ばれるシステムに１つしかないラッチを獲得する。この更新のためのラッチ獲得方法としては、ボトムアップのラッチカップリングを用いる。そして、更新されたページのＳＭ＿ｂｉｔに“１”を設定する。その後、関連するページの更新が終わった段階で、ＳＭ＿ｂｉｔを“０”に設定し、木ラッチを解放する。
【００６５】
そして、経路誤り判定手段２２３は、インデックスページを降下していく際に、ＳＭ＿ｂｉｔに“１”が設定されているページに至った場合、経路誤りの可能性があると判定する。そして、経路誤り判定手段２２３は、経路誤りの可能性があると判定した場合、さらに、処理対象の検索キーの値が、当該ページに含まれている検索キーの値よりも大きいか否かを判定し、大きい場合に経路が誤っていると判定する。このとき、経路誤り判定手段２２３は、木ラッチが解放されるまで待機する。
そして、経路誤り判定手段２２３は、木ラッチが解放された後、経路再探索手段２２４（経路復旧手段）に経路誤りがあった旨を通知する。
【００６６】
経路再探索手段（経路復旧手段）２２４は、経路誤り判定手段２２３で経路誤りと判定された場合に、経路の復旧を行うものである。ここでは、経路再探索手段２２４は、再度最上位のページからデータの探索を行うことで、経路の復旧を行う。この場合、経路再探索手段２２４は、プロセス管理手段４０に対して、当該プロセスの再起動を要求する。この後、プロセスが再起動されることで、正しい経路によりデータ（葉ページ）が探索されることになる。
【００６７】
なお、ここでは、経路再探索手段２２４が、プロセスを再起動することで、最上位のページからデータの探索を行うこととしたが、経路誤りと判定したページの上位ページから再度探索を行うこととしてもよい。この場合、例えば、各ページにページの更新によって値が変化するログ用番号（ＬＳＮ：Log Sequence Number）を付しておき、経路探索時には、各ページのログ用番号を記憶し、復旧時には、このログ用番号が変化していない上位のページまで遡ることで、正しい経路に復旧することができる。
【００６８】
木構造更新手段２３は、木構造情報ＴＲにおけるページの追加、削除等に伴う木構造の更新を行うものである。ここでは、木構造更新手段２３は、ページ削除手段２３１と、ページ分割・追加手段２３２とを備えている。
【００６９】
ページ削除手段２３１は、不用になったページを削除して、木構造情報ＴＲを更新するものである。このページ削除手段２３１は、データ操作手段１０によってデータＤＴが削除されることで、参照先のページがなくなったインデックスページ、あるいは、参照先が他のディレクトリ分散型記憶装置（図示せず）へのポインタのみとなったインデックスページを削除する。
【００７０】
なお、ページ削除手段２３１は、削除ビット設定手段２３１ａを備え、ページを削除する場合、削除ビット設定手段２３１ａによって、当該ページに対して削除ビットを設定し、プロセス管理手段４０に対して、削除ビット設定時点で起動されていたプロセスの終了を待つ旨の通知を行う。そして、ページ削除手段２３１は、削除ビット設定時点で起動されていたプロセスの終了をプロセス管理手段４０から通知された段階で、該当するページを削除し、木構造情報ＴＲを更新する。
これによって、削除ビット設定時点で当該ページを参照していたプロセスの動作を保証することができる。
【００７１】
削除ビット設定手段２３１ａは、指定されたページに削除ビットを設定するものである。具体的には、削除ビット設定手段２３１ａは、指定されたページの「削除ビットＤｂ」の領域（図２参照）に、削除対象のページであることを示すビット（例えば、値“１”）を設定する。これによって、削除ビットが設定された後に、当該ページを参照するプロセスは、当該ページが無効であることを認識することができる。
【００７２】
ページ分割・追加手段２３２は、新規にページを追加するものである。なお、ページ分割・追加手段２３２は、新規にページを追加し、元のページのエントリ数がエントリ制限情報ＥＬで示される最大値を越える場合、元のエントリの半分を新たなページに移すことでページの分割を行い、木構造情報ＴＲを更新する。
このページ分割・追加手段２３２は、データ操作手段１０によってデータＤＴが追加されることによって、そのデータＤＴを参照する親ページのエントリ数が、エントリ制限情報ＥＬで示される最大値を超過する場合に、該当ページを分割する。なお、ページ分割・追加手段２３２は、親ページのエントリ数が、さらに、エントリ制限情報ＥＬで示される最大値を超過する場合には、順次親ページを分割する。そして、その分割がルートページにまで波及した場合、ページ分割・追加手段２３２は、当該ルートページを分割し、その上位にルートページを生成する。
ここでは、ページ分割・追加手段２３２は、境界値設定手段２３２ａと、管理対象ページ判定手段２３２ｂと、ポインタ設定手段２３２ｃとを備えている。
【００７３】
境界値設定手段２３２ａは、ページが追加又は分割される際に、ページ内に各ページ間の検索キーの境界値を設定するものである。具体的には、境界値設定手段２３２ａは、インデックスページの「終端検索キーＫｅ」の領域（図２参照）に、追加又は分割により新たに生成された後続のインデックスページの先頭に記述されている検索キーの値を設定する。
【００７４】
ここで、図４を参照（適宜図１参照）して、インデックスページの境界値設定の手法について説明する。ここでは、インデックスページを分割する場合を例に説明する。図４は、インデックスページの分割により境界値を設定する例を説明するための説明図であって、（ａ）は分割前、（ｂ）は分割後のインデックスページの内容を示している。
【００７５】
ここでは、図４（ａ）に示すインデックスページＰ１は、Ｋ０以上Ｋｎ未満（Ｋ０≦Ｋｉ＜Ｋｎ）の検索キーを有するインデックスページである。ここで、検索キーＫｉ以降を分割することとする。
この場合、ページ分割・追加手段２３２は、図４（ｂ）に示すように、インデックスページＰ１を、検索キーの値がＫｉ未満のインデックスページＰ２と、Ｋｉ以上のインデックスページＰ３とに分割する。このとき、境界値設定手段２３２ａが、インデックスページＰ３における先頭の検索キーの値Ｋｉを、インデックスページＰ２の「終端検索キーＫｅ」の領域に設定する。これによって、インデックスページの検索キーの境界値により、インデックスページの検索キーの両端を示すことができるため、前記した経路誤り判定手段２２３は、経路の誤りを判定することが可能になる。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００７６】
管理対象ページ判定手段２３２ｂは、ページを分割することにより生成された２つのページが、当該装置ＰＥＡの管理対象ページであるか否かを判定するものである。ここでは、管理対象ページ判定手段２３２ｂは、ページ内のすべてのポインタが、当該装置ＰＥＡ以外の他のディレクトリ分散型記憶装置（図示せず）で管理されているページを指し示すポインタ（リモートポインタ）である場合に、当該ページを管理対象ページでないと判定する。一方、ページ内のポインタのうち一つでも当該装置ＰＥＡで管理されているページを指し示すポインタ（ローカルポインタ）である場合は、当該ページを管理対象ページであると判定する。
なお、管理対象ページ判定手段２３２ｂは、分割により生成されたページを管理対象ページでないと判定したときは、ページ削除手段２３１によって、当該ページを削除する。これによって、不用なページが管理から除外されることになる。
【００７７】
ポインタ設定手段２３２ｃは、ページの追加又は分割によって、新たに生成されたページへのポインタを親ページに設定するものである。なお、ポインタ設定手段２３２ｃは、ページの分割の際は、管理対象ページ判定手段２３２ｂによって、管理対象ページであると判定されたページのみ親ページにポインタを設定する。
【００７８】
ここで、図５〜図８を参照（適宜図１参照）して、インデックスページの分割手法について説明する。図５は、インデックスページを分割した際の分割パターンを説明するための説明図である。
ここでは、図５（ａ）に示すように、インデックスページＰ１（親ページ）の検索キーＫｉのポインタで示されているインデックスページＰ２（子ページ）は、エントリ数がエントリ制限情報ＥＬで示される最大値の状態（Ｆｕｌｌ ｅｎｔｒｙ）であるとする。
【００７９】
図５（ａ）に示した状態で、インデックスページＰ２に新たなエントリを設定しようとすると、ページ分割・追加手段２３２によって、図５（ｂ）に示すように、インデックスページＰ２が分割される。このとき、分割直後のインデックスページＰ２は、親ページ（インデックスページＰ１）からポインタで指し示されているページ（インデックスページＰ２１：便宜上「左側ページ」と呼ぶ）と、新たに分割により生成され親ページ（インデックスページＰ１）からポインタで指し示されていないページ（インデックスページＰ２２：便宜上「右側ページ」と呼ぶ）とに分割されることになる。
【００８０】
このように分割されたとき、分割されたページのそれぞれが、当該装置ＰＥＡで管理されているページを指し示すポインタを含んでいるか、当該装置ＰＥＡ以外の他のディレクトリ分散型記憶装置（図示せず）で管理されているページを指し示すポインタのみであるかによって、分割パターンを（ｂ−１）、（ｂ−２）及び（ｂ−３）に分類することができる。なお、当該装置ＰＥＡで管理されているページを指し示すポインタをロールポインタと呼び、図中「ｌｏｃａｌ」で示す。また、当該装置ＰＥＡ以外の他のディレクトリ分散型記憶装置（図示せず）で管理されているページを指し示すポインタをリモートポインタと呼び、図中「ｒｅｍｏｔｅ」で示す。
【００８１】
まず、第１の分割パターンは、（ｂ−１）に示すように、分割されたページ（インデックスページＰ２１，Ｐ２２）のどちらにもローカルポインタが含まれている分割パターンである。
また、第２の分割パターンは、（ｂ−２）に示すように、左側ページＰ２１にはローカルポインタが含まれているが、右側ページＰ２２にはローカルポインタが含まれておらずリモートポインタのみが含まれている分割パターンである。
また、第３の分割パターンは、（ｂ−３）に示すように、右側ページＰ２２にはローカルポインタが含まれているが、左側ページＰ２１にはローカルポインタが含まれておらずリモートポインタのみが含まれている分割パターンである。
【００８２】
このように、インデックスパターンを分割した場合、リモートポインタを有していないページは、当該装置ＰＥＡには不要なページであるため削除する必要がある。
そこで、以下、図６〜図８を参照（適宜図１参照）して、分割後の処理について説明する。図６は、第１の分割パターンにおける分割後の処理を説明するための説明図である。図７は、第２の分割パターンにおける分割後の処理を説明するための説明図である。図８は、第３の分割パターンにおける分割後の処理を説明するための説明図である。
【００８３】
第１の分割パターンでは、図６（ａ）に示すように、分割されたページ（インデックスページＰ２１，Ｐ２２）のどちらにもローカルポインタが含まれているため、ページを削除する必要はない。そこで、ディレクトリ分散型記憶装置ＰＥＡは、図６（ｂ）に示すように、分割により新たに生成されたページ（インデックスページＰ２２）へのポインタ（ローカルポインタ）を親ページ（インデックスページＰ１）に設定する。
【００８４】
また、第２の分割パターンでは、図７（ａ）に示すように、左側ページＰ２１にはローカルポインタが含まれているが、右側ページＰ２２にはローカルポインタが含まれていないため、右側ページＰ２２を削除する必要がある。そこで、ディレクトリ分散型記憶装置ＰＥＡは、図７（ｂ）に示すように、分割により新たに生成されたページ（インデックスページＰ２２）を削除し、削除されたページのコピーを管理している他のディレクトリ分散型記憶装置へのポインタ（リモートポインタ）を親ページ（インデックスページＰ１）に設定する。
【００８５】
また、第３の分割パターンでは、図８（ａ）に示すように、右側ページＰ２２にはローカルポインタが含まれているが、左側ページＰ２１にはローカルポインタが含まれていないため、左側ページＰ２１を削除する必要がある。そこで、ディレクトリ分散型記憶装置ＰＥＡは、図８（ｂ）に示すように、親ページ（インデックスページＰ１）からポインタで指し示されている左側ページ（インデックスページＰ２１）を削除し、削除されたページのコピーを管理している他のディレクトリ分散型記憶装置へのポインタ（リモートポインタ）を親ページ（インデックスページＰ１）に設定する。さらに、分割により新たに生成されたページ（インデックスページＰ２２）へのポインタ（ローカルポインタ）を親ページ（インデックスページＰ１）に設定する。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００８６】
制御情報送受信手段３０は、通信制御部１を介して、図示していないクライアントコンピュータや他のディレクトリ分散型記憶装置と制御情報の送受信を行うものである。ここでは、制御情報送受信手段３０は、クライアントコンピュータ等から受信した制御情報をデータ操作手段１０や木構造管理手段２０に出力し、データ操作手段１０や木構造管理手段２０から出力された制御信号をクライアントコンピュータ等に送信する。
【００８７】
プロセス管理手段４０は、ディレクトリ分散型記憶装置ＰＥＡ内で起動されるプロセスを管理するものである。
ここでは、プロセス管理手段４０は、経路探索手段２２からプロセスの再起動が通知された場合、要求のあったプロセスを再起動する。これによって、経路探索手段２２における経路探索がリスタートされることになる。
また、ページ削除手段２３１から、削除ビット設定時点で起動されていたプロセスの終了を待つ旨の通知があった場合、プロセス管理手段４０は、その時点において起動していたプロセスがすべて終了した段階で、ページ削除手段２３１にプロセスの終了を通知する。これによって、他のプロセスに影響を与えることなくページを削除することができる。
【００８８】
以上説明したように、ディレクトリ分散型記憶装置ＰＥＡを構成することで、木構造の上位から下位の層に向かってラッチを設定する際に、従来のようなラッチカップリングを行う必要がないため、処理要求の移譲が発生する場合であっても、ネットワーク上のメッセージ伝送の回数が１回で済む。このように、ネットワーク上のメッセージ伝送の頻度を抑えることができるため、従来に比べ、システム規模の拡大によるスループットの向上の効果を高めることができる。
【００８９】
なお、ここでは、ディレクトリ分散型記憶装置ＰＥＡのディレクトリ構造がＦａｔ−Ｂｔｒｅｅ構造であるものとして説明を行ったが、一般的な並列Ｂｔｒｅｅ構造を有する場合であっても構わない。
また、ディレクトリ分散型記憶装置ＰＥＡの制御部３は、一般的なコンピュータにプログラムを実行させ、コンピュータ内の演算装置や記憶装置を動作させることにより実現することができる。ここで実現される処理要求の移譲を行うデータ処理要求移譲プログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００９０】
［ディレクトリ分散型記憶装置の動作］
次に、図９及び図１０を参照して、ディレクトリ分散型記憶装置の動作について説明する。なお、ここでは、ディレクトリ分散型記憶装置ＰＥＡの木構造管理手段２０において行われる、処理要求の移譲処理動作とページの分割処理について、詳細に説明を行うことにする。図９は、本発明のディレクトリ分散型記憶装置における処理要求の移譲処理動作を示すフローチャートである。図１０は、本発明のディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。
【００９１】
（移譲処理動作）
最初に、図９を参照（適宜図１参照）して、データの処理要求の移譲処理動作について説明する。
まず、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２によって、初期値として、親ページを“ｎｕｌｌ”、子ページをルートページに設定する（ステップＳ１）。そして、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２によって、木構造情報ＴＲを参照することで、要求のあった検索キーのページをアクセスする際に、さらに子ページへの降下が必要であるか否かを判定する（ステップＳ２）。
【００９２】
ここで、降下が必要でない場合（ステップＳ２でＮｏ）、そのページが要求のあった葉ページであるため、ディレクトリ分散型記憶装置ＰＥＡは、データ操作手段１０によって、当該葉ページへの処理を実行し（ステップＳ３）、動作を終了する。一方、降下が必要である場合（ステップＳ２でＹｅｓ）、ディレクトリ分散型記憶装置ＰＥＡは、移譲判定手段２２１によって、木構造情報ＴＲを参照し、要求のあったページのポインタが自装置ＰＥＡで管理されているページへのポインタであるか否かに基づいて、移譲が必要であるか否かを判定する（ステップＳ４）。
【００９３】
ここで、移譲が必要な場合（ステップＳ４でＹｅｓ）、ディレクトリ分散型記憶装置ＰＥＡは、移譲手段２２２によって、移譲先の他のディレクトリ分散型記憶装置（図示せず）へ処理要求の移譲を要求し（移譲要求メッセージ送信）、動作を終了する。この段階で、移譲先への移譲処理が開始されたことになる。なお、処理要求の移譲を要求された他のディレクトリ分散型記憶装置は、後記するステップＳ５以降の動作を実行する。
一方、移譲が必要でない場合（ステップＳ４でＮｏ）、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２からの指示に基づいてラッチ設定手段２１により、子ページにラッチを設定する（ステップＳ５）。
【００９４】
そして、ディレクトリ分散型記憶装置ＰＥＡは、経路誤り判定手段２２３によって、処理対象の検索キーが当該ページに属するものであるか否かを判定することで、経路の誤りを判定する（ステップＳ６）。すなわち、経路誤り判定手段２２３が、検索キーの値が当該ページに設定されている先頭の検索キーの値以上で、終端検索キーの値未満であることを判定することで、経路の正誤を判定する。
ここで、経路に誤りがある場合（ステップＳ６で「誤」）、ディレクトリ分散型記憶装置ＰＥＡは、経路再探索手段２２４によって、プロセス管理手段４０に対してプロセスの再起動を要求することで、ステップＳ１から再度探索動作を行う。
一方、経路が正しい場合（ステップＳ６で「正」）、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２によって、対象となるページを子ページに降下させる。すなわち、経路探索手段２２が、子ページを新たな親ページに設定し、孫ページを新たな子ページに設定する（ステップＳ７）。
【００９５】
さらに、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２からの指示に基づいてラッチ設定手段２１により、親ページのラッチを解除する（ステップＳ８）。
その後、ディレクトリ分散型記憶装置ＰＥＡは、ステップＳ１に戻って、処理対象の葉ページに到達するまで動作を続ける。
【００９６】
以上の動作によって、ディレクトリ分散型記憶装置ＰＥＡは、処理対象のページが当該装置ＰＥＡに存在しない場合、ネットワーク上で１回の移譲要求メッセージを送信だけで、他のディレクトリ分散型記憶装置に処理を移譲することができる。また、処理途中で他のプロセスの動作によるページの分割等が発生した場合でも、経路誤りを検出することができるため、正しい経路で目的の処理対象ページに到達することができる。
【００９７】
（分割処理動作）
次に、図１０を参照（適宜図１、図６〜図８参照）して、ページの分割処理動作について説明する。ここでは、インデックスページのエントリ数がエントリ制限情報ＥＬで示される最大値を超過した以降の動作について説明する。
【００９８】
まず、ディレクトリ分散型記憶装置ＰＥＡは、ページ分割・追加手段２３２によって、対象のページ（インデックスページ）を分割する（ステップＳ２０）。
そして、ディレクトリ分散型記憶装置ＰＥＡは、境界値設定手段２３２ａによって、ページ内に検索キーの境界値を設定する（ステップＳ２１）。
【００９９】
その後、ディレクトリ分散型記憶装置ＰＥＡは、管理対象ページ判定手段２３２ｂによって、分割されたページのうちで、リモートポインタのみが設定されているページが存在するか否かを判定する（ステップＳ２２）。ここで、リモートポインタのみが設定されているページが存在しない場合（ステップＳ２２でＮｏ）、ディレクトリ分散型記憶装置ＰＥＡは、ポインタ設定手段２３２ｃによって、親ページにポインタが設定されていない、分割によって新たに生成されたページ（図６中、インデックスページＰ２２〔右側ページ〕）のポインタを親ページに設定し（ステップＳ２３）、動作を終了する。
【０１００】
一方、リモートポインタのみが設定されているページが存在する場合（ステップＳ２２でＹｅｓ）、ディレクトリ分散型記憶装置ＰＥＡは、管理対象ページ判定手段２３２ｂによって、当該ページへのポインタが親ページに設定されているか否かを判定する（ステップＳ２４）。
【０１０１】
ここで、当該ページへのポインタが親ページに設定されていない場合（ステップＳ２４でＮｏ）、すなわち、分割によって新たに生成されたページ（図７中、インデックスページＰ２２〔右側ページ〕）である場合、ディレクトリ分散型記憶装置ＰＥＡは、ページ削除手段２３１によって、当該ページを削除する（ステップＳ２５）。その後、ディレクトリ分散型記憶装置ＰＥＡは、ポインタ設定手段２３２ｃによって、当該ページの先頭に設定されていたリモートポインタ（他のディレクトリ分散型記憶装置へのポインタ）を親ページに設定し（ステップＳ２６）、動作を終了する。
【０１０２】
一方、当該ページへのポインタが親ページに設定されている場合（ステップＳ２４でＹｅｓ）、すなわち、分割の元となったページ（図８中、インデックスページＰ２１〔左側ページ〕）である場合、ディレクトリ分散型記憶装置ＰＥＡは、ページ削除手段２３１によって、当該ページを削除する（ステップＳ２７）。なお、このとき、ページ削除手段２３１では、削除ビット設定手段２３１ａによって、当該ページに削除ビットを設定し、削除ビット設定時点で起動されていたプロセスの終了を待って当該ページの削除を行う。
【０１０３】
そして、親ページに設定されていた当該ページへのローカルポインタのエントリの内容を、他のディレクトリ分散型記憶装置に蓄積されている当該ページのコピーページへのリモートポインタに変更する（ステップＳ２８）。その後、ディレクトリ分散型記憶装置ＰＥＡは、ポインタ設定手段２３２ｃによって、分割によって新たに生成されたページ（図８中、インデックスページＰ２２〔右側ページ〕）のポインタ（ローカルポインタ）を親ページに設定し（ステップＳ２９）、動作を終了する。
以上の動作によって、ディレクトリ分散型記憶装置ＰＥＡは、インデックスページを分割する際に、各ページに検索キーの境界値を設定するため、当該ページを参照するプロセスが経路誤りを検出することが可能になる。
【０１０４】
≪第２実施形態≫
［ディレクトリ分散型記憶装置の構成］
次に、図１１を参照して、第２実施形態に係るディレクトリ分散型記憶装置の構成について説明する。図１１は、本発明の第２実施形態に係るディレクトリ分散型記憶装置の構成を示すブロック図である。
図１１に示したディレクトリ分散型記憶装置ＰＥＢは、ネットワークＮに接続された他のディレクトリ分散型記憶装置（図示せず）と協働し、データベース等のデータを分散して記憶するものである。
【０１０５】
なお、ディレクトリ分散型記憶装置ＰＥＢは、ページ分割・追加手段２３２Ｂを、図１で説明したディレクトリ分散型記憶装置ＰＥＡのページ分割・追加手段２３２における管理対象ページ判定手段２３２ｂの機能を変更した管理対象ページ判定手段２３２Ｂｂとし、新たにエントリ複製手段２３２ｄを付加して構成している。管理対象ページ判定手段２３２Ｂｂ及びエントリ複製手段２３２ｄ以外の構成は、図１で説明したディレクトリ分散型記憶装置ＰＥＡと同一の構成であるため、同一の符号を付し、説明を省略する。
【０１０６】
管理対象ページ判定手段２３２Ｂｂは、ページを分割することにより生成された２つのページが、当該装置ＰＥＢの管理対象のページであるか否かを判定するものである。なお、基本的には、管理対象ページ判定手段２３２Ｂｂは、図１で説明した管理対象ページ判定手段２３２ｂと同一の機能を有しているが、図８で説明した第３の分割パターンにおける分割手法のみが異なっている。
この管理対象ページ判定手段２３２Ｂｂは、分割された元のページを管理対象ページでないと判定したときは、後記するエントリ複製手段２３２ｄによって、分割により新たに生成されたページの内容を、分割された元のページに上書きした後に、ページ削除手段２３１によって、分割により新たに生成されたページを削除する点が異なっている。
【０１０７】
エントリ複製手段２３２ｄは、管理対象ページ判定手段２３２Ｂｂによって指定された複製元のページの内容を、同じく指定された複製先のページに上書きするものである。
ここで、図１２を参照（適宜図１１参照）して、図８で説明した第３の分割パターンとの差異点について説明する。図１２は、第３の分割パターンにおける分割後の処理を説明するための説明図である。
【０１０８】
図１２（ａ）に示すように、第３の分割パターンにおいては、右側ページＰ２２にはローカルポインタが含まれているが、左側ページＰ２１にはローカルポインタが含まれていないため、左側ページＰ２１を削除する必要がある。
このとき、ディレクトリ分散型記憶装置ＰＥＢは、図１２（ｂ）に示すように、分割により新たに生成された右側ページ（インデックスページＰ２２）の内容を、親ページ（インデックスページＰ１）からポインタで指し示されている左側ページ（インデックスページＰ２１）に上書きし、その後、右側ページ（インデックスページＰ２２）を削除する。さらに、親ページ（インデックスページＰ１)に設定されている元の左側ページへのローカルポインタのエントリＫｉを他のディレクトリ分散型記憶装置に蓄積されている元の左側ページのコピーページへのリモートポインタを設定し、残った子インデックスページの始端を表すエントリＫｊを新たに追加してコピー先の子ページ（インデックスページＰ２２）へのリモートポインタを設定する。
【０１０９】
この手法によれば、分割直後は、インデックスページＰ２２へのポインタが存在していないため、インデックスページＰ２２へアクセスが発生していない。このため、図８で説明した分割手法では、ページを削除する際に分割前のページにアクセスしていたプロセスは再起動されることになるが、この手法では、ページを削除する際に分割前のページにアクセスしていたプロセスは、分割により検索キーが境界値を越えた場合にだけ再起動されるため、再起動される確率が２分の１となり、より効率的に動作させることができる。
【０１１０】
［ディレクトリ分散型記憶装置の動作］
次に、図１３を参照（適宜図１１及び図１２参照）して、ディレクトリ分散型記憶装置の動作について説明する。図１３は、本発明の第２実施形態に係るディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。なお、処理要求の移譲処理動作については、図９で説明した動作と同一であるため説明を省略する。
【０１１１】
（分割処理動作）
図１３のステップＳ２０〜Ｓ２６は、図１０と同一の動作であるため、同一の符号を付し、説明を省略する。
ディレクトリ分散型記憶装置ＰＥＢは、分割したページへのポインタが親ページに設定されている場合（ステップＳ２４でＹｅｓ）、すなわち、分割の元となったページ（図１２中、インデックスページＰ２１〔左側ページ〕）である場合、エントリ複製手段２３２ｄによって、分割により新たに生成されたページ（図１２中、インデックスページＰ２２〔右側ページ〕）の内容（エントリ）を、分割の元となったページ（図１２中、インデックスページＰ２１〔左側ページ〕）に上書きする（ステップＳ３０）。
【０１１２】
そして、ディレクトリ分散型記憶装置ＰＥＢは、ページ削除手段２３１によって、インデックスページＰ２２〔右側ページ〕を削除する（ステップＳ３１）。
その後、ディレクトリ分散型記憶装置ＰＥＢは、親ページに設定されていた分割の元となったページ（図１２中、インデックスページＰ２１〔左側ページ〕）へのローカルポインタのエントリの内容を、他のディレクトリ分散型記憶装置に蓄積されている当該ページのコピーページへのリモートポインタに設定しなおし（ステップＳ３２）、分割の元となったページのローカルポインタを親ページに設定し（ステップＳ３３）、動作を終了する。
【０１１３】
以上の動作によって、ディレクトリ分散型記憶装置ＰＥＢは、インデックスページを分割する際に、各ページに検索キーの境界値を設定するため、当該ページを参照するプロセスが経路誤りを検出することが可能になる。また、プロセスの再起動の回数を減らすことができる。
【図面の簡単な説明】
【０１１４】
【図１】本発明のディレクトリ分散型記憶装置の構成を示すブロック図である。
【図２】木構造情報を構成するインデックスページの構造を示すデータ構造図である。
【図３】ディレクトリ分散型記憶装置間で行う処理の移譲手順を示す模式図である。
【図４】インデックスページの分割により境界値を設定する例を説明するための説明図であって、（ａ）は分割前、（ｂ）は分割後のインデックスページの内容を示している。
【図５】インデックスページを分割した際の分割パターンを説明するための説明図である。
【図６】第１の分割パターンにおける分割後の処理を説明するための説明図である。
【図７】第２の分割パターンにおける分割後の処理を説明するための説明図である。
【図８】第３の分割パターンにおける分割後の処理を説明するための説明図である。
【図９】本発明のディレクトリ分散型記憶装置における処理要求の移譲処理動作を示すフローチャートである。
【図１０】本発明のディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。
【図１１】本発明の第２実施形態に係るディレクトリ分散型記憶装置の構成を示すブロック図である。
【図１２】本発明の第２実施形態に係るディレクトリ分散型記憶装置において、第３の分割パターンにおける分割後の処理を説明するための説明図である。
【図１３】本発明の第２実施形態に係るディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。
【図１４】従来の分散データ格納システムにおけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造を示す図である。
【図１５】従来の並列計算機における処理要求の移譲動作を示すフローチャートである。
【図１６】計算機間で処理の移譲を伴わないラッチカップリングの動作例を示す模式図である。
【図１７】計算機間で処理の移譲を伴うラッチカップリングの動作例を示す模式図である。
【符号の説明】
【０１１５】
ＰＥＡ，ＰＥＢ ディレクトリ分散型記憶装置
１ 通信制御部
２ 記憶部
３ 制御部
１０ データ操作手段
１１ データ送受信手段
１２ データ参照手段
１３ データ更新手段
２０ 木構造管理手段
２１ ラッチ設定手段（ロック設定手段）
２２ 経路探索手段
２２１ 移譲判定手段
２２２ 移譲手段
２２３ 経路誤り判定手段
２２４ 経路再探索手段（経路復旧手段）
２３ 木構造更新手段
２３１ ページ削除手段
２３１ａ 削除ビット設定手段
２３２ ページ分割・追加手段
２３２ａ 境界値設定手段
２３２ｂ 管理対象ページ判定手段
２３２ｃ ポインタ設定手段
２３２ｄ エントリ複製手段
３０ 制御情報送受信手段
４０ プロセス管理手段
【技術分野】
【０００１】
本発明は、木構造を有するディレクトリ構造を分散環境下で実現するディレクトリ分散型記憶装置及びデータ処理要求移譲プログラムに関する。
【背景技術】
【０００２】
近年、ネットワーク上に並列に配置された計算機（ＰＥ：Processing Element）上にデータベース等のデータを分散して記憶することで、データにアクセスする際の負荷分散と並行性動作とを実現したシステム（分散データ格納システム）が存在する。
このようなシステムにおいては、アクセス集中による負荷の偏りが存在する場合、その負荷の大きいＰＥがボトルネックとなり、システム全体の処理能力が低下してしまう。そこで、各ＰＥに負荷を均等に分配するためのディレクトリ構造と、そのディレクトリ構造における並行性制御とが提案されている（例えば、非特許文献１参照）。
【０００３】
（Ｆａｔ−Ｂｔｒｅｅ構造）
ここで、図１４を参照して、従来の分散データ格納システムにおけるディレクトリ構造について、その概要を説明する。図１４は、従来の分散データ格納システムにおけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造の構成例を示す図である。
図１４に示すように、Ｆａｔ−Ｂｔｒｅｅ構造は、データを示す葉ページＰｄを各計算機ＰＥに均等に分配した構造となっている。また、Ｆａｔ−Ｂｔｒｅｅ構造は、葉ページＰｄ以外のインデックスを示すインデックスページＰｉを各計算機ＰＥに分配した構造となっている。
【０００４】
なお、各インデックスページＰｉに登録（エントリ）される下位層のインデックスページの数と、葉ページＰｄに登録されるデータ（データページ）の数とは、予め定められた数に制限されている。この制限された数を超過する場合は、各ページは分割され、木構造が更新されることになる。
【０００５】
このように、葉ページＰｄ及びインデックスページＰｉを分配することで、各計算機ＰＥの記憶部に記憶されるのは、全体の木構造に対して、ルートページＰｉＲから、均等に分配された葉ページＰｄまでの部分木となる。すなわち、計算機ＰＥ１には部分木Ｒ１が、計算機ＰＥ２には部分木Ｒ２が、計算機ＰＥ３には部分木Ｒ３が、計算機ＰＥ４には部分木Ｒ４がそれぞれ記憶されることになる。
これによって、各計算機ＰＥに対するアクセスの分散が行われる。また、各計算機ＰＥでは、記憶している葉ページＰｄの探索に必要のないインデックスページＰｉを保持していないため、高速に葉ページＰｄにアクセスすることができる。
【０００６】
ここで、並行性制御を説明するために必要な用語について説明しておく。
「木をたどる主体」…木構造において、木をたどる主体は、システムに格納されたある葉ページを取得するために、各ノード上で葉ページ処理要求（処理要求）を構成する一連のプロセス（プロセスの集合体）である。
【０００７】
「ページのラッチ」…ある葉ページ要求Ａｎを構成するプロセスによってラッチが設定されたページは、その他の葉ページ要求Ａｍ（ｍ≠ｎ）に属するプロセスからのアクセスが制限される。この制限の種類によって複数のラッチが存在する。例えば、他から読み込みも変更も破棄も行えないラッチ、変更や破棄は行えないが読み込みは行えるラッチ等がある。このラッチによりアクセスが制限されたプロセスは実行を一時停止し、当該ラッチが解除された後、再び当該ページへのラッチ獲得やアクセスを試みる。なお、ラッチは例えばセマフォを用いて実装される。
【０００８】
「木構造の一貫性」…木構造ごとに決められた手順に従って葉ページ要求を行う限り、木構造が変更している最中に、一部の葉ページへアクセスができない状況になっても、要求が正常に一時停止され、最終的に正しい葉ページを取得できる性質をいう。
「アクセスパス」…ルートページＰｉＲ及び要求する葉ページＰｄと、これらの各ページ間に含まれるページを意味する。
「ロック」…アクセスパスに対して、他の処理要求に属するプロセスからのアクセスを制御するもので、デットロック検出機能を持つ。
【０００９】
（並行性制御）
次に、従来の分散データ格納システムにおける並行性制御について説明する。図１４で説明したＦａｔ−Ｂｔｒｅｅ構造では、木構造の一貫性を保証するため、並行性制御が必須となる。この並行性制御においては、アクセスパスに対して、他のプロセスからのアクセスを制御するロックが用いられる。一般に、このロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（セマフォの一種）が用いられている。
このＦａｔ−Ｂｔｒｅｅ構造において、葉ページのデータが参照、更新等される場合、並列計算機は、まず、ルートページにラッチを設定する。その後、下位層のページ（子ページ）のポインタを取得し、子ページにラッチを設定し、ルートページ（親ページ）のラッチを解除する。この動作を、上位層から下位層に向けて葉ページまで繰り返すことで、並行性を保証しながら葉ページを更新等することが可能になる。このような上位層から下位層に向けてラッチの設定及び解除を順次繰り返す動作を「ラッチカップリング」という。
【００１０】
また、ある計算機（例えば、ＰＥ１）が、自身の記憶部には記憶されていない葉ページＰｄについての処理要求があった場合、その葉ページＰｄを管理している他の計算機（例えば、ＰＥ２）に処理要求を通知し、他の計算機がその処理要求を継続して実行する必要がある。このように、処理要求を他の計算機に継続して実行させることを、処理要求の移譲という。
【００１１】
ここで、図１５〜図１７を参照（適宜図１４参照）して、従来の並列計算機における処理要求の移譲動作について詳細に説明する。図１５は、従来の並列計算機における処理要求の移譲動作を示すフローチャートである。図１６は、計算機間で処理の移譲を伴わないラッチカップリングの動作例を示す模式図である。図１７は、計算機間で処理の移譲を伴うラッチカップリングの動作例を示す模式図である。
並列計算機は、データの処理要求（参照、更新等）があった各計算機ＰＥにおいて、以下の動作を実行する。ここでは、計算機ＰＥ１の動作を主に説明する。
【００１２】
まず、計算機ＰＥ１は、初期値として、親ページを“ｎｕｌｌ”、子ページをルートページに設定する（ステップＳ５０）。そして、計算機ＰＥ１は、要求に示されたデータのアクセスパスに基づいて、子ページへ降下が必要であるか否かを判定する（ステップＳ５１）。
ここで、降下が必要でない場合（ステップＳ５１でＮｏ）、そのページが要求のあった葉ページであるため、当該葉ページへの処理を実行し（ステップＳ５２）、動作を終了する。一方、降下が必要である場合（ステップＳ５１でＹｅｓ）、計算機ＰＥ１は、要求に示されたデータのアクセスパスに基づいて、他の計算機へ処理要求を移譲するか否かを判定する（ステップＳ５３）。
【００１３】
ここで、移譲が必要な場合（ステップＳ５３でＹｅｓ）、計算機ＰＥ１は、移譲先の計算機（ここでは、計算機ＰＥ２とする）へ処理要求の移譲を要求する（移譲要求メッセージ送信）。この段階で、移譲先への移譲処理が開始されたことになる。なお、処理要求の移譲を要求された計算機ＰＥ２は、計算機ＰＥ２において後記するステップＳ５４以降の動作を実行する。
【００１４】
一方、移譲が必要でない場合（ステップＳ５３でＮｏ）、計算機ＰＥ１は、子ページにラッチを設定し（ステップＳ５４）、その子ページに降下（子ページを新たな親ページに、孫ページを新たな子ページに設定）する（ステップＳ５５）。
なお、計算機ＰＥ１は、他の計算機におけるステップＳ５３の判定により、当該他の計算機（ここでは、計算機ＰＥ3とする）から、処理要求の移譲を要求された場合も、ステップＳ５４以降の動作を実行する。この段階で、移譲元からの移譲処理が開始されたことになる。
【００１５】
その後、計算機ＰＥ１は、移譲元の計算機（計算機ＰＥ３）からの移譲処理中である場合（ステップＳ５６でＹｅｓ）、計算機ＰＥ３へ要求に対する応答を通知する。一方、移譲元の計算機（計算機ＰＥ３）からの移譲処理中でない場合（ステップＳ５６でＮｏ）、親ページのラッチを解除する（ステップＳ５７）。
なお、計算機ＰＥ１は、移譲先の計算機（計算機ＰＥ２）から移譲の要求に対する応答を通知された場合（移譲応答メッセージ受信）も、ステップＳ５７の動作を実行する。
【００１６】
そして、計算機ＰＥ１は、移譲先の計算機（計算機ＰＥ２）への移譲処理中である場合（ステップＳ５８でＹｅｓ）、計算機ＰＥ２へ移譲の完了を通知し（移譲完了メッセージ送信）、動作を終了する。この段階で、移譲先への移譲処理が完了したことになる。
一方、移譲先の計算機（計算機ＰＥ２）への移譲処理中でない場合（ステップＳ５８でＮｏ）、計算機ＰＥ１は、ステップＳ５１に戻って、処理対象の葉ページに到達するまで動作を続ける。
なお、計算機ＰＥ１は、移譲元の計算機（計算機ＰＥ３）から移譲の完了を通知された場合も、ステップＳ５１に戻って動作を実行する。なお、この段階で、移譲元からの移譲処理が完了したことになる。
【００１７】
例えば、図１６（ａ）に示すように、ルートページＰ１から対象データの葉ページＰ４までが、同一の計算機ＰＥ１内で管理されている場合、図１６（ｂ）に示すように、葉ページＰ４までの処理要求を受け付けた計算機ＰＥ１は、他の計算機に参照先の葉ページＰ４に対する処理要求を移譲することなく、計算機ＰＥ１内で、各ページＰ１からＰ４まで、ラッチカップリングを行いながら、最下層の葉ページＰ４に対してラッチをかけ、参照、更新等の処理を行うことができる。なお、図１６（ｂ）中“Ｌ”は、ラッチが設定された状態を示している。
【００１８】
一方、図１７（ａ）に示すように、ルートページＰ１から参照先の葉ページＰ４までが、葉ページＰ４までの処理要求を受け付けた計算機ＰＥ１内で管理されていない場合、計算機間で処理要求の移譲が行われる。例えば、図１７（ａ）に示すように、ルートページＰ１から対象データの葉ページＰ４までにおいて、インデックスページＰ３及び葉ページＰ４が計算機ＰＥ２でしか管理されていない場合、計算機ＰＥ１にデータ（葉ページＰ４）の処理要求（参照、更新等）がなされると、インデックスページＰ３以下の子ノードへの降下処理は、計算機ＰＥ２に移譲されることになる。
【００１９】
これによって、図１７（ｂ）に示すように、異なる計算機間で、ラッチカップリングを行いながら、最下層の葉ページＰ４に対してラッチをかけ、参照、更新等の処理を行うことができる。なお、図１７（ｂ）中、破線で示した移譲処理は、図１７（ｃ）に示すように、計算機ＰＥ１及びＰＥ２間で、各メッセージが送受信されることで行われる。この各メッセージは、図１５のステップＳ５３でＹｅｓの場合に計算機ＰＥ２に送信される移譲要求メッセージ、ステップＳ５７の前に計算機ＰＥ２から受信する移譲応答メッセージ、ステップＳ５８でＹｅｓの場合に計算機ＰＥ２に送信される移譲完了メッセージである。
【非特許文献１】吉原朋宏、他４名，「並列ディレクトリ構造Ｆａｔ−Ｂｔｒｅｅの並行性制御とその評価」，［online］，平成１７年３月２７日，電子情報通信学会第１６回データ工学ワークショップ第３回日本データベース学会年次大会，［平成１８年８月４日検索］，インターネット＜URL:http://www.ieice.org/iss/de/DEWS/DEWS2005/procs/papers/2A-o4.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【００２０】
一般に、データをネットワーク上に分散して蓄積する分散データ格納システムにおいて、データを木構造で管理する場合、複数の計算機（ＰＥ）間でデータの一貫性を維持するため、並行性制御を行う必要がある。この並行性制御を行うために、従来の分散データ格納システムでは、木構造で管理されたデータに対して、更新、挿入、削除等の操作を行う場合、木構造の上位から下位の層に向かってラッチ（あるいはロック）カップリングを行っている。
しかし、ラッチカップリングにより、計算機（ＰＥ）間での処理要求の移譲が発生した場合、図１７（ｃ）に示したように、複数（３回）のメッセージがネットワーク上で伝送されることになるため、ネットワークレイテンシが増大する。また、分散データ格納システムでは、スループットの向上を目的として、システム規模を大きくする場合がある。このとき、システム規模の拡大に伴いネットワーク上のメッセージ伝送の頻度が多くなり、スループットの向上の効果が得られにくくなるという問題がある。
【００２１】
本発明は、以上のような問題点に鑑みてなされたものであり、データを木構造で管理する場合に、メッセージ伝送の負荷が大きいラッチカップリングを行わずに、並行性制御を行うことが可能なディレクトリ分散型記憶装置及びデータ処理要求移譲プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２２】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載のディレクトリ分散型記憶装置は、記憶手段と、木構造更新手段と、経路探索手段とを備え、ネットワーク環境下で木構造を有するディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記経路探索手段が、経路誤り判定手段と、経路復旧手段と、移譲判定手段と、移譲手段とを備える構成とした。
【００２３】
かかる構成において、ディレクトリ分散型記憶装置は、ページを順に子ページの方向にロックの設定と解除とを行いながら探索していく途中でページの分割が発生した場合、経路誤り判定手段によって、経路誤りを判定する。なお、ここでいうロックには、デッドロック検出機能を持たない高速かつ単純なラッチも含む。
そして、ディレクトリ分散型記憶装置は、経路復旧手段によって、経路誤り判定手段で経路誤りと判定された場合に、経路の復旧を行う。
【００２４】
また、ディレクトリ分散型記憶装置は、移譲判定手段によって、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する。そして、ディレクトリ分散型記憶装置は、移譲手段によって、移譲判定手段で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求（移譲要求メッセージ）を他のディレクトリ分散型記憶装置へ送信する。
なお、従来では、処理要求の移譲途中に経路誤りを発生させないようにページのロック制御を行うため、複数のメッセージを他のディレクトリ分散型記憶装置との間で送受信する必要があったが、このディレクトリ分散型記憶装置では、経路誤りを検出可能としたことで、処理要求の移譲を１回のメッセージ送信で行うことが可能になる。
【００２５】
また、請求項２に記載のディレクトリ分散型記憶装置は、記憶手段と、木構造更新手段と、経路探索手段とを備え、ネットワーク環境下で木構造を有するディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記木構造更新手段が境界値設定手段を備え、前記経路探索手段が、経路誤り判定手段と、経路再探索手段と、移譲判定手段と、移譲手段とを備える構成とした。
【００２６】
かかる構成において、ディレクトリ分散型記憶装置は、境界値設定手段によって、データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだページ内で、参照先の数が予め定めた制限値を超過して当該ページを分割する際に、その分割されたページごとに、当該ページで管理する検索キーの境界値を設定する。これによって、親ページを参照することなく、当該ページで管理されている子ページが、どの検索キーの範囲のページがあるのかを特定することができる。
【００２７】
そして、ディレクトリ分散型記憶装置は、ページを順に子ページの方向にロックの設定と解除とを行いながら探索していく途中でページの分割が発生した場合、経路誤り判定手段によって、境界値設定手段で設定された境界値に基づいて検索キーが該当するページに存在するか否かにより、経路誤りを判定する。なお、ここでいうロックには、デッドロック検出機能を持たない高速かつ単純なラッチも含む。
そして、ディレクトリ分散型記憶装置は、経路再探索手段によって、経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから経路の探索を行う。これによって、正しい経路が探索されることになる。
【００２８】
また、ディレクトリ分散型記憶装置は、移譲判定手段によって、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する。そして、ディレクトリ分散型記憶装置は、移譲手段によって、移譲判定手段で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求（移譲要求メッセージ）を他のディレクトリ分散型記憶装置へ送信する。
なお、従来では、処理要求の移譲途中に経路誤りを発生させないようにページのロック制御を行うため、複数のメッセージを他のディレクトリ分散型記憶装置との間で送受信する必要があったが、このディレクトリ分散型記憶装置では、経路誤りを検出可能としたことで、処理要求の移譲を１回のメッセージ送信で行うことが可能になる。
【００２９】
また、請求項３に記載のディレクトリ分散型記憶装置は、請求項２に記載のディレクトリ分散型記憶装置において、プロセスを管理するプロセス管理手段を備え、木構造更新手段が、前記ページを分割した際に、当該ディレクトリ分散型記憶装置以外の参照先のみからなるページを、当該ディレクトリ分散型記憶装置の管理対象外のページであると判定する管理対象ページ判定手段と、この管理対象ページ判定手段で管理対象外のページであると判定したページを削除するページ削除手段とを備え、前記ページ削除手段が、当該ページを参照するプロセスが存在しなくなった段階で、当該ページを削除する構成とした。
【００３０】
かかる構成において、ディレクトリ分散型記憶装置は、木構造更新手段がページを分割した際に、管理対象ページ判定手段によって、当該ディレクトリ分散型記憶装置以外の参照先のみからなるページを、当該ディレクトリ分散型記憶装置の管理対象外のページであると判定する。なお、この管理対象外のページより下位のページは、他のディレクトリ分散型記憶装置で管理されているため、当該ディレクトリ分散型記憶装置で管理する必要がないページである。
そして、ディレクトリ分散型記憶装置は、ページ削除手段によって、管理対象ページ判定手段で管理対象外のページであると判定したページを削除する。このとき、ページ削除手段は、削除対象のページを参照するプロセスが存在しなくなった段階で、当該ページを削除する。これによって、完全に不要になったページのみが削除されることになる。
【００３１】
さらに、請求項４に記載のディレクトリ分散型記憶装置は、請求項３に記載のディレクトリ分散型記憶装置において、木構造更新手段が、前記ページを分割した際に、親ページに参照先が記述されている一方のページが当該ディレクトリ分散型記憶装置以外の参照先のみからなるページである場合に、分割された他方のページの内容を前記一方のページに上書きするエントリ複製手段を備え、このエントリ複製手段により上書きされた後に、前記ページ削除手段が、前記他方のページを削除する構成とした。
【００３２】
かかる構成において、ディレクトリ分散型記憶装置は、エントリ複製手段によって、分割された他方のページの内容を、親ページに参照先が記述されている一方のページに上書きする。そして、ディレクトリ分散型記憶装置は、ページ削除手段によって、他方のページを削除する。このとき、他方のページを参照している親ページは存在しないため、上位のページからの参照の有無を確認することなく削除することができる。
【００３３】
また、請求項５に記載のデータ処理要求移譲プログラムは、データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページで構成されるディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記データへの処理要求を、ネットワークに接続された他のディレクトリ分散型記憶装置に移譲するために、コンピュータを、境界値設定手段、ロック設定手段、経路誤り判定手段、経路再探索手段、移譲判定手段、移譲手段、として機能させる構成とした。
【００３４】
かかる構成によれば、データ処理要求移譲プログラムは、境界値設定手段によって、ページ内の参照先の数が予め定めた制限値を超過して当該ページを分割する際に、分割されたページごとに、当該ページで管理する検索キーの境界値を設定する。これによって、親ページを参照することなく、当該ページで管理されている子ページが、どの検索キーの範囲のページがあるのかを特定することができる。
【００３５】
また、データ処理要求移譲プログラムは、ロック設定手段によって、データまでの経路を探索する経路において、上位のページにロックを設定し、下位ページへの参照先を取得した後に、ロックを解除し、下位のページにロックを設定する処理を繰り返す。
さらに、データ処理要求移譲プログラムは、経路誤り判定手段によって、データまでの経路を探索する経路途中のページにおいて、当該データの検索キーの値が、境界値設定手段で設定された境界値の範囲内であるか否かに基づいて、経路誤りを判定する。
そして、データ処理要求移譲プログラムは、経路再探索手段によって、経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから経路の探索を行う。これによって、正しい経路が探索されることになる。
【００３６】
また、データ処理要求移譲プログラムは、移譲判定手段によって、ページ内の参照先に基づいて、データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する。そして、データ処理要求移譲プログラムは、移譲手段によって、移譲判定手段で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求（移譲要求メッセージ）を他のディレクトリ分散型記憶装置へ送信する。
【発明の効果】
【００３７】
本発明は、以下に示す優れた効果を奏するものである。
請求項１、請求項２又は請求項５に記載の発明によれば、ラッチカップリング処理を行わないため、処理要求を他のディレクトリ分散型記憶装置に移譲する場合に、ネットワークを介したメッセージの送受信回数を１回で処理することができる。これによって、システム規模の拡大を行った場合に、ネットワークへの負荷を抑えることができ、スループットを向上させることができる。
【００３８】
請求項３に記載の発明によれば、サービスを継続したまま、不要になったページを削除することが可能となり、メモリの効率的利用が可能で、データを探索する際の処理速度を高速化することができる。
請求項４に記載の発明によれば、親ページに参照先が記述されていないページを削除するため、経路再探索手段が行う再探索の回数を減らすことができ、データを探索する際の処理速度を高速化することができる。
【発明を実施するための最良の形態】
【００３９】
≪第１実施形態≫
［ディレクトリ分散型記憶装置の構成］
まず、図１を参照して、第１実施形態に係るディレクトリ分散型記憶装置の構成について説明する。図１は、本発明の第１実施形態に係るディレクトリ分散型記憶装置の構成を示すブロック図である。
【００４０】
図１に示したディレクトリ分散型記憶装置ＰＥＡは、ネットワークＮに接続された他のディレクトリ分散型記憶装置（図示せず）と協働し、データベース等のデータを分散して記憶するものである。このディレクトリ分散型記憶装置ＰＥＡは、図１４で説明したＦａｔ−Ｂｔｒｅｅ構造のディレクトリ構造によってデータを記憶管理する計算機ＰＥに相当する。ここでは、ディレクトリ分散型記憶装置ＰＥＡは、通信制御部１と、記憶部２と、制御部３とを備えている。
【００４１】
通信制御部１は、ネットワークＮを介して、クライアントコンピュータ（図示せず）や他のディレクトリ分散型記憶装置（図示せず）と、データや制御情報の送受信を行うものである。例えば、通信制御部１は、ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）の通信プロトコルによってデータ等の送受信を行う通信ボードである。
【００４２】
記憶部２は、データベース等のデータや、ディレクトリ構造を特定する木構造情報等を記憶しておくもので、一般的なハードディスク等の記憶装置である。この記憶部２には、データＤＴと、木構造情報ＴＲと、エントリ制限情報ＥＬとを記憶している。
【００４３】
データＤＴは、Ｆａｔ−Ｂｔｒｅｅ構造における葉ページであって、データの実体である。このデータＤＴは、記憶領域の予め定められたページ単位で管理され、所定のページ数（後記するエントリ制限情報ＥＬに含まれる）を超過する場合は分割される。
【００４４】
木構造情報ＴＲは、Ｆａｔ−Ｂｔｒｅｅ構造のデータ構造を示す情報である。ここでは、木構造情報ＴＲは、Ｆａｔ−Ｂｔｒｅｅ構造のルートページから、記憶部２に記憶されているデータ（葉ページ）ＤＴまでのアクセスパスを示すインデックスページを記憶している。
【００４５】
ここで、図２を参照して木構造情報ＴＲの内容について説明する。図２は、木構造情報を構成するインデックスページの構造を示すデータ構造図である。従来、Ｆａｔ−Ｂｔｒｅｅ構造のインデックスページは、インデックスページを検索する際のキーとなる「検索キー」と、下層のインデックスページ（又は葉ページ）の参照先を示す「ポインタ」とを対として、検索キーが昇順（又は降順）となるように複数連結したデータ構造を有している。
この木構造情報ＴＲでは、図２に示すように、「検索キー」と「ポインタ」との対の情報以外に、「削除ビットＤｂ」と、「始端検索キーＫｓ」と、「終端検索キーＫｅ」とを付加している。
【００４６】
「削除ビットＤｂ」は、当該インデックスページが有効なページであるか否かを示す情報である。この削除ビットＤｂに、インデックスページが削除対象のページとなっていることを示すビット（例えば、値“１”）を設定することで、無効なページであることを意味することとする。
【００４７】
「始端検索キーＫｓ」は、当該インデックページおいて管理される検索キーの始端の値を示す情報である。
「終端検索キーＫｅ」は、同じ階層で後続するインデックスページとの検索キーの境界値を示す情報である。この終端検索キーＫｅは、例えば、図２に示すように、インデックスページＰ２にインデックスページＰ３が続く場合、後続のインデックスページＰ３における先頭の検索キー（始端検索キー）の値“Ｋｉ”と、インデックスページＰ２の終端検索キーＫｅの値とを同一に設定しておく。これによって、インデックスページＰ２において、検索キーの値の範囲を明確にすることができる。なお、インデックスページが、ルートページである場合は、終端検索キーの値は、検索キーの値とはならない特殊な値、例えば“ｎｕｌｌ”を設定しておく。この場合、各階層の最終のインデックスページにおける終端検索キーの値も、“ｎｕｌｌ”が設定されることになる。
この「削除ビットＤｂ」、「始端検索キーＫｓ」及び「終端検索キーＫｅ」の具体的な利用方法については、後記することとする。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００４８】
エントリ制限情報ＥＬは、Ｆａｔ−Ｂｔｒｅｅ構造において、インデックスページに登録される子ページの数の最大値や、葉ページとして登録できるデータの数の最大値を示す情報である。このエントリ制限情報ＥＬは、後記する制御部３によって参照され、データの更新に伴う木構造の変化が発生するか否かを判定するために用いられる。
【００４９】
制御部３は、ディレクトリ分散型記憶装置ＰＥＡ全体の動作を制御するものであって、一般的なコンピュータにおけるＣＰＵ（Central Processing Unit：中央処理装置）を制御するものである。なお、制御部３は、一般的なＯＳ（Operating System）上で、クライアントコンピュータ（図示せず）や他のディレクトリ分散型記憶装置（図示せず）からの要求に基づいて、複数のプロセスにより動作するものである。ここでは、制御部３は、データ操作手段１０と、木構造管理手段２０と、制御情報送受信手段３０と、プロセス管理手段４０とを備えている。
【００５０】
データ操作手段１０は、通信制御部１を介して、データの送受信操作を行うものである。なお、データ操作手段１０は、木構造管理手段２０において、データへのアクセスパスが、当該ディレクトリ分散型記憶装置ＰＥＡが管理するデータＤＴへのアクセスパスである場合にのみ起動される。ここでは、データ操作手段１０は、データ送受信手段１１と、データ参照手段１２と、データ更新手段１３とを備えている。
【００５１】
データ送受信手段１１は、制御情報送受信手段３０から通知されるデータの送信元（例えば、クライアントコンピュータ等）から、通信制御部１を介してデータを受信したり、データの送信先（例えば、クライアントコンピュータ等）に、通信制御部１を介してデータを送信したりするものである。
このデータ送受信手段１１は、データ参照手段１２から出力されるデータを、通信制御部１を介して送信し、通信制御部１を介して受信したデータをデータ更新手段１３に出力する。
【００５２】
データ参照手段１２は、記憶部２に記憶されているデータＤＴを読み出すものである。このデータ参照手段１２は、木構造管理手段２０から通知される制御情報（記憶元のアドレス等のアクセスパス）に基づいて、データＤＴを記憶部２から読み出す。このデータ参照手段１２で読み出されたデータＤＴは、データ送受信手段１１に出力される。
【００５３】
データ更新手段１３は、データ送受信手段１１で受信したデータを、記憶部２に書き込むものである。このデータ更新手段１３は、木構造管理手段２０から通知される制御情報（記憶先のアドレス等のアクセスパス）に基づいて、データを記憶部２に書き込む。
また、データ更新手段１３は、木構造管理手段２０から通知される制御情報に基づいて、指示されたデータＤＴを記憶部２から削除する動作も行う。なお、データＤＴを削除する場合、親ページのインデックスページに設定されているポインタを削除する必要があるため、データＤＴを削除した旨を木構造管理手段２０に通知する。
【００５４】
木構造管理手段２０は、記憶部２に記憶されている木構造情報ＴＲとエントリ制限情報ＥＬとに基づいて、記憶部２に記憶されるデータＤＴを階層構造で管理するものである。また、木構造管理手段２０は、Ｆａｔ−Ｂｔｒｅｅ構造（図１４参照）のディレクトリ構造によりデータＤＴを管理するものとする。ここでは、木構造管理手段２０は、ラッチ設定手段２１と、経路探索手段２２と、木構造更新手段２３とを備えている。
【００５５】
ラッチ設定手段（ロック設定手段）２１は、後記する経路探索手段２２でページを探索する際に、経路探索手段２２からの要求に基づいて、要求されたページに対してラッチを設定したり、解除したりするものである。このラッチは、ロックの一種であり、デッドロック検出機能を持たないセマフォの一種である。なお、ここでは、ラッチを用いることにしているが、デッドロック検出機能を持つ一般的なロックを用いることとしてもよい。
【００５６】
経路探索手段２２は、木構造情報ＴＲを参照して、制御情報送受信手段３０から制御情報として通知される検索キーに基づいて、ルートページから子ページに向かって、順次インデックスページに対するラッチの設定及び解除を繰り返しながら、処理対象の葉ページを検索し、ラッチを設定するものである。ここでは、経路探索手段２２は、移譲判定手段２２１と、移譲手段２２２と、経路誤り判定手段２２３と、経路再探索手段２２４とを備えている。
【００５７】
移譲判定手段２２１は、要求された処理を自装置で継続するか、他のディレクトリ分散型記憶装置（図示せず）に移譲するか否かを判定するものである。ここでは、移譲判定手段２２１は、木構造情報ＴＲのインデックスページにおいて、検索キーに対応するポインタが、自装置の木構造情報ＴＲで管理されているインデックスページを指し示している場合に、自装置で処理を継続すると判定する。
一方、ポインタが他のディレクトリ分散型記憶装置（図示せず）で管理されているインデックスページを指し示している場合、移譲判定手段２２１は、他のディレクトリ分散型記憶装置に、要求された処理を移譲すると判定する。なお、移譲すると判定した場合、移譲判定手段２２１は、その旨を移譲手段２２２に通知する。
【００５８】
移譲手段２２２は、移譲判定手段２２１で他のディレクトリ分散型記憶装置へ処理要求を移譲すると判定した場合に、処理要求を他のディレクトリ分散型記憶装置へ送信するものである。ここでは、移譲手段２２２は、移譲判定手段２２１から、移譲する旨を通知された段階で、制御情報送受信手段３０を介して、他のディレクトリ分散型記憶装置に、処理プロセスを特定する識別子であるトランザクションＩＤ、検索キーの値、インデックスページのポインタ、並びに、要求された処理内容（参照、挿入、更新、削除）を含んだ制御情報を移譲要求メッセージとして通知する。
【００５９】
ここで、図３を参照（適宜図１参照）して、経路探索手段２２により行うディレクトリ分散型記憶装置間の処理の移譲手順について説明する。図３は、ディレクトリ分散型記憶装置間で行う処理の移譲手順を示す模式図である。
なお、ここでは、図３（ａ）に示すように、ディレクトリ構造が図１４に示したＦａｔ−Ｂｔｒｅｅ構造において、ルートページＰ１から対象データの葉ページＰ４までが、異なるディレクトリ分散型記憶装置ＰＥＡ（ＰＥ１，ＰＥ２）で管理されているものとする。
【００６０】
このとき、ディレクトリ分散型記憶装置ＰＥ１は、図３（ｂ）に示すように、ディレクトリ分散型記憶装置ＰＥ１の内部で管理しているページＰ１にラッチを設定し、その子ページであるページＰ２を探索した後、親ページとなるページＰ１のラッチを解除する。その後、ディレクトリ分散型記憶装置ＰＥ１は、ページＰ２にラッチを設定し、その子ページであるページＰ３を探索する。このとき、ページＰ３は、ディレクトリ分散型記憶装置ＰＥ２で管理されているため、ディレクトリ分散型記憶装置ＰＥ１は、親ページとなるページＰ２のラッチを解除し、ディレクトリ分散型記憶装置ＰＥ２に対して、葉ページＰ４に対する処理を移譲する。
【００６１】
その後、ディレクトリ分散型記憶装置ＰＥ２が、ページＰ３にラッチを設定し、その子ページである葉ページＰ４を探索した後、親ページとなるページＰ３のラッチを解除する。そして、ディレクトリ分散型記憶装置ＰＥ２は、葉ページＰ４にラッチを設定し、葉ページＰ４に対する処理（参照、更新等）を行う。なお、図３（ｂ）中“Ｌ”は、ラッチが設定された状態を示している。
このとき、図３（ｂ）中、破線で示した移譲処理において、図３（ｃ）に示すように、ディレクトリ分散型記憶装置ＰＥ１から、ディレクトリ分散型記憶装置ＰＥ２に対して、移譲要求メッセージのみが送信される。
【００６２】
なお、この場合、図３（ｂ）に示すように、子ページにラッチを設定する前に親ページのラッチを解除するため、他のプロセスによる処理によって、木構造情報ＴＲが更新される場合があり、子ページに降下する際に経路誤りが発生することがある。
そこで、ディレクトリ分散型記憶装置ＰＥＡは、後記する経路誤り判定手段２２３により、経路誤りを判定し、正しい経路を補償することとしている。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００６３】
経路誤り判定手段２２３は、インデックスページを降下していく際に、その経路に誤りがあるか否かを判定するものである。ここでは、経路誤り判定手段２２３は、木構造情報ＴＲのインデックスページにおいて、処理対象の検索キーが当該インデックスページに属するものであるか否かを判定することで、経路の誤りを判定する。
具体的には、経路誤り判定手段２２３は、処理対象の検索キーの値が、インデックスページにおける「始端検索キーＫｓ」の領域（図２参照）に記述されている検索キーの値以上で、「終端検索キーＫｅ」の領域（図２参照）に記述されている検索キーの値未満であるときに、経路が正しいと判定し、それ以外のときに、経路が誤っていると判定する。なお、経路が誤っていると判定した場合、経路誤り判定手段２２３は、その旨を経路再探索手段２２４に通知する。
【００６４】
なお、ここでは、経路誤り判定手段２２３が、検索キーの始端及び終端に基づいて経路誤りを判定することとしたが、既存の技術であるＡＲＩＥＳ／ＩＭ（Algorithm for Recovery and Isolation Exploiting Semantics for Index Management）という方式で用いられている方法を応用して用いてもよい。
このＡＲＩＥＳ／ＩＭ方式の方法を応用すると、まず、ＳＭ＿ｂｉｔというビットを各ページに設け、初期値として“０”に設定しておく。そして、ページを更新する際には、木ラッチと呼ばれるシステムに１つしかないラッチを獲得する。この更新のためのラッチ獲得方法としては、ボトムアップのラッチカップリングを用いる。そして、更新されたページのＳＭ＿ｂｉｔに“１”を設定する。その後、関連するページの更新が終わった段階で、ＳＭ＿ｂｉｔを“０”に設定し、木ラッチを解放する。
【００６５】
そして、経路誤り判定手段２２３は、インデックスページを降下していく際に、ＳＭ＿ｂｉｔに“１”が設定されているページに至った場合、経路誤りの可能性があると判定する。そして、経路誤り判定手段２２３は、経路誤りの可能性があると判定した場合、さらに、処理対象の検索キーの値が、当該ページに含まれている検索キーの値よりも大きいか否かを判定し、大きい場合に経路が誤っていると判定する。このとき、経路誤り判定手段２２３は、木ラッチが解放されるまで待機する。
そして、経路誤り判定手段２２３は、木ラッチが解放された後、経路再探索手段２２４（経路復旧手段）に経路誤りがあった旨を通知する。
【００６６】
経路再探索手段（経路復旧手段）２２４は、経路誤り判定手段２２３で経路誤りと判定された場合に、経路の復旧を行うものである。ここでは、経路再探索手段２２４は、再度最上位のページからデータの探索を行うことで、経路の復旧を行う。この場合、経路再探索手段２２４は、プロセス管理手段４０に対して、当該プロセスの再起動を要求する。この後、プロセスが再起動されることで、正しい経路によりデータ（葉ページ）が探索されることになる。
【００６７】
なお、ここでは、経路再探索手段２２４が、プロセスを再起動することで、最上位のページからデータの探索を行うこととしたが、経路誤りと判定したページの上位ページから再度探索を行うこととしてもよい。この場合、例えば、各ページにページの更新によって値が変化するログ用番号（ＬＳＮ：Log Sequence Number）を付しておき、経路探索時には、各ページのログ用番号を記憶し、復旧時には、このログ用番号が変化していない上位のページまで遡ることで、正しい経路に復旧することができる。
【００６８】
木構造更新手段２３は、木構造情報ＴＲにおけるページの追加、削除等に伴う木構造の更新を行うものである。ここでは、木構造更新手段２３は、ページ削除手段２３１と、ページ分割・追加手段２３２とを備えている。
【００６９】
ページ削除手段２３１は、不用になったページを削除して、木構造情報ＴＲを更新するものである。このページ削除手段２３１は、データ操作手段１０によってデータＤＴが削除されることで、参照先のページがなくなったインデックスページ、あるいは、参照先が他のディレクトリ分散型記憶装置（図示せず）へのポインタのみとなったインデックスページを削除する。
【００７０】
なお、ページ削除手段２３１は、削除ビット設定手段２３１ａを備え、ページを削除する場合、削除ビット設定手段２３１ａによって、当該ページに対して削除ビットを設定し、プロセス管理手段４０に対して、削除ビット設定時点で起動されていたプロセスの終了を待つ旨の通知を行う。そして、ページ削除手段２３１は、削除ビット設定時点で起動されていたプロセスの終了をプロセス管理手段４０から通知された段階で、該当するページを削除し、木構造情報ＴＲを更新する。
これによって、削除ビット設定時点で当該ページを参照していたプロセスの動作を保証することができる。
【００７１】
削除ビット設定手段２３１ａは、指定されたページに削除ビットを設定するものである。具体的には、削除ビット設定手段２３１ａは、指定されたページの「削除ビットＤｂ」の領域（図２参照）に、削除対象のページであることを示すビット（例えば、値“１”）を設定する。これによって、削除ビットが設定された後に、当該ページを参照するプロセスは、当該ページが無効であることを認識することができる。
【００７２】
ページ分割・追加手段２３２は、新規にページを追加するものである。なお、ページ分割・追加手段２３２は、新規にページを追加し、元のページのエントリ数がエントリ制限情報ＥＬで示される最大値を越える場合、元のエントリの半分を新たなページに移すことでページの分割を行い、木構造情報ＴＲを更新する。
このページ分割・追加手段２３２は、データ操作手段１０によってデータＤＴが追加されることによって、そのデータＤＴを参照する親ページのエントリ数が、エントリ制限情報ＥＬで示される最大値を超過する場合に、該当ページを分割する。なお、ページ分割・追加手段２３２は、親ページのエントリ数が、さらに、エントリ制限情報ＥＬで示される最大値を超過する場合には、順次親ページを分割する。そして、その分割がルートページにまで波及した場合、ページ分割・追加手段２３２は、当該ルートページを分割し、その上位にルートページを生成する。
ここでは、ページ分割・追加手段２３２は、境界値設定手段２３２ａと、管理対象ページ判定手段２３２ｂと、ポインタ設定手段２３２ｃとを備えている。
【００７３】
境界値設定手段２３２ａは、ページが追加又は分割される際に、ページ内に各ページ間の検索キーの境界値を設定するものである。具体的には、境界値設定手段２３２ａは、インデックスページの「終端検索キーＫｅ」の領域（図２参照）に、追加又は分割により新たに生成された後続のインデックスページの先頭に記述されている検索キーの値を設定する。
【００７４】
ここで、図４を参照（適宜図１参照）して、インデックスページの境界値設定の手法について説明する。ここでは、インデックスページを分割する場合を例に説明する。図４は、インデックスページの分割により境界値を設定する例を説明するための説明図であって、（ａ）は分割前、（ｂ）は分割後のインデックスページの内容を示している。
【００７５】
ここでは、図４（ａ）に示すインデックスページＰ１は、Ｋ０以上Ｋｎ未満（Ｋ０≦Ｋｉ＜Ｋｎ）の検索キーを有するインデックスページである。ここで、検索キーＫｉ以降を分割することとする。
この場合、ページ分割・追加手段２３２は、図４（ｂ）に示すように、インデックスページＰ１を、検索キーの値がＫｉ未満のインデックスページＰ２と、Ｋｉ以上のインデックスページＰ３とに分割する。このとき、境界値設定手段２３２ａが、インデックスページＰ３における先頭の検索キーの値Ｋｉを、インデックスページＰ２の「終端検索キーＫｅ」の領域に設定する。これによって、インデックスページの検索キーの境界値により、インデックスページの検索キーの両端を示すことができるため、前記した経路誤り判定手段２２３は、経路の誤りを判定することが可能になる。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００７６】
管理対象ページ判定手段２３２ｂは、ページを分割することにより生成された２つのページが、当該装置ＰＥＡの管理対象ページであるか否かを判定するものである。ここでは、管理対象ページ判定手段２３２ｂは、ページ内のすべてのポインタが、当該装置ＰＥＡ以外の他のディレクトリ分散型記憶装置（図示せず）で管理されているページを指し示すポインタ（リモートポインタ）である場合に、当該ページを管理対象ページでないと判定する。一方、ページ内のポインタのうち一つでも当該装置ＰＥＡで管理されているページを指し示すポインタ（ローカルポインタ）である場合は、当該ページを管理対象ページであると判定する。
なお、管理対象ページ判定手段２３２ｂは、分割により生成されたページを管理対象ページでないと判定したときは、ページ削除手段２３１によって、当該ページを削除する。これによって、不用なページが管理から除外されることになる。
【００７７】
ポインタ設定手段２３２ｃは、ページの追加又は分割によって、新たに生成されたページへのポインタを親ページに設定するものである。なお、ポインタ設定手段２３２ｃは、ページの分割の際は、管理対象ページ判定手段２３２ｂによって、管理対象ページであると判定されたページのみ親ページにポインタを設定する。
【００７８】
ここで、図５〜図８を参照（適宜図１参照）して、インデックスページの分割手法について説明する。図５は、インデックスページを分割した際の分割パターンを説明するための説明図である。
ここでは、図５（ａ）に示すように、インデックスページＰ１（親ページ）の検索キーＫｉのポインタで示されているインデックスページＰ２（子ページ）は、エントリ数がエントリ制限情報ＥＬで示される最大値の状態（Ｆｕｌｌ ｅｎｔｒｙ）であるとする。
【００７９】
図５（ａ）に示した状態で、インデックスページＰ２に新たなエントリを設定しようとすると、ページ分割・追加手段２３２によって、図５（ｂ）に示すように、インデックスページＰ２が分割される。このとき、分割直後のインデックスページＰ２は、親ページ（インデックスページＰ１）からポインタで指し示されているページ（インデックスページＰ２１：便宜上「左側ページ」と呼ぶ）と、新たに分割により生成され親ページ（インデックスページＰ１）からポインタで指し示されていないページ（インデックスページＰ２２：便宜上「右側ページ」と呼ぶ）とに分割されることになる。
【００８０】
このように分割されたとき、分割されたページのそれぞれが、当該装置ＰＥＡで管理されているページを指し示すポインタを含んでいるか、当該装置ＰＥＡ以外の他のディレクトリ分散型記憶装置（図示せず）で管理されているページを指し示すポインタのみであるかによって、分割パターンを（ｂ−１）、（ｂ−２）及び（ｂ−３）に分類することができる。なお、当該装置ＰＥＡで管理されているページを指し示すポインタをロールポインタと呼び、図中「ｌｏｃａｌ」で示す。また、当該装置ＰＥＡ以外の他のディレクトリ分散型記憶装置（図示せず）で管理されているページを指し示すポインタをリモートポインタと呼び、図中「ｒｅｍｏｔｅ」で示す。
【００８１】
まず、第１の分割パターンは、（ｂ−１）に示すように、分割されたページ（インデックスページＰ２１，Ｐ２２）のどちらにもローカルポインタが含まれている分割パターンである。
また、第２の分割パターンは、（ｂ−２）に示すように、左側ページＰ２１にはローカルポインタが含まれているが、右側ページＰ２２にはローカルポインタが含まれておらずリモートポインタのみが含まれている分割パターンである。
また、第３の分割パターンは、（ｂ−３）に示すように、右側ページＰ２２にはローカルポインタが含まれているが、左側ページＰ２１にはローカルポインタが含まれておらずリモートポインタのみが含まれている分割パターンである。
【００８２】
このように、インデックスパターンを分割した場合、リモートポインタを有していないページは、当該装置ＰＥＡには不要なページであるため削除する必要がある。
そこで、以下、図６〜図８を参照（適宜図１参照）して、分割後の処理について説明する。図６は、第１の分割パターンにおける分割後の処理を説明するための説明図である。図７は、第２の分割パターンにおける分割後の処理を説明するための説明図である。図８は、第３の分割パターンにおける分割後の処理を説明するための説明図である。
【００８３】
第１の分割パターンでは、図６（ａ）に示すように、分割されたページ（インデックスページＰ２１，Ｐ２２）のどちらにもローカルポインタが含まれているため、ページを削除する必要はない。そこで、ディレクトリ分散型記憶装置ＰＥＡは、図６（ｂ）に示すように、分割により新たに生成されたページ（インデックスページＰ２２）へのポインタ（ローカルポインタ）を親ページ（インデックスページＰ１）に設定する。
【００８４】
また、第２の分割パターンでは、図７（ａ）に示すように、左側ページＰ２１にはローカルポインタが含まれているが、右側ページＰ２２にはローカルポインタが含まれていないため、右側ページＰ２２を削除する必要がある。そこで、ディレクトリ分散型記憶装置ＰＥＡは、図７（ｂ）に示すように、分割により新たに生成されたページ（インデックスページＰ２２）を削除し、削除されたページのコピーを管理している他のディレクトリ分散型記憶装置へのポインタ（リモートポインタ）を親ページ（インデックスページＰ１）に設定する。
【００８５】
また、第３の分割パターンでは、図８（ａ）に示すように、右側ページＰ２２にはローカルポインタが含まれているが、左側ページＰ２１にはローカルポインタが含まれていないため、左側ページＰ２１を削除する必要がある。そこで、ディレクトリ分散型記憶装置ＰＥＡは、図８（ｂ）に示すように、親ページ（インデックスページＰ１）からポインタで指し示されている左側ページ（インデックスページＰ２１）を削除し、削除されたページのコピーを管理している他のディレクトリ分散型記憶装置へのポインタ（リモートポインタ）を親ページ（インデックスページＰ１）に設定する。さらに、分割により新たに生成されたページ（インデックスページＰ２２）へのポインタ（ローカルポインタ）を親ページ（インデックスページＰ１）に設定する。
図１に戻って、ディレクトリ分散型記憶装置の構成について説明を続ける。
【００８６】
制御情報送受信手段３０は、通信制御部１を介して、図示していないクライアントコンピュータや他のディレクトリ分散型記憶装置と制御情報の送受信を行うものである。ここでは、制御情報送受信手段３０は、クライアントコンピュータ等から受信した制御情報をデータ操作手段１０や木構造管理手段２０に出力し、データ操作手段１０や木構造管理手段２０から出力された制御信号をクライアントコンピュータ等に送信する。
【００８７】
プロセス管理手段４０は、ディレクトリ分散型記憶装置ＰＥＡ内で起動されるプロセスを管理するものである。
ここでは、プロセス管理手段４０は、経路探索手段２２からプロセスの再起動が通知された場合、要求のあったプロセスを再起動する。これによって、経路探索手段２２における経路探索がリスタートされることになる。
また、ページ削除手段２３１から、削除ビット設定時点で起動されていたプロセスの終了を待つ旨の通知があった場合、プロセス管理手段４０は、その時点において起動していたプロセスがすべて終了した段階で、ページ削除手段２３１にプロセスの終了を通知する。これによって、他のプロセスに影響を与えることなくページを削除することができる。
【００８８】
以上説明したように、ディレクトリ分散型記憶装置ＰＥＡを構成することで、木構造の上位から下位の層に向かってラッチを設定する際に、従来のようなラッチカップリングを行う必要がないため、処理要求の移譲が発生する場合であっても、ネットワーク上のメッセージ伝送の回数が１回で済む。このように、ネットワーク上のメッセージ伝送の頻度を抑えることができるため、従来に比べ、システム規模の拡大によるスループットの向上の効果を高めることができる。
【００８９】
なお、ここでは、ディレクトリ分散型記憶装置ＰＥＡのディレクトリ構造がＦａｔ−Ｂｔｒｅｅ構造であるものとして説明を行ったが、一般的な並列Ｂｔｒｅｅ構造を有する場合であっても構わない。
また、ディレクトリ分散型記憶装置ＰＥＡの制御部３は、一般的なコンピュータにプログラムを実行させ、コンピュータ内の演算装置や記憶装置を動作させることにより実現することができる。ここで実現される処理要求の移譲を行うデータ処理要求移譲プログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００９０】
［ディレクトリ分散型記憶装置の動作］
次に、図９及び図１０を参照して、ディレクトリ分散型記憶装置の動作について説明する。なお、ここでは、ディレクトリ分散型記憶装置ＰＥＡの木構造管理手段２０において行われる、処理要求の移譲処理動作とページの分割処理について、詳細に説明を行うことにする。図９は、本発明のディレクトリ分散型記憶装置における処理要求の移譲処理動作を示すフローチャートである。図１０は、本発明のディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。
【００９１】
（移譲処理動作）
最初に、図９を参照（適宜図１参照）して、データの処理要求の移譲処理動作について説明する。
まず、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２によって、初期値として、親ページを“ｎｕｌｌ”、子ページをルートページに設定する（ステップＳ１）。そして、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２によって、木構造情報ＴＲを参照することで、要求のあった検索キーのページをアクセスする際に、さらに子ページへの降下が必要であるか否かを判定する（ステップＳ２）。
【００９２】
ここで、降下が必要でない場合（ステップＳ２でＮｏ）、そのページが要求のあった葉ページであるため、ディレクトリ分散型記憶装置ＰＥＡは、データ操作手段１０によって、当該葉ページへの処理を実行し（ステップＳ３）、動作を終了する。一方、降下が必要である場合（ステップＳ２でＹｅｓ）、ディレクトリ分散型記憶装置ＰＥＡは、移譲判定手段２２１によって、木構造情報ＴＲを参照し、要求のあったページのポインタが自装置ＰＥＡで管理されているページへのポインタであるか否かに基づいて、移譲が必要であるか否かを判定する（ステップＳ４）。
【００９３】
ここで、移譲が必要な場合（ステップＳ４でＹｅｓ）、ディレクトリ分散型記憶装置ＰＥＡは、移譲手段２２２によって、移譲先の他のディレクトリ分散型記憶装置（図示せず）へ処理要求の移譲を要求し（移譲要求メッセージ送信）、動作を終了する。この段階で、移譲先への移譲処理が開始されたことになる。なお、処理要求の移譲を要求された他のディレクトリ分散型記憶装置は、後記するステップＳ５以降の動作を実行する。
一方、移譲が必要でない場合（ステップＳ４でＮｏ）、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２からの指示に基づいてラッチ設定手段２１により、子ページにラッチを設定する（ステップＳ５）。
【００９４】
そして、ディレクトリ分散型記憶装置ＰＥＡは、経路誤り判定手段２２３によって、処理対象の検索キーが当該ページに属するものであるか否かを判定することで、経路の誤りを判定する（ステップＳ６）。すなわち、経路誤り判定手段２２３が、検索キーの値が当該ページに設定されている先頭の検索キーの値以上で、終端検索キーの値未満であることを判定することで、経路の正誤を判定する。
ここで、経路に誤りがある場合（ステップＳ６で「誤」）、ディレクトリ分散型記憶装置ＰＥＡは、経路再探索手段２２４によって、プロセス管理手段４０に対してプロセスの再起動を要求することで、ステップＳ１から再度探索動作を行う。
一方、経路が正しい場合（ステップＳ６で「正」）、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２によって、対象となるページを子ページに降下させる。すなわち、経路探索手段２２が、子ページを新たな親ページに設定し、孫ページを新たな子ページに設定する（ステップＳ７）。
【００９５】
さらに、ディレクトリ分散型記憶装置ＰＥＡは、経路探索手段２２からの指示に基づいてラッチ設定手段２１により、親ページのラッチを解除する（ステップＳ８）。
その後、ディレクトリ分散型記憶装置ＰＥＡは、ステップＳ１に戻って、処理対象の葉ページに到達するまで動作を続ける。
【００９６】
以上の動作によって、ディレクトリ分散型記憶装置ＰＥＡは、処理対象のページが当該装置ＰＥＡに存在しない場合、ネットワーク上で１回の移譲要求メッセージを送信だけで、他のディレクトリ分散型記憶装置に処理を移譲することができる。また、処理途中で他のプロセスの動作によるページの分割等が発生した場合でも、経路誤りを検出することができるため、正しい経路で目的の処理対象ページに到達することができる。
【００９７】
（分割処理動作）
次に、図１０を参照（適宜図１、図６〜図８参照）して、ページの分割処理動作について説明する。ここでは、インデックスページのエントリ数がエントリ制限情報ＥＬで示される最大値を超過した以降の動作について説明する。
【００９８】
まず、ディレクトリ分散型記憶装置ＰＥＡは、ページ分割・追加手段２３２によって、対象のページ（インデックスページ）を分割する（ステップＳ２０）。
そして、ディレクトリ分散型記憶装置ＰＥＡは、境界値設定手段２３２ａによって、ページ内に検索キーの境界値を設定する（ステップＳ２１）。
【００９９】
その後、ディレクトリ分散型記憶装置ＰＥＡは、管理対象ページ判定手段２３２ｂによって、分割されたページのうちで、リモートポインタのみが設定されているページが存在するか否かを判定する（ステップＳ２２）。ここで、リモートポインタのみが設定されているページが存在しない場合（ステップＳ２２でＮｏ）、ディレクトリ分散型記憶装置ＰＥＡは、ポインタ設定手段２３２ｃによって、親ページにポインタが設定されていない、分割によって新たに生成されたページ（図６中、インデックスページＰ２２〔右側ページ〕）のポインタを親ページに設定し（ステップＳ２３）、動作を終了する。
【０１００】
一方、リモートポインタのみが設定されているページが存在する場合（ステップＳ２２でＹｅｓ）、ディレクトリ分散型記憶装置ＰＥＡは、管理対象ページ判定手段２３２ｂによって、当該ページへのポインタが親ページに設定されているか否かを判定する（ステップＳ２４）。
【０１０１】
ここで、当該ページへのポインタが親ページに設定されていない場合（ステップＳ２４でＮｏ）、すなわち、分割によって新たに生成されたページ（図７中、インデックスページＰ２２〔右側ページ〕）である場合、ディレクトリ分散型記憶装置ＰＥＡは、ページ削除手段２３１によって、当該ページを削除する（ステップＳ２５）。その後、ディレクトリ分散型記憶装置ＰＥＡは、ポインタ設定手段２３２ｃによって、当該ページの先頭に設定されていたリモートポインタ（他のディレクトリ分散型記憶装置へのポインタ）を親ページに設定し（ステップＳ２６）、動作を終了する。
【０１０２】
一方、当該ページへのポインタが親ページに設定されている場合（ステップＳ２４でＹｅｓ）、すなわち、分割の元となったページ（図８中、インデックスページＰ２１〔左側ページ〕）である場合、ディレクトリ分散型記憶装置ＰＥＡは、ページ削除手段２３１によって、当該ページを削除する（ステップＳ２７）。なお、このとき、ページ削除手段２３１では、削除ビット設定手段２３１ａによって、当該ページに削除ビットを設定し、削除ビット設定時点で起動されていたプロセスの終了を待って当該ページの削除を行う。
【０１０３】
そして、親ページに設定されていた当該ページへのローカルポインタのエントリの内容を、他のディレクトリ分散型記憶装置に蓄積されている当該ページのコピーページへのリモートポインタに変更する（ステップＳ２８）。その後、ディレクトリ分散型記憶装置ＰＥＡは、ポインタ設定手段２３２ｃによって、分割によって新たに生成されたページ（図８中、インデックスページＰ２２〔右側ページ〕）のポインタ（ローカルポインタ）を親ページに設定し（ステップＳ２９）、動作を終了する。
以上の動作によって、ディレクトリ分散型記憶装置ＰＥＡは、インデックスページを分割する際に、各ページに検索キーの境界値を設定するため、当該ページを参照するプロセスが経路誤りを検出することが可能になる。
【０１０４】
≪第２実施形態≫
［ディレクトリ分散型記憶装置の構成］
次に、図１１を参照して、第２実施形態に係るディレクトリ分散型記憶装置の構成について説明する。図１１は、本発明の第２実施形態に係るディレクトリ分散型記憶装置の構成を示すブロック図である。
図１１に示したディレクトリ分散型記憶装置ＰＥＢは、ネットワークＮに接続された他のディレクトリ分散型記憶装置（図示せず）と協働し、データベース等のデータを分散して記憶するものである。
【０１０５】
なお、ディレクトリ分散型記憶装置ＰＥＢは、ページ分割・追加手段２３２Ｂを、図１で説明したディレクトリ分散型記憶装置ＰＥＡのページ分割・追加手段２３２における管理対象ページ判定手段２３２ｂの機能を変更した管理対象ページ判定手段２３２Ｂｂとし、新たにエントリ複製手段２３２ｄを付加して構成している。管理対象ページ判定手段２３２Ｂｂ及びエントリ複製手段２３２ｄ以外の構成は、図１で説明したディレクトリ分散型記憶装置ＰＥＡと同一の構成であるため、同一の符号を付し、説明を省略する。
【０１０６】
管理対象ページ判定手段２３２Ｂｂは、ページを分割することにより生成された２つのページが、当該装置ＰＥＢの管理対象のページであるか否かを判定するものである。なお、基本的には、管理対象ページ判定手段２３２Ｂｂは、図１で説明した管理対象ページ判定手段２３２ｂと同一の機能を有しているが、図８で説明した第３の分割パターンにおける分割手法のみが異なっている。
この管理対象ページ判定手段２３２Ｂｂは、分割された元のページを管理対象ページでないと判定したときは、後記するエントリ複製手段２３２ｄによって、分割により新たに生成されたページの内容を、分割された元のページに上書きした後に、ページ削除手段２３１によって、分割により新たに生成されたページを削除する点が異なっている。
【０１０７】
エントリ複製手段２３２ｄは、管理対象ページ判定手段２３２Ｂｂによって指定された複製元のページの内容を、同じく指定された複製先のページに上書きするものである。
ここで、図１２を参照（適宜図１１参照）して、図８で説明した第３の分割パターンとの差異点について説明する。図１２は、第３の分割パターンにおける分割後の処理を説明するための説明図である。
【０１０８】
図１２（ａ）に示すように、第３の分割パターンにおいては、右側ページＰ２２にはローカルポインタが含まれているが、左側ページＰ２１にはローカルポインタが含まれていないため、左側ページＰ２１を削除する必要がある。
このとき、ディレクトリ分散型記憶装置ＰＥＢは、図１２（ｂ）に示すように、分割により新たに生成された右側ページ（インデックスページＰ２２）の内容を、親ページ（インデックスページＰ１）からポインタで指し示されている左側ページ（インデックスページＰ２１）に上書きし、その後、右側ページ（インデックスページＰ２２）を削除する。さらに、親ページ（インデックスページＰ１)に設定されている元の左側ページへのローカルポインタのエントリＫｉを他のディレクトリ分散型記憶装置に蓄積されている元の左側ページのコピーページへのリモートポインタを設定し、残った子インデックスページの始端を表すエントリＫｊを新たに追加してコピー先の子ページ（インデックスページＰ２２）へのリモートポインタを設定する。
【０１０９】
この手法によれば、分割直後は、インデックスページＰ２２へのポインタが存在していないため、インデックスページＰ２２へアクセスが発生していない。このため、図８で説明した分割手法では、ページを削除する際に分割前のページにアクセスしていたプロセスは再起動されることになるが、この手法では、ページを削除する際に分割前のページにアクセスしていたプロセスは、分割により検索キーが境界値を越えた場合にだけ再起動されるため、再起動される確率が２分の１となり、より効率的に動作させることができる。
【０１１０】
［ディレクトリ分散型記憶装置の動作］
次に、図１３を参照（適宜図１１及び図１２参照）して、ディレクトリ分散型記憶装置の動作について説明する。図１３は、本発明の第２実施形態に係るディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。なお、処理要求の移譲処理動作については、図９で説明した動作と同一であるため説明を省略する。
【０１１１】
（分割処理動作）
図１３のステップＳ２０〜Ｓ２６は、図１０と同一の動作であるため、同一の符号を付し、説明を省略する。
ディレクトリ分散型記憶装置ＰＥＢは、分割したページへのポインタが親ページに設定されている場合（ステップＳ２４でＹｅｓ）、すなわち、分割の元となったページ（図１２中、インデックスページＰ２１〔左側ページ〕）である場合、エントリ複製手段２３２ｄによって、分割により新たに生成されたページ（図１２中、インデックスページＰ２２〔右側ページ〕）の内容（エントリ）を、分割の元となったページ（図１２中、インデックスページＰ２１〔左側ページ〕）に上書きする（ステップＳ３０）。
【０１１２】
そして、ディレクトリ分散型記憶装置ＰＥＢは、ページ削除手段２３１によって、インデックスページＰ２２〔右側ページ〕を削除する（ステップＳ３１）。
その後、ディレクトリ分散型記憶装置ＰＥＢは、親ページに設定されていた分割の元となったページ（図１２中、インデックスページＰ２１〔左側ページ〕）へのローカルポインタのエントリの内容を、他のディレクトリ分散型記憶装置に蓄積されている当該ページのコピーページへのリモートポインタに設定しなおし（ステップＳ３２）、分割の元となったページのローカルポインタを親ページに設定し（ステップＳ３３）、動作を終了する。
【０１１３】
以上の動作によって、ディレクトリ分散型記憶装置ＰＥＢは、インデックスページを分割する際に、各ページに検索キーの境界値を設定するため、当該ページを参照するプロセスが経路誤りを検出することが可能になる。また、プロセスの再起動の回数を減らすことができる。
【図面の簡単な説明】
【０１１４】
【図１】本発明のディレクトリ分散型記憶装置の構成を示すブロック図である。
【図２】木構造情報を構成するインデックスページの構造を示すデータ構造図である。
【図３】ディレクトリ分散型記憶装置間で行う処理の移譲手順を示す模式図である。
【図４】インデックスページの分割により境界値を設定する例を説明するための説明図であって、（ａ）は分割前、（ｂ）は分割後のインデックスページの内容を示している。
【図５】インデックスページを分割した際の分割パターンを説明するための説明図である。
【図６】第１の分割パターンにおける分割後の処理を説明するための説明図である。
【図７】第２の分割パターンにおける分割後の処理を説明するための説明図である。
【図８】第３の分割パターンにおける分割後の処理を説明するための説明図である。
【図９】本発明のディレクトリ分散型記憶装置における処理要求の移譲処理動作を示すフローチャートである。
【図１０】本発明のディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。
【図１１】本発明の第２実施形態に係るディレクトリ分散型記憶装置の構成を示すブロック図である。
【図１２】本発明の第２実施形態に係るディレクトリ分散型記憶装置において、第３の分割パターンにおける分割後の処理を説明するための説明図である。
【図１３】本発明の第２実施形態に係るディレクトリ分散型記憶装置におけるページの分割処理動作を示すフローチャートである。
【図１４】従来の分散データ格納システムにおけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造を示す図である。
【図１５】従来の並列計算機における処理要求の移譲動作を示すフローチャートである。
【図１６】計算機間で処理の移譲を伴わないラッチカップリングの動作例を示す模式図である。
【図１７】計算機間で処理の移譲を伴うラッチカップリングの動作例を示す模式図である。
【符号の説明】
【０１１５】
ＰＥＡ，ＰＥＢ ディレクトリ分散型記憶装置
１ 通信制御部
２ 記憶部
３ 制御部
１０ データ操作手段
１１ データ送受信手段
１２ データ参照手段
１３ データ更新手段
２０ 木構造管理手段
２１ ラッチ設定手段（ロック設定手段）
２２ 経路探索手段
２２１ 移譲判定手段
２２２ 移譲手段
２２３ 経路誤り判定手段
２２４ 経路再探索手段（経路復旧手段）
２３ 木構造更新手段
２３１ ページ削除手段
２３１ａ 削除ビット設定手段
２３２ ページ分割・追加手段
２３２ａ 境界値設定手段
２３２ｂ 管理対象ページ判定手段
２３２ｃ ポインタ設定手段
２３２ｄ エントリ複製手段
３０ 制御情報送受信手段
４０ プロセス管理手段
【特許請求の範囲】
【請求項１】
データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページを木構造情報として記憶する記憶手段と、前記ページの更新に伴い前記木構造情報を更新する木構造更新手段と、前記木構造情報に基づいて、前記データまでの経路を前記ページのロックの設定と解除とを行いながら探索する経路探索手段とを備え、ネットワーク環境下で前記ディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、
前記経路探索手段が、
前記データまでの経路を探索する経路途中のページにおいて、経路誤りを判定する経路誤り判定手段と、
この経路誤り判定手段で経路誤りと判定された場合に、前記経路の復旧を行う経路復旧手段と、
前記ページ内の参照先に基づいて、前記データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段と、
この移譲判定手段で前記他のディレクトリ分散型記憶装置へ前記処理要求を移譲すると判定した場合に、前記処理要求を前記他のディレクトリ分散型記憶装置へ送信する移譲手段と、を備えていることを特徴とするディレクトリ分散型記憶装置。
【請求項２】
データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページを木構造情報として記憶する記憶手段と、前記ページの更新に伴い前記木構造情報を更新する木構造更新手段と、前記木構造情報に基づいて、前記データまでの経路を前記ページのロックの設定と解除とを行いながら探索する経路探索手段とを備え、ネットワーク環境下で前記ディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、
前記木構造更新手段が、
前記ページ内の参照先の数が予め定めた制限値を超過して当該ページを分割する際に、分割されたページごとに、当該ページで管理する前記検索キーの境界値を設定する境界値設定手段を備え、
前記経路探索手段が、
前記データまでの経路を探索する経路途中のページにおいて、当該データの検索キーの値が、前記境界値設定手段で設定された境界値の範囲内であるか否かに基づいて、経路誤りを判定する経路誤り判定手段と、
この経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから経路の探索を行う経路再探索手段と、
前記ページ内の参照先に基づいて、前記データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段と、
この移譲判定手段で前記他のディレクトリ分散型記憶装置へ前記処理要求を移譲すると判定した場合に、前記処理要求を前記他のディレクトリ分散型記憶装置へ送信する移譲手段と、を備えていることを特徴とするディレクトリ分散型記憶装置。
【請求項３】
プロセスを管理するプロセス管理手段を備え、
前記木構造更新手段が、
前記ページを分割した際に、当該ディレクトリ分散型記憶装置以外の参照先のみからなるページを、当該ディレクトリ分散型記憶装置の管理対象外のページであると判定する管理対象ページ判定手段と、
この管理対象ページ判定手段で管理対象外のページであると判定したページを削除するページ削除手段とを備え、
前記ページ削除手段が、当該ページを参照するプロセスが存在しなくなった段階で、当該ページを削除することを特徴とする請求項２に記載のディレクトリ分散型記憶装置。
【請求項４】
前記木構造更新手段が、
前記ページを分割した際に、親ページに参照先が記述されている一方のページが当該ディレクトリ分散型記憶装置以外の参照先のみからなるページである場合に、分割された他方のページの内容を前記一方のページにコピーするエントリ複製手段を備え、
このエントリ複製手段によりコピーされた後に、前記ページ削除手段が、前記他方のページを削除することを特徴とする請求項３に記載のディレクトリ分散型記憶装置。
【請求項５】
データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページで構成されるディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記データへの処理要求を、ネットワークに接続された他のディレクトリ分散型記憶装置に移譲するために、コンピュータを、
前記ページ内の参照先の数が予め定めた制限値を超過して当該ページを分割する際に、分割されたページごとに、当該ページで管理する検索キーの境界値を設定する境界値設定手段、
前記データまでの経路を探索する経路において、上位のページにロックを設定し、下位ページへの参照先を取得した後に、前記ロックを解除し、下位のページにロックを設定する処理を繰り返すロック設定手段、
前記データまでの経路を探索する経路途中のページにおいて、当該データの検索キーの値が、前記境界値設定手段で設定された境界値の範囲内であるか否かに基づいて、経路誤りを判定する経路誤り判定手段、
この経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから探索を行う経路再探索手段、
前記ページ内の参照先に基づいて、前記データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段、
この移譲判定手段で前記他のディレクトリ分散型記憶装置へ前記処理要求を移譲すると判定した場合に、前記処理要求を前記他のディレクトリ分散型記憶装置へ送信する移譲手段、として機能させることを特徴とするデータ処理要求移譲プログラム。
【請求項１】
データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページを木構造情報として記憶する記憶手段と、前記ページの更新に伴い前記木構造情報を更新する木構造更新手段と、前記木構造情報に基づいて、前記データまでの経路を前記ページのロックの設定と解除とを行いながら探索する経路探索手段とを備え、ネットワーク環境下で前記ディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、
前記経路探索手段が、
前記データまでの経路を探索する経路途中のページにおいて、経路誤りを判定する経路誤り判定手段と、
この経路誤り判定手段で経路誤りと判定された場合に、前記経路の復旧を行う経路復旧手段と、
前記ページ内の参照先に基づいて、前記データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段と、
この移譲判定手段で前記他のディレクトリ分散型記憶装置へ前記処理要求を移譲すると判定した場合に、前記処理要求を前記他のディレクトリ分散型記憶装置へ送信する移譲手段と、を備えていることを特徴とするディレクトリ分散型記憶装置。
【請求項２】
データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページを木構造情報として記憶する記憶手段と、前記ページの更新に伴い前記木構造情報を更新する木構造更新手段と、前記木構造情報に基づいて、前記データまでの経路を前記ページのロックの設定と解除とを行いながら探索する経路探索手段とを備え、ネットワーク環境下で前記ディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、
前記木構造更新手段が、
前記ページ内の参照先の数が予め定めた制限値を超過して当該ページを分割する際に、分割されたページごとに、当該ページで管理する前記検索キーの境界値を設定する境界値設定手段を備え、
前記経路探索手段が、
前記データまでの経路を探索する経路途中のページにおいて、当該データの検索キーの値が、前記境界値設定手段で設定された境界値の範囲内であるか否かに基づいて、経路誤りを判定する経路誤り判定手段と、
この経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから経路の探索を行う経路再探索手段と、
前記ページ内の参照先に基づいて、前記データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段と、
この移譲判定手段で前記他のディレクトリ分散型記憶装置へ前記処理要求を移譲すると判定した場合に、前記処理要求を前記他のディレクトリ分散型記憶装置へ送信する移譲手段と、を備えていることを特徴とするディレクトリ分散型記憶装置。
【請求項３】
プロセスを管理するプロセス管理手段を備え、
前記木構造更新手段が、
前記ページを分割した際に、当該ディレクトリ分散型記憶装置以外の参照先のみからなるページを、当該ディレクトリ分散型記憶装置の管理対象外のページであると判定する管理対象ページ判定手段と、
この管理対象ページ判定手段で管理対象外のページであると判定したページを削除するページ削除手段とを備え、
前記ページ削除手段が、当該ページを参照するプロセスが存在しなくなった段階で、当該ページを削除することを特徴とする請求項２に記載のディレクトリ分散型記憶装置。
【請求項４】
前記木構造更新手段が、
前記ページを分割した際に、親ページに参照先が記述されている一方のページが当該ディレクトリ分散型記憶装置以外の参照先のみからなるページである場合に、分割された他方のページの内容を前記一方のページにコピーするエントリ複製手段を備え、
このエントリ複製手段によりコピーされた後に、前記ページ削除手段が、前記他方のページを削除することを特徴とする請求項３に記載のディレクトリ分散型記憶装置。
【請求項５】
データを検索するための検索キーと木構造を有するディレクトリ構造の下位のページへの参照先とを含んだ複数のページで構成されるディレクトリ構造を分散して管理するディレクトリ分散型記憶装置において、前記データへの処理要求を、ネットワークに接続された他のディレクトリ分散型記憶装置に移譲するために、コンピュータを、
前記ページ内の参照先の数が予め定めた制限値を超過して当該ページを分割する際に、分割されたページごとに、当該ページで管理する検索キーの境界値を設定する境界値設定手段、
前記データまでの経路を探索する経路において、上位のページにロックを設定し、下位ページへの参照先を取得した後に、前記ロックを解除し、下位のページにロックを設定する処理を繰り返すロック設定手段、
前記データまでの経路を探索する経路途中のページにおいて、当該データの検索キーの値が、前記境界値設定手段で設定された境界値の範囲内であるか否かに基づいて、経路誤りを判定する経路誤り判定手段、
この経路誤り判定手段で経路誤りと判定された場合に、再度上位のページから探索を行う経路再探索手段、
前記ページ内の参照先に基づいて、前記データへの要求処理を他のディレクトリ分散型記憶装置へ移譲するか否かを判定する移譲判定手段、
この移譲判定手段で前記他のディレクトリ分散型記憶装置へ前記処理要求を移譲すると判定した場合に、前記処理要求を前記他のディレクトリ分散型記憶装置へ送信する移譲手段、として機能させることを特徴とするデータ処理要求移譲プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００８−４６７００（Ｐ２００８−４６７００Ａ）
【公開日】平成２０年２月２８日（２００８．２．２８）
【国際特許分類】
【出願番号】特願２００６−２１９２０１（Ｐ２００６−２１９２０１）
【出願日】平成１８年８月１１日（２００６．８．１１）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り （１）ｉ）２００６年２月２４日に社団法人電子情報通信学会の「第１７回データ工学ワークショップ（ＤＥＷＳ２００６）」のホームページ（ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／）において予稿集として発表（表題：「並列Ｂｔｒｅｅ構造Ｆａｔ−Ｂｔｒｅｅにおけるリクエスト委譲コストを削減する並行性制御手法」、掲載アドレス：ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／ｄｏｃ／７Ｃ−ｏ３．ｐｄｆ） ｉｉ）社団法人電子情報通信学会が２００６年３月３日に開催した「第１７回データ工学ワークショップ（ＤＥＷＳ２００６）」において発表 ｉｉｉ）２００６年６月３０日に社団法人電子情報通信学会の「第１７回データ工学ワークショップ（ＤＥＷＳ２００６）」のホームページ（ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／）において論文集として発表（表題：「並列Ｂｔｒｅｅ構造Ｆａｔ−Ｂｔｒｅｅにおけるリクエスト委譲コストを削減する並行性制御手法」、掲載アドレス：ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／ｄｏｃ／７Ｃ−ｏ３．ｐｄｆ） （２）ｉ）社団法人電子情報通信学会から２００６年７月７日に発行された「電子情報通信学会技術研究報告（ＩＳＳＮ ０９１３−５６８５ 信学技報Ｖｏｌ．１０６ Ｎｏ．１５０）」において発表 ｉｉ）社団法人電子情報通信学会が２００６年７月１４日に開催した「電子情報通信学会技術研究報告（データ工学）」において発表 （３）ｉ）社団法人情報処理学会から２００６年７月１３日〜１４日に発行された「情報処理学会研究報告（ＩＳＳＮ ０９１９−６０７２情処研報Ｖｏｌ．２００６，Ｎｏ．７８）」において発表 ｉｉ）社団法人情報処理学会が２００６年７月１４日に開催した「夏のデータベースワークショップ２００６（ＤＢＷＳ２００６）」において発表
【出願人】（３０４０２１４１７）国立大学法人東京工業大学 (1,821)
【出願人】（０００００４３５２）日本放送協会 (2,206)
【Ｆターム（参考）】
【公開日】平成２０年２月２８日（２００８．２．２８）
【国際特許分類】
【出願日】平成１８年８月１１日（２００６．８．１１）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り （１）ｉ）２００６年２月２４日に社団法人電子情報通信学会の「第１７回データ工学ワークショップ（ＤＥＷＳ２００６）」のホームページ（ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／）において予稿集として発表（表題：「並列Ｂｔｒｅｅ構造Ｆａｔ−Ｂｔｒｅｅにおけるリクエスト委譲コストを削減する並行性制御手法」、掲載アドレス：ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／ｄｏｃ／７Ｃ−ｏ３．ｐｄｆ） ｉｉ）社団法人電子情報通信学会が２００６年３月３日に開催した「第１７回データ工学ワークショップ（ＤＥＷＳ２００６）」において発表 ｉｉｉ）２００６年６月３０日に社団法人電子情報通信学会の「第１７回データ工学ワークショップ（ＤＥＷＳ２００６）」のホームページ（ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／）において論文集として発表（表題：「並列Ｂｔｒｅｅ構造Ｆａｔ−Ｂｔｒｅｅにおけるリクエスト委譲コストを削減する並行性制御手法」、掲載アドレス：ｈｔｔｐ：／／ｗｗｗ．ｉｅｉｃｅ．ｏｒｇ／ｉｓｓ／ｄｅ／ＤＥＷＳ／ＤＥＷＳ２００６／ｄｏｃ／７Ｃ−ｏ３．ｐｄｆ） （２）ｉ）社団法人電子情報通信学会から２００６年７月７日に発行された「電子情報通信学会技術研究報告（ＩＳＳＮ ０９１３−５６８５ 信学技報Ｖｏｌ．１０６ Ｎｏ．１５０）」において発表 ｉｉ）社団法人電子情報通信学会が２００６年７月１４日に開催した「電子情報通信学会技術研究報告（データ工学）」において発表 （３）ｉ）社団法人情報処理学会から２００６年７月１３日〜１４日に発行された「情報処理学会研究報告（ＩＳＳＮ ０９１９−６０７２情処研報Ｖｏｌ．２００６，Ｎｏ．７８）」において発表 ｉｉ）社団法人情報処理学会が２００６年７月１４日に開催した「夏のデータベースワークショップ２００６（ＤＢＷＳ２００６）」において発表
【出願人】（３０４０２１４１７）国立大学法人東京工業大学 (1,821)
【出願人】（０００００４３５２）日本放送協会 (2,206)
【Ｆターム（参考）】
[ Back to top ]