【手続補正書】
【提出日】平成21年12月25日(2009.12.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データベースのインデックスキーの旧データに対して該旧データと置き換えられる新しいインデックスキーの新データが供給されたときに、前記インデックスキーの更新を行うデータベースのインデックスキー更新方法において、
前記旧データあるいは新データのインデックスキーを、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、
カップルドノードツリーのリーフノードのインデックスキーとして格納した、差分ツリーを取得する差分ツリー取得ステップと、
前記差分ツリーのルートノードを前記検索開始ノードとして前記新データあるいは旧データの全てのインデックスキーを検索キーとして検索を行い、検索キーと一致した前記検索結果キーであるインデックスキーは差分ツリーから削除し、前記検索結果キーであるインデックスキーと一致しない検索キーを差分データの挿入キーあるいは削除キーとし、前記新データあるいは旧データの全てのインデックスキーによる検索が終了した後に前記差分ツリーに削除されずに残ったインデックスキーを差分データの削除キーあるいは挿入キーとして差分データを作成する差分データ作成ステップと、
前記旧データのインデックスキーをリーフノードのインデックスキーとして格納した前記カップルドノードツリーである更新ツリーを取得する更新ツリー取得ステップと、
前記差分データから取り出した削除キーを前記更新ツリーから削除し、前記差分データから取り出した挿入キーを前記更新ツリーに挿入することにより新データのインデックスキーをリーフノードのインデックスキーとして格納した新データカップルドノードツリーを作成し、該新データカップルドノードツリーに基づいて、前記旧データを前記新データに更新する新旧インデックスキー更新ステップと、
を備えることを特徴とするインデックスキー更新方法。
【請求項２】
データベースのインデックスキーの旧データに対して該旧データと置き換えられる新しいインデックスキーの新データが供給されたときに、前記インデックスキーの更新を行うデータベースのインデックスキー更新に用いる前記旧データと前記新データの差分データ作成方法において、
前記旧データあるいは新データのインデックスキーを、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、
カップルドノードツリーのリーフノードのインデックスキーとして格納した、差分ツリーを取得する差分ツリー取得ステップと、
前記差分ツリーのルートノードを前記検索開始ノードとして前記新データあるいは旧データの全てのインデックスキーを検索キーとして検索を行い、検索キーと一致した前記検索結果キーであるインデックスキーは差分ツリーから削除し、前記検索結果キーであるインデックスキーと一致しない検索キーを差分データの挿入キーあるいは削除キーとし、前記新データあるいは旧データの全てのインデックスキーによる検索が終了した後に前記差分ツリーに削除されずに残ったインデックスキーを差分データの削除キーあるいは挿入キーとして差分データを作成する差分データ作成ステップと、
を備えることを特徴とする差分データ作成方法。
【請求項３】
請求項２記載の差分データ作成方法において、
前記カップルドノードツリーは、配列に記憶され、前記リンク先のノード対の代表ノードの位置を示す情報は、そのノードが格納された前記配列の配列要素の配列番号であることを特徴とする差分データ作成方法。
【請求項４】
請求項３記載の差分データ作成方法において、
前記差分ツリー取得ステップは、前記旧データあるいは新データから最初に取り出したインデックスキーを含むリーフノードを該差分ツリーのルートノードとした後、それ以後前記旧データあるいは新データから取り出した前記インデックスキーを前記検索キーとして該差分ツリーから該当するリーフノードを検索するとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードが格納された配列要素の配列番号をスタックに順次格納し、前記検索キーと前記該当するリーフノードに含まれるインデックスキーの間で大小比較とビット列比較を行い、ビット列比較で異なるビット値となる先頭のビット位置と前記スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係により挿入されるインデックスキーを含むリーフノードともう一方のノードからなるノード対の挿入位置を決定し、前記大小関係により挿入するインデックスキーを含むリーフノードを前記挿入されるノード対のどちらのノードとするかを決定するインデックスキーの挿入処理を繰り返すものであることを特徴とする差分データ作成方法。
【請求項５】
データベースのインデックスキーの旧データと該旧データと置き換えられる新しいインデックスキーの新データの差分データを用いて前記インデックスキーの更新を行うインデックスキーの差分データ更新方法において、
前記旧データのインデックスキーを、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、
カップルドノードツリーのリーフノードのインデックスキーとして格納した前記カップルドノードツリーである更新ツリーを取得する更新ツリー取得ステップと、
前記旧データあるいは新データのインデックスキーを前記カップルドノードツリーのリーフノードのインデックスキーとして格納した差分ツリーのルートノードを前記検索開始ノードとして前記新データあるいは旧データの全てのインデックスキーを検索キーとして検索を行い、検索キーと一致した前記検索結果キーであるインデックスキーは差分ツリーから削除し、前記検索結果キーであるインデックスキーと一致しない検索キーを差分データの挿入キーあるいは削除キーとし、前記新データあるいは旧データの全てのインデックスキーによる検索が終了した後に前記差分ツリーに削除されずに残ったインデックスキーを前記差分データの削除キーあるいは挿入キーとして作成した差分データから取り出した削除キーを前記更新ツリーから削除し、前記差分データから取り出した挿入キーを前記更新ツリーに挿入することにより新データのインデックスキーをリーフノードのインデックスキーとして格納した新データカップルドノードツリーを作成し、該新データカップルドノードツリーに基づいて、前記旧データを前記新データに更新する新旧インデックスキー更新ステップと、
を備えることを特徴とするインデックスキーの差分データ更新方法。
【請求項６】
請求項５記載のインデックスキーの差分データ更新方法において、
前記カップルドノードツリーは、配列に記憶され、前記リンク先のノード対の代表ノードの位置を示す情報は、そのノードが格納された前記配列の配列要素の配列番号であることを特徴とするインデックスキーの差分データ更新方法。
【請求項７】
請求項６記載のインデックスキーの差分データ更新方法において、
前記更新ツリー取得ステップは、前記旧データから最初に取り出したインデックスキーを含むリーフノードを該更新ツリーのルートノードとした後、それ以後前記旧データから取り出した前記インデックスキーを前記検索キーとして該更新ツリーから該当するリーフノードを検索するとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードが格納された配列要素の配列番号をスタックに順次格納し、前記検索キーと前記該当するリーフノードに含まれるインデックスキーの間で大小比較とビット列比較を行い、ビット列比較で異なるビット値となる先頭のビット位置と前記スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係により挿入されるインデックスキーを含むリーフノードともう一方のノードからなるノード対の挿入位置を決定し、前記大小関係により挿入するインデックスキーを含むリーフノードを前記挿入されるノード対のどちらのノードとするかを決定するインデックスキーの挿入処理を繰り返すものであることを特徴とするインデックスキーの差分データ更新方法。
【請求項８】
請求項７記載のインデックスキーの差分データ更新方法において、
前記更新ツリー取得ステップは、前記旧データのインデックスキーに加えて、前記差分データの挿入キーを取り出して前記インデックスキーの挿入処理を繰り返すものであり、
前記新旧インデックスキー更新ステップは、前記差分データから取り出した削除キーを前記更新ツリーから削除することにより新データのインデックスキーをリーフノードのインデックスキーとして格納した新データカップルドノードツリーを作成し、該新データカップルドノードツリーに基づいて、前記旧データを前記新データに更新するものであることを特徴とするインデックスキーの差分データ更新方法。
【請求項９】
請求項５記載のインデックスキーの差分データ更新方法において、
前記旧データのインデックスキーはカップルドノードツリーに格納されており、
前記更新ツリー取得ステップは、該カップルドノードツリーのルートノードの位置を示す位置情報を取得するものであり、
前記新旧インデックスキー更新ステップは、前記新データカップルドノードツリーを作成することで前記旧データを前記新データに更新する、
ことを特徴とするインデックスキーの差分データ更新方法。
【請求項１０】
データベースのインデックスキーの旧データに対して該旧データと置き換えられる新しいインデックスキーの新データが供給されたときに、前記インデックスキーの更新を行うデータベースのインデックスキー更新に用いる前記旧データと前記新データの差分データ作成装置において、
前記旧データあるいは新データのインデックスキーを、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、
カップルドノードツリーのリーフノードのインデックスキーとして格納した、差分ツリーを取得する差分ツリー取得手段と、
前記差分ツリーのルートノードを前記検索開始ノードとして前記新データあるいは旧データの全てのインデックスキーを検索キーとして検索を行い、検索キーと一致した前記検索結果キーであるインデックスキーは差分ツリーから削除し、前記検索結果キーであるインデックスキーと一致しない検索キーを差分データの挿入キーあるいは削除キーとし、前記新データあるいは旧データの全てのインデックスキーによる検索が終了した後に前記差分ツリーに削除されずに残ったインデックスキーを差分データの削除キーあるいは挿入キーとして差分データを作成する差分データ作成手段と、
を備えることを特徴とする差分データ作成装置。
【請求項１１】
データベースのインデックスキーの旧データと該旧データと置き換えられる新しいインデックスキーの新データの差分データを用いて前記インデックスキーの更新を行うインデックスキーの差分データ更新装置において、
前記旧データのインデックスキーを、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、
カップルドノードツリーのリーフノードのインデックスキーとして格納した前記カップルドノードツリーである更新ツリーを取得する更新ツリー取得手段と、
前記旧データあるいは新データのインデックスキーを前記カップルドノードツリーのリーフノードのインデックスキーとして格納した差分ツリーのルートノードを前記検索開始ノードとして前記新データあるいは旧データの全てのインデックスキーを検索キーとして検索を行い、検索キーと一致した前記検索結果キーであるインデックスキーは差分ツリーから削除し、前記検索結果キーであるインデックスキーと一致しない検索キーを差分データの挿入キーあるいは削除キーとし、前記新データあるいは旧データの全てのインデックスキーによる検索が終了した後に前記差分ツリーに削除されずに残ったインデックスキーを差分データの削除キーあるいは挿入キーとして作成した差分データから取り出した削除キーを前記更新ツリーから削除し、前記差分データから取り出した挿入キーを前記更新ツリーに挿入することにより新データのインデックスキーをリーフノードのインデックスキーとして格納した新データカップルドノードツリーを作成し、該新データカップルドノードツリーに基づいて、前記旧データを前記新データに更新する新旧インデックスキー更新手段と、
を備えることを特徴とするインデックスキーの差分データ更新装置。
【請求項１２】
請求項１１記載のインデックスキーの差分データ更新装置において、
前記旧データのインデックスキーはカップルドノードツリーに格納されており、
前記更新ツリー取得手段は、該カップルドノードツリーのルートノードの位置を示す位置情報を取得するものであり、
前記新旧インデックスキー更新手段は、前記新データカップルドノードツリーを作成することで前記旧データを前記新データに更新する、
ことを特徴とするインデックスキーの差分データ更新装置。
【請求項１３】
データベースのインデックスキーの旧データに対して該旧データと置き換えられる新しいインデックスキーの新データが供給されたときに、前記インデックスキーの更新を行うデータベースのインデックスキー更新に用いられるコンピュータ上で動作するプログラムにおいて、
前記旧データあるいは新データのインデックスキーを、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、
カップルドノードツリーのリーフノードのインデックスキーとして格納した、差分ツリーを取得する差分ツリー取得ステップと、
前記差分ツリーのルートノードを前記検索開始ノードとして前記新データあるいは旧データの全てのインデックスキーを検索キーとして検索を行い、検索キーと一致した前記検索結果キーであるインデックスキーは差分ツリーから削除し、前記検索結果キーであるインデックスキーと一致しない検索キーを差分データの挿入キーあるいは削除キーとし、前記新データあるいは旧データの全てのインデックスキーによる検索が終了した後に前記差分ツリーに削除されずに残ったインデックスキーを差分データの削除キーあるいは挿入キーとして差分データを作成する差分データ作成ステップと、
をコンピュータに実行させることを特徴とするプログラム。
【請求項１４】
データベースのインデックスキーの旧データに対して該旧データと置き換えられる新しいインデックスキーの新データが供給されたときに、前記インデックスキーの更新を行うデータベースのインデックスキー更新に用いられるコンピュータ上で動作するプログラムにおいて、
前記旧データのインデックスキーを、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成されたカップルドノードツリーのリーフノードのインデックスキーとして格納した、更新ツリーを取得する更新ツリー取得ステップと、
請求項１３記載の前記差分データ作成ステップで作成された差分データから取り出した削除キーを前記更新ツリーから削除し、前記差分データから取り出した挿入キーを前記更新ツリーに挿入することにより新データのインデックスキーをリーフノードのインデックスキーとして格納した新データカップルドノードツリーを作成し、該新データカップルドノードツリーに基づいて、前記旧データを前記新データに更新する新旧インデックスキー更新ステップと、
をコンピュータに実行させることを特徴とするプログラム。
【請求項１５】
請求項１３又は請求項１４記載のプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
旧データとは一致しなかった検索キー、すなわち新データに追加されたキーは、挿入キーとして差分データに取り込まれる。新データにより検索されず旧データに残存したキー、すなわち新データに存在しないキーは、削除キーとして差分データに取り込まれる。
なお、上述の説明では、新データに含まれる全てのキーで旧データに含まれるキーを検索する、としたが、差分データを作成するのであるから、旧データに含まれる全てのキーで新データに含まれるキーを検索する、として差分データを作成してもよいことは明らかである。その場合は、新データに残存したキーが挿入キーとして差分データに取り込まれ、新データと一致しなかった旧データが削除キーとして差分データに取り込まれる。

【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
差分データ作成装置３００において作成された差分データは、差分データ更新装置４００ａ〜４００ｘに送られ、それぞれの差分データ格納領域４２０ａ〜４２０ｘに格納され、それぞれのインデックス格納領域４２１ａ〜４２１ｘに格納された旧データを新データに更新するために用いられる。特に図示はしていないが、差分データ更新装置４００ａ〜４００ｘにおいても、データ処理装置や、差分データ格納領域、インデックス格納領域及びその他の記憶領域を有するデータ格納装置が備えられている。
なお、以下においては、上述の例えば差分データ格納領域３２０に格納された差分データを差分データ３２０と表記するように、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合がある。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
図３Ｃは、差分データ作成装置３００の機能ブロック構成を説明する図である。
図に示すように、差分データ作成装置３００は、差分ツリー取得手段３３０と差分データ作成手段３３１の機能ブロックを含む。これらの機能ブロックは、図３Ｂに例示するハードウェアと以下において説明する処理フローを実行するソフトウェアにより実現される。
差分ツリー取得手段３３０は、旧データあるいは新データのインデックスキーをカップルドノードツリーのリーフノードのインデックスキーとして格納した、差分ツリーを取得する。
差分データ作成手段３３１は、差分ツリーのルートノードを検索開始ノードとして新データあるいは旧データの全てのインデックスキーを検索キーとして検索を行い、検索キーと一致した検索結果キーであるインデックスキーは差分ツリーから削除し、検索結果キーであるインデックスキーと一致しない検索キーを差分データの挿入キーあるいは削除キーとする。そして、新データあるいは旧データの全てのインデックスキーによる検索が終了した後に差分ツリーに削除されずに残ったインデックスキーを差分データの削除キーあるいは挿入キーとして差分データを作成する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００６７
【補正方法】変更
【補正の内容】
【００６７】
図３Ｄは、差分データ更新装置の機能ブロック構成を説明する図である。
図に示すように、差分データ更新装置４００は、更新ツリー取得手段４２２と新旧インデックスキー更新手段４２３の機能ブロックを含む。これらの機能ブロックは、図３Ｂに示す差分データ更新装置４００ａ〜４００ｘについて説明したハードウェアと以下において説明する処理フローを実行するソフトウェアにより実現される。
更新ツリー取得手段４２２は、旧データのインデックスキーをカップルドノードツリーのリーフノードのインデックスキーとして格納した更新ツリーを取得する。
新旧インデックスキー更新手段４２３は、差分データ作成手段３３１が作成した差分データから取り出した削除キーを更新ツリーから削除し、差分データから取り出した挿入キーを更新ツリーに挿入することにより新データのインデックスキーをリーフノードのインデックスキーとして格納した新データカップルドノードツリーを作成し、新データカップルドノードツリーに基づいて、旧データを新データに更新する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００６８
【補正方法】変更
【補正の内容】
【００６８】
次に、上述の出願において、本出願人により提案されたカップルドノードツリーを用いた基本的な検索処理、カップルドノードツリーにおける挿入削除処理、及びカップルドノードツリーに含まれるインデックスキーの最小値を求める処理等の応用処理の一部について、本発明を理解するために必要な範囲で紹介する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６９
【補正方法】変更
【補正の内容】
【００６９】
図４は、本出願人による出願である上記特願２００６−２９３６１９で提案されたビット列検索の基本動作を示したフローチャートである。
まず、ステップＳ４０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後に説明する各種応用検索において行われる。
取得された検索開始ノードの配列番号は、図示しない検索開始ノード設定エリアに設定されるが、この検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置」の一つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードの配列番号を得る。」、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１７０
【補正方法】変更
【補正の内容】
【０１７０】
【図１】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【図２Ａ】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２Ｂ】カップルドノードツリーのツリー構造を概念的に示す図である。
【図３Ａ】本発明の原理を説明する図である。
【図３Ｂ】本発明を実施するためのハードウェア構成例を説明する図である。
【図３Ｃ】差分データ作成装置の機能ブロック構成を説明する図である。
【図３Ｄ】差分データ更新装置の機能ブロック構成を説明する図である。
【図４】ビット列検索の基本動作を示したフローチャートである。
【図５】カップルドノードツリーに格納されたインデックスキーの最小値を求める処理を示したフローチャートである。
【図６】カップルドノードツリーに格納されたインデックスキーを昇順に取り出す処理を示したフローチャートである。
【図７Ａ】挿入処理の前段である検索処理の処理フローを示す図である。
【図７Ｂ】挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
【図７Ｃ】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。
【図７Ｄ】ルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【図８Ａ】削除処理の前段である検索処理の処理フローを示す図である。
【図８Ｂ】削除処理の後段の処理フローを説明する図である。
【図９】新旧データによる差分データ作成処理の概要を説明する図である。
【図１０】新旧データによる差分データ作成の処理フローを説明する図である。
【図１１】旧データによりカップルドノードツリーを作成する処理フローを説明する図である。
【図１２】差分データに更新データを格納する処理フローを説明する図である。
【図１３】差分ツリーに残ったキーを削除キーとして差分データを作成する処理フローを説明する図である。
【図１４】差分データにより旧データを新データに更新する処理の概要を説明する図である。
【図１５】差分データにより旧データを新データに更新する処理フローを説明する図である。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１７１
【補正方法】変更
【補正の内容】
【０１７１】
１０、２０、３０   配列番号
１００      配列
１０１      ノード
１０２      ノード種別
１０３      弁別ビット位置
１０４      代表ノード番号
１１１      ノード対
１１２      ノード［０］、代表ノード
１１３      ノード［１］、代表ノードと対をなすノード
１１８      インデックスキー
３００      差分データ作成装置
３０１      データ処理装置
３０２      中央処理装置
３０３      キャッシュメモリ
３０４      バス
３０５      主記憶装置
３０６      外部記憶装置
３０７      通信装置
３０９      配列
３１０      探索経路スタック
３２０      差分データ格納領域
３２１      旧データ格納領域
３２２      新データ格納領域
３３０      差分ツリー取得手段
３３１      差分データ作成手段
４００      差分データ更新装置
４２０      差分データ格納領域
４２１      インデックス格納領域
４２２      更新ツリー取得手段
４２３      新旧インデックスキー更新手段
【手続補正１０】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2009157853.tif 000001
【図２Ａ】
2009157853.tif 000002
【図２Ｂ】
2009157853.tif 000003
【図３Ａ】
2009157853.tif 000004
【図３Ｂ】
2009157853.tif 000005
【図３Ｃ】
2009157853.tif 000006
【図３Ｄ】
2009157853.tif 000007
【図４】
2009157853.tif 000008
【図５】
2009157853.tif 000009
【図６】
2009157853.tif 000010
【図７Ａ】
2009157853.tif 000011
【図７Ｂ】
2009157853.tif 000012
【図７Ｃ】
2009157853.tif 000013
【図７Ｄ】
2009157853.tif 000014
【図８Ａ】
2009157853.tif 000015
【図８Ｂ】
2009157853.tif 000016
【図９】
2009157853.tif 000017
【図１０】
2009157853.tif 000018
【図１１】
2009157853.tif 000019
【図１２】
2009157853.tif 000020
【図１３】
2009157853.tif 000021
【図１４】
2009157853.tif 000022
【図１５】
2009157853.tif 000023