(57)【要約】【課題】  ノンブロッキング検索演算のためのＲ−tree基盤の同時性制御方法を提供する。【解決手段】  本発明は、空間データベース・システムを利用した多様なサービス環境での空間客体に対する検索の速い応答時間を保障し、検索演算がノードを読んでいる間にも同じノードに更新演算をできるリング・コード・リスト基盤の同時性制御技法と、検索演算がロックやラッチなしに索引を探索できるバージョン基盤の同時性制御技法を含む。本発明によれば、空間データベース・システムの検索演算がブロッキングなしに進行できるため、衝突がしばしば起きる環境での検索演算速度が２倍から４倍向上する特性を持つことになる。  【選択図】  図１
2006350522.tif 000002
【特許請求の範囲】
【請求項１】
ノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法であって、
多次元索引のための同時性制御において、ノード構造の各エントリ間にリング・コード・リスト構造を含み、エントリ挿入、削除、変更時に前記リング・コード・リストを構成する順序を調整して、検索演算がロックやラッチを獲得することなく演算を処理することを特徴とする、ノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法。
【請求項２】
前記エントリ挿入が、ノードの一番目の空きスロットを探す段階；
エントリが挿入される位置の次に位置するエントリと挿入されるエントリのデータリンクを連結する段階；及び、
前記エントリが挿入される位置の直ぐ以前に位置するエントリと挿入されるエントリを連結する段階；からなることを特徴とする、請求項１記載のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法。
【請求項３】
前記エントリ削除が、削除するスロットを探し、削除するエントリに削除表示を記録する段階；及び、
前記削除するエントリの前後のエントリを連結する段階；からなることを特徴とする、請求項１記載のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法。
【請求項４】
索引毎に一つずつ維持され、削除演算をするためにリンクを解除した後、その値が増加されると、その増加された値を該当ノードのエントリに維持するために使用される全域エントリ削除係数；所定演算を遂行する前に最新の全域エントリ削除係数として記録された値であって、索引演算テーブルに維持され、各演算毎に一つずつ維持される地域エントリ削除係数；及び索引が行われている演算を管理する索引演算テーブル；を利用して削除表示されたエントリを再活用するＲ−ｔｒｅｅ基盤の同時性が制御されたエントリ再活用方法において、
エントリの再活用は、所定ノードが削除され、前記ノードに対する全域エントリ削除係数が貯蔵された状態で挿入演算遂行時、前記索引演算テーブルの地域エントリ削除係数中の最小地域エントリ削除係数と前記ノードの全域エントリ削除係数の大きさを比較する段階；及び、
前記全域エントリ削除係数が地域エントリ削除係数より大きければ、前記削除されたノードに直ちに挿入を行わず、挿入されるノードの次のエントリに対して挿入が可能かどうかを検査して、挿入可能なノードに挿入演算を遂行する段階；からなることを特徴とするノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性が制御されたエントリの再活用方法。
【請求項５】
前記エントリの再活用が、いかなる検索演算も該当エントリを読む可能性がないと判断される時、行なわれ得るようにすることを特徴とする、請求項４記載のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性が制御されたエントリの再活用方法。
【請求項６】
バージョンを生成してノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性を制御する方法において、
挿入演算がノードにエントリを挿入する毎に新しいバージョンを生成することなく、分割時にだけ新しいバージョンを生成し、生成されたバージョンを利用して分割が行われることを特徴とするノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法。
【請求項７】
前記挿入演算の遂行時に挿入する必要のある端末ノードが、多くの親ノードを経て、各ノードのＭＢＲがバージョンされているかどうかの有無、または該当ノードがルート・ノードなのかどうかを判断して探し、ノードをスタックに入れながら進行することを特徴とする、請求項６記載のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法。
【請求項８】
前記挿入する必要のある端末ノードを探したが、該当ノードが満杯で、ノードを分割しなければならない場合、新しいノード二個を生成する段階；及び
前記生成されたノードに該当ノードのエントリを分けて持ち、親ノードのＭＢＲを変更する段階；を遂行することを特徴とする、請求項７記載のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法。
【請求項９】
挿入演算中、子ノードのすべてのＭＢＲを含む代表ＭＢＲが変わった時、親ノードでの該当エントリのＭＢＲを変更し、
エントリの変更は、
新しいエントリを割当てる段階；及び
既存のエントリに移行するポインターを前記新しく割当受けたエントリを示すように設定する段階；を遂行して行なわれることを特徴とする、請求項７記載のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法。
【請求項１０】
ノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性が制御された削除方法であって、
エントリを削除することにおいて、削除する必要のあるエントリがある端末ノードを探し、該当端末ノード内でエントリを削除し、前記削除する必要のあるエントリがある端末ノードを、端末ノードまでの経路を貯蔵している削除スタック及び削除するエントリと重なるエントリを貯蔵している検索スタックを同時に使用して、探すことを特徴とする、ノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性が制御された削除方法。
【請求項１１】
前記エントリを削除することにおいて、該当端末ノードの親ノードを探し、親ノードの該当端末ノードを示すエントリを探す段階；
該当エントリを削除して、親ノードが空いているかどうかの有無を検査する段階；
親ノードが空いていない場合、親ノードの代表ＭＢＲの変化を上位ノードに反映させる段階；及び
前記該当の親ノードが空いている場合、該当親ノードを削除して、再活用のための段階；を遂行することを特徴とする、請求項１０記載のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性が制御された削除方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法に関するものである。特に、ノードのエントリ等を連結してノードにエントリを挿入している間にもロックやラッチを獲得することなく検索演算を可能にし、ノード分割が進行中のノードでも検索演算がロックやラッチを獲得することなくノードを探索できるようにし、使用者の質疑処理時、さらに速い応答時間を保障できるようにするノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法に関するものである。
【背景技術】
【０００２】
一般的に多次元索引の同時性制御技法では、検索演算が最小限のロックやラッチを獲得するための研究が進められている。一次元索引の同時性制御技法の中には、検索演算がロックやラッチを獲得することなく索引を探索するＴ−ｔｒｅｅ基盤の同時性制御技法が提案された（非特許文献１及び３）。
【０００３】
従来の多次元索引は、探索経路の変更問題点を持っている。探索経路の変更問題を解決するための従来の同時性制御技法は、二種類の形態に分けられる。
【０００４】
一番目は、自身が探索した経路上の変更を許容しない方法で、二番目は、探索した経路上の変更を許容するが、変更を検出すると、すぐにそれを直す方法である。
【０００５】
一番目の方法の代表的な技法は、ロック結合（Ｌｏｃｋ  Ｃｏｕｐｌｉｎｇ）方式で、現在ノードのロックを獲得してから子ノードに移動する前に現在ノードのロックを解除することなく、子ノードを探索する方法である。
【０００６】
このような方式は、挿入演算時、端末ノードの変更されたＭＢＲ（Ｍｉｎｉｍｕｍ  Ｂｏｕｎｄｉｎｇ  Ｒｅｃｔａｎｇｌｅ）を親ノードに反映しなければならないＲ−Ｔｒｅｅ系列の同時性制御技法には適合しない方式で、更新演算によってロックが長時間維持されるため検索演算の効率を下げるという問題点を持っている。
【０００７】
二番目方法は、子ノードが変更されたことを判断できる方法と誤った経路を正しく直せる方法が必要で、このような代表的な技法は、Ｒｌｉｎｋ−Ｔｒｅｅである。
【０００８】
Ｒｌｉｎｋ−Ｔｒｅｅは、子ノードが変更されたことを判断するためにＬＳＮ（Ｌｏｇｉｃａｌ  Ｓｅｑｕｅｎｃｅ  Ｎｕｍｂｅｒ）を利用して、ノード間リンクを維持することにより誤った経路の問題を解決する。
【０００９】
Ｒｌｉｎｋ−Ｔｒｅｅは、Ｂｌｉｎｋ−Ｔｒｅｅを多次元索引に適用した索引技法で、Ｒ−Ｔｒｅｅはエントリ間の順序がないという特徴を持っているため、Ｂｌｉｎｋ−Ｔｒｅｅの最大キーと同じ役割をＬＳＮが担当する。
【００１０】
親ノードのエントリに各々子ノードのＬＳＮを維持しており、親ノードから読み出したエントリＬＳＮが子ノードに貯蔵されているノードＬＳＮと異なる場合、親ノードから読み出したＬＳＮと会う時まで、同じレベルのリンクを沿うことにより探索経路の変更問題を解決する。
【００１１】
このような方式は、ノードに子ノードのＬＳＮを貯蔵することによりノードのファンアウト（Ｆａｎ−ｏｕｔ）を減少させるという問題があり、端末ノードのＭＢＲが変更された場合、親ノードに反映するためにロック結合方式を利用して反映しなければならないため、検索演算の効率を下げるという問題点を有している。
【００１２】
前記の多次元同時性制御技法は、検索演算がロックやラッチを少なくても一回以上はノードで獲得して索引を探索しなければならず、それによりノードの探索時間が長引くという問題点を有している。
【００１３】
過去の一次元索引のための同時性制御技法の中で、検索演算がロックやラッチを獲得することなく索引を探索できる技法が提案されている（非特許文献２）。
【００１４】
それは、更新演算がノードにエントリを挿入しようとする場合、ノードのエントリを新しいノードに複写した後、複写されたノードにエントリを挿入する方法を使用して検索演算がロックやラッチを獲得しなければならないという問題点を解決した。
【００１５】
しかし、このような技法は、一つの挿入演算によってゴミノードが一つずつ発生するため、多くのゴミノードを削除するための付加的な費用がかかるという問題点があった。
【非特許文献１】ティー．ジェイ．レーマン及びエム．ジェイ．カレイ（Ｔ．Ｊ．Ｌｅｈｍａｎ  ａｎｄ  Ｍ．Ｊ．Ｃａｒｅｙ）著，「ア  スタディ  オブ  インデックス  ストラクチャーズ  フォー  メイン  メモリー  データベース  マネージメント  システムズ（Ａ  ｓｔｕｄｙ  ｏｆ  ｉｎｄｅｘ  ｓｔｒｕｃｔｕｒｅｓ  ｆｏｒ  ｍａｉｎ  ｍｅｍｏｒｙ  ｄａｔａｂａｓｅ  ｍａｎａｇｅｍｅｎｔ  ｓｙｓｔｅｍｓ）」，Ｉｎ  Ｐｒｏｃ．ｏｆ  ｔｈｅ  Ｃｏｎｆ．Ｏｎ  Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａ  Ｂａｓｅｓ，１９８６年，８月，２９４〜３０３頁
【非特許文献２】ジェイ．ニバージェルト、エイチ．ヒンターベルガー、及びケー．シー．セブシック（Ｊ．Ｎｉｅｖｅｒｇｅｌｔ，Ｈ．Ｈｉｎｔｅｒｂｅｒｇｅｒ  ａｎｄ  Ｋ．Ｃ．Ｓｅｖｃｉｋ）著，「ザ  グリッド  ファイル：アン  アダプタブル，シンメトリック  マルチキー  ファイル  ストラクチャー（Ｔｈｅ  Ｇｒｉｄ  Ｆｉｌｅ：Ａｎ  Ａｄａｐｔａｂｌｅ，Ｓｙｍｍｅｔｒｉｃ  Ｍｕｌｔｉｋｅｙ  Ｆｉｌｅ  Ｓｔｒｕｃｔｕｒｅ）」，ＡＣＭ  ＴＯＤＳ，１９８４年，三月，第９巻（Ｎｏ．１）
【非特許文献３】アール．ラストージ、エス．セッシャドリ、ピー．  ボーハノンン、ディー．  レインバウ，エイ．シルバーシャッツ、及びエス．スダーシャン（Ｒ．Ｒａｓｔｏｇｉ，Ｓ．Ｓｅｓｈａｄｒｉ，Ｐ．Ｂｏｈａｎｎｏｎ，Ｄ．Ｌｅｉｎｂａｕｇｈ，Ａ．Ｓｉｌｂｅｒｓｃｈａｔｚ  ａｎｄ  Ｓ．Ｓｕｄａｒｓｈａｎ）著，「ロジッカル  アンド  フィジカル  バージョニング  イン  メイン  メモリー  データベース（Ｌｏｇｉｃａｌ  ａｎｄ  Ｐｈｙｓｉｃａｌ  Ｖｅｒｓｉｏｎｉｎｇ  ｉｎ  Ｍａｉｎ  Ｍｅｍｏｒｙ  Ｄａｔａｂａｓｅｓ）」，Ｉｎ  Ｐｒｏｃ  ｏｆ  ｔｈｅ  Ｉｎｔ．Ｃｏｎｆ．ｏｎ  Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａ  Ｂａｓｅｓ，１９９７年，秋
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、前記のような問題点を解決するためのものである。本発明の目的は、挿入演算がノードにエントリを挿入する度に新しいバージョンを生成することなく、分割時にのみ新しいバージョンを生成して、生成されたバージョンを利用して分割を行って、過度なゴミノードによって生じる問題点を解決できるようにしたノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法を提供することである。
【００１７】
本発明の他の目的は、各ノードのエントリをリング・コード・リストに連結して、ノード探索時にロックやラッチを要請しない構造を使用することにより、検索を主とする空間データベース・システムにおいて、速い応答時間を保障できるようにしたノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法を提供することである。
【課題を解決するための手段】
【００１８】
前記本発明の目的を達成するため、本発明のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法は、多次元索引のためのＲ−ｔｒｅｅ基盤の同時性制御において、ノード構造の各エントリ間にリング・コード・リスト構造を含み、エントリ挿入、削除、変更時に前記リング・コード・リストを構成する順序を調整して、検索演算がロックやラッチを獲得することなく演算を処理することを特徴とする。
【００１９】
また、前記目的を達成するため、本発明のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性が制御されたエントリの再活用方法は、索引毎に一つずつ維持され、削除演算をするためにリンクを解除した後、その値が増加されると、その増加された値を該当ノードのエントリに維持するために使用される全域エントリ削除係数；所定演算を行う前に最新の全域エントリ削除係数として記録された値であって、索引演算テーブルに維持され、各演算毎に一つずつ維持される地域エントリ削除係数；及び索引が行われている演算を管理する索引演算テーブル；を利用して削除表示されたエントリを再活用するＲ−ｔｒｅｅ基盤の同時性が制御されたエントリ再活用方法において、エントリの再活用は所定ノードが削除され、前記ノードに対する全域エントリ削除係数が貯蔵された状態で挿入演算遂行時、前記索引演算テーブルの地域エントリ削除係数中の最小地域エントリ削除係数と前記ノードの全域エントリ削除係数の大きさを比較する段階；及び前記全域エントリ削除係数が、地域エントリ削除係数より大きければ前記削除されたノードに直ぐに挿入を行わず、挿入されるノードの次エントリ等に対して挿入が可能かどうか検査して、挿入可能なノードに挿入演算を遂行する段階；からなることを特徴とする。
【００２０】
また、前記目的を達成するため、本発明のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性制御方法は、バージョンを生成してＲ−ｔｒｅｅ基盤の同時性を制御する方法において、挿入演算がノードにエントリを挿入する毎に新しいバージョンを生成することなく、分割時にだけ新しいバージョンを生成し、生成されたバージョンを利用して分割が行われることを特徴とする。
【００２１】
前記目的を達成するため、本発明のノンブロッキング検索演算のためのＲ−ｔｒｅｅ基盤の同時性が制御された削除方法は、エントリを削除することにおいて、削除する必要のあるエントリがある端末ノードを探して、該当端末ノード内でエントリを削除し、前記削除する必要のあるエントリがある端末ノードを、端末ノードまでの経路を貯蔵している削除スタック及び削除するエントリと重なるエントリを貯蔵している検索スタックを同時に使用して、探すことを特徴とする。
【発明の効果】
【００２２】
本発明は、空間データベース・システムを利用した多様なサービス環境での空間客体に対する検索の速い応答時間を保障し、検索演算がノードを読んでいる間にも同じノードに更新演算をできるリング・コード・リスト基盤の同時性制御技法と検索演算がロックやラッチなしに索引を探索できるバージョン基盤の同時性制御技法を含むため、空間データベース・システムの検索演算がブロッキングなしに進行できるため、衝突がしばしば起きる環境での検索演算が２倍から４倍向上する効果を有する。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の好ましい実施形態を添付された図面を参照してより詳細に説明する。但し、下記の実施形態は本発明を例示するだけのものであり、本発明の内容が下記の実施形態に限定されるものではない。本発明は、図示しないが質疑処理機を通じて入力される使用者の質疑に対してデータベースから質疑結果を検索する検索エンジン及び客体の挿入、削除等の同時性制御機能を遂行するための同時性制御ユニットを具備する空間データベース・システムからなる。
【００２４】
図１は、本発明の空間データベース・システムのためのＲ−Ｔｒｅｅの構成を示した例示図である。図示したように、本発明による空間データベース・システムのためのＲ−Ｔｒｅｅは、非端末ノード１００と端末ノード２００で構成される。非端末ノード１００は、非端末エントリ１０１を含み、端末ノード２００は、端末エントリ２０１を含む。
【００２５】
図２は、図１の非端末ノード１００の構成を示した例示図で、非端末ノード１００は非端末ヘッダー１０３と非端末エントリ１０１で構成され、エントリ間リング・コード・リストで連結された構造である。
【００２６】
図３は、図１の端末ノード２００の構成を示した例示図で、端末ノード２００は端末ヘッダー２０３と端末エントリ２０１で構成され、エントリ間リング・コード・リストで連結された構造である。
【００２７】
上記のような図２と図３の構造で、挿入演算は単位演算を保障する。なぜなら、リンクは、ワードアライン（Ｗｏｒｄ−Ａｌｉｇｎ）に合わせた大きさを有しており、リンクを連結する演算は一つの命令語（Ｉｎｓｔｒｕｃｔｉｏｎ）で可能であるので、リンクを連結する演算中にインタラプトが発生し得ないからである。
【００２８】
図４、図５は、リング・コード・リスト基盤の挿入変更の過程を示した例示図で、図４はエントリを挿入する前のノードの状態を、図５は新しいエントリを挿入した状態を示したものである。
【００２９】
図示したように、最大５個のエントリを持つことができるノードで３個のノードを使用して２個のノードが空いている状態（３００：使用中のノードは、ｓｌｔＦｓｔの連結リストで構成されており、空いているノードは、ｓｌｔＦｒｅｅの連結リストで構成されている）で、まず、挿入するエントリの内容をエントリ４に入れ、エントリ４の次にエントリ３を連結する。その次に、エントリ２の次にエントリ４を連結してエントリ２とエントリ３間に挿入演算をした後、最大５個のエントリを持つことができるノードで４個のノードを使用して１個のノードが空いている状態４００になる。
【００３０】
ｓｌｔＦｓｔは、ノードの一番目のスロット（ｓｌｏｔ）を意味し、ｓｌｔＦｒｅｅはノードの一番目の空きスロットを示す。（１）空きスロットを探した後に、ＯＩＤ（Ｏｂｊｅｃｔ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｎｕｍｂｅｒ）とＭＢＲ（Ｍｉｎｉｍｕｍ  Ｂｏｕｎｄｉｎｇ  Ｒｅｃｔａｎｇｌｅ）を複写する。（２）エントリ３とエントリ４のデータリンクを連結して、（３）最後にエントリ２をエントリ４と連結する。（３）の過程が（２）より先に起きる場合、検索演算はエントリ４を読むことができ、エントリ３へのリンクがまだ連結されていないためエントリ３を読むことができないという問題が生じる。したがって（２）のような過程は（３）の前に遂行されなければならない。即ち、上記の順序で連結することにより、新しいエントリ（Ｅｎｔｒｙ４）をエントリ２とエントリ３間に入れることができ、この順序どおり連結すると、新しいエントリをノードに追加する時も、検索演算は、いかなる支障もなしに検索を遂行できるという長所がある。
【００３１】
図６は、リング・コード・リスト基盤の削除変更の過程を示した例示図で、エントリ２を削除した後のノードの状態を示したものである。即ち、図４の状態から図５の状態と図６の状態になるもので、これによれば、最大５個のエントリを持つことができるノードで３個のノードを使用して２個のノードが空いている状態３００からエントリ２を削除演算した後、最大５個のエントリを有するノードで２個のエントリを使用して３個のノードが空いている状態５００になる。
【００３２】
即ち、（１）削除するスロットを探し、（２）エントリ１とエントリ３を連結する。もし、エントリ２とエントリ３のデータリンクを解除する場合、削除する前にすでにエントリ２を読んでいる検索演算は、エントリ３へ移動できないという問題が生じるため、エントリ２とエントリ３のデータリンクを解除してはならない。前記削除演算は、該当エントリに削除表示だけすることによりなされる。
【００３３】
図７〜図９は、リング・コード・リスト基盤のエントリ再活用の過程を示した例示図で、前記図６により削除表示をしておいたエントリの再使用に対する内容である。図７〜図９によると、エントリ削除係数（ＥＤＳＮ：Ｅｎｔｒｙ  Ｄｅｌｅｔｅ  Ｓｅｑｕｅｎｃｅ  Ｎｕｍｂｅｒ）を利用した削除後挿入に対する過程を示している。
【００３４】
エントリ再使用の根本的な問題は、削除されたエントリに対して検索演算が読んでいるかどうか分からないために、削除されたエントリを再使用できないということである。したがって、本発明では削除されたエントリに検索演算が読んでいないことを保障するための方法を考慮する。
【００３５】
エントリ削除係数をノードの各エントリに維持して、索引に遂行されている演算を管理する索引演算テーブル（ＩＯＴ：Ｉｎｄｅｘ  Ｏｐｅｒａｔｉｏｎ  Ｔａｂｌｅ）を利用することにより、このような問題を解決する。
【００３６】
ＥＤＳＮは、順次的に増加する値であり、全域エントリ削除係数（Ｇ−ＥＤＳＮ：Ｇｌｏｂａｌ  ＥＤＳＮ）と地域エントリ削除係数（Ｌ−ＥＤＳＮ：  Ｌｏｃａｌ  ＥＤＳＮ）がある。Ｇ−ＥＤＳＮは、索引毎に一つずつ維持され、削除演算をするためにリンクを解除した後、Ｇ−ＥＤＳＮを増加して、増加されたＧ−ＥＤＳＮをエントリに貯蔵するために使用する。Ｌ−ＥＤＳＮは、演算を遂行する前に最新のＧ−ＥＤＳＮを記録しておいた値である。Ｌ−ＥＤＳＮは、ＩＯＴに維持され、各演算毎に一つずつ維持される。
【００３７】
ＩＯＴで管理される演算のライフタイム（Ｌｉｆｅｔｉｍｅ）は、一つのノードを検索して、終了される時点までで、次のノードを探索するためには新しいＧ−ＥＤＳＮをＩＯＴのＬ−ＥＤＳＮに複写しなければならない。これは、演算のライフタイムを非常に短くすることによりエントリ再使用を早めるためである。
【００３８】
検索演算を除外した更新演算のＬ−ＥＤＳＮは、∞である。Ｌ−ＥＤＳＮは、挿入演算が遂行される時、挿入されるエントリのＥＤＳＮを確認して、ＥＤＳＮより小さいＬ−ＥＤＳＮを持った演算がＩＯＴに存在する場合、そのエントリは検索演算により検索されているエントリであるかも分からないため、そのエントリを挿入しないように使用される。各エントリのＥＤＳＮ初期値は、−∞である。
【００３９】
図７で初期Ｇ−ＥＤＳＮは、５で、３個の演算が同時に実行されている。Ｏ１は、Ｌ−ＥＤＳＮ値が５で、検索演算をする。Ｏ２は削除演算をし、Ｏ３は挿入演算をし、Ｏ１がＲ２に対してキーを比較する時点であると仮定する。ここで、Ｏ２がＲ２を削除すると、まずＲ１からＲ２へのリンクを解除した後、Ｒ２のＥＤＳＮは、Ｇ−ＥＤＳＮを増加させた値の６となって貯蔵される。
【００４０】
図８は、Ｒ２が削除され、ＥＤＳＮが貯蔵された様子を示す。その次に、図８の状態で挿入演算が遂行されると、ｓｌｔＦｒｅｅはＲ２を示すためにＲ２に挿入しようとする。しかし、ＩＯＴのＬ−ＥＤＳＮ中の最小Ｌ−ＥＤＳＮの５よりＲ２のＥＤＳＮの６が大きいので、Ｒ２に挿入をしてはならない。
【００４１】
ＥＤＳＮが小さいということは、演算中に誰かが削除演算にリンクを解除する前に、そのエントリを検索していたかもしれないという可能性を持っているため、そのエントリに挿入をしてはならないのである。したがって、図９のように各エントリは連結される。Ｏ１が演算を終了した以後に挿入演算を遂行するなら、Ｒ２にエントリが挿入され得る。
【００４２】
図１０は、バージョン基盤の検索（ＦｉｎｄＦｉｒｓｔ）の動作の流れを示した例示図で、検索（ＦｉｎｄＦｉｒｓｔ）は質疑範囲に属する一番目のエントリを探す過程である。
【００４３】
ルート・ノードをスタックにプッシュ（ｐｕｓｈ）してエントリを探す過程を通じて一番目のエントリを探し出す。即ち、ルート・ノードを検索スタックに入れた後（段階７０１）、検索スタックが空いているかを調査し（段階７０２）、検索スタックが空いていれば終了し、空いていなければ検索スタックからアイテムを一つ取り出す（段階７０３）。
【００４４】
以後、ＲＩＤ（Ｒｅｃｏｒｄ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｎｕｍｂｅｒ）かどうかを調査して（段階７０４）、ＲＩＤと判断されると結果を返還して（段階７０８）、段階（段階７０２）へ進行する。ＲＩＤでないと判断されると、検索しようとするＭＢＲと現在エントリのＭＢＲが重なるかを調査し（段階７０６）、重ならないものと判断されると、他のエントリへ移動し（段階７０５）、再び段階（７０６）を遂行する。重なるものと判断されると、検索スタックにアイテム一つを挿入して（段階７０７）、前記段階（７０５）へ進行する。
【００４５】
図１１は、バージョン基盤の検索（ＦｉｎｄＮｅｘｔ）の動作の流れを示した例示図で、検索（ＦｉｎｄＮｅｘｔ）はスタックが空いている時まで反復しながらノードを巡廻する過程を遂行する。即ち、検索スタックが空いているか調査し（段階８０１）、空いている場合は終了して、空いていない場合、検索スタックにアイテムを一つ取り出す（段階８０２）。
【００４６】
そして、ＲＩＤかどうかを判断し（段階８０３）、ＲＩＤなら結果を返還して（段階８０７）、段階（８０１）へ進行し、ＲＩＤでなければ、検索しようとするＭＢＲと現在エントリのＭＢＲが重なるかを判断し（段階８０５）、重ならないものと判断されると、他のエントリへ移動し（段階８０４）、再び段階（８０５）を遂行し、重なるものと判断されると、検索スタックにアイテム一つを挿入して（段階８０６）、前記段階（８０４）へ進行する。
【００４７】
図１２は、バージョン基盤の挿入（Ｉｎｓｅｒｔ）の動作の流れを示した例示図で、挿入（Ｉｎｓｅｒｔ）は、客体を挿入する端末ノードを探す挿入（ＦｉｎｄＬｅａｆ）過程と端末ノードに客体を挿入する過程に分けて考えられる。
【００４８】
端末ノード分割で返還されるようにするリトライ（Ｒｅｔｒｙ）値の初期値をツルー（Ｔｒｕｅ）に設定した後（段階９０１）、リトライ値がトゥルー（Ｔｒｕｅ）である場合、挿入を終了し、フォールス（Ｆａｌｓｅ）である場合（段階９０２）、リトライをフォールスに設定（段階９０３）した後、挿入（ＦｉｎｄＬｅａｆ）（段階９０４）を遂行する。
【００４９】
挿入（ＦｉｎｄＬｅａｆ）過程中に使用した挿入スタックからアイテムを一つ取り出し、そのアイテムを端末ノードとする（段階９０５）。この端末ノードに挿入を遂行しなければならないので、ノードが満杯かどうか判断をした後（段階９０６）、満杯である場合、段階（９０７）を遂行し、そうでなければ、端末ノードに直接エントリを挿入する（段階９０８）。
【００５０】
まず、分割が起きた場合（段階９０７）、その結果をリトライに設定した後、もし、この値がトゥルーである場合（段階９１１）、この端末ノードをバージョン表示して、ゴミ収集器に追加して（段階９１２）、そうでなければ、端末ノードのロックを解除して（段階９１３）、終了する。
【００５１】
次に、端末ノードに直ぐに挿入をした場合（段階９０８）、挿入の代表ＭＢＲが変更された場合、挿入（ＵｐｄａｔａＰａｒｅｎｔ）（段階９１０）を遂行し、そうでなければ、端末ノードのロックを解除（段階９１３）して、終了する。
【００５２】
図１３は、バージョン基盤の挿入（ＦｉｎｄＬｅａｆ）の動作の流れを示した図で、挿入演算遂行時挿入しなければならない端末ノードを探す例示図である。
【００５３】
図１３によると、挿入（段階９０４）は、非端末ノードのＭＢＲを最小に増やせるエントリを探しながら（段階１００６）、端末ノード方向に索引を探索し、端末ノードに会えば（段階１００３）、函数の探索を終了する。
【００５４】
挿入（段階９０４）では、端末ノードを探すために探索しながら、探索された非端末ノードと端末ノードをスタックに積まれた過程が遂行される。これは挿入演算時、親ノードのＭＢＲを拡張したり（段階９１０）、ノードの分割が起きる場合に（段階９０７）使用される。
【００５５】
段階１００４のように、万一、ノードがバージョンされていた場合とは、ノードのロックを獲得するために待つ間に、他の演算によりノードが分割される場合である。このような場合は、スタックを利用し（１００７）、親ノードを再び探索することになる。
【００５６】
図１４は、バージョン基盤の挿入（ＵｐｄａｔｅＰａｒｅｎｔ）の動作の流れを示した図で、図１２で挿入演算により親ノードのＭＢＲを変更する必要がある場合、スタックから親ノードを一つずつ取り出して変更することを示したものである。
【００５７】
図１４によると、挿入演算時、親ノードのＭＢＲを拡張する場合（段階９１０）の過程が示されている。挿入（ＵｐｄａｔｅＰａｒｅｎｔ）は、スタックを利用して親ノード方向に移動しながら（段階１１０２）、子ノードのノードＭＢＲが変更された場合、親ノードのエントリＭＢＲを変更させる作業（段階１１０４）を遂行する。
【００５８】
万一、スタックに貯蔵されている親ノードがバージョンされた場合、挿入（ＦｉｎｄＬａｔｅｓｔＮｏｄｅ）函数を呼出して、バージョンされているノードのための最新バージョンを探す（段階１１０３）。最新バージョンを探した後、挿入（ＵｐｄａｔｅＥｎｔｒｙ１）（段階１１０４）を利用してノードのエントリＭＢＲを変更する。
【００５９】
挿入（ＵｐｄａｔｅＰａｒｅｎｔ）は、エントリ再使用問題によってノードに空きエントリがあるが、挿入をできない場合が発生し得る。このような場合は、暫時、他の演算に制御を移して、再びエントリを再使用できるかどうか再度試みが終わるまで待つ。
【００６０】
検索演算は、ロックやラッチを要請しない演算であり、またＩＯＴに記録される検索演算のＬ−ＥＤＳＮはとても短いライフタイムを持つため、挿入（ＵｐｄａｔｅＰａｒｅｎｔ）は、長時間待たないでエントリを再使用できる。
【００６１】
図１５は、バージョン基盤の挿入（ＦｉｎｄＬａｔｅｓｔＮｏｄｅ）の動作の流れを、図１６は図１５の理解を助けるための図面を示したものである。
【００６２】
子ノードの単純挿入または挿入後、分割が起きた場合、親ノード内の子ノードの該当エントリを変更する必要があるが、ここで、スタックに貯蔵され、かつ親であると分かっているノードが分割され、該当エントリが横の他のノードに移っていった場合に備えて適切なノードを探す過程が行われる。
【００６３】
即ち、挿入（ＦｉｎｄＬａｔｅｓｔＮｏｄｅ）函数は、ポインターのエントリを含むバージョンになっていない最新ノードを探す過程を遂行する。図１６で、Ｎ３がバージョンされている場合、探さなければならない検索空間（Ｓｅａｒｃｈ  Ｓｐａｃｅ）は、Ｎ５とＮ６であるため、Ｎ３の右側リンクに沿ってＮ５とＮ６へ移動しながら探そうとするエントリを持った最新バージョンを探す。
【００６４】
図１７及び図１８は、バージョン基盤の挿入（ＳｐｌｉｔＬｅａｆＮｏｄｅ）の動作の流れを表した図で、挿入するのに適切な端末ノードを探したが、該当ノードが満杯でノードを分割しなければならない場合で、新しいノードニ個を生成して、該当ノードのエントリを分けて持ち、親ノードのＭＢＲを変更する必要がある場合に対する処理も含む。
【００６５】
図１７、１８によれば、挿入（ＳｐｌｉｔＬｅａｆＮｏｄｅ）は、端末ノードを分割する過程である。基本的に分割過程は、分割するノードをそのまま置いて新しいノード二個を生成して、分割される前のノードの状態を変更することなく維持するバージョン基盤の分割技法を使用する。
【００６６】
分割するノードが端末ノードなら、分割後、適当なノードに長方形（Ｒｅｃｔ：Ｒｅｃｔａｎｇｌｅ）を挿入することになる。挿入（ＳｐｌｉｔＬｅａｆＮｏｄｅ）は、ノードの左側ノードと右側ノードに対して各々ロックを獲得した後、開始する（段階１３０７、１３０８）。ノードのロックは、常に左側から右側方向の順序で獲得する。
【００６７】
万一、分割するノードが端末ノードでない場合、ロックを獲得する間、他の演算との交錯状態（Ｄｅａｄｌｏｃｋ）が発生し得る。したがって、段階１３０３と同様にノードのロックを解いて、左側から右側方向にロックを獲得する。
【００６８】
ロックを獲得後に該当ノードがバージョンされているかどうか確認する必要があり（段階１３０５）、バージョンされていた場合、挿入過程を再び開始する。これは、ノードのロックを解いて（段階１３０６）、ノードと連結された左側ノードを探した後、再びノードのロックを獲得する場合と、ノードがバージョンされて、他の挿入演算によってノードが分割された場合とがある。
【００６９】
したがって、該当ノードを分割してはならない場合、再び挿入演算を遂行する。新しいノード二個を生成して（段階１３１５）、互いのリンクを連結して（段階１３１７）、二個のノード中最も適切なノードに長方形（Ｒｅｃｔ）を挿入する（段階１３１８）。その後、挿入演算で残る処理は、親ノードに新しく生じたノードのポインターとＭＢＲを挿入することである（段階１３２６）。
【００７０】
万一、親ノードに空きエントリがない場合、親ノードを挿入（ＳｐｌｉｔＩｎｔｅｒｎａｌＮｏｄｅ）を利用して分割し（段階１３３３）、そうでない場合、親ノードにエントリを挿入し、万一、親ノードのＭＢＲが変更された場合（段階１３２７）、挿入（ＵｐｄａｔｅＰａｒｅｎｔ）（段階１３２８）を呼出すことにより、親ノードを示す上位ノードのエントリＭＢＲを変更する必要がある。
【００７１】
段階（１３２０）でスタックが空いているということは、ノードがルート・ノードであることを表しているので、新しいルート・ノードのためのノードを生成した後（段階１３２２）、ルート・ノード・ポインターを新しいルート・ノードに替えて、既存ルート・ノードはバージョンされたことを表示する（段階１３２４）。スタックが空いていない場合、親ノードにエントリを挿入する必要があるので、スタックにノードを一つポップ（ｐｏｐ）して、ポップしたノードの最新ノードを親に貯蔵する（段階１３２１）。
【００７２】
探すノードに空きエントリがあれば挿入して（段階１３２６）、なかったなら、該当ノードを分割する（段階１３３３）。最後に段階（１３２９）のように分割する前のノードが示す左側と右側ノードを連結し、分割されたノードの右側リンクを新しく生成した左側ノードに連結することにより（段階１３２９）、挿入（ＦｉｎｄＬａｔｅｓｔＮｏｄｅ）時にノードの最新バージョンを探せるようにする。
【００７３】
図１９及び図２０は、バージョン基盤の挿入（ＳｐｌｉｔＩｎｔｅｒｎａｌＮｏｄｅ）の動作の流れを示した図で、端末ノードではない非端末ノードを分割しなければならない場合を示したものである。
【００７４】
図１９、図２０によると、分割するノードが非端末ノードなら、分割後、新しく生成した二個の子ノードのためのエントリ二個を挿入することになる。すべての過程は、挿入（ＳｐｌｉｔＬｅａｆＮｏｄｅ）と類似で、ノードにエントリを挿入する部分だけが異なる。
【００７５】
挿入（ＳｐｌｉｔＬｅａｆＮｏｄｅ）は、挿入するのに適当なノードを探してエントリを挿入するが、挿入（ＳｐｌｉｔＩｎｔｅｒｎａｌＮｏｄｅ）は新しく生成されたノードの中に分割されたノードが入っているノードを探し、探したノードに二個の子ノードを挿入する演算をする（段階１４１８）。
【００７６】
図２１は、バージョン基盤の挿入（ＵｐｄａｔｅＥｎｔｒｙ１）の動作の流れを示したもので、挿入演算過程中、子ノードのすべてのＭＢＲを含む代表ＭＢＲが変わった時、親ノードで該当エントリのＭＢＲを変更する状態を示したものである。エントリの変更は、新しいエントリ割当を受けた既存のエントリに移行するポインターを新しく割当受けたエントリを示すよう設定することによりなされる。
【００７７】
図２２によれば、ノードのエントリに対する変更演算は、エントリのＭＢＲを変更したり、エントリのノードポインターを変更する演算である。検索演算がラックやラッチなしにノードを探索しながら変更演算がエントリの内容を変更することは、単位演算を保障することができないため本発明では、変更演算をエントリの挿入演算と削除演算で遂行する方法を使用する。
【００７８】
段階（１５０２）で挿入する必要のあるエントリがＲ４で、削除する必要のあるエントリがＲ２とすると、Ｒ４とＲ３のリンクをまず図２２のように連結し（１）、次にＲ１とＲ４を連結することにより（２）、検索演算がいかなる問題もなしに検索できるように保障する。
【００７９】
図２３は、バージョン基盤の挿入（ＵｐｄａｔｅＥｎｔｒｙ２）の動作の流れを示した図で、挿入演算により端末ノードが分割されて二個の子ノードができ、親ノードに二個のエントリを一度に挿入する必要のある場合に対する例示図である。
【００８０】
図２４によれば、既存の分割技法では新しい一つのエントリだけを挿入する過程で挿入（ＵｐｄａｔｅＥｎｔｒｙ２）を完了できたが、本発明の分割技法では新しいノードが二個作られるために、分割する前のノードを示していたエントリを新しいノードを示すエントリに変更すると同時に、新しいエントリを挿入する演算が単位演算で遂行されなければならない。
【００８１】
このような演算を二個の新しいエントリの挿入（段階１６０２）と既存のエントリの削除演算（段階１６０３）で処理する。段階１６０１〜１６０３は、このような過程を説明する。
【００８２】
図２４で挿入する必要のあるエントリがＲ４とＲ５で、削除する必要のあるエントリがＲ２とすると、Ｒ４とＲ５（１）、Ｒ３のリンクをまず連結（２）して、次にＲ１とＲ４を連結（３）することにより検索演算がいかなる問題もなしに検索できるように保障する。
【００８３】
図２５は、バージョン基盤の削除（Ｄｅｌｅｔｅ）の動作の流れを示した例示図で、削除する必要のあるエントリが存在する適当な端末ノードを探し、該当ノード内でエントリを削除する過程であり、これは適当な端末ノードを探す過程で検索スタックと削除スタックを同時に使用する方法を記述しており、該当エントリの削除時、ノード内に残るエントリが無くなる場合に関する処理である。
【００８４】
図２５によると、削除演算は二個のスタックを利用する。検索スタックは、削除するエントリを探すためのスタックで、削除スタックはノードでエントリを削除した後、ノードのＭＢＲが変更された場合に親ノードに反映させるために使用する。
【００８５】
削除演算は、削除するエントリが存在する端末ノードを探した後（段階１７１５）、該当エントリを削除（段階１７０４）する。エントリを削除したノードのＭＢＲが縮小されると（段階１７０８）、親ノードのエントリＭＢＲを変更する演算をする（段階１７０９）。
【００８６】
万一、ノードのエントリが、すべて削除された場合、ノードを削除し、削除されたノードを示す親ノードのエントリを削除する（段階１７０６）。しかし、ノードの削除は、検索演算が削除するノードを検索しているかも分からないので、直ちにノードを削除してはならない。
【００８７】
削除演算は、削除する客体と客体のＭＢＲを利用して削除するエントリを探す。削除演算での端末ノードを探すためにスタックを使用する方法は、検索演算で検索しようとするエントリを探すためにスタックを使用する方法と、挿入演算での挿入しようとする端末ノードを探すためにスタックを使用する方法とを統合した方法と似ている。
【００８８】
これは、Ｒ−Ｔｒｅｅ構造上、ノードのＭＢＲが重なっている場合が発生し得るために色々な端末ノードを探索してこそ、削除したエントリを探すことができる。したがって、本発明では二個のスタックを利用して削除するエントリを探す。検索スタックをポップする毎に、削除スタックにプッシュ（ｐｕｓｈ）する方法を使用する。
【００８９】
しかし、削除スタックは、端末ノードまでの経路を貯蔵するためのスタックであるので、同じレベルのノードが削除スタック内に数個存在してはならない。したがって、削除スタックにプッシュする時は、削除スタックに入っているノードのレベルを検査する必要がある（段階１７１２）。
【００９０】
ノードのレベルは、索引の深さが増加する度に一つずつ増加する。即ち、ルートが最も小さい値を有し、端末ノードが最も大きい値を有する。万一、削除スタック内に検索スタックでポップしたノードのレベルより高いレベルがあれば、低いレベルが出るまで削除スタックをポップして、このような問題を解決する（段階１７１３）。段階１７１５で検索スタックをポップしたノードが端末ノードなら、削除スタックでノードをポップし（段階１７１８）、端末ノードへの経路で該当ノードを除去し、削除するエントリが該当ノードにあるかどうか確認する（段階１７１９）。
【００９１】
万一、削除するエントリを探せない場合には、検索スタックを利用し（段階１７２２）、次のノードを探索することになる。結局、削除する端末ノードを探すようになれば、削除スタックには端末ノードを除外した端末ノードまでの経路が残ることになる。
【００９２】
段階１７０４でエントリを削除してからノードにエントリが一つも無い場合は、ノードを削除しなければならず、また親ノードの削除するノードを示すエントリを削除しなければならない（段階１７０６）。
【００９３】
図２６は、バージョン基盤の削除（ＤｅｌｅｔｅＰａｒｅｎｔ）の動作の流れを示した例示図である。
【００９４】
図２６によれば、前記削除演算（Ｄｅｌｅｔｅ）でエントリを削除してから（段階１７０４）、ノードにエントリが一つも無い場合、削除（ＤｅｌｅｔｅＰａｒｅｎｔ）函数を利用して親ノードのエントリを削除する。エントリが一つでも残っている場合は、親ノードのＭＢＲだけを変更する（段階１８１０）。
【００９５】
削除（ＤｅｌｅｔｅＰａｒｅｎｔ）で削除するエントリを持った親ノードを探す過程は、挿入（ＵｐｄａｔｅＰａｒｅｎｔ）で変更するエントリを探す親ノードを探す方法と同一である。エントリを探したら、エントリを削除し（段階１８０４）、同一な方法で親ノードに適用することになる。
【００９６】
上述したように、本発明の好ましい実施形態を参照して説明したが、該当技術分野の熟練した当業者は、下記の特許請求の範囲に記載された本発明の思想及び領域から外れることのない範囲内で、本発明を多様に修正または変形して実施できる。
【産業上の利用可能性】
【００９７】
以上、説明したように本発明は、多次元索引が更新演算よりは検索演算の頻度が高いという特性を考慮して、検索演算がいかなるロックやラッチにもかかることなく索引を探索できる同時性制御技法であり、また検索演算がノードの探索中にも更新演算ができるようにノード内のエントリをリング・コード・リストに連結して、ノード分割を遂行する場合、バージョン基盤の分割技法を使用して検索演算が分割されるノードにロックやラッチを獲得することなくノードを探索できるようにすることにより空間データベース・システムを利用した多様な種類の地理情報サービス等をインターネットを通して提供されている環境で、サービスが空間検索質疑要請に対してさらに速い応答時間を保障することが可能になる。
【図面の簡単な説明】
【００９８】
【図１】本発明の空間データベース・システムのためのＲ−Ｔｒｅｅの構成を示した例示図である。
【図２】図１で非端末ノードの構成を示した例示図である。
【図３】図１で端末ノードの構成を示した例示図である。
【図４】リング・コード・リスト基盤の挿入変更の過程を示した例示図である。
【図５】リング・コード・リスト基盤の挿入変更の過程を示した例示図である。
【図６】リング・コード・リスト基盤の削除変更の過程を示した例示図である。
【図７】リング・コード・リスト基盤のエントリ再活用の過程を示した例示図である。
【図８】リング・コード・リスト基盤のエントリ再活用の過程を示した例示図である。
【図９】リング・コード・リスト基盤のエントリ再活用の過程を示した例示図である。
【図１０】バージョン基盤の検索（ＦｉｎｄＦｉｒｓｔ）の動作の流れを示した例示図である。
【図１１】バージョン基盤の検索（ＦｉｎｄＮｅｘｔ）の動作の流れを示した例示図である。
【図１２】バージョン基盤の挿入（ｉｎｓｅｒｔ）の動作の流れを示した例示図である。
【図１３】バージョン基盤の挿入（ＦｉｎｄＬｅａｆ）の動作の流れを示した例示図である。
【図１４】バージョン基盤の挿入（ＵｐｄａｔｅＰａｒｅｎｔ）の動作の流れを示した例示図である。
【図１５】バージョン基盤の挿入（ＦｉｎｄＬａｔｅｓｔＮｏｄｅ）の動作の流れを示した例示図である。
【図１６】バージョン基盤の挿入動作の流れを示した例示図である。
【図１７】バージョン基盤の挿入（ＳｐｌｉｔＬｅａｆＮｏｄｅ）の動作の流れを示した例示図である。
【図１８】バージョン基盤の挿入動作の流れを示した例示図である。
【図１９】バージョン基盤の挿入（ＳｐｌｉｔＩｎｔｅｒｎａｌＮｏｄｅ）の動作の流れを示した例示図である。
【図２０】バージョン基盤の挿入動作の流れを示した例示図である。
【図２１】バージョン基盤の挿入（ＵｐｄａｔｅＥｎｔｒｙ１）の動作の流れを示した例示図である。
【図２２】バージョン基盤の挿入動作の流れを示した例示図である。
【図２３】バージョン基盤の挿入（ＵｐｄａｔｅＥｎｔｒｙ２）の動作の流れを示した例示図である。
【図２４】バージョン基盤の挿入動作の流れを示した例示図である。
【図２５】バージョン基盤の削除（Ｄｅｌｅｔｅ）の動作の流れを示した例示図である。
【図２６】バージョン基盤の削除（ＤｅｌｅｔｅＰａｒｅｎｔ）の動作の流れを示した例示図である。
【符号の説明】
【００９９】
１００：非端末ノード                    １０１：非端末ノードのエントリ
１０３：非端末ヘッダー                  ２００：端末ノード
２０１：端末ノードのエントリ            ２０３：端末ヘッダー
【図１】
2006350522.tif 000003
【図２】
2006350522.tif 000004
【図３】
2006350522.tif 000005
【図４】
2006350522.tif 000006
【図５】
2006350522.tif 000007
【図６】
2006350522.tif 000008
【図７】
2006350522.tif 000009
【図８】
2006350522.tif 000010
【図９】
2006350522.tif 000011
【図１０】
2006350522.tif 000012
【図１１】
2006350522.tif 000013
【図１２】
2006350522.tif 000014
【図１３】
2006350522.tif 000015
【図１４】
2006350522.tif 000016
【図１５】
2006350522.tif 000017
【図１６】
2006350522.tif 000018
【図１７】
2006350522.tif 000019
【図１８】
2006350522.tif 000020
【図１９】
2006350522.tif 000021
【図２０】
2006350522.tif 000022
【図２１】
2006350522.tif 000023
【図２２】
2006350522.tif 000024
【図２３】
2006350522.tif 000025
【図２４】
2006350522.tif 000026
【図２５】
2006350522.tif 000027
【図２６】
2006350522.tif 000028