ディレクトリ更新方法及びディレクトリ更新プログラム、並びに、木構造型データ記憶装置
【課題】 Ｆａｔ−Ｂｔｒｅｅ構造におけるデータ更新時に、効率的に木構造の更新を行うディレクトリ分散型記憶装置を提供する。
【解決手段】 ディレクトリ分散型記憶装置１は、エントリ数が予め定めた制限未満である最も下位のノードを探索する第１フェーズ実行手段６３１と、そのノード以下のノードに対して排他ラッチを設定し、葉ノード３１の更新に伴い分割対象となる親ノードに排他ラッチが設定されている場合に葉ノード３１を更新し、分割対象となる親ノードに排他ラッチが設定されていない場合に排他ラッチの範囲を拡大する第２フェーズ実行手段６３２とを備えることを特徴とする。
【解決手段】 ディレクトリ分散型記憶装置１は、エントリ数が予め定めた制限未満である最も下位のノードを探索する第１フェーズ実行手段６３１と、そのノード以下のノードに対して排他ラッチを設定し、葉ノード３１の更新に伴い分割対象となる親ノードに排他ラッチが設定されている場合に葉ノード３１を更新し、分割対象となる親ノードに排他ラッチが設定されていない場合に排他ラッチの範囲を拡大する第２フェーズ実行手段６３２とを備えることを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新を効率的に行うディレクトリ更新方法及びディレクトリ更新プログラム、並びに、木構造型データ記憶装置に関する。
【背景技術】
【０００２】
近年、並列に配置された計算機（ＰＥ：Processing Element）上にデータベース等のデータを分散して記憶することで、データにアクセスする際の負荷分散と並行性動作とを実現したシステムが存在する。
このようなシステムにおいては、アクセス集中による負荷の偏りが存在する場合、その負荷の大きいＰＥがボトルネックとなり、システム全体の処理能力が低下してしまう。そこで、各ＰＥに負荷を均等に分配するためのディレクトリ構造と、そのディレクトリ構造における並行性制御とが提案されている（例えば、非特許文献１参照）。
ここで、図１３を参照して、従来の並列計算機におけるディレクトリ構造について、その概要を説明する。図１３は、従来の並列計算機におけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造を示す図である。
【０００３】
（Ｆａｔ−Ｂｔｒｅｅ構造）
図１３に示すように、Ｆａｔ−Ｂｔｒｅｅ構造は、データを示す葉ノードＮｌを各計算機ＰＥに均等に分配している。また、Ｆａｔ−Ｂｔｒｅｅ構造は、葉ノードＮｌ以外のインデックスを示すインデックスノードＮｉとして、各計算機ＰＥに配置されている葉ノードＮｌへのアクセスパスとなるインデックスノードＮｉのみを各計算機ＰＥに分配している。
なお、各インデックスノードＮｉに登録（エントリ）される下位層のインデックスノードの数と、葉ノードＮｌに登録されるデータ（データページ）の数とは、予め定められた数に制限されている。この制限された数を超過する場合は、各ノードは分割され、木構造が更新（ＳＭＯ：Structure Modification Operation）されることになる。これによって、あるアクセスパスに対して負荷が集中することを回避している。
【０００４】
このように、葉ノードＮｌ及びインデックスノードＮｉを分配することで、各計算機ＰＥの記憶部に記憶されるのは、全体の木構造に対して、ルートノードＮｉRから、均等に分配された葉ノードＮｌまでの部分木となる。すなわち、計算機ＰＥ1には部分木Ｒ1が、計算機ＰＥ2には部分木Ｒ2が、計算機ＰＥ3には部分木Ｒ3が、計算機ＰＥ4には部分木Ｒ4がそれぞれ記憶されることになる。
これによって、各計算機ＰＥに対するアクセスの分散が行われる。また、各計算機ＰＥでは、記憶している葉ノードＮｌの探索に必要のないインデックスノードＮｉを保持していないため、高速に葉ノードＮｌにアクセスすることができる。
【０００５】
（並行性制御）
次に、従来の並列計算機における並行性制御について説明する。図１３で説明したＦａｔ−Ｂｔｒｅｅ構造では、木構造の一貫性を保証するため、並行性制御が必須である。この並行性制御においては、アクセスパスに対して、他のプロセスからのアクセスを制御するロックが用いられる。このロックには、以下の表１に示す５種類（ＩＳ，ＩＸ，Ｓ，ＳＩＸ，Ｘ）のモードがある。
【０００６】
【表１】
【０００７】
表１中、“○”印は、同時に複数のロックを設定できることを示している。
なお、以下では、ＩＳ、ＩＸ、Ｓ、ＳＩＸ及びＸの各モードのロックをそれぞれ、ＩＳロック（インテント共有ロック）、ＩＸロック（インテント排他ロック）、Ｓロック（共有ロック）、ＳＩＸロック（インテント排他付き共有ロック）及びＸロック（排他ロック）と呼ぶ。
ここで、ＩＳロック（インテント共有ロック）は、下位層の一部のリソースにＳロックを設定し、そのリソースを読み取るプロセスの意思を示すものである。また、ＩＸロック（インテント排他ロック）は、下位層の一部のリソースにＸロックを設定し、そのリソースを変更するプロセスの意思を示すものである。また、Ｓロック（共有ロック）は、リソースを読み取り専用とする旨を示すものである。また、ＳＩＸロック（インテント排他付き共有ロック）は、リソースの同時読み取りを許可し、下位層のリソースにＩＸロックを設定し、プロセスがそのリソースを変更する意図を示すものである。さらに、Ｘロック（排他ロック）は、他のプロセスからの読み取り、変更を禁止する旨を示すものである。
【０００８】
ただし、一般には、これらのロックには、デッドロック検出機能を持たない高速かつ単純なラッチが用いられる。このラッチは、セマフォの一種であって、以下、前記した各ロックをラッチにより実現した場合を、特に、ＩＳラッチ（インテント共有ラッチ）、ＩＸラッチ（インテント排他ラッチ）、Ｓラッチ（共有ラッチ）、ＳＩＸラッチ（インテント排他付き共有ラッチ）、及び、Ｘラッチ（排他ラッチ）と呼ぶ。
【０００９】
次に、図１３を参照して、前記した表１の５種類のロック（ラッチ）を用いた、並行性制御方式の一例であるＩＮＣ−ＯＰＴ（INCremental OPTimistic）方式について説明する。
（ＩＮＣ−ＯＰＴ方式の参照時のプロトコル）
まず、ＩＮＣ−ＯＰＴ方式におけるデータの参照時のプロトコルについて説明する。ＩＮＣ−ＯＰＴ方式における、データである葉ノードＮｌの検索は、以下の〔Ｒ−１〕〜〔Ｒ−３〕の手順により行われる。
〔Ｒ−１〕ルートノードＮｉRにＩＳラッチを設定する。
〔Ｒ−２〕上位層のノード（親ノード）に設定されて下位層のノード（子ノード）のポインタを取得し、子ノードにラッチ（ＩＳラッチ）を設定し、親ノードのラッチを解放する動作を葉ノードＮｌまで繰り返す（以下、この動作をラッチカップリングという）。
〔Ｒ−３〕葉ノードＮｌにＳラッチを設定する。
これによって、葉ノードＮｌを読み出す（参照する）ことが可能になる。
【００１０】
（ＩＮＣ−ＯＰＴ方式の更新時のプロトコル）
次に、ＩＮＣ−ＯＰＴ方式におけるデータの更新時のプロトコルについて説明する。ＩＮＣ−ＯＰＴ方式における、葉ノードＮｌの更新は、以下の〔Ｗ−１〕、〔Ｗ−２〕の２つのフェーズで行われる。
〔Ｗ−１（第１フェーズ）〕ルートノードＮｉRから葉ノードＮｌまで、ＩＸラッチカップリングによりＩＸラッチを設定し、最下層の葉ノードＮｌにＸラッチを設定する。ここで、葉ノードＮｌを更新する際に、予め定められたデータ（データページ）の数を超過することで、木構造に変化（ＳＭＯ）が発生する場合は、葉ノードＮｌのＸラッチを解放し、第２フェーズに移行する。なお、ＳＭＯが発生しない場合は、そのまま葉ノードＮｌを更新し動作を終了する。
〔Ｗ−２（第２フェーズ）〕葉ノードＮｌとその親ノードに対してＸラッチを設定する。もし、葉ノードＮｌを分割することで、親ノードもエントリ数の制限を超過する場合は、さらに上位（親）のノードにＸラッチの範囲を拡大していく。そして、親ノードの分割が必要でなくなった段階で、葉ノードＮｌの更新（ＳＭＯを含む）を行う。
以上の動作によって、ＩＮＣ−ＯＰＴ方式は、Ｆａｔ−Ｂｔｒｅｅ構造を維持したまま、データ（葉ノード）の参照、更新が可能になる。
【非特許文献１】宮崎純，横田治夫，「並列ディレクトリ構造Ｆａｔ−Ｂｔｒｅｅの並行性制御とその評価」，情報処理学会研究会報告，データベースシステムＤＢＳ−１２４−６９，ｐｐ．３７−４４，情報処理学会，Ｊｕｌ．２００１
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかし、前記したＩＮＣ−ＯＰＴ方式では、データの更新時のプロトコルにおいて、ＳＭＯが発生する場合、第２フェーズを処理するための動作（リスタート）を複数回行う必要がある。例えば、ルートノードまで更新が及ぶ場合、木構造の木の高さと同じフェーズ数分のリスタートが必要となり、あるプロセスからの更新命令に対する応答時間を増加させてしまうという問題がある。
さらに、上位層において、複数回Ｘラッチを設定することになり、他のプロセスからの読み取り、変更を禁止する期間が増大し、システム全体のスループットが低下してしまうという問題がある。
【００１２】
本発明は、以上のような問題点に鑑みてなされたものであり、従来のＩＮＣ−ＯＰＴ方式に比べて、リスタート回数を少なく抑え、ＳＭＯに要するＸラッチの獲得時間を短くするディレクトリ更新方法及びディレクトリ更新プログラム、並びに、木構造型データ記憶装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載のディレクトリ更新方法は、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、第１フェーズ実行ステップと、第２フェーズ実行ステップとを含む手順とした。
【００１４】
この手順において、ディレクトリ更新方法は、第１フェーズ実行ステップとして、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、エントリ数が予め定めた制限未満（非フルエントリ）である最も下位のノード（非フルエントリノード）を探索する。そして、ディレクトリ更新方法は、葉ノードに対して、他のプロセスからの読み取り、変更を禁止する排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合には、その葉ノードを更新する。一方、ディレクトリ更新方法は、エントリ数が予め定めた制限を超過する場合には、葉ノードを更新（分割）することで、その親ノードのエントリ数に影響を及ぼすことになるため、ここでは一旦葉ノードの排他ロックを解放し、次の第２フェーズ実行ステップに移行する。
【００１５】
そして、ディレクトリ更新方法は、第２フェーズ実行ステップとして、第１フェーズ実行ステップで探索された非フルエントリノード以下のノードに対してＸロック（排他ロック）を設定する。そして、ディレクトリ更新方法は、葉ノードの更新に伴い分割対象となる親ノードにＸロックが設定されている場合に、葉ノードを更新し、その葉ノードの更新により分割対象となる親ノードにＸロックが設定されていない場合に、非フルエントリノードよりもさらに上位の非フルエントリノードを探索し、その探索された非フルエントリノードより下位のノードに排他ロックの範囲を拡大する。これによって、ディレクトリ更新方法は、動作をリスタートさせて第２フェーズ実行ステップに移行した場合に、非フルエントリノード以下のノードに対して一度にＸロックを設定するため、葉ノードから順次上位のノードにＸロックを設定する場合に比べ、第２フェーズ実行ステップをリスタートする回数を減らすことができる。
なお、ここで、排他ロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ）を用いることが望ましい。
【００１６】
また、請求項２に記載のディレクトリ更新方法は、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行ステップと、前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行ステップとを含むこととした。
さらに、第２フェーズ実行ステップが、排他ロック設定ステップと、排他ロック有効判定ステップと、ノード更新ステップとをさらに含み、前記排他ロック有効判定ステップで木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２フェーズ実行ステップを繰り返す手順とした。
【００１７】
この手順によれば、ディレクトリ更新方法は、第１フェーズ実行ステップで、ルートノードから更新対象となる葉ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索する。このように、ＩＸロックを順次設定することで、他のプロセスが葉ノードに対してＸロックを設定することを防止し、当該プロセスが確実に葉ノードに対してＸロックを設定することが可能になる。
なお、ディレクトリ更新方法は、第１フェーズ実行ステップで、第１の非フルエントリノードを探索するとともに、葉ノードに対して排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合に葉ノードの更新を行い、エントリ数が予め定めた制限を超過する場合に葉ノードの更新を行わずに排他ロックを解放する。これによって、葉ノードのエントリ数が予め定めた制限未満である場合には、第１フェーズ実行ステップで動作が終了することになる。
【００１８】
そして、ディレクトリ更新方法は、第２フェーズ実行ステップで、ルートノードから第１の非フルエントリノードの親ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する。
さらに、ディレクトリ更新方法は、第２フェーズ実行ステップにおいて、第２の非フルエントリノードの探索と並行し、排他ロック設定ステップで、第１の非フルエントリノードから葉ノードまでの経路において、各ノードにＸロック（排他ロック）を設定する。そして、排他ロック有効判定ステップで、排他ロック設定ステップで設定したＸロックが、葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する。すなわち、葉ノードを分割することで影響を受ける親ノードに対してＸロックが設定されているかどうかを判定する。
【００１９】
そして、木構造の更新に関連するノードに対してＸロックが設定されていると判定された場合、ディレクトリ更新方法は、ノード更新ステップで葉ノードの更新を行う。一方、木構造の変化に関連するノードに対してＸロックが設定されていないと判定された場合、ディレクトリ更新方法は、第２の非フルエントリノードを第１の非フルエントリノードとして、第２フェーズ実行ステップを繰り返す。
これによって、ディレクトリ更新方法は、動作をリスタートさせて第２フェーズ実行ステップに移行した場合に、非フルエントリノードより下位のノードに対して一度にＸロックを設定するため、葉ノードから順次上位のノードにＸロックを設定する場合に比べ、第２フェーズ実行ステップをリスタートする回数を減らすことができる。
なお、ここで、排他ロック及びインテント排他ロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ及びインテント排他ラッチ）を用いることが望ましい。
【００２０】
さらに、請求項３に記載のディレクトリ更新プログラムは、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴うディレクトリの更新を行うために、コンピュータを、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段、前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段として機能させる構成とした。
さらに、第２フェーズ実行手段が、排他ロック設定手段と、排他ロック有効判定手段と、ノード更新手段と、ノード再設定手段とを備える構成とした。
【００２１】
かかる構成によれば、ディレクトリ更新プログラムは、第１フェーズ実行手段によって、ルートノードから更新対象となる葉ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索する。
なお、ディレクトリ更新プログラムは、第１フェーズ実行手段で、第１の非フルエントリノードを探索するとともに、葉ノードに対して排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合に葉ノードの更新を行い、エントリ数が予め定めた制限を超過する場合に葉ノードの更新を行わずに排他ロックを解放する。
【００２２】
そして、ディレクトリ更新プログラムは、第２フェーズ実行手段によって、ルートノードから第１の非フルエントリノードの親ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する。
さらに、ディレクトリ更新プログラムは、排他ロック設定手段によって、第１の非フルエントリノードから葉ノードまでの経路において、各ノードにＸロックを設定し、排他ロック有効判定手段によって、排他ロック設定手段で設定したＸロックが、葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する。
【００２３】
そして、木構造の変化に関連するノードに対してＸロックが設定されていると判定された場合、ディレクトリ更新プログラムは、ノード更新手段によって、葉ノードの更新を行う。
一方、木構造の変化に関連するノードに対してＸロックが設定されていないと判定された場合、ディレクトリ更新プログラムは、ノード再設定手段によって、第２の非フルエントリノードを第１の非フルエントリノードとして設定する。これによって、Ｘロックの範囲が拡大されることになる。
なお、ここで、排他ロック及びインテント排他ロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ及びインテント排他ラッチ）を用いることが望ましい。
【００２４】
また、請求項４に記載の木構造型データ記憶装置は、木構造における各ノードのエントリ数を制限したディレクトリ構造によって、データを記憶する木構造型データ記憶装置において、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段と、前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段とを備える構成とした。
さらに、第２フェーズ実行手段が、排他ロック設定手段と、排他ロック有効判定手段と、ノード更新手段と、ノード再設定手段とを備える構成とした。
【００２５】
かかる構成によれば、木構造型データ記憶装置は、第１フェーズ実行手段によって、ルートノードから更新対象となる葉ノードまでの経路において、Ｘロックを設定する旨を示すＩＸロックを下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索する。
なお、木構造型データ記憶装置は、第１フェーズ実行手段で、第１の非フルエントリノードを探索するとともに、葉ノードに対して排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合に葉ノードの更新を行い、エントリ数が予め定めた制限を超過する場合に葉ノードの更新を行わずに排他ロックを解放する。
【００２６】
そして、木構造型データ記憶装置は、第２フェーズ実行手段によって、ルートノードから第１の非フルエントリノードの親ノードまでの経路において、Ｘロックを設定する旨を示すＩＸロックを下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する。
さらに、木構造型データ記憶装置は、排他ロック設定手段によって、第１の非フルエントリノードから葉ノードまでの経路において、各ノードにＸロックを設定し、排他ロック有効判定手段によって、排他ロック設定手段で設定したＸロックが、葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する。
そして、木構造の変化に関連するノードに対してＸロックが設定されていると判定された場合、ディレクトリ分散型記憶装置は、ノード更新手段によって、葉ノードの更新を行う。
一方、木構造の変化に関連するノードに対してＸロックが設定されていないと判定された場合、木構造型データ記憶装置は、ノード再設定手段によって、第２の非フルエントリノードを第１の非フルエントリノードとして設定する。
なお、ここで、Ｘロック（排他ロック）及びＩＸロック（インテント排他ロック）には、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ及びインテント排他ラッチ）を用いることが望ましい。
【発明の効果】
【００２７】
本発明によれば、更新対象となる葉ノードを更新することでディレクトリ構造の木構造に変化が発生する場合、葉ノードから順次親ノードに排他ロック（排他ラッチ）を設定する手順を行わず、エントリ数が予め定めた制限未満である最も下位のノード以降に対して排他ロック（排他ラッチ）を設定する。これによって、葉ノードから順次排他ロック（排他ラッチ）の範囲を拡大させるＩＮＣ−ＯＰＴ方式に比べ、リスタートの回数を減らすことができ、ディレクトリ構造の変更に伴う時間を減らすことができる。
【００２８】
さらに、本発明によれば、リスタート回数を減らすことで、排他ロック（排他ラッチ）を設定している時間を減らすことができるため、他のプロセスからの葉ノードに対するアクセスに対する応答性を高めることができる。また、ディレクトリ構造を分散して記憶するシステムの場合、システム全体のスループットを改善することができる。
【発明を実施するための最良の形態】
【００２９】
［ディレクトリ分散型記憶装置（木構造型データ記憶装置）の構成］
まず、図１を参照して、ディレクトリ分散型記憶装置の構成について説明する。図１は、本発明に係る木構造型データ記憶装置の最良の形態であるディレクトリ分散型記憶装置の構成を示すブロック図である。
図１に示したディレクトリ分散型記憶装置１は、ネットワークＮに接続された他のディレクトリ分散型記憶装置（図示せず）と協働し、データベース等のデータを分散して記憶するものである。このディレクトリ分散型記憶装置１は、図１３で説明したＦａｔ−Ｂｔｒｅｅ構造のディレクトリ構造によってデータを記憶管理する計算機ＰＥに相当する。
ここでは、ディレクトリ分散型記憶装置１は、通信制御部２と、記憶部３と、制御部４とを備えている。また、ここでは、ロック制御として、デッドロック検出機能を持たないラッチを用いることとする。
【００３０】
通信制御部２は、ネットワークＮを介して、クライアントコンピュータ（図示せず）や他のディレクトリ分散型記憶装置（図示せず）と、データや制御情報（ノード情報を含む）の送受信を行うものである。例えば、通信制御部２は、ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）の通信プロトコルによってデータ等の送受信を行う通信ボードである。
【００３１】
記憶部３は、データベース等のデータや、ディレクトリ構造を特定するノード情報等を記憶しておくもので、一般的なハードディスク等の記憶装置である。この記憶部３には、データ３１と、ノード情報３２と、エントリ制限情報３３とを記憶している。
【００３２】
データ３１は、Ｆａｔ−Ｂｔｒｅｅ構造における葉ノードであって、データの実体である。このデータ３１は、記憶領域の予め定められたページ単位で管理され、所定のページ数（後記するエントリ制限情報３３に含まれる）を超過する場合は分割される。
【００３３】
ノード情報３２は、Ｆａｔ−Ｂｔｒｅｅ構造のデータ構造を示す情報である。ここでは、ノード情報３２は、Ｆａｔ−Ｂｔｒｅｅ構造のルートノードから、この記憶部３に記憶されているデータ（葉ノード）３１までのアクセスパスを示している。
さらに、ノード情報３２は、各ノードにどのプロセスから、どのロック（ラッチ）が設定されているかを示す情報を含んでいる。
【００３４】
エントリ制限情報３３は、Ｆａｔ−Ｂｔｒｅｅ構造において、ノードに登録される子ノードの数の最大値や、葉ノードとして登録できるデータ（データページ）の数の最大値を示している。このエントリ制限情報３３は、後記する制御部４によって参照され、データの更新に伴う木構造の変化（ＳＭＯ）が発生するか否かを判定するために用いられる。
【００３５】
制御部４は、ディレクトリ分散型記憶装置１全体の動作を制御するものであって、一般的なコンピュータにおけるＣＰＵ（Central Processing Unit：中央処理装置）に相当するものである。ここでは、制御部４は、データ操作手段５と、データ管理手段６と、制御情報送受信手段７とを備えている。
【００３６】
データ操作手段５は、通信制御部２を介して、データの送受信操作を行うものである。ここでは、データ操作手段５は、データ送受信手段５１と、データ参照手段５２と、データ更新手段５３とを備えている。
【００３７】
データ送受信手段５１は、データ管理手段６のデータ操作制御手段６１から制御情報として通知されるデータの送信元（例えば、クライアントコンピュータ等）から、通信制御部２を介してデータを受信したり、データ操作制御手段６１から制御情報として通知されるデータの送信先（例えば、クライアントコンピュータ等）に、通信制御部２を介してデータを送信したりするものである。
このデータ送受信手段５１は、データ参照手段５２から出力されるデータを、通信制御部２を介して送信し、通信制御部２を介して受信したデータをデータ更新手段５３に出力する。
【００３８】
データ参照手段５２は、記憶部３に記憶されているデータ３１を読み出すものである。このデータ参照手段５２は、データ管理手段６のデータ操作制御手段６１から通知される制御情報（記憶元のアドレス等）に基づいて、データ３１を記憶部３から読み出す。このデータ参照手段５２で読み出されたデータ３１は、データ送受信手段５１に出力される。
【００３９】
データ更新手段５３は、データ送受信手段５１で受信したデータを、記憶部３に書き込むものである。このデータ更新手段５３は、データ管理手段６のデータ操作制御手段６１から通知される制御情報（記憶先のアドレス等）に基づいて、データを記憶部３に書き込む。なお、データ更新手段５３は、データ操作制御手段６１から通知される制御情報（記憶先のアドレス等）に基づいて、指示されたデータ３１を記憶部３から削除する動作も行うものとする。
【００４０】
データ管理手段６は、記憶部３に記憶されているノード情報３２とエントリ制限情報３３とに基づいて、記憶部３に記憶されるデータ３１を階層構造で管理するものである。また、このデータ管理手段６は、Ｆａｔ−Ｂｔｒｅｅ構造（図１３参照）のディレクトリ構造によりデータ３１を管理するものとする。ここでは、データ管理手段６は、データ操作制御手段６１と、データ参照制御手段６２と、データ更新制御手段６３とを備えている。
【００４１】
データ操作制御手段６１は、図示していないクライアントコンピュータ等から送信される制御情報を、後記する制御情報送受信手段７を介して受信することで、その制御情報で示されるデータの操作を行うものでもある。
ここで、制御情報とは、データを制御する情報である。例えば、データを記憶する旨を示すデータ記憶指示、データを送信する旨を示すデータ送信指示、データを削除する旨を示すデータ削除指示等、あるいはこれらの指示に対する応答等である。
【００４２】
例えば、制御情報が、データを記憶する旨を示すデータ記憶指示である場合、データ操作制御手段６１は、その旨をデータ更新手段５３に通知する。また、制御情報が、データを送信する旨を示すデータ送信指示である場合、データ操作制御手段６１は、その旨をデータ参照手段５２に通知する。また、制御情報が、データを削除する旨を示すデータ削除指示である場合、データ操作制御手段６１は、その旨をデータ更新手段５３に通知する。また、データ操作制御手段６１は、これらの操作指示（データ記憶指示、データ送信指示、データ削除指示）の操作結果を制御情報送受信手段７に対して応答として出力する。
【００４３】
なお、データ操作制御手段６１は、データ操作が、データの参照を行うものである場合は、その旨を後記するデータ参照制御手段６２に通知し、他のプロセスに対する排他制御を行うものとする。また、データ操作制御手段６１は、データ操作が、データの更新を行うものである場合は、その旨を後記するデータ更新制御手段６３に通知し、他のプロセスに対する排他制御や、木構造の変更（ＳＭＯ）を行う。
【００４４】
データ参照制御手段６２は、データの読み出し等である参照系の操作において、他のプロセスに対する排他制御を行うものである。例えば、データ参照制御手段６２は、ルートノードにＩＳラッチ（表１参照）を設定し、親ノードに設定されている子ノードのポインタを取得し、子ノードにラッチ（ＩＳラッチ）を設定し、親ノードのラッチを解放する動作をデータ（葉ノード）３１まで繰り返す。そして、データ（葉ノード）３１にＳラッチを（表１参照）設定することで、データ（葉ノード）３１の参照（読み出し）を可能にする。
【００４５】
データ更新制御手段６３は、データの追加、更新等の更新系の操作において、他のプロセスに対する排他制御や、木構造の変更（ＳＭＯ）を行うものである。ここでは、データ更新制御手段６３は、第１フェーズ実行手段６３１と、第２フェーズ実行手段６３２とを備えている。
【００４６】
第１フェーズ実行手段６３１は、第１フェーズとして、エントリ数が予め定めた制限未満である最も下位のノード（第１の非フルエントリノード）を探索するとともに、データ（葉ノード）３１の更新を行うものである。ここでは、第１フェーズ実行手段６３１は、第１非フルエントリノード探索手段６３１ａと、葉ノードラッチ設定手段６３１ｂと、ノード更新手段６３１ｃとを備えている。
【００４７】
第１非フルエントリノード探索手段６３１ａは、ルートノードから更新対象となるデータ（葉ノード）３１までの経路において、Ｘラッチ（排他ラッチ：表１参照）を設定する旨を示すＩＸラッチ（インテント排他ラッチ：表１参照）を下位層に対して設定し、その上位層に対するＩＸラッチの設定を解放する手順を下位層に向かって繰り返すラッチカップリングを行いながら、エントリ数が予め定めた制限未満である最も下位のノード（第１の非フルエントリノード）を探索するものである。ここでは、第１非フルエントリノード探索手段６３１ａは、ＳＭＯが発生しない最下層のノードをルートノードから順次探索し、そのノードのルートノードからの木の高さを保持しておく。
【００４８】
葉ノードラッチ設定手段６３１ｂは、更新対象となるデータ（葉ノード）３１に対してＸラッチを設定するものである。これによって、他のプロセスに対して、更新対象となるデータ（葉ノード）３１の読み取り、変更を禁止することができる。
【００４９】
ノード更新手段６３１ｃは、葉ノードラッチ設定手段６３１ｂによってＸラッチが設定された、更新対象となるデータ（葉ノード）３１を更新するものである。なお、ノード更新手段６３１ｃは、記憶部３のノード情報３２とエントリ制限情報３３とを参照し、データ３１を追加、更新する際に、エントリ数が超過する場合に、データ（葉ノード）３１の分割や、その親ノードの分割といった木構造に変化を及ぼす操作（ＳＭＯ）が発生する場合は、データ（葉ノード）３１を更新せず、データ３１に対するＸラッチを解放する。そして、第２フェーズ実行手段６３２に、第１非フルエントリノード探索手段６３１ａで探索された第１の非フルエントリノードの位置（その親ノードのルートノードからの木の高さ）を通知する。
このように、第１フェーズ実行手段６３１は、ＳＭＯが発生しない場合は、第１フェーズ実行手段６３１でデータ（葉ノード）３１の更新を完了するが、ＳＭＯが発生する場合は、第２フェーズ実行手段６３２に処理を移行する。
【００５０】
第２フェーズ実行手段６３２は、第２フェーズとして、第１フェーズ実行手段６３１で探索された第１の非フルエントリノードより上位のノードで、エントリ数が予め定めた制限未満である最も下位のノード（第２の非フルエントリノード）を探索するとともに、データ（葉ノード）３１の更新を行うものである。ここでは、第２フェーズ実行手段６３２は、第２非フルエントリノード探索手段６３２ａと、子ノードラッチ設定手段６３２ｂと、ラッチ有効判定手段６３２ｃと、ノード更新手段６３２ｄと、ノード再設定手段６３２ｅとを備えている。
【００５１】
第２非フルエントリノード探索手段６３２ａは、ルートノードから、第１の非フルエントリノードの親ノードまでの経路において、ＩＸラッチカップリングを行いながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索するものである。
【００５２】
子ノードラッチ設定手段（排他ロック設定手段）６３２ｂは、第２非フルエントリノード探索手段６３２ａで探索された第２の非フルエントリノードより下位層の子ノード（葉ノードを含む）に対して、Ｘラッチを設定するものである。
【００５３】
ラッチ有効判定手段（排他ロック有効判定手段）６３２ｃは、子ノードラッチ設定手段６３２ｂで設定したＸラッチが、データ（葉ノード）３１の更新に伴う木構造の変化（ＳＭＯ）に関連するノードに対して設定されているかどうかを判定するものである。すなわち、このラッチ有効判定手段６３２ｃは、ノードの分割が発生するすべてのノードにＸラッチが設定されており、かつ、その親ノードにＸラッチが設定されているかどうかを判定する。このように、ノードの分割が発生するすべてのノードと、その親ノードにＸラッチが設定されていれば、他のプロセスからの影響を受けることなく、木構造の変更が可能になる。
【００５４】
ノード更新手段６３２ｄは、ラッチ有効判定手段６３２ｃで木構造の変化に関連するノードに対してＸラッチが設定されていると判定された場合に、データ（葉ノード）３１の更新を行うものである。すなわち、このノード更新手段６３２ｄは、データ（葉ノード）３１の更新を行う際に、データ３１の分割を行う。また、その親ノード（インデックスノード）で分割が必要な場合は、順次上位の親ノードに遡って分割を行う。これによって、データ（葉ノード）３１に対するアクセスの均等化が図られることになる。
【００５５】
ノード再設定手段６３２ｅは、ラッチ有効判定手段６３２ｃで木構造の変化に関連するノードに対してＸラッチが設定されていないと判定された場合に、第２の非フルエントリノードを第１の非フルエントリノードとして再設定するものである。すなわち、第２の非フルエントリノードのルートノードからの木の高さを保持し直す。なお、このとき、ノード再設定手段６３２ｅは、すべてのＸラッチを解放する。
そして、ノード再設定手段６３２ｅは、第２非フルエントリノード探索手段６３２ａに制御を移行させる。
【００５６】
このように、データ更新制御手段６３を構成することで、データ更新制御手段６３は、データ（葉ノード）３１の更新を、以下の〔第１フェーズ〕、〔第２フェーズ〕の２つのフェーズで行うことになる。
【００５７】
〔第１フェーズ〕ルートノードから葉ノードまで、ＩＸラッチカップリングによりＩＸラッチを設定し、最下層の葉ノードにＸラッチを設定する。また、フルエントリでないインデックスノード（第１の非フルエントリノード）が存在したら、そのノードの位置（ルートノードからの高さ）を保持（マーク）する。マークするノードの位置は、非フルエントリノードが存在する度に逐次更新される。もし、ＳＭＯが発生しない場合は、葉ノードを更新して終了する。もし、ＳＭＯが発生する場合は、葉ノードのＸラッチを解放し、第２フェーズに移行する。
【００５８】
〔第２フェーズ〕ルートノードから、第１フェーズでマークした第１の非フルエントリノードの親ノードまで、順次ＩＸラッチカップリングによりＩＸラッチを設定し、第１の非フルエントリノード以下のノードにＸラッチを設定する。もし、設定したＸラッチの範囲が、ＳＭＯを行うために十分な範囲に設定されていなければ、マークの位置によるＸラッチの範囲を変化させ、ＳＭＯを行うために十分な範囲となった段階で、葉ノードを更新して終了する。
なお、本方式は、第１フェーズにおいて、フルエントリでないインデックスノード（第１の非フルエントリノード）の位置（ルートノードからの高さ）を保持（マーク）しておくため、ＭＡＲＫ−ＯＰＴ（MARKing OPTimistic）方式と呼ぶこととする。
【００５９】
制御情報送受信手段７は、通信制御部２を介して、図示していないクライアントコンピュータ等と制御情報の送受信を行うものである。ここでは、制御情報送受信手段７は、クライアントコンピュータ等から受信した制御情報をデータ操作制御手段６１に出力し、データ操作制御手段６１から出力された制御信号をクライアントコンピュータ等に送信する。
【００６０】
以上、説明したように、ディレクトリ分散型記憶装置１を構成することで、第２フェーズでは、第１フェーズでマークした第１の非フルエントリノードの親ノードまでＩＸラッチカップリングを行い、第１の非フルエントリノード以下のノードにＸラッチを設定するため、Ｘラッチの範囲を葉ノードから順次拡げていく従来のＩＮＣ−ＯＰＴ方式に比べて、リスタートを行う回数を減らすことができる。
また、ここでは、ディレクトリ（ノード情報）とデータ（葉ノード）とを複数のディレクトリ分散型記憶装置で分散して記憶する形態としたが、本発明は、この形態に限定されるものではない。例えば、１つの記憶装置（木構造型データ記憶装置）のみに、すべてのノード情報と葉ノードとを記憶し、各ノードのエントリ数を制限したディレクトリ構造を形成している場合であっても、本発明に係るディレクトリ更新を行うことは可能である。この場合であっても、ＩＮＣ−ＯＰＴ方式に比べて、リスタートを行う回数を減らすことができ、ＳＭＯに要するＸラッチの獲得時間を短くすることができる。ただし、システム全体のスループットを向上させるには、複数の木構造型データ記憶装置（ディレクトリ分散型記憶装置）で、ディレクトリ（ノード情報）とデータ（葉ノード）とを分散するほうが望ましいと言える。
なお、ディレクトリ分散型記憶装置１の制御部４は、一般的なコンピュータにプログラムを実行させ、コンピュータ内の演算装置や記憶装置を動作させることにより実現することができる。ここで実現されるディレクトリの更新を行うディレクトリ更新プログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００６１】
［ディレクトリ分散型記憶装置の動作］
次に、図２及び図３を参照（適宜図１参照）して、ディレクトリ分散型記憶装置の動作について説明する。なお、ここでは、ディレクトリ分散型記憶装置１のデータ更新制御手段６３において行われる、本発明に係るディレクトリ更新方法（ＭＡＲＫ−ＯＰＴ方式）について、詳細に説明を行うことにする。図２は、ＭＡＲＫ−ＯＰＴ方式の第１フェーズの動作を示すフローチャートである。図３は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【００６２】
《ＭＡＲＫ−ＯＰＴ方式》
（第１フェーズ；第１フェーズ実行ステップ）
ディレクトリ分散型記憶装置１は、第１フェーズ実行手段６３１において、以下の手順で第１フェーズの動作（図２参照）を実行する。
まず、ディレクトリ分散型記憶装置１は、第１非フルエントリノード探索手段６３１ａによって、初期値として、エントリ数が制限を超過していないノードの階層番号を示す変数〔マーク用階層番号（ｎ）〕に、木構造の木の高さを示すツリー高“Ｈ”を設定する（ステップＳ１）。さらに、ディレクトリ分散型記憶装置１は、初期値として、親ノードを識別するための変数（Ｐａｒｅｎｔ）に“ｎｕｌｌ”、子ノードを識別するための変数（Ｃｈｉｌｄ）にルートノードを示す識別子“ＲＯＯＴ”を設定し、ループに使用するインデックス用階層番号（ｈ）と非フルエントリノードの位置を示すマーク値（ｍ）とにそれぞれ“１”を設定する（ステップＳ２）。
【００６３】
そして、ディレクトリ分散型記憶装置１は、インデックス用階層番号（ｈ）が、マーク用階層番号（ｎ）に達していないかどうかを判定し（ステップＳ３）、達した場合（ステップＳ３でＮｏ）、ステップＳ８に進む。
一方、インデックス用階層番号（ｈ）が、マーク用階層番号（ｎ）に達していない場合（ステップＳ３でＹｅｓ）、ディレクトリ分散型記憶装置１は、第１非フルエントリノード探索手段６３１ａによって、子ノード（Ｃｈｉｌｄ）にＩＸラッチを設定し、親ノード（Ｐａｒｅｎｔ）に設定されているラッチを解放する（ステップＳ４）。ただし、最初は親ノード（Ｐａｒｅｎｔ）には、ＩＸラッチが設定されていないため、ステップＳ４のラッチの解放は、ラッチが設定されている場合にのみなされる。
続けて、ディレクトリ分散型記憶装置１は、第１非フルエントリノード探索手段６３１ａによって、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ５）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ５でＹｅｓ）、ステップＳ７に進む。
【００６４】
一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ５でＮｏ）、マーク値（ｍ）に現在の階層番号であるインデックス用階層番号（ｈ）を設定し、非フルエントリノードの位置を保持（マーク）しておく（ステップＳ６）。
そして、ディレクトリ分散型記憶装置１は、現在の子ノード直下のノードを新しい子ノード（新子ノード）として決定し、親ノード（Ｐａｒｅｎｔ）に子ノード（Ｃｈｉｌｄ）、子ノード（Ｃｈｉｌｄ）に新子ノード（ＮｅｗＣｈｉｌｄ）を設定し直す。さらに、インデックス用階層番号（ｈ）に“１”を加算することで、１つ下の階層に制御対象を移動する（ステップＳ７）。そして、ステップＳ３に戻る。
【００６５】
このステップＳ３からステップＳ７までのループによって、ルートノードから、葉ノードの親ノードに対してＩＸラッチカップリングが行われることになる。
そして、ディレクトリ分散型記憶装置１は、葉ノードラッチ設定手段６３１ｂによって、子ノード（この段階では葉ノード）に対してＸラッチを設定し、その親ノードのラッチを解放する（ステップＳ８）。
【００６６】
ここで、ディレクトリ分散型記憶装置１は、ノード更新手段６３１ｃによって、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（葉ノード）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ９）。ここで、葉ノードがフルエントリでない場合（ステップＳ９でＮｏ）、ノード更新手段６３１ｃが葉ノードの更新操作を実行し（ステップＳ１０）、すべてのラッチを解放し（ステップＳ１１）、動作を終了する。
一方、葉ノードがフルエントリの場合（ステップＳ９でＹｅｓ）、ディレクトリ分散型記憶装置１は、すべてのラッチを解放し（ステップＳ１２）、マーク用階層番号（ｎ）に、マーク値（ｍ）を設定し（ステップＳ１３）、第２フェーズに移行する。
【００６７】
（第２フェーズ；第２フェーズ実行ステップ）
次に、ディレクトリ分散型記憶装置１は、第２フェーズ実行手段６３２において、以下の手順で第２フェーズの動作（図３参照）を実行する。
まず、ディレクトリ分散型記憶装置１は、第２非フルエントリノード探索手段６３２ａによって、ルートノードからマーク用階層番号（ｎ）で示される非フルエントリノードの親ノードまで、ＩＸラッチカップリングを行う（ステップＳ２０〜ステップＳ２５）。なお、このステップＳ２０〜ステップＳ２５までの動作は、図２で説明したステップＳ２〜ステップＳ７までの動作と同一であるため説明を省略する。
【００６８】
そして、ディレクトリ分散型記憶装置１は、ステップＳ２５（ステップＳ７）まででＩＸラッチカップリングされたノードの子ノード、すなわち、マーク用階層番号（ｎ）で示される非フルエントリノードと、そのコピー（複製）にＸラッチを設定し、親ノードのＩＸラッチを解放する（ステップＳ２６）。ここで、コピー（複製）とは、図１３で説明した計算機ＰＥ間で、同一のインデックスノードＮｉをコピーしてそれぞれのＰＥで保有している場合、そのＰＥ毎のインデックスノードＮｉを指す。
さらに、ディレクトリ分散型記憶装置１は、現在の子ノード直下のノードを新しい子ノード（新子ノード）として決定し、親ノード（Ｐａｒｅｎｔ）に子ノード（Ｃｈｉｌｄ）、子ノード（Ｃｈｉｌｄ）に新子ノード（ＮｅｗＣｈｉｌｄ）を設定し直す。さらに、インデックス用階層番号（ｈ）に“１”を加算することで、１つ下の階層に制御対象を移動する（ステップＳ２７）。
【００６９】
そして、ディレクトリ分散型記憶装置１は、インデックス用階層番号（ｈ）が、ツリー高“Ｈ”に達していないかどうかを判定し（ステップＳ２８）、達した場合（ステップＳ２８でＮｏ）は、ステップＳ３１に進む。
一方、インデックス用階層番号（ｈ）が、ツリー高“Ｈ”を超えていない場合（ステップＳ２８でＹｅｓ）、ディレクトリ分散型記憶装置１は、子ノードラッチ設定手段６３２ｂによって、子ノードとそのコピー（複製）にＸラッチを設定する（ステップＳ２９；排他ロック設定ステップ）。
続けて、ディレクトリ分散型記憶装置１は、子ノードラッチ設定手段６３２ｂによって、現在の子ノード直下のノードを新しい子ノード（新子ノード）として決定し、親ノード（Ｐａｒｅｎｔ）に子ノード（Ｃｈｉｌｄ）、子ノード（Ｃｈｉｌｄ）に新子ノード（ＮｅｗＣｈｉｌｄ）を設定し直す。さらに、インデックス用階層番号（ｈ）に“１”を加算することで、１つ下の階層に制御対象を移動する（ステップＳ３０）。そして、ステップＳ２８に戻る。
このステップＳ２８からステップＳ３０までのループによって、ステップＳ２７で設定された子ノード以下のノードにＸラッチが設定されることになる。
【００７０】
そして、ディレクトリ分散型記憶装置１は、ラッチ有効判定手段６３２ｃによって、Ｘラッチが、データ（葉ノード）３１の更新に伴う木構造の変化（ＳＭＯ）に関連するノードに対してなされているかどうかを判定する（ステップＳ３１；排他ロック有効判定ステップ）。ここで、ＸラッチがＳＭＯを行うためには不十分である場合（ステップＳ３１でＮｏ）、すべてのラッチを解放し（ステップＳ３２）、マーク用階層番号（ｎ）に、マーク値（ｍ）を設定し（ステップＳ３３；ノード再設定ステップ）、ステップＳ２０に戻る（リスタートする）。すなわち、Ｘラッチの範囲を拡げる動作を実行する。
一方、ＸラッチがＳＭＯを行うために十分な設定がなされている場合（ステップＳ３１でＹｅｓ）、ノード更新手段６３２ｄが葉ノード及びそれに関連するノードの更新操作（ＳＭＯ）を実行し（ステップＳ３４；ノード更新ステップ）、すべてのラッチを解放し（ステップＳ３５）、動作を終了する。
【００７１】
以上のＭＡＲＫ−ＯＰＴ方式による第１フェーズ（図２参照）及び第２フェーズ（図３参照）の動作によって、ディレクトリ分散型記憶装置１は、第１フェーズによってマークされたノードによって、Ｘラッチの設定範囲を定めることができ、葉ノードから順次Ｘラッチの範囲を拡大していくＩＮＣ−ＯＰＴ方式に比べ、第２フェーズを再実行するリスタートの回数を減らすことができる。
なお、ディレクトリ更新方法は、第１フェーズ及び第２フェーズで説明した各ステップにより、ディレクトリを更新する方法であって、ディレクトリ更新プログラムは、この第１フェーズ及び第２フェーズで説明した各ステップをコンピュータに実行させるためのプログラムである。
【００７２】
以上、本発明に係るディレクトリ分散型記憶装置１の動作として、ＭＡＲＫ−ＯＰＴ方式の動作について説明したが、本発明はこれに限定されるものではない。例えば、このＭＡＲＫ−ＯＰＴ方式は、他のプロセスの動作によって、途中で木構造に変化があった場合でも処理に変更はないが、その木構造の変化によって処理を変えることとしてもよい。以下、ＭＡＲＫ−ＯＰＴ方式を拡張したＩＮＣ−ＭＡＲＫ−ＯＰＴ方式、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式及び２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式について説明を行う。
【００７３】
《ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式》
まず、図４を参照して、ＩＮＣ−ＭＡＲＫ−ＯＰＴ（INCremental MARKing OPTimistic）方式について説明する。図４は、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。なお、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズは、図２で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７４】
このＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズにおいて、木の構造が変化したと判断された場合にリスタートを行う方式である。
図４に示すように、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズにおけるステップＳ２６とステップＳ２７の間に、ステップＳ２６１ａ〜ステップＳ２６１ｃを追加している。他のステップについては、図３で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７５】
すなわち、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、ステップＳ２６で親ノードのＩＸラッチを解放した段階で、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ２６１ａ）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ２６１ａでＹｅｓ）、すべてのラッチを解放し（ステップＳ２６１ｂ）、マーク用階層番号（ｎ）に、マーク値（ｍ）を設定し（ステップＳ２６１ｃ）、ステップＳ２０に戻る（リスタートする）。一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ２６１ａでＮｏ）は、ＭＡＲＫ−ＯＰＴ方式と同様にステップＳ２７以降の動作を実行する。
【００７６】
このように、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、木の構造が変化したと判断された段階で直ちにリスタートを行うため、ＳＭＯの範囲が拡大している場合には、ＭＡＲＫ−ＯＰＴ方式より不必要なＸラッチを減らすことができる。
【００７７】
《２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式》
次に、図５を参照して、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ（2-Phase INTegrated MARKing OPTimistic）方式について説明する。図５は、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。なお、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズは、図２で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７８】
この２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズにおいて、木の構造が変化したと判断された場合に、そのノード以下のノードに対してＩＸラッチカップリングを行う方式である。
図５に示すように、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズにおけるステップＳ２６とステップＳ２７の間に、ステップＳ２６１ａ及びステップＳ２６１ｄを追加している。他のステップについては、図３で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７９】
すなわち、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、ステップＳ２６で親ノードのＩＸラッチを解放した段階で、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ２６１ａ）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ２６１ａでＹｅｓ）、マーク用階層番号（ｎ）に、現在の階層番号であるインデックス用階層番号（ｈ）を設定し（ステップＳ２６１ｄ）、第１フェーズ（図２）のステップＳ７に戻る。一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ２６１ａでＮｏ）は、ＭＡＲＫ−ＯＰＴ方式と同様にステップＳ２７以降の動作を実行する。
【００８０】
このように、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、木の構造が変化したと判断されてもリスタートを行わず、第１フェーズに切り替えて処理を行う。これによって、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式よりもリスタート回数を少なくし、ＭＡＲＫ−ＯＰＴ方式より不必要なＸラッチを減らすことができる。
【００８１】
《２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式》
次に、図６を参照して、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ（2-Phase REPetitive MARKing OPTimistic）方式について説明する。図６は、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。なお、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズは、図２で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００８２】
この２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズにおいて、木の構造が変化したと判断された場合に、リスタートを行う方式である。なお、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式との違いは、リスタート後は第１フェーズに戻って処理を行うことである。
図６に示すように、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズにおけるステップＳ２６とステップＳ２７の間に、ステップＳ２６１ａ及びステップＳ２６１ｂを追加している。他のステップについては、図３で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００８３】
すなわち、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、ステップＳ２６で親ノードのＩＸラッチを解放した段階で、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ２６１ａ）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ２６１ａでＹｅｓ）、すべてのラッチを解放し（ステップＳ２６１ｂ）、第１フェーズ（図２）のステップＳ１に戻る。一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ２６１ａでＮｏ）は、ＭＡＲＫ−ＯＰＴ方式と同様にステップＳ２７以降の動作を実行する。
【００８４】
このように、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、木の構造が変化したと判断された段階で直ちにリスタートし、第１フェーズに戻って処理を行うため、リスタート回数は、ＭＡＲＫ−ＯＰＴ方式に比べて多くなるが、不必要なＸラッチの設定を最も少なくすることができる。
【００８５】
［ディレクトリ更新動作の具体例］
次に、ディレクトリ分散型記憶装置１（図１参照）におけるディレクトリ更新の動作について、具体例を示して説明する。ここでは、一例として、図７に示すようなディレクトリ更新が行われる例について説明する。図７（ａ）は、ディレクトリ更新前のディレクトリ構造を示し、図７（ｂ）は、データ追加に伴うディレクト更新後のディレクト構造を示している。
【００８６】
図７（ａ）に示すように、ディレクトリ更新前は、Ｄ1−Ｄ2−Ｄ3−Ｄ4−Ｄ5−Ｄ6の各ノードの階層によって、データ３１として葉ノードＤ6が記憶部３に記憶されている。なお、ここでは、インデックスノード及び葉ノードのエントリ数の最大値（制限値）を“３”とする。すなわち、インデックスノードＤ2、Ｄ5は、子ノードがフルエントリ状態であるフルエントリインデックスノードとなっており、葉ノードＤ6は、データがフルエントリ状態であるフルエントリ葉ノードとなっているものとする。
【００８７】
この図７（ａ）の状態において、葉ノードＤ6にデータを追加すると、図７（ｂ）に示すように、葉ノードＤ6は葉ノードＤ61、Ｄ62に分割され、その親ノードであるインデックスノードＤ5は、エントリ数の最大数を超過するため、インデックスノードＤ51、Ｄ52に分割されることになる。
この例に基づいて、前記したＭＡＲＫ−ＯＰＴ方式、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式及び２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の各方式の動作について具体的に説明する。
【００８８】
《ＭＡＲＫ−ＯＰＴ方式》
まず、図８及び図９を参照して、ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図８及び図９は、ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、図中変数「ｎ」、「ｈ」及び「ｍ」は、図２及び図３のフローチャートに用いたマーク用階層番号、インデックス用階層番号及びマーク値をそれぞれ示している。
【００８９】
図８（ａ）に示すように、ＭＡＲＫ−ＯＰＴ方式は、第１フェーズで、ＩＸラッチカップリングによって、状態Ｐ１から状態Ｐ９として、ルートノードＤ1から葉ノードＤ6の親ノード（インデックスノードＤ5）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ１において、マーク値（ｍ）に“１”を設定し、状態Ｐ５において、マーク値（ｍ）に“３”を設定し、状態Ｐ７において、マーク値（ｍ）に“４”を設定する。そして、状態Ｐ１０に示すように、葉ノードＤ6にＸラッチを設定し、状態Ｐ１１に示すように親ノードのＩＸラッチを解放する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ4及びＤ5にＸラッチの設定が必要）であるため、状態Ｐ１２に示すように葉ノードＤ6のＸラッチを解放し第２フェーズの動作（リスタート）を行う。
【００９０】
続けて、図８（ｂ）に示すように、ＭＡＲＫ−ＯＰＴ方式は、第２フェーズで、ＩＸラッチカップリングによって、状態Ｐ１３から状態Ｐ１７として、ルートノードＤ1から、第１フェーズでマークしたマーク値（ｍ：ここでは“４”）のノードの親ノード（インデックスノードＤ3）まで、順次ＩＸラッチを設定する。そして、親ノード（インデックスノードＤ3）以下の子ノードにＸラッチを設定する。そして、状態Ｐ２０に示すように、インデックスノードＤ4〜Ｄ6にＸラッチを設定した段階で、葉ノードＤ6の更新を行う。そして、葉ノードＤ6の更新（及びインデックスノードＤ5の分割）後、全ラッチを解放し動作を終了する。
なお、この図８（ｂ）は、処理中に上位ノードで更新操作（ＳＭＯ）が発生しなかった場合の動作を示している。この処理中に上位ノードで更新操作（ＳＭＯ）が発生した場合の動作については、図９を参照して説明を行う。
【００９１】
図９（ａ）は、上位ノードで更新操作（ＳＭＯ）が発生した場合におけるリスタートの１回目の動作を示し、図９（ｂ）は、リスタートの２回目の動作を示している。なお、図９では、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになった例を示している。
【００９２】
図９（ａ）に示すように、ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、ＩＸラッチカップリングによって、状態Ｐ２１から状態Ｐ２５として、ルートノードＤ1から、第１フェーズでマークしたマーク値（ｍ：ここでは“４”）のノードの親ノード（インデックスノードＤ3）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ２１において、マーク値（ｍ）に“１”を設定し、状態Ｐ２５において、マーク値（ｍ）に“３”を設定する。
そして、親ノード（インデックスノードＤ3）以下の子ノードにＸラッチを設定する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であるため、状態Ｐ２９に示すようにすべてのラッチを解放し、第２フェーズの動作（リスタート２回目）を行う。
【００９３】
続けて、図９（ｂ）に示しように、ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート２回目で、ＩＸラッチカップリングによって、状態Ｐ３０から状態Ｐ３２として、ルートノードＤ1から、第２フェーズのリスタート１回目でマークしたマーク値（ｍ：ここでは“３”）のノードの親ノード（インデックスノードＤ2）まで、順次ＩＸラッチを設定する。そして、親ノード（インデックスノードＤ2）以下の子ノードにＸラッチを設定する。そして、状態Ｐ３７に示すように、インデックスノードＤ3〜Ｄ6にＸラッチを設定した段階で、葉ノードＤ6の更新を行う。そして、葉ノードＤ6の更新（及びインデックスノードＤ4及びＤ5の分割）後、全ラッチを解放し動作を終了する。
【００９４】
《ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式》
次に、図１０を参照して、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図１０は、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズ及びＳＭＯが発生しなかった場合の第２フェーズの動作は、図８で説明したＭＡＲＫ−ＯＰＴ方式の動作と同じであるため説明を省略する。
ここでは、図１０（ａ）に示すように、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになった例を示している。
【００９５】
ここで、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、ＩＸラッチカップリングによって、状態Ｐ４１から状態Ｐ４５として、ルートノードＤ1から、第１フェーズでマークしたマーク値（ｍ：ここでは“４”）のノードの親ノード（インデックスノードＤ3）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ４１において、マーク値（ｍ）に“１”を設定し、状態Ｐ４５において、マーク値（ｍ）に“３”を設定する。
【００９６】
そして、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、子ノード（インデックスノードＤ4）にＸラッチを設定し、親ノード（インデックスノードＤ3）のＩＸラッチを解放した状態Ｐ４７において、すでに葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であると判断する。そこで、状態Ｐ４８に示すようにすべてのラッチを解放し、第２フェーズの動作（リスタート２回目）を行う。
なお、第２フェーズのリスタート２回目の動作は、図９（ｂ）の動作と同じになるため説明を省略する。
【００９７】
《２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式》
次に、図１１を参照して、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図１１は、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズ及びＳＭＯが発生しなかった場合の第２フェーズの動作は、図８で説明したＭＡＲＫ−ＯＰＴ方式の動作と同じであるため説明を省略する。
ここでも、図１０（ａ）と同様に、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになったものとしている。
【００９８】
ここで、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、状態Ｐ６１から状態Ｐ６７に遷移する。なお、この状態Ｐ６１〜状態Ｐ６７は、図１０（ａ）の状態Ｐ４１〜状態Ｐ４７と同じ状態である。
そして、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、状態Ｐ６７において、すでに葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であると判断し、第１フェーズの途中（ステップＳ７：図２参照）にフェーズを切り替えて動作を継続する。
【００９９】
そして、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、マーク用階層番号（ｈ）に対応するインデックスノードより下位のインデックスノード（Ｄ5以下）に対してＩＸラッチカップリングを行う。そして、状態Ｐ７１に示すように、葉ノードＤ6にＸラッチを設定し、状態Ｐ７２に示すように親ノードのＩＸラッチを解放する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であるため、状態Ｐ７３に示すように葉ノードＤ6のＸラッチを解放し第２フェーズの動作（リスタート２回目）を行う。
なお、第２フェーズのリスタート２回目の動作は、図９（ｂ）の動作と同じになるため説明を省略する。
【０１００】
《２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式》
次に、図１２を参照して、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図１２は、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズ及びＳＭＯが発生しなかった場合の第２フェーズの動作は、図８で説明したＭＡＲＫ−ＯＰＴ方式の動作と同じであるため説明を省略する。
ここでも、図１０（ａ）と同様に、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになったものとしている。
【０１０１】
ここで、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、状態Ｐ８１から状態Ｐ８８に遷移する。なお、この状態Ｐ８１〜状態Ｐ８８は、図１０（ａ）の状態Ｐ４１〜状態Ｐ４８と同じ状態である。そして、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、状態Ｐ８８以降、第１フェーズに戻って動作を再開（リスタート２回目）する。
【０１０２】
そして、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、図１２（ｂ）に示すように、第１フェーズを実行し、ＩＸラッチカップリングによって、状態Ｐ８９から状態Ｐ９７に示すように、ルートノードＤ1から葉ノードＤ6の親ノード（インデックスノードＤ5）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ８９において、マーク値（ｍ）に“１”を設定し、状態Ｐ９３において、マーク値（ｍ）に“３”を設定する。そして、状態Ｐ９８に示すように、葉ノードＤ6にＸラッチを設定し、状態Ｐ９９に示すように親ノードのＩＸラッチを解放する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であるため、状態Ｐ１００に示すように葉ノードＤ6のＸラッチを解放し第２フェーズの動作（リスタート３回目）を行う。
なお、第２フェーズのリスタート３回目の動作は、図９（ｂ）の動作と同じになるため説明を省略する。
【０１０３】
以上説明したように、ＭＡＲＫ−ＯＰＴ方式、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式及び２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、第１フェーズによってマークされたノードによってＸラッチの設定範囲を定めるため、葉ノードから順次Ｘラッチの範囲を拡大していくＩＮＣ−ＯＰＴ方式に比べ、リスタートの回数を減らすことができる。
【図面の簡単な説明】
【０１０４】
【図１】本発明に係るディレクトリ分散型記憶装置（木構造型データ記憶装置）の構成を示すブロック図である。
【図２】ＭＡＲＫ−ＯＰＴ方式の第１フェーズの動作を示すフローチャートである。
【図３】ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図４】ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図５】２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図６】２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図７】ディレクトリの更新例を示す図であって、（ａ）は更新前、（ｂ）は更新後の状態を示す。
【図８】ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第１フェーズ及び第２フェーズ）を模式的に示す模式図である。
【図９】ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ：リスタート１回目及び２回目）を模式的に示す模式図である。
【図１０】ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ）を模式的に示す模式図である。
【図１１】２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ）を模式的に示す模式図である。
【図１２】２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ）を模式的に示す模式図である。
【図１３】従来の並列計算機におけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造を示す図である。
【符号の説明】
【０１０５】
１ ディレクトリ分散型記憶装置（木構造型データ記憶装置）
２ 通信制御部
３ 記憶部
４ 制御部
５ データ操作手段
５１ データ送受信手段
５２ データ参照手段
５３ データ更新手段
６ データ管理手段
６１ データ操作制御手段
６２ データ参照制御手段
６３ データ更新制御手段
６３１ 第１フェーズ実行手段
６３１ａ 第１非フルエントリノード探索手段
６３１ｂ 葉ノードラッチ設定手段
６３１ｃ ノード更新手段
６３２ 第２フェーズ実行手段
６３２ａ 第２非フルエントリノード探索手段
６３２ｂ 子ノードラッチ設定手段（排他ロック設定手段）
６３２ｃ ラッチ有効判定手段（排他ロック有効判定手段）
６３２ｄ ノード更新手段
６３２ｅ ノード再設定手段
７ 制御情報送受信手段
【技術分野】
【０００１】
本発明は、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新を効率的に行うディレクトリ更新方法及びディレクトリ更新プログラム、並びに、木構造型データ記憶装置に関する。
【背景技術】
【０００２】
近年、並列に配置された計算機（ＰＥ：Processing Element）上にデータベース等のデータを分散して記憶することで、データにアクセスする際の負荷分散と並行性動作とを実現したシステムが存在する。
このようなシステムにおいては、アクセス集中による負荷の偏りが存在する場合、その負荷の大きいＰＥがボトルネックとなり、システム全体の処理能力が低下してしまう。そこで、各ＰＥに負荷を均等に分配するためのディレクトリ構造と、そのディレクトリ構造における並行性制御とが提案されている（例えば、非特許文献１参照）。
ここで、図１３を参照して、従来の並列計算機におけるディレクトリ構造について、その概要を説明する。図１３は、従来の並列計算機におけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造を示す図である。
【０００３】
（Ｆａｔ−Ｂｔｒｅｅ構造）
図１３に示すように、Ｆａｔ−Ｂｔｒｅｅ構造は、データを示す葉ノードＮｌを各計算機ＰＥに均等に分配している。また、Ｆａｔ−Ｂｔｒｅｅ構造は、葉ノードＮｌ以外のインデックスを示すインデックスノードＮｉとして、各計算機ＰＥに配置されている葉ノードＮｌへのアクセスパスとなるインデックスノードＮｉのみを各計算機ＰＥに分配している。
なお、各インデックスノードＮｉに登録（エントリ）される下位層のインデックスノードの数と、葉ノードＮｌに登録されるデータ（データページ）の数とは、予め定められた数に制限されている。この制限された数を超過する場合は、各ノードは分割され、木構造が更新（ＳＭＯ：Structure Modification Operation）されることになる。これによって、あるアクセスパスに対して負荷が集中することを回避している。
【０００４】
このように、葉ノードＮｌ及びインデックスノードＮｉを分配することで、各計算機ＰＥの記憶部に記憶されるのは、全体の木構造に対して、ルートノードＮｉRから、均等に分配された葉ノードＮｌまでの部分木となる。すなわち、計算機ＰＥ1には部分木Ｒ1が、計算機ＰＥ2には部分木Ｒ2が、計算機ＰＥ3には部分木Ｒ3が、計算機ＰＥ4には部分木Ｒ4がそれぞれ記憶されることになる。
これによって、各計算機ＰＥに対するアクセスの分散が行われる。また、各計算機ＰＥでは、記憶している葉ノードＮｌの探索に必要のないインデックスノードＮｉを保持していないため、高速に葉ノードＮｌにアクセスすることができる。
【０００５】
（並行性制御）
次に、従来の並列計算機における並行性制御について説明する。図１３で説明したＦａｔ−Ｂｔｒｅｅ構造では、木構造の一貫性を保証するため、並行性制御が必須である。この並行性制御においては、アクセスパスに対して、他のプロセスからのアクセスを制御するロックが用いられる。このロックには、以下の表１に示す５種類（ＩＳ，ＩＸ，Ｓ，ＳＩＸ，Ｘ）のモードがある。
【０００６】
【表１】
【０００７】
表１中、“○”印は、同時に複数のロックを設定できることを示している。
なお、以下では、ＩＳ、ＩＸ、Ｓ、ＳＩＸ及びＸの各モードのロックをそれぞれ、ＩＳロック（インテント共有ロック）、ＩＸロック（インテント排他ロック）、Ｓロック（共有ロック）、ＳＩＸロック（インテント排他付き共有ロック）及びＸロック（排他ロック）と呼ぶ。
ここで、ＩＳロック（インテント共有ロック）は、下位層の一部のリソースにＳロックを設定し、そのリソースを読み取るプロセスの意思を示すものである。また、ＩＸロック（インテント排他ロック）は、下位層の一部のリソースにＸロックを設定し、そのリソースを変更するプロセスの意思を示すものである。また、Ｓロック（共有ロック）は、リソースを読み取り専用とする旨を示すものである。また、ＳＩＸロック（インテント排他付き共有ロック）は、リソースの同時読み取りを許可し、下位層のリソースにＩＸロックを設定し、プロセスがそのリソースを変更する意図を示すものである。さらに、Ｘロック（排他ロック）は、他のプロセスからの読み取り、変更を禁止する旨を示すものである。
【０００８】
ただし、一般には、これらのロックには、デッドロック検出機能を持たない高速かつ単純なラッチが用いられる。このラッチは、セマフォの一種であって、以下、前記した各ロックをラッチにより実現した場合を、特に、ＩＳラッチ（インテント共有ラッチ）、ＩＸラッチ（インテント排他ラッチ）、Ｓラッチ（共有ラッチ）、ＳＩＸラッチ（インテント排他付き共有ラッチ）、及び、Ｘラッチ（排他ラッチ）と呼ぶ。
【０００９】
次に、図１３を参照して、前記した表１の５種類のロック（ラッチ）を用いた、並行性制御方式の一例であるＩＮＣ−ＯＰＴ（INCremental OPTimistic）方式について説明する。
（ＩＮＣ−ＯＰＴ方式の参照時のプロトコル）
まず、ＩＮＣ−ＯＰＴ方式におけるデータの参照時のプロトコルについて説明する。ＩＮＣ−ＯＰＴ方式における、データである葉ノードＮｌの検索は、以下の〔Ｒ−１〕〜〔Ｒ−３〕の手順により行われる。
〔Ｒ−１〕ルートノードＮｉRにＩＳラッチを設定する。
〔Ｒ−２〕上位層のノード（親ノード）に設定されて下位層のノード（子ノード）のポインタを取得し、子ノードにラッチ（ＩＳラッチ）を設定し、親ノードのラッチを解放する動作を葉ノードＮｌまで繰り返す（以下、この動作をラッチカップリングという）。
〔Ｒ−３〕葉ノードＮｌにＳラッチを設定する。
これによって、葉ノードＮｌを読み出す（参照する）ことが可能になる。
【００１０】
（ＩＮＣ−ＯＰＴ方式の更新時のプロトコル）
次に、ＩＮＣ−ＯＰＴ方式におけるデータの更新時のプロトコルについて説明する。ＩＮＣ−ＯＰＴ方式における、葉ノードＮｌの更新は、以下の〔Ｗ−１〕、〔Ｗ−２〕の２つのフェーズで行われる。
〔Ｗ−１（第１フェーズ）〕ルートノードＮｉRから葉ノードＮｌまで、ＩＸラッチカップリングによりＩＸラッチを設定し、最下層の葉ノードＮｌにＸラッチを設定する。ここで、葉ノードＮｌを更新する際に、予め定められたデータ（データページ）の数を超過することで、木構造に変化（ＳＭＯ）が発生する場合は、葉ノードＮｌのＸラッチを解放し、第２フェーズに移行する。なお、ＳＭＯが発生しない場合は、そのまま葉ノードＮｌを更新し動作を終了する。
〔Ｗ−２（第２フェーズ）〕葉ノードＮｌとその親ノードに対してＸラッチを設定する。もし、葉ノードＮｌを分割することで、親ノードもエントリ数の制限を超過する場合は、さらに上位（親）のノードにＸラッチの範囲を拡大していく。そして、親ノードの分割が必要でなくなった段階で、葉ノードＮｌの更新（ＳＭＯを含む）を行う。
以上の動作によって、ＩＮＣ−ＯＰＴ方式は、Ｆａｔ−Ｂｔｒｅｅ構造を維持したまま、データ（葉ノード）の参照、更新が可能になる。
【非特許文献１】宮崎純，横田治夫，「並列ディレクトリ構造Ｆａｔ−Ｂｔｒｅｅの並行性制御とその評価」，情報処理学会研究会報告，データベースシステムＤＢＳ−１２４−６９，ｐｐ．３７−４４，情報処理学会，Ｊｕｌ．２００１
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかし、前記したＩＮＣ−ＯＰＴ方式では、データの更新時のプロトコルにおいて、ＳＭＯが発生する場合、第２フェーズを処理するための動作（リスタート）を複数回行う必要がある。例えば、ルートノードまで更新が及ぶ場合、木構造の木の高さと同じフェーズ数分のリスタートが必要となり、あるプロセスからの更新命令に対する応答時間を増加させてしまうという問題がある。
さらに、上位層において、複数回Ｘラッチを設定することになり、他のプロセスからの読み取り、変更を禁止する期間が増大し、システム全体のスループットが低下してしまうという問題がある。
【００１２】
本発明は、以上のような問題点に鑑みてなされたものであり、従来のＩＮＣ−ＯＰＴ方式に比べて、リスタート回数を少なく抑え、ＳＭＯに要するＸラッチの獲得時間を短くするディレクトリ更新方法及びディレクトリ更新プログラム、並びに、木構造型データ記憶装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、前記目的を達成するために創案されたものであり、まず、請求項１に記載のディレクトリ更新方法は、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、第１フェーズ実行ステップと、第２フェーズ実行ステップとを含む手順とした。
【００１４】
この手順において、ディレクトリ更新方法は、第１フェーズ実行ステップとして、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、エントリ数が予め定めた制限未満（非フルエントリ）である最も下位のノード（非フルエントリノード）を探索する。そして、ディレクトリ更新方法は、葉ノードに対して、他のプロセスからの読み取り、変更を禁止する排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合には、その葉ノードを更新する。一方、ディレクトリ更新方法は、エントリ数が予め定めた制限を超過する場合には、葉ノードを更新（分割）することで、その親ノードのエントリ数に影響を及ぼすことになるため、ここでは一旦葉ノードの排他ロックを解放し、次の第２フェーズ実行ステップに移行する。
【００１５】
そして、ディレクトリ更新方法は、第２フェーズ実行ステップとして、第１フェーズ実行ステップで探索された非フルエントリノード以下のノードに対してＸロック（排他ロック）を設定する。そして、ディレクトリ更新方法は、葉ノードの更新に伴い分割対象となる親ノードにＸロックが設定されている場合に、葉ノードを更新し、その葉ノードの更新により分割対象となる親ノードにＸロックが設定されていない場合に、非フルエントリノードよりもさらに上位の非フルエントリノードを探索し、その探索された非フルエントリノードより下位のノードに排他ロックの範囲を拡大する。これによって、ディレクトリ更新方法は、動作をリスタートさせて第２フェーズ実行ステップに移行した場合に、非フルエントリノード以下のノードに対して一度にＸロックを設定するため、葉ノードから順次上位のノードにＸロックを設定する場合に比べ、第２フェーズ実行ステップをリスタートする回数を減らすことができる。
なお、ここで、排他ロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ）を用いることが望ましい。
【００１６】
また、請求項２に記載のディレクトリ更新方法は、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行ステップと、前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行ステップとを含むこととした。
さらに、第２フェーズ実行ステップが、排他ロック設定ステップと、排他ロック有効判定ステップと、ノード更新ステップとをさらに含み、前記排他ロック有効判定ステップで木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２フェーズ実行ステップを繰り返す手順とした。
【００１７】
この手順によれば、ディレクトリ更新方法は、第１フェーズ実行ステップで、ルートノードから更新対象となる葉ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索する。このように、ＩＸロックを順次設定することで、他のプロセスが葉ノードに対してＸロックを設定することを防止し、当該プロセスが確実に葉ノードに対してＸロックを設定することが可能になる。
なお、ディレクトリ更新方法は、第１フェーズ実行ステップで、第１の非フルエントリノードを探索するとともに、葉ノードに対して排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合に葉ノードの更新を行い、エントリ数が予め定めた制限を超過する場合に葉ノードの更新を行わずに排他ロックを解放する。これによって、葉ノードのエントリ数が予め定めた制限未満である場合には、第１フェーズ実行ステップで動作が終了することになる。
【００１８】
そして、ディレクトリ更新方法は、第２フェーズ実行ステップで、ルートノードから第１の非フルエントリノードの親ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する。
さらに、ディレクトリ更新方法は、第２フェーズ実行ステップにおいて、第２の非フルエントリノードの探索と並行し、排他ロック設定ステップで、第１の非フルエントリノードから葉ノードまでの経路において、各ノードにＸロック（排他ロック）を設定する。そして、排他ロック有効判定ステップで、排他ロック設定ステップで設定したＸロックが、葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する。すなわち、葉ノードを分割することで影響を受ける親ノードに対してＸロックが設定されているかどうかを判定する。
【００１９】
そして、木構造の更新に関連するノードに対してＸロックが設定されていると判定された場合、ディレクトリ更新方法は、ノード更新ステップで葉ノードの更新を行う。一方、木構造の変化に関連するノードに対してＸロックが設定されていないと判定された場合、ディレクトリ更新方法は、第２の非フルエントリノードを第１の非フルエントリノードとして、第２フェーズ実行ステップを繰り返す。
これによって、ディレクトリ更新方法は、動作をリスタートさせて第２フェーズ実行ステップに移行した場合に、非フルエントリノードより下位のノードに対して一度にＸロックを設定するため、葉ノードから順次上位のノードにＸロックを設定する場合に比べ、第２フェーズ実行ステップをリスタートする回数を減らすことができる。
なお、ここで、排他ロック及びインテント排他ロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ及びインテント排他ラッチ）を用いることが望ましい。
【００２０】
さらに、請求項３に記載のディレクトリ更新プログラムは、木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴うディレクトリの更新を行うために、コンピュータを、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段、前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段として機能させる構成とした。
さらに、第２フェーズ実行手段が、排他ロック設定手段と、排他ロック有効判定手段と、ノード更新手段と、ノード再設定手段とを備える構成とした。
【００２１】
かかる構成によれば、ディレクトリ更新プログラムは、第１フェーズ実行手段によって、ルートノードから更新対象となる葉ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索する。
なお、ディレクトリ更新プログラムは、第１フェーズ実行手段で、第１の非フルエントリノードを探索するとともに、葉ノードに対して排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合に葉ノードの更新を行い、エントリ数が予め定めた制限を超過する場合に葉ノードの更新を行わずに排他ロックを解放する。
【００２２】
そして、ディレクトリ更新プログラムは、第２フェーズ実行手段によって、ルートノードから第１の非フルエントリノードの親ノードまでの経路において、Ｘロック（排他ロック）を設定する旨を示すＩＸロック（インテント排他ロック）を下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する。
さらに、ディレクトリ更新プログラムは、排他ロック設定手段によって、第１の非フルエントリノードから葉ノードまでの経路において、各ノードにＸロックを設定し、排他ロック有効判定手段によって、排他ロック設定手段で設定したＸロックが、葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する。
【００２３】
そして、木構造の変化に関連するノードに対してＸロックが設定されていると判定された場合、ディレクトリ更新プログラムは、ノード更新手段によって、葉ノードの更新を行う。
一方、木構造の変化に関連するノードに対してＸロックが設定されていないと判定された場合、ディレクトリ更新プログラムは、ノード再設定手段によって、第２の非フルエントリノードを第１の非フルエントリノードとして設定する。これによって、Ｘロックの範囲が拡大されることになる。
なお、ここで、排他ロック及びインテント排他ロックには、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ及びインテント排他ラッチ）を用いることが望ましい。
【００２４】
また、請求項４に記載の木構造型データ記憶装置は、木構造における各ノードのエントリ数を制限したディレクトリ構造によって、データを記憶する木構造型データ記憶装置において、最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段と、前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段とを備える構成とした。
さらに、第２フェーズ実行手段が、排他ロック設定手段と、排他ロック有効判定手段と、ノード更新手段と、ノード再設定手段とを備える構成とした。
【００２５】
かかる構成によれば、木構造型データ記憶装置は、第１フェーズ実行手段によって、ルートノードから更新対象となる葉ノードまでの経路において、Ｘロックを設定する旨を示すＩＸロックを下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索する。
なお、木構造型データ記憶装置は、第１フェーズ実行手段で、第１の非フルエントリノードを探索するとともに、葉ノードに対して排他ロックを設定し、葉ノードのエントリ数が予め定めた制限未満である場合に葉ノードの更新を行い、エントリ数が予め定めた制限を超過する場合に葉ノードの更新を行わずに排他ロックを解放する。
【００２６】
そして、木構造型データ記憶装置は、第２フェーズ実行手段によって、ルートノードから第１の非フルエントリノードの親ノードまでの経路において、Ｘロックを設定する旨を示すＩＸロックを下位層に対して設定し、その上位層に対するＩＸロックの設定を解放する手順を下位層に向かって繰り返しながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する。
さらに、木構造型データ記憶装置は、排他ロック設定手段によって、第１の非フルエントリノードから葉ノードまでの経路において、各ノードにＸロックを設定し、排他ロック有効判定手段によって、排他ロック設定手段で設定したＸロックが、葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する。
そして、木構造の変化に関連するノードに対してＸロックが設定されていると判定された場合、ディレクトリ分散型記憶装置は、ノード更新手段によって、葉ノードの更新を行う。
一方、木構造の変化に関連するノードに対してＸロックが設定されていないと判定された場合、木構造型データ記憶装置は、ノード再設定手段によって、第２の非フルエントリノードを第１の非フルエントリノードとして設定する。
なお、ここで、Ｘロック（排他ロック）及びＩＸロック（インテント排他ロック）には、デッドロック検出機能を持たない高速かつ単純なラッチ（排他ラッチ及びインテント排他ラッチ）を用いることが望ましい。
【発明の効果】
【００２７】
本発明によれば、更新対象となる葉ノードを更新することでディレクトリ構造の木構造に変化が発生する場合、葉ノードから順次親ノードに排他ロック（排他ラッチ）を設定する手順を行わず、エントリ数が予め定めた制限未満である最も下位のノード以降に対して排他ロック（排他ラッチ）を設定する。これによって、葉ノードから順次排他ロック（排他ラッチ）の範囲を拡大させるＩＮＣ−ＯＰＴ方式に比べ、リスタートの回数を減らすことができ、ディレクトリ構造の変更に伴う時間を減らすことができる。
【００２８】
さらに、本発明によれば、リスタート回数を減らすことで、排他ロック（排他ラッチ）を設定している時間を減らすことができるため、他のプロセスからの葉ノードに対するアクセスに対する応答性を高めることができる。また、ディレクトリ構造を分散して記憶するシステムの場合、システム全体のスループットを改善することができる。
【発明を実施するための最良の形態】
【００２９】
［ディレクトリ分散型記憶装置（木構造型データ記憶装置）の構成］
まず、図１を参照して、ディレクトリ分散型記憶装置の構成について説明する。図１は、本発明に係る木構造型データ記憶装置の最良の形態であるディレクトリ分散型記憶装置の構成を示すブロック図である。
図１に示したディレクトリ分散型記憶装置１は、ネットワークＮに接続された他のディレクトリ分散型記憶装置（図示せず）と協働し、データベース等のデータを分散して記憶するものである。このディレクトリ分散型記憶装置１は、図１３で説明したＦａｔ−Ｂｔｒｅｅ構造のディレクトリ構造によってデータを記憶管理する計算機ＰＥに相当する。
ここでは、ディレクトリ分散型記憶装置１は、通信制御部２と、記憶部３と、制御部４とを備えている。また、ここでは、ロック制御として、デッドロック検出機能を持たないラッチを用いることとする。
【００３０】
通信制御部２は、ネットワークＮを介して、クライアントコンピュータ（図示せず）や他のディレクトリ分散型記憶装置（図示せず）と、データや制御情報（ノード情報を含む）の送受信を行うものである。例えば、通信制御部２は、ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）の通信プロトコルによってデータ等の送受信を行う通信ボードである。
【００３１】
記憶部３は、データベース等のデータや、ディレクトリ構造を特定するノード情報等を記憶しておくもので、一般的なハードディスク等の記憶装置である。この記憶部３には、データ３１と、ノード情報３２と、エントリ制限情報３３とを記憶している。
【００３２】
データ３１は、Ｆａｔ−Ｂｔｒｅｅ構造における葉ノードであって、データの実体である。このデータ３１は、記憶領域の予め定められたページ単位で管理され、所定のページ数（後記するエントリ制限情報３３に含まれる）を超過する場合は分割される。
【００３３】
ノード情報３２は、Ｆａｔ−Ｂｔｒｅｅ構造のデータ構造を示す情報である。ここでは、ノード情報３２は、Ｆａｔ−Ｂｔｒｅｅ構造のルートノードから、この記憶部３に記憶されているデータ（葉ノード）３１までのアクセスパスを示している。
さらに、ノード情報３２は、各ノードにどのプロセスから、どのロック（ラッチ）が設定されているかを示す情報を含んでいる。
【００３４】
エントリ制限情報３３は、Ｆａｔ−Ｂｔｒｅｅ構造において、ノードに登録される子ノードの数の最大値や、葉ノードとして登録できるデータ（データページ）の数の最大値を示している。このエントリ制限情報３３は、後記する制御部４によって参照され、データの更新に伴う木構造の変化（ＳＭＯ）が発生するか否かを判定するために用いられる。
【００３５】
制御部４は、ディレクトリ分散型記憶装置１全体の動作を制御するものであって、一般的なコンピュータにおけるＣＰＵ（Central Processing Unit：中央処理装置）に相当するものである。ここでは、制御部４は、データ操作手段５と、データ管理手段６と、制御情報送受信手段７とを備えている。
【００３６】
データ操作手段５は、通信制御部２を介して、データの送受信操作を行うものである。ここでは、データ操作手段５は、データ送受信手段５１と、データ参照手段５２と、データ更新手段５３とを備えている。
【００３７】
データ送受信手段５１は、データ管理手段６のデータ操作制御手段６１から制御情報として通知されるデータの送信元（例えば、クライアントコンピュータ等）から、通信制御部２を介してデータを受信したり、データ操作制御手段６１から制御情報として通知されるデータの送信先（例えば、クライアントコンピュータ等）に、通信制御部２を介してデータを送信したりするものである。
このデータ送受信手段５１は、データ参照手段５２から出力されるデータを、通信制御部２を介して送信し、通信制御部２を介して受信したデータをデータ更新手段５３に出力する。
【００３８】
データ参照手段５２は、記憶部３に記憶されているデータ３１を読み出すものである。このデータ参照手段５２は、データ管理手段６のデータ操作制御手段６１から通知される制御情報（記憶元のアドレス等）に基づいて、データ３１を記憶部３から読み出す。このデータ参照手段５２で読み出されたデータ３１は、データ送受信手段５１に出力される。
【００３９】
データ更新手段５３は、データ送受信手段５１で受信したデータを、記憶部３に書き込むものである。このデータ更新手段５３は、データ管理手段６のデータ操作制御手段６１から通知される制御情報（記憶先のアドレス等）に基づいて、データを記憶部３に書き込む。なお、データ更新手段５３は、データ操作制御手段６１から通知される制御情報（記憶先のアドレス等）に基づいて、指示されたデータ３１を記憶部３から削除する動作も行うものとする。
【００４０】
データ管理手段６は、記憶部３に記憶されているノード情報３２とエントリ制限情報３３とに基づいて、記憶部３に記憶されるデータ３１を階層構造で管理するものである。また、このデータ管理手段６は、Ｆａｔ−Ｂｔｒｅｅ構造（図１３参照）のディレクトリ構造によりデータ３１を管理するものとする。ここでは、データ管理手段６は、データ操作制御手段６１と、データ参照制御手段６２と、データ更新制御手段６３とを備えている。
【００４１】
データ操作制御手段６１は、図示していないクライアントコンピュータ等から送信される制御情報を、後記する制御情報送受信手段７を介して受信することで、その制御情報で示されるデータの操作を行うものでもある。
ここで、制御情報とは、データを制御する情報である。例えば、データを記憶する旨を示すデータ記憶指示、データを送信する旨を示すデータ送信指示、データを削除する旨を示すデータ削除指示等、あるいはこれらの指示に対する応答等である。
【００４２】
例えば、制御情報が、データを記憶する旨を示すデータ記憶指示である場合、データ操作制御手段６１は、その旨をデータ更新手段５３に通知する。また、制御情報が、データを送信する旨を示すデータ送信指示である場合、データ操作制御手段６１は、その旨をデータ参照手段５２に通知する。また、制御情報が、データを削除する旨を示すデータ削除指示である場合、データ操作制御手段６１は、その旨をデータ更新手段５３に通知する。また、データ操作制御手段６１は、これらの操作指示（データ記憶指示、データ送信指示、データ削除指示）の操作結果を制御情報送受信手段７に対して応答として出力する。
【００４３】
なお、データ操作制御手段６１は、データ操作が、データの参照を行うものである場合は、その旨を後記するデータ参照制御手段６２に通知し、他のプロセスに対する排他制御を行うものとする。また、データ操作制御手段６１は、データ操作が、データの更新を行うものである場合は、その旨を後記するデータ更新制御手段６３に通知し、他のプロセスに対する排他制御や、木構造の変更（ＳＭＯ）を行う。
【００４４】
データ参照制御手段６２は、データの読み出し等である参照系の操作において、他のプロセスに対する排他制御を行うものである。例えば、データ参照制御手段６２は、ルートノードにＩＳラッチ（表１参照）を設定し、親ノードに設定されている子ノードのポインタを取得し、子ノードにラッチ（ＩＳラッチ）を設定し、親ノードのラッチを解放する動作をデータ（葉ノード）３１まで繰り返す。そして、データ（葉ノード）３１にＳラッチを（表１参照）設定することで、データ（葉ノード）３１の参照（読み出し）を可能にする。
【００４５】
データ更新制御手段６３は、データの追加、更新等の更新系の操作において、他のプロセスに対する排他制御や、木構造の変更（ＳＭＯ）を行うものである。ここでは、データ更新制御手段６３は、第１フェーズ実行手段６３１と、第２フェーズ実行手段６３２とを備えている。
【００４６】
第１フェーズ実行手段６３１は、第１フェーズとして、エントリ数が予め定めた制限未満である最も下位のノード（第１の非フルエントリノード）を探索するとともに、データ（葉ノード）３１の更新を行うものである。ここでは、第１フェーズ実行手段６３１は、第１非フルエントリノード探索手段６３１ａと、葉ノードラッチ設定手段６３１ｂと、ノード更新手段６３１ｃとを備えている。
【００４７】
第１非フルエントリノード探索手段６３１ａは、ルートノードから更新対象となるデータ（葉ノード）３１までの経路において、Ｘラッチ（排他ラッチ：表１参照）を設定する旨を示すＩＸラッチ（インテント排他ラッチ：表１参照）を下位層に対して設定し、その上位層に対するＩＸラッチの設定を解放する手順を下位層に向かって繰り返すラッチカップリングを行いながら、エントリ数が予め定めた制限未満である最も下位のノード（第１の非フルエントリノード）を探索するものである。ここでは、第１非フルエントリノード探索手段６３１ａは、ＳＭＯが発生しない最下層のノードをルートノードから順次探索し、そのノードのルートノードからの木の高さを保持しておく。
【００４８】
葉ノードラッチ設定手段６３１ｂは、更新対象となるデータ（葉ノード）３１に対してＸラッチを設定するものである。これによって、他のプロセスに対して、更新対象となるデータ（葉ノード）３１の読み取り、変更を禁止することができる。
【００４９】
ノード更新手段６３１ｃは、葉ノードラッチ設定手段６３１ｂによってＸラッチが設定された、更新対象となるデータ（葉ノード）３１を更新するものである。なお、ノード更新手段６３１ｃは、記憶部３のノード情報３２とエントリ制限情報３３とを参照し、データ３１を追加、更新する際に、エントリ数が超過する場合に、データ（葉ノード）３１の分割や、その親ノードの分割といった木構造に変化を及ぼす操作（ＳＭＯ）が発生する場合は、データ（葉ノード）３１を更新せず、データ３１に対するＸラッチを解放する。そして、第２フェーズ実行手段６３２に、第１非フルエントリノード探索手段６３１ａで探索された第１の非フルエントリノードの位置（その親ノードのルートノードからの木の高さ）を通知する。
このように、第１フェーズ実行手段６３１は、ＳＭＯが発生しない場合は、第１フェーズ実行手段６３１でデータ（葉ノード）３１の更新を完了するが、ＳＭＯが発生する場合は、第２フェーズ実行手段６３２に処理を移行する。
【００５０】
第２フェーズ実行手段６３２は、第２フェーズとして、第１フェーズ実行手段６３１で探索された第１の非フルエントリノードより上位のノードで、エントリ数が予め定めた制限未満である最も下位のノード（第２の非フルエントリノード）を探索するとともに、データ（葉ノード）３１の更新を行うものである。ここでは、第２フェーズ実行手段６３２は、第２非フルエントリノード探索手段６３２ａと、子ノードラッチ設定手段６３２ｂと、ラッチ有効判定手段６３２ｃと、ノード更新手段６３２ｄと、ノード再設定手段６３２ｅとを備えている。
【００５１】
第２非フルエントリノード探索手段６３２ａは、ルートノードから、第１の非フルエントリノードの親ノードまでの経路において、ＩＸラッチカップリングを行いながら、エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索するものである。
【００５２】
子ノードラッチ設定手段（排他ロック設定手段）６３２ｂは、第２非フルエントリノード探索手段６３２ａで探索された第２の非フルエントリノードより下位層の子ノード（葉ノードを含む）に対して、Ｘラッチを設定するものである。
【００５３】
ラッチ有効判定手段（排他ロック有効判定手段）６３２ｃは、子ノードラッチ設定手段６３２ｂで設定したＸラッチが、データ（葉ノード）３１の更新に伴う木構造の変化（ＳＭＯ）に関連するノードに対して設定されているかどうかを判定するものである。すなわち、このラッチ有効判定手段６３２ｃは、ノードの分割が発生するすべてのノードにＸラッチが設定されており、かつ、その親ノードにＸラッチが設定されているかどうかを判定する。このように、ノードの分割が発生するすべてのノードと、その親ノードにＸラッチが設定されていれば、他のプロセスからの影響を受けることなく、木構造の変更が可能になる。
【００５４】
ノード更新手段６３２ｄは、ラッチ有効判定手段６３２ｃで木構造の変化に関連するノードに対してＸラッチが設定されていると判定された場合に、データ（葉ノード）３１の更新を行うものである。すなわち、このノード更新手段６３２ｄは、データ（葉ノード）３１の更新を行う際に、データ３１の分割を行う。また、その親ノード（インデックスノード）で分割が必要な場合は、順次上位の親ノードに遡って分割を行う。これによって、データ（葉ノード）３１に対するアクセスの均等化が図られることになる。
【００５５】
ノード再設定手段６３２ｅは、ラッチ有効判定手段６３２ｃで木構造の変化に関連するノードに対してＸラッチが設定されていないと判定された場合に、第２の非フルエントリノードを第１の非フルエントリノードとして再設定するものである。すなわち、第２の非フルエントリノードのルートノードからの木の高さを保持し直す。なお、このとき、ノード再設定手段６３２ｅは、すべてのＸラッチを解放する。
そして、ノード再設定手段６３２ｅは、第２非フルエントリノード探索手段６３２ａに制御を移行させる。
【００５６】
このように、データ更新制御手段６３を構成することで、データ更新制御手段６３は、データ（葉ノード）３１の更新を、以下の〔第１フェーズ〕、〔第２フェーズ〕の２つのフェーズで行うことになる。
【００５７】
〔第１フェーズ〕ルートノードから葉ノードまで、ＩＸラッチカップリングによりＩＸラッチを設定し、最下層の葉ノードにＸラッチを設定する。また、フルエントリでないインデックスノード（第１の非フルエントリノード）が存在したら、そのノードの位置（ルートノードからの高さ）を保持（マーク）する。マークするノードの位置は、非フルエントリノードが存在する度に逐次更新される。もし、ＳＭＯが発生しない場合は、葉ノードを更新して終了する。もし、ＳＭＯが発生する場合は、葉ノードのＸラッチを解放し、第２フェーズに移行する。
【００５８】
〔第２フェーズ〕ルートノードから、第１フェーズでマークした第１の非フルエントリノードの親ノードまで、順次ＩＸラッチカップリングによりＩＸラッチを設定し、第１の非フルエントリノード以下のノードにＸラッチを設定する。もし、設定したＸラッチの範囲が、ＳＭＯを行うために十分な範囲に設定されていなければ、マークの位置によるＸラッチの範囲を変化させ、ＳＭＯを行うために十分な範囲となった段階で、葉ノードを更新して終了する。
なお、本方式は、第１フェーズにおいて、フルエントリでないインデックスノード（第１の非フルエントリノード）の位置（ルートノードからの高さ）を保持（マーク）しておくため、ＭＡＲＫ−ＯＰＴ（MARKing OPTimistic）方式と呼ぶこととする。
【００５９】
制御情報送受信手段７は、通信制御部２を介して、図示していないクライアントコンピュータ等と制御情報の送受信を行うものである。ここでは、制御情報送受信手段７は、クライアントコンピュータ等から受信した制御情報をデータ操作制御手段６１に出力し、データ操作制御手段６１から出力された制御信号をクライアントコンピュータ等に送信する。
【００６０】
以上、説明したように、ディレクトリ分散型記憶装置１を構成することで、第２フェーズでは、第１フェーズでマークした第１の非フルエントリノードの親ノードまでＩＸラッチカップリングを行い、第１の非フルエントリノード以下のノードにＸラッチを設定するため、Ｘラッチの範囲を葉ノードから順次拡げていく従来のＩＮＣ−ＯＰＴ方式に比べて、リスタートを行う回数を減らすことができる。
また、ここでは、ディレクトリ（ノード情報）とデータ（葉ノード）とを複数のディレクトリ分散型記憶装置で分散して記憶する形態としたが、本発明は、この形態に限定されるものではない。例えば、１つの記憶装置（木構造型データ記憶装置）のみに、すべてのノード情報と葉ノードとを記憶し、各ノードのエントリ数を制限したディレクトリ構造を形成している場合であっても、本発明に係るディレクトリ更新を行うことは可能である。この場合であっても、ＩＮＣ−ＯＰＴ方式に比べて、リスタートを行う回数を減らすことができ、ＳＭＯに要するＸラッチの獲得時間を短くすることができる。ただし、システム全体のスループットを向上させるには、複数の木構造型データ記憶装置（ディレクトリ分散型記憶装置）で、ディレクトリ（ノード情報）とデータ（葉ノード）とを分散するほうが望ましいと言える。
なお、ディレクトリ分散型記憶装置１の制御部４は、一般的なコンピュータにプログラムを実行させ、コンピュータ内の演算装置や記憶装置を動作させることにより実現することができる。ここで実現されるディレクトリの更新を行うディレクトリ更新プログラムは、通信回線を介して配布することも可能であるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【００６１】
［ディレクトリ分散型記憶装置の動作］
次に、図２及び図３を参照（適宜図１参照）して、ディレクトリ分散型記憶装置の動作について説明する。なお、ここでは、ディレクトリ分散型記憶装置１のデータ更新制御手段６３において行われる、本発明に係るディレクトリ更新方法（ＭＡＲＫ−ＯＰＴ方式）について、詳細に説明を行うことにする。図２は、ＭＡＲＫ−ＯＰＴ方式の第１フェーズの動作を示すフローチャートである。図３は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【００６２】
《ＭＡＲＫ−ＯＰＴ方式》
（第１フェーズ；第１フェーズ実行ステップ）
ディレクトリ分散型記憶装置１は、第１フェーズ実行手段６３１において、以下の手順で第１フェーズの動作（図２参照）を実行する。
まず、ディレクトリ分散型記憶装置１は、第１非フルエントリノード探索手段６３１ａによって、初期値として、エントリ数が制限を超過していないノードの階層番号を示す変数〔マーク用階層番号（ｎ）〕に、木構造の木の高さを示すツリー高“Ｈ”を設定する（ステップＳ１）。さらに、ディレクトリ分散型記憶装置１は、初期値として、親ノードを識別するための変数（Ｐａｒｅｎｔ）に“ｎｕｌｌ”、子ノードを識別するための変数（Ｃｈｉｌｄ）にルートノードを示す識別子“ＲＯＯＴ”を設定し、ループに使用するインデックス用階層番号（ｈ）と非フルエントリノードの位置を示すマーク値（ｍ）とにそれぞれ“１”を設定する（ステップＳ２）。
【００６３】
そして、ディレクトリ分散型記憶装置１は、インデックス用階層番号（ｈ）が、マーク用階層番号（ｎ）に達していないかどうかを判定し（ステップＳ３）、達した場合（ステップＳ３でＮｏ）、ステップＳ８に進む。
一方、インデックス用階層番号（ｈ）が、マーク用階層番号（ｎ）に達していない場合（ステップＳ３でＹｅｓ）、ディレクトリ分散型記憶装置１は、第１非フルエントリノード探索手段６３１ａによって、子ノード（Ｃｈｉｌｄ）にＩＸラッチを設定し、親ノード（Ｐａｒｅｎｔ）に設定されているラッチを解放する（ステップＳ４）。ただし、最初は親ノード（Ｐａｒｅｎｔ）には、ＩＸラッチが設定されていないため、ステップＳ４のラッチの解放は、ラッチが設定されている場合にのみなされる。
続けて、ディレクトリ分散型記憶装置１は、第１非フルエントリノード探索手段６３１ａによって、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ５）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ５でＹｅｓ）、ステップＳ７に進む。
【００６４】
一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ５でＮｏ）、マーク値（ｍ）に現在の階層番号であるインデックス用階層番号（ｈ）を設定し、非フルエントリノードの位置を保持（マーク）しておく（ステップＳ６）。
そして、ディレクトリ分散型記憶装置１は、現在の子ノード直下のノードを新しい子ノード（新子ノード）として決定し、親ノード（Ｐａｒｅｎｔ）に子ノード（Ｃｈｉｌｄ）、子ノード（Ｃｈｉｌｄ）に新子ノード（ＮｅｗＣｈｉｌｄ）を設定し直す。さらに、インデックス用階層番号（ｈ）に“１”を加算することで、１つ下の階層に制御対象を移動する（ステップＳ７）。そして、ステップＳ３に戻る。
【００６５】
このステップＳ３からステップＳ７までのループによって、ルートノードから、葉ノードの親ノードに対してＩＸラッチカップリングが行われることになる。
そして、ディレクトリ分散型記憶装置１は、葉ノードラッチ設定手段６３１ｂによって、子ノード（この段階では葉ノード）に対してＸラッチを設定し、その親ノードのラッチを解放する（ステップＳ８）。
【００６６】
ここで、ディレクトリ分散型記憶装置１は、ノード更新手段６３１ｃによって、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（葉ノード）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ９）。ここで、葉ノードがフルエントリでない場合（ステップＳ９でＮｏ）、ノード更新手段６３１ｃが葉ノードの更新操作を実行し（ステップＳ１０）、すべてのラッチを解放し（ステップＳ１１）、動作を終了する。
一方、葉ノードがフルエントリの場合（ステップＳ９でＹｅｓ）、ディレクトリ分散型記憶装置１は、すべてのラッチを解放し（ステップＳ１２）、マーク用階層番号（ｎ）に、マーク値（ｍ）を設定し（ステップＳ１３）、第２フェーズに移行する。
【００６７】
（第２フェーズ；第２フェーズ実行ステップ）
次に、ディレクトリ分散型記憶装置１は、第２フェーズ実行手段６３２において、以下の手順で第２フェーズの動作（図３参照）を実行する。
まず、ディレクトリ分散型記憶装置１は、第２非フルエントリノード探索手段６３２ａによって、ルートノードからマーク用階層番号（ｎ）で示される非フルエントリノードの親ノードまで、ＩＸラッチカップリングを行う（ステップＳ２０〜ステップＳ２５）。なお、このステップＳ２０〜ステップＳ２５までの動作は、図２で説明したステップＳ２〜ステップＳ７までの動作と同一であるため説明を省略する。
【００６８】
そして、ディレクトリ分散型記憶装置１は、ステップＳ２５（ステップＳ７）まででＩＸラッチカップリングされたノードの子ノード、すなわち、マーク用階層番号（ｎ）で示される非フルエントリノードと、そのコピー（複製）にＸラッチを設定し、親ノードのＩＸラッチを解放する（ステップＳ２６）。ここで、コピー（複製）とは、図１３で説明した計算機ＰＥ間で、同一のインデックスノードＮｉをコピーしてそれぞれのＰＥで保有している場合、そのＰＥ毎のインデックスノードＮｉを指す。
さらに、ディレクトリ分散型記憶装置１は、現在の子ノード直下のノードを新しい子ノード（新子ノード）として決定し、親ノード（Ｐａｒｅｎｔ）に子ノード（Ｃｈｉｌｄ）、子ノード（Ｃｈｉｌｄ）に新子ノード（ＮｅｗＣｈｉｌｄ）を設定し直す。さらに、インデックス用階層番号（ｈ）に“１”を加算することで、１つ下の階層に制御対象を移動する（ステップＳ２７）。
【００６９】
そして、ディレクトリ分散型記憶装置１は、インデックス用階層番号（ｈ）が、ツリー高“Ｈ”に達していないかどうかを判定し（ステップＳ２８）、達した場合（ステップＳ２８でＮｏ）は、ステップＳ３１に進む。
一方、インデックス用階層番号（ｈ）が、ツリー高“Ｈ”を超えていない場合（ステップＳ２８でＹｅｓ）、ディレクトリ分散型記憶装置１は、子ノードラッチ設定手段６３２ｂによって、子ノードとそのコピー（複製）にＸラッチを設定する（ステップＳ２９；排他ロック設定ステップ）。
続けて、ディレクトリ分散型記憶装置１は、子ノードラッチ設定手段６３２ｂによって、現在の子ノード直下のノードを新しい子ノード（新子ノード）として決定し、親ノード（Ｐａｒｅｎｔ）に子ノード（Ｃｈｉｌｄ）、子ノード（Ｃｈｉｌｄ）に新子ノード（ＮｅｗＣｈｉｌｄ）を設定し直す。さらに、インデックス用階層番号（ｈ）に“１”を加算することで、１つ下の階層に制御対象を移動する（ステップＳ３０）。そして、ステップＳ２８に戻る。
このステップＳ２８からステップＳ３０までのループによって、ステップＳ２７で設定された子ノード以下のノードにＸラッチが設定されることになる。
【００７０】
そして、ディレクトリ分散型記憶装置１は、ラッチ有効判定手段６３２ｃによって、Ｘラッチが、データ（葉ノード）３１の更新に伴う木構造の変化（ＳＭＯ）に関連するノードに対してなされているかどうかを判定する（ステップＳ３１；排他ロック有効判定ステップ）。ここで、ＸラッチがＳＭＯを行うためには不十分である場合（ステップＳ３１でＮｏ）、すべてのラッチを解放し（ステップＳ３２）、マーク用階層番号（ｎ）に、マーク値（ｍ）を設定し（ステップＳ３３；ノード再設定ステップ）、ステップＳ２０に戻る（リスタートする）。すなわち、Ｘラッチの範囲を拡げる動作を実行する。
一方、ＸラッチがＳＭＯを行うために十分な設定がなされている場合（ステップＳ３１でＹｅｓ）、ノード更新手段６３２ｄが葉ノード及びそれに関連するノードの更新操作（ＳＭＯ）を実行し（ステップＳ３４；ノード更新ステップ）、すべてのラッチを解放し（ステップＳ３５）、動作を終了する。
【００７１】
以上のＭＡＲＫ−ＯＰＴ方式による第１フェーズ（図２参照）及び第２フェーズ（図３参照）の動作によって、ディレクトリ分散型記憶装置１は、第１フェーズによってマークされたノードによって、Ｘラッチの設定範囲を定めることができ、葉ノードから順次Ｘラッチの範囲を拡大していくＩＮＣ−ＯＰＴ方式に比べ、第２フェーズを再実行するリスタートの回数を減らすことができる。
なお、ディレクトリ更新方法は、第１フェーズ及び第２フェーズで説明した各ステップにより、ディレクトリを更新する方法であって、ディレクトリ更新プログラムは、この第１フェーズ及び第２フェーズで説明した各ステップをコンピュータに実行させるためのプログラムである。
【００７２】
以上、本発明に係るディレクトリ分散型記憶装置１の動作として、ＭＡＲＫ−ＯＰＴ方式の動作について説明したが、本発明はこれに限定されるものではない。例えば、このＭＡＲＫ−ＯＰＴ方式は、他のプロセスの動作によって、途中で木構造に変化があった場合でも処理に変更はないが、その木構造の変化によって処理を変えることとしてもよい。以下、ＭＡＲＫ−ＯＰＴ方式を拡張したＩＮＣ−ＭＡＲＫ−ＯＰＴ方式、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式及び２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式について説明を行う。
【００７３】
《ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式》
まず、図４を参照して、ＩＮＣ−ＭＡＲＫ−ＯＰＴ（INCremental MARKing OPTimistic）方式について説明する。図４は、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。なお、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズは、図２で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７４】
このＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズにおいて、木の構造が変化したと判断された場合にリスタートを行う方式である。
図４に示すように、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズにおけるステップＳ２６とステップＳ２７の間に、ステップＳ２６１ａ〜ステップＳ２６１ｃを追加している。他のステップについては、図３で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７５】
すなわち、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、ステップＳ２６で親ノードのＩＸラッチを解放した段階で、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ２６１ａ）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ２６１ａでＹｅｓ）、すべてのラッチを解放し（ステップＳ２６１ｂ）、マーク用階層番号（ｎ）に、マーク値（ｍ）を設定し（ステップＳ２６１ｃ）、ステップＳ２０に戻る（リスタートする）。一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ２６１ａでＮｏ）は、ＭＡＲＫ−ＯＰＴ方式と同様にステップＳ２７以降の動作を実行する。
【００７６】
このように、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、木の構造が変化したと判断された段階で直ちにリスタートを行うため、ＳＭＯの範囲が拡大している場合には、ＭＡＲＫ−ＯＰＴ方式より不必要なＸラッチを減らすことができる。
【００７７】
《２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式》
次に、図５を参照して、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ（2-Phase INTegrated MARKing OPTimistic）方式について説明する。図５は、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。なお、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズは、図２で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７８】
この２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズにおいて、木の構造が変化したと判断された場合に、そのノード以下のノードに対してＩＸラッチカップリングを行う方式である。
図５に示すように、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズにおけるステップＳ２６とステップＳ２７の間に、ステップＳ２６１ａ及びステップＳ２６１ｄを追加している。他のステップについては、図３で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００７９】
すなわち、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、ステップＳ２６で親ノードのＩＸラッチを解放した段階で、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ２６１ａ）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ２６１ａでＹｅｓ）、マーク用階層番号（ｎ）に、現在の階層番号であるインデックス用階層番号（ｈ）を設定し（ステップＳ２６１ｄ）、第１フェーズ（図２）のステップＳ７に戻る。一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ２６１ａでＮｏ）は、ＭＡＲＫ−ＯＰＴ方式と同様にステップＳ２７以降の動作を実行する。
【００８０】
このように、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、木の構造が変化したと判断されてもリスタートを行わず、第１フェーズに切り替えて処理を行う。これによって、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式よりもリスタート回数を少なくし、ＭＡＲＫ−ＯＰＴ方式より不必要なＸラッチを減らすことができる。
【００８１】
《２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式》
次に、図６を参照して、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ（2-Phase REPetitive MARKing OPTimistic）方式について説明する。図６は、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。なお、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズは、図２で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００８２】
この２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズにおいて、木の構造が変化したと判断された場合に、リスタートを行う方式である。なお、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式との違いは、リスタート後は第１フェーズに戻って処理を行うことである。
図６に示すように、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、ＭＡＲＫ−ＯＰＴ方式の第２フェーズにおけるステップＳ２６とステップＳ２７の間に、ステップＳ２６１ａ及びステップＳ２６１ｂを追加している。他のステップについては、図３で説明したＭＡＲＫ−ＯＰＴ方式と同じ動作であるため説明を省略する。
【００８３】
すなわち、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、ステップＳ２６で親ノードのＩＸラッチを解放した段階で、記憶部３のノード情報３２及びエントリ制限情報３３を参照することで、子ノード（Ｃｈｉｌｄ）のエントリ数が最大（フルエントリ）となっているかどうかを判定する（ステップＳ２６１ａ）。ここで、子ノード（Ｃｈｉｌｄ）がフルエントリの場合（ステップＳ２６１ａでＹｅｓ）、すべてのラッチを解放し（ステップＳ２６１ｂ）、第１フェーズ（図２）のステップＳ１に戻る。一方、子ノード（Ｃｈｉｌｄ）がフルエントリでない場合（ステップＳ２６１ａでＮｏ）は、ＭＡＲＫ−ＯＰＴ方式と同様にステップＳ２７以降の動作を実行する。
【００８４】
このように、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、木の構造が変化したと判断された段階で直ちにリスタートし、第１フェーズに戻って処理を行うため、リスタート回数は、ＭＡＲＫ−ＯＰＴ方式に比べて多くなるが、不必要なＸラッチの設定を最も少なくすることができる。
【００８５】
［ディレクトリ更新動作の具体例］
次に、ディレクトリ分散型記憶装置１（図１参照）におけるディレクトリ更新の動作について、具体例を示して説明する。ここでは、一例として、図７に示すようなディレクトリ更新が行われる例について説明する。図７（ａ）は、ディレクトリ更新前のディレクトリ構造を示し、図７（ｂ）は、データ追加に伴うディレクト更新後のディレクト構造を示している。
【００８６】
図７（ａ）に示すように、ディレクトリ更新前は、Ｄ1−Ｄ2−Ｄ3−Ｄ4−Ｄ5−Ｄ6の各ノードの階層によって、データ３１として葉ノードＤ6が記憶部３に記憶されている。なお、ここでは、インデックスノード及び葉ノードのエントリ数の最大値（制限値）を“３”とする。すなわち、インデックスノードＤ2、Ｄ5は、子ノードがフルエントリ状態であるフルエントリインデックスノードとなっており、葉ノードＤ6は、データがフルエントリ状態であるフルエントリ葉ノードとなっているものとする。
【００８７】
この図７（ａ）の状態において、葉ノードＤ6にデータを追加すると、図７（ｂ）に示すように、葉ノードＤ6は葉ノードＤ61、Ｄ62に分割され、その親ノードであるインデックスノードＤ5は、エントリ数の最大数を超過するため、インデックスノードＤ51、Ｄ52に分割されることになる。
この例に基づいて、前記したＭＡＲＫ−ＯＰＴ方式、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式及び２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の各方式の動作について具体的に説明する。
【００８８】
《ＭＡＲＫ−ＯＰＴ方式》
まず、図８及び図９を参照して、ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図８及び図９は、ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、図中変数「ｎ」、「ｈ」及び「ｍ」は、図２及び図３のフローチャートに用いたマーク用階層番号、インデックス用階層番号及びマーク値をそれぞれ示している。
【００８９】
図８（ａ）に示すように、ＭＡＲＫ−ＯＰＴ方式は、第１フェーズで、ＩＸラッチカップリングによって、状態Ｐ１から状態Ｐ９として、ルートノードＤ1から葉ノードＤ6の親ノード（インデックスノードＤ5）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ１において、マーク値（ｍ）に“１”を設定し、状態Ｐ５において、マーク値（ｍ）に“３”を設定し、状態Ｐ７において、マーク値（ｍ）に“４”を設定する。そして、状態Ｐ１０に示すように、葉ノードＤ6にＸラッチを設定し、状態Ｐ１１に示すように親ノードのＩＸラッチを解放する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ4及びＤ5にＸラッチの設定が必要）であるため、状態Ｐ１２に示すように葉ノードＤ6のＸラッチを解放し第２フェーズの動作（リスタート）を行う。
【００９０】
続けて、図８（ｂ）に示すように、ＭＡＲＫ−ＯＰＴ方式は、第２フェーズで、ＩＸラッチカップリングによって、状態Ｐ１３から状態Ｐ１７として、ルートノードＤ1から、第１フェーズでマークしたマーク値（ｍ：ここでは“４”）のノードの親ノード（インデックスノードＤ3）まで、順次ＩＸラッチを設定する。そして、親ノード（インデックスノードＤ3）以下の子ノードにＸラッチを設定する。そして、状態Ｐ２０に示すように、インデックスノードＤ4〜Ｄ6にＸラッチを設定した段階で、葉ノードＤ6の更新を行う。そして、葉ノードＤ6の更新（及びインデックスノードＤ5の分割）後、全ラッチを解放し動作を終了する。
なお、この図８（ｂ）は、処理中に上位ノードで更新操作（ＳＭＯ）が発生しなかった場合の動作を示している。この処理中に上位ノードで更新操作（ＳＭＯ）が発生した場合の動作については、図９を参照して説明を行う。
【００９１】
図９（ａ）は、上位ノードで更新操作（ＳＭＯ）が発生した場合におけるリスタートの１回目の動作を示し、図９（ｂ）は、リスタートの２回目の動作を示している。なお、図９では、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになった例を示している。
【００９２】
図９（ａ）に示すように、ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、ＩＸラッチカップリングによって、状態Ｐ２１から状態Ｐ２５として、ルートノードＤ1から、第１フェーズでマークしたマーク値（ｍ：ここでは“４”）のノードの親ノード（インデックスノードＤ3）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ２１において、マーク値（ｍ）に“１”を設定し、状態Ｐ２５において、マーク値（ｍ）に“３”を設定する。
そして、親ノード（インデックスノードＤ3）以下の子ノードにＸラッチを設定する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であるため、状態Ｐ２９に示すようにすべてのラッチを解放し、第２フェーズの動作（リスタート２回目）を行う。
【００９３】
続けて、図９（ｂ）に示しように、ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート２回目で、ＩＸラッチカップリングによって、状態Ｐ３０から状態Ｐ３２として、ルートノードＤ1から、第２フェーズのリスタート１回目でマークしたマーク値（ｍ：ここでは“３”）のノードの親ノード（インデックスノードＤ2）まで、順次ＩＸラッチを設定する。そして、親ノード（インデックスノードＤ2）以下の子ノードにＸラッチを設定する。そして、状態Ｐ３７に示すように、インデックスノードＤ3〜Ｄ6にＸラッチを設定した段階で、葉ノードＤ6の更新を行う。そして、葉ノードＤ6の更新（及びインデックスノードＤ4及びＤ5の分割）後、全ラッチを解放し動作を終了する。
【００９４】
《ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式》
次に、図１０を参照して、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図１０は、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズ及びＳＭＯが発生しなかった場合の第２フェーズの動作は、図８で説明したＭＡＲＫ−ＯＰＴ方式の動作と同じであるため説明を省略する。
ここでは、図１０（ａ）に示すように、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになった例を示している。
【００９５】
ここで、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、ＩＸラッチカップリングによって、状態Ｐ４１から状態Ｐ４５として、ルートノードＤ1から、第１フェーズでマークしたマーク値（ｍ：ここでは“４”）のノードの親ノード（インデックスノードＤ3）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ４１において、マーク値（ｍ）に“１”を設定し、状態Ｐ４５において、マーク値（ｍ）に“３”を設定する。
【００９６】
そして、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式は、子ノード（インデックスノードＤ4）にＸラッチを設定し、親ノード（インデックスノードＤ3）のＩＸラッチを解放した状態Ｐ４７において、すでに葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であると判断する。そこで、状態Ｐ４８に示すようにすべてのラッチを解放し、第２フェーズの動作（リスタート２回目）を行う。
なお、第２フェーズのリスタート２回目の動作は、図９（ｂ）の動作と同じになるため説明を省略する。
【００９７】
《２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式》
次に、図１１を参照して、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図１１は、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズ及びＳＭＯが発生しなかった場合の第２フェーズの動作は、図８で説明したＭＡＲＫ−ＯＰＴ方式の動作と同じであるため説明を省略する。
ここでも、図１０（ａ）と同様に、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになったものとしている。
【００９８】
ここで、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、状態Ｐ６１から状態Ｐ６７に遷移する。なお、この状態Ｐ６１〜状態Ｐ６７は、図１０（ａ）の状態Ｐ４１〜状態Ｐ４７と同じ状態である。
そして、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、状態Ｐ６７において、すでに葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であると判断し、第１フェーズの途中（ステップＳ７：図２参照）にフェーズを切り替えて動作を継続する。
【００９９】
そして、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式は、マーク用階層番号（ｈ）に対応するインデックスノードより下位のインデックスノード（Ｄ5以下）に対してＩＸラッチカップリングを行う。そして、状態Ｐ７１に示すように、葉ノードＤ6にＸラッチを設定し、状態Ｐ７２に示すように親ノードのＩＸラッチを解放する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であるため、状態Ｐ７３に示すように葉ノードＤ6のＸラッチを解放し第２フェーズの動作（リスタート２回目）を行う。
なお、第２フェーズのリスタート２回目の動作は、図９（ｂ）の動作と同じになるため説明を省略する。
【０１００】
《２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式》
次に、図１２を参照して、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の動作を具体的に説明する。図１２は、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態を模式的に示す模式図である。なお、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第１フェーズ及びＳＭＯが発生しなかった場合の第２フェーズの動作は、図８で説明したＭＡＲＫ−ＯＰＴ方式の動作と同じであるため説明を省略する。
ここでも、図１０（ａ）と同様に、他のプロセスの動作によりＳＭＯが発生し、インデックスノードＤ4がフルエントリインデックスノードになったものとしている。
【０１０１】
ここで、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、第２フェーズのリスタート１回目で、状態Ｐ８１から状態Ｐ８８に遷移する。なお、この状態Ｐ８１〜状態Ｐ８８は、図１０（ａ）の状態Ｐ４１〜状態Ｐ４８と同じ状態である。そして、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、状態Ｐ８８以降、第１フェーズに戻って動作を再開（リスタート２回目）する。
【０１０２】
そして、２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、図１２（ｂ）に示すように、第１フェーズを実行し、ＩＸラッチカップリングによって、状態Ｐ８９から状態Ｐ９７に示すように、ルートノードＤ1から葉ノードＤ6の親ノード（インデックスノードＤ5）まで、順次ＩＸラッチを設定する。また、ＩＸラッチ設定中に、フルエントリとなっていないインデックスノードを探索し、マーク値（ｍ）にその状態におけるマーク用階層番号（ｈ）の値を設定する。ここでは、状態Ｐ８９において、マーク値（ｍ）に“１”を設定し、状態Ｐ９３において、マーク値（ｍ）に“３”を設定する。そして、状態Ｐ９８に示すように、葉ノードＤ6にＸラッチを設定し、状態Ｐ９９に示すように親ノードのＩＸラッチを解放する。この状態では、葉ノードＤ6を更新するためのＸラッチが不十分（インデックスノードＤ3〜Ｄ5にＸラッチの設定が必要）であるため、状態Ｐ１００に示すように葉ノードＤ6のＸラッチを解放し第２フェーズの動作（リスタート３回目）を行う。
なお、第２フェーズのリスタート３回目の動作は、図９（ｂ）の動作と同じになるため説明を省略する。
【０１０３】
以上説明したように、ＭＡＲＫ−ＯＰＴ方式、ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式、２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式及び２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式は、第１フェーズによってマークされたノードによってＸラッチの設定範囲を定めるため、葉ノードから順次Ｘラッチの範囲を拡大していくＩＮＣ−ＯＰＴ方式に比べ、リスタートの回数を減らすことができる。
【図面の簡単な説明】
【０１０４】
【図１】本発明に係るディレクトリ分散型記憶装置（木構造型データ記憶装置）の構成を示すブロック図である。
【図２】ＭＡＲＫ−ＯＰＴ方式の第１フェーズの動作を示すフローチャートである。
【図３】ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図４】ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図５】２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図６】２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式の第２フェーズの動作を示すフローチャートである。
【図７】ディレクトリの更新例を示す図であって、（ａ）は更新前、（ｂ）は更新後の状態を示す。
【図８】ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第１フェーズ及び第２フェーズ）を模式的に示す模式図である。
【図９】ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ：リスタート１回目及び２回目）を模式的に示す模式図である。
【図１０】ＩＮＣ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ）を模式的に示す模式図である。
【図１１】２Ｐ−ＩＮＴ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ）を模式的に示す模式図である。
【図１２】２Ｐ−ＲＥＰ−ＭＡＲＫ−ＯＰＴ方式のラッチ状態（第２フェーズ）を模式的に示す模式図である。
【図１３】従来の並列計算機におけるディレクトリ構造の一例であるＦａｔ−Ｂｔｒｅｅ構造を示す図である。
【符号の説明】
【０１０５】
１ ディレクトリ分散型記憶装置（木構造型データ記憶装置）
２ 通信制御部
３ 記憶部
４ 制御部
５ データ操作手段
５１ データ送受信手段
５２ データ参照手段
５３ データ更新手段
６ データ管理手段
６１ データ操作制御手段
６２ データ参照制御手段
６３ データ更新制御手段
６３１ 第１フェーズ実行手段
６３１ａ 第１非フルエントリノード探索手段
６３１ｂ 葉ノードラッチ設定手段
６３１ｃ ノード更新手段
６３２ 第２フェーズ実行手段
６３２ａ 第２非フルエントリノード探索手段
６３２ｂ 子ノードラッチ設定手段（排他ロック設定手段）
６３２ｃ ラッチ有効判定手段（排他ロック有効判定手段）
６３２ｄ ノード更新手段
６３２ｅ ノード再設定手段
７ 制御情報送受信手段
【特許請求の範囲】
【請求項１】
木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、前記エントリ数が予め定めた制限未満である最も下位の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行ステップと、
この第１フェーズ実行ステップで前記葉ノードの更新を行わなかった場合に、前記非フルエントリノード以下のノードに対して排他ロックを設定し、前記葉ノードより上位のノードであって、前記葉ノードの更新に伴い分割対象となる親ノードに排他ロックが設定されている場合に前記葉ノードの更新を行い、分割対象となる前記親ノードに排他ロックが設定されていない場合に、前記非フルエントリノードより上位の非フルエントリノードを探索し、当該非フルエントリノードより下位のノードに排他ロックの範囲を拡大する第２フェーズ実行ステップと、
を含んでいることを特徴とするディレクトリ更新方法。
【請求項２】
木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行ステップと、
前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行ステップとを含み、
この第２フェーズ実行ステップが、
前記第１の非フルエントリノードから前記葉ノードまでの経路において、各ノードに排他ロックを設定する排他ロック設定ステップと、
この排他ロック設定ステップで設定した排他ロックが、前記葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する排他ロック有効判定ステップと、
前記木構造の変化に関連するノードに対して排他ロックが設定されていると判定された場合に、前記葉ノードの更新を行うノード更新ステップとをさらに含み、
前記木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２の非フルエントリノードを前記第１の非フルエントリノードとして、前記第２フェーズ実行ステップを繰り返すことを特徴とするディレクトリ更新方法。
【請求項３】
木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴うディレクトリの更新を行うために、コンピュータを、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段、
前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段として機能させ、
この第２フェーズ実行手段が、
前記第１の非フルエントリノードから前記葉ノードまでの経路において、各ノードに排他ロックを設定する排他ロック設定手段と、
この排他ロック設定手段で設定した排他ロックが、前記葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する排他ロック有効判定手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていると判定された場合に、前記葉ノードの更新を行うノード更新手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２の非フルエントリノードを前記第１の非フルエントリノードとして設定するノード再設定手段と、
を備えていることを特徴とするディレクトリ更新プログラム。
【請求項４】
木構造における各ノードのエントリ数を制限したディレクトリ構造によって、データを記憶する木構造型データ記憶装置において、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段と、
前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段とを備え、
この第２フェーズ実行手段が、
前記第１の非フルエントリノードから前記葉ノードまでの経路において、各ノードに排他ロックを設定する排他ロック設定手段と、
この排他ロック設定手段で設定した排他ロックが、前記葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する排他ロック有効判定手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていると判定された場合に、前記葉ノードの更新を行うノード更新手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２の非フルエントリノードを前記第１の非フルエントリノードとして設定するノード再設定手段と、
を備えていることを特徴とする木構造型データ記憶装置。
【請求項１】
木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、前記エントリ数が予め定めた制限未満である最も下位の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行ステップと、
この第１フェーズ実行ステップで前記葉ノードの更新を行わなかった場合に、前記非フルエントリノード以下のノードに対して排他ロックを設定し、前記葉ノードより上位のノードであって、前記葉ノードの更新に伴い分割対象となる親ノードに排他ロックが設定されている場合に前記葉ノードの更新を行い、分割対象となる前記親ノードに排他ロックが設定されていない場合に、前記非フルエントリノードより上位の非フルエントリノードを探索し、当該非フルエントリノードより下位のノードに排他ロックの範囲を拡大する第２フェーズ実行ステップと、
を含んでいることを特徴とするディレクトリ更新方法。
【請求項２】
木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴う際のディレクトリ更新方法であって、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行ステップと、
前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行ステップとを含み、
この第２フェーズ実行ステップが、
前記第１の非フルエントリノードから前記葉ノードまでの経路において、各ノードに排他ロックを設定する排他ロック設定ステップと、
この排他ロック設定ステップで設定した排他ロックが、前記葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する排他ロック有効判定ステップと、
前記木構造の変化に関連するノードに対して排他ロックが設定されていると判定された場合に、前記葉ノードの更新を行うノード更新ステップとをさらに含み、
前記木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２の非フルエントリノードを前記第１の非フルエントリノードとして、前記第２フェーズ実行ステップを繰り返すことを特徴とするディレクトリ更新方法。
【請求項３】
木構造における各ノードのエントリ数を制限したディレクトリ構造において、前記木構造の変化を伴うディレクトリの更新を行うために、コンピュータを、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段、
前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段として機能させ、
この第２フェーズ実行手段が、
前記第１の非フルエントリノードから前記葉ノードまでの経路において、各ノードに排他ロックを設定する排他ロック設定手段と、
この排他ロック設定手段で設定した排他ロックが、前記葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する排他ロック有効判定手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていると判定された場合に、前記葉ノードの更新を行うノード更新手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２の非フルエントリノードを前記第１の非フルエントリノードとして設定するノード再設定手段と、
を備えていることを特徴とするディレクトリ更新プログラム。
【請求項４】
木構造における各ノードのエントリ数を制限したディレクトリ構造によって、データを記憶する木構造型データ記憶装置において、
最上位層のルートノードから更新対象となる最下位層の葉ノードまでの経路において、排他ロックを設定する旨を示すインテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返し、前記エントリ数が予め定めた制限未満である最も下位の第１の非フルエントリノードを探索するとともに、前記葉ノードに対して排他ロックを設定し、前記葉ノードのエントリ数が予め定めた制限未満である場合に前記葉ノードの更新を行い、前記エントリ数が予め定めた制限を超過する場合に前記葉ノードの更新を行わずに排他ロックを解放する第１フェーズ実行手段と、
前記ルートノードから前記第１の非フルエントリノードの親ノードまでの経路において、前記インテント排他ロックを下位層に対して設定し、その上位層に対する前記インテント排他ロックの設定を解放する手順を下位層に向かって繰り返すとともに、前記エントリ数が予め定めた制限未満である最も下位の第２の非フルエントリノードを探索する第２フェーズ実行手段とを備え、
この第２フェーズ実行手段が、
前記第１の非フルエントリノードから前記葉ノードまでの経路において、各ノードに排他ロックを設定する排他ロック設定手段と、
この排他ロック設定手段で設定した排他ロックが、前記葉ノードの更新に伴う木構造の変化に関連するノードに対して設定されているかどうかを判定する排他ロック有効判定手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていると判定された場合に、前記葉ノードの更新を行うノード更新手段と、
前記木構造の変化に関連するノードに対して排他ロックが設定されていないと判定された場合に、前記第２の非フルエントリノードを前記第１の非フルエントリノードとして設定するノード再設定手段と、
を備えていることを特徴とする木構造型データ記憶装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００６−２２８０６０（Ｐ２００６−２２８０６０Ａ）
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【出願番号】特願２００５−４３０２３（Ｐ２００５−４３０２３）
【出願日】平成１７年２月１８日（２００５．２．１８）
【出願人】（３０４０２１４１７）国立大学法人東京工業大学 (1,821)
【出願人】（０００００４３５２）日本放送協会 (2,206)
【Ｆターム（参考）】
【公開日】平成１８年８月３１日（２００６．８．３１）
【国際特許分類】
【出願日】平成１７年２月１８日（２００５．２．１８）
【出願人】（３０４０２１４１７）国立大学法人東京工業大学 (1,821)
【出願人】（０００００４３５２）日本放送協会 (2,206)
【Ｆターム（参考）】
[ Back to top ]