(57)【要約】【課題】カップルドノードツリーを２つに分割し、また２つのカップルドノードツリーを結合する手法を提供する。【解決手段】処理元のカップルドノードツリーのインデックスキーの最小値あるいは最大値を求めてそれらインデックスキーを順次分割点となるインデックスキーまで削除し、削除したインデックスキーを処理先のカップルドノードツリーに挿入することによりカップルドノードツリーを分割する。一方のカップルドノードツリーを上記分割方法の処理元として削除処理を行い、他方を処理先として挿入処理を行ってカップルドノードツリーを結合する。【選択図】図１２
2008159025.tif 000002
【特許請求の範囲】
【請求項１】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成されたカップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割するインデックスキーを決定する分割キーを取得するステップと、
前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理元最小値あるいは最大値取得ステップと、
前記分割キーと前記最小値あるいは最大値との大小を比較し、該最小値が前記分割キーより大きければあるいは該最大値が前記分割キーより小ければ処理を終了する比較ステップと、
前記比較の結果、該最小値が前記分割キーより大きくなければあるいは該最大値が前記分割キーより小さくなければ、
該最小値あるいは該最大値のインデックスキーを挿入することにより新たな処理先カップルドノードツリーを生成する生成ステップと、
前記処理元カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記比較ステップ、前記生成ステップ及び前記削除ステップを前記処理元最小値あるいは最大値取得ステップで取得された最小値あるいは最大値が前記分割キーより大きくなるまであるいは小さくなるまで繰り返すことを特徴とするカップルドノードツリーの分割方法。
【請求項２】
請求項１に記載のカップルドノードツリーの分割方法において、
前記最小値あるいは最大値取得ステップは、前記処理元カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する２つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるステップであることを特徴とするカップルドノードツリーの分割方法。
【請求項３】
請求項１又は請求項２に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次スタックに保持されていくものであり、
前記生成ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値を前記処理先カップルドノードツリーの挿入キーとして設定し、
前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている配列番号のブランチノードの弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である処理先親ノードを決定し、
該処理先親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの分割方法。
【請求項４】
請求項３に記載のカップルドノードツリーの分割方法において、
前記生成ステップは、さらに前記処理先親ノードを、挿入キーを含むリーフノードを挿入した挿入済みノードとして設定するステップを含み、
前記処理先最大値あるいは最小値取得ステップは、前記挿入済みノードを検索開始ノードとして前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得するものであることを特徴とするカップルドノードツリーの分割方法。
【請求項５】
請求項４に記載のカップルドノードツリーの分割方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの分割方法。
【請求項６】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された２つのカッ
プルドノードツリーの結合方法において、
前記２つのカップルドノードツリーの一方の処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理元最小値あるいは最大値取得ステップと、
前記２つのカップルドノードツリーの他方の処理先カップルドノードツリーに前記最小値あるいは最大値のインデックスキーを挿入する挿入ステップと、
前記処理元カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記挿入ステップ及び前記削除ステップを前記処理元カップルドノードツリーがすべて削除されるまで繰り返すことを特徴とするカップルドノードツリーの結合方法。
【請求項７】
請求項６に記載のカップルドノードツリーの結合方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次スタックに保持されていくものであり、
前記挿入ステップは、
前記最小値あるいは前記最大値を前記処理先カップルドノードツリーの挿入キーとして設定し、
前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている配列番号のブランチノードの弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である親ノードを決定し、
該親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの結合方法。
【請求項８】
請求項７に記載のカップルドノードツリーの結合方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの結合方法。
【請求項９】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり
、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、カップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割する分割キーを取得するステップと、
前記処理元カップルドノードツリーの部分木であって前記分割キーをその最大値あるいは最小値とするもののうちで最大の部分木のルートノードである分割ノードを求める分割ノード取得ステップと、
前記分割ノードをルートノードとする部分木である分割ノードツリーを挿入することにより新たな処理先のカップルドノードツリーを生成するする生成ステップと、
前記分割ノードツリーを前記処理元カップルドノードツリーから削除する削除ステップ
を含むことを特徴とするカップルドノードツリーの分割方法。
【請求項１０】
請求項９に記載のカップルドノードツリーの分割方法において、
前記分割ノード取得ステップは、前記処理元のルートノードを前記検索開始ノードとし、前記分割キーを前記検索キーとして検索を行い、前記ルートノードから前記分割キーに至る検索におけるリンク経路上のブランチノードであって該ブランチノードからの全てのリンク先のノードに前記分割キーより大きいあるいは小さいインデックスキーを含むリーフノードが存在せず、かつカップルドノードツリー上で最も上位にあるブランチノードを前記分割ノードとして取得することを特徴とするカップルドノードツリーの分割方法。
【請求項１１】
請求項１０に記載のカップルドノードツリーの分割方法において、
前記ルートノードから前記分割ノードに至る前記リンク経路のブランチノードと前記ノード対をなすノードであって、該ノードよりカップルドノードツリー上で下位の全てのリーフノードが前記分割キーより大きいあるいは小さいインデックスキーを含まず、かつカップルドノードツリー上で最も上位にあるノードを次の分割ノードとして取得する次分割ノード取得ステップを備え、
前記分割ノードを前記次の分割ノードとして前記生成ステップと前記削除ステップを実行することを特徴とするカップルドノードツリーの分割方法。
【請求項１２】
請求項１０又は請求項１１に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次スタックに保持されていくことを特徴とするカップルドノードツリーの分割方法。
【請求項１３】
請求項１２に記載のカップルドノードツリーの分割方法において、
前記分割ノード取得ステップは、前記スタックに格納された配列番号を、前記代表ノードの格納された配列要素の配列番号となるまで、あるいは前記代表ノードと対をなすノードの格納された配列要素の配列番号となるまで順次読み出し、該読み出した前記代表ノードの格納された配列要素の配列番号あるいは前記代表ノードと対をなすノードの格納され
た配列要素の配列番号の配列要素に格納されたノードを前記分割ノードとして取得することを特徴とするカップルドノードツリーの分割方法。
【請求項１４】
請求項１３に記載のカップルドノードツリーの分割方法において、
前記次分割ノード取得ステップは、前記スタックに格納された、前記分割ノードの格納された配列要素の配列番号より前に格納された配列番号を、前記代表ノードと対をなすノードの格納された配列要素の配列番号となるまで、あるいは前記代表ノードの格納された配列要素の配列番号となるまで順次読み出し、該読み出した前記代表ノードと対をなすノードの格納された配列要素の配列番号あるいは前記代表ノードの格納された配列要素の配列番号の配列要素に格納されたノードと対をなすノードを前記次の分割ノードとして取得することを特徴とするカップルドノードツリーの分割方法。
【請求項１５】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された２つのカップルドノードツリーの結合方法において、
前記２つのカップルドノードツリーの一方の処理元カップルドノードツリーのインデックスキーの最大値あるいは最小値を求める処理元最大値あるいは最小値取得ステップと、
前記２つのカップルドノードツリーの他方の処理先カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理先最小値あるいは最大値取得ステップと、
前記処理元最大値あるいは最小値取得ステップで求めた処理元カップルドノードツリーのインデックスキーの最大値あるいは最小値と前記処理先最小値あるいは最大値取得ステップで求めた処理先カップルドノードツリーのインデックスキーの最小値あるいは最大値の差分ビット位置を求める差分ビット位置取得ステップと、
前記差分ビット位置取得ステップで求めた差分ビット位置に基づき前記処理元から分割して処理先に結合する部分木のルートノードである分割結合ノードを求める分割結合ノード取得ステップと、
前記差分ビット位置取得ステップで求めた差分ビット位置に基づき分割結合ノード取得ステップで求めた分割結合ノードを結合する処理先の結合位置を求める結合位置取得ステップと、
前記分割結合ノード取得ステップで求めた分割結合ノードを前記結合位置取得ステップで求めた処理先の結合位置に挿入する挿入ステップと、
前記分割結合ノード取得ステップで求めた分割結合ノードを前記処理元カップルドノードツリーから削除する削除ステップと、
を含むことを特徴とするカップルドノードツリーの結合方法。
【請求項１６】
請求項１５に記載のカップルドノードツリーの結合方法において、
前記処理元最大値あるいは最小値取得ステップは、前記処理元カップルドノードツリー
のルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する２つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最大値あるいは最小値を求めるステップであり、
前記処理先最小値あるいは最大値取得ステップは、前記処理先カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する２つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理先カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるステップであることを特徴とするカップルドノードツリーの結合方法。
【請求項１７】
請求項１６に記載のカップルドノードツリーの結合方法において、
前記処理元カップルドノードツリー及び処理先カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記処理元最大値あるいは最小値取得ステップ及び前記処理先最小値あるいは最大値取得ステップにおける前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次それぞれ処理元のスタック及び処理先のスタックに保持されていくことを特徴とするカップルドノードツリーの結合方法。
【請求項１８】
請求項１７に記載のカップルドノードツリーの結合方法において、
前記分割結合ノード取得ステップは、前記処理元のスタックに格納された配列番号の１つ前に格納された配列番号から、該配列番号の配列要素に格納されたブランチノードの弁別ビット位置が前記差分ビット位置より上位になるまで読み出し、該読み出した配列要素の次に前記処理元のスタックに格納された配列番号の配列要素に格納されたノードを分割結合ノードとして求め、
前記結合位置取得ステップは、前記処理先のスタックに格納された配列番号の１つ前に格納された配列番号から、該配列番号の配列要素に格納されたブランチノードの弁別ビット位置が前記差分ビット位置より上位になるまで読み出し、該読み出した配列要素の次に前記処理先のスタックに格納された配列番号の配列要素に格納されたノードを結合位置として求めることを特徴とするカップルドノードツリーの結合方法。
【請求項１９】
請求項１〜１８のいずれか１つに記載のカップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する検索方法に関するものであり、特に本出願人が特願２００６−１８７８２７において提案したカップルドノードツリーの分割／結合方法及びそのプログラムに関するものである。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【０００３】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【０００４】
図３２は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【０００５】
図３２の例では、インデックスキー“１０００１０”を保持するノード１７５０ａがルートノードとなっており、その検査ビット位置は０である。ノード１７５０ａの左リンク１７４０ａにはノード１７５０ｂが接続され、右リンク１７４１ａにはノード１７５０ｆが接続されている。
【０００６】
ノード１７５０ｂの保持するインデックスキーは“０１００１１”であり、検査ビット位置２０３０ｂは１である。ノード１７５０ｂの左リンク１７４０ｂにはノード１７５０ｃが、右リンク１７４１ｂにはノード１７５０ｄが接続されている。ノード１７５０ｃが保持するインデックスキーは“０００１１１”、検査ビット位置は３である。ノード１７５０ｄが保持するインデックスキーは“０１１０１０”、検査ビット位置は２である。
【０００７】
ノード１７５０ｃから実線で接続された部分はノード１７５０ｃの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ１７４０ｃは、その欄が空欄であることを示している。点線の接続された右ポインタ１７４１ｃの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード１７５０ｃを右ポインタが指定していることを表している。
【０００８】
ノード１７５０ｄの右ポインタ１７４１ｄはノード１７５０ｄ自身を指しており、左リンク１７４０ｄにはノード１７５０ｅが接続されている。ノード１７５０ｅの保持するインデックスキーは“０１００１０”、検査ビット位置は５である。ノード１７５０ｅの左ポインタ１７４０ｅはノード１７５０ｂを、右ポインタ１７４１ｅはノード１７５０ｅを指している。
【０００９】
また、ノード１７５０ｆの保持するインデックスキーは“１０１０１１”であり、検査ビット位置１７３０ｆは２である。ノード１７５０ｆの左リンク１７４０ｆにはノード１７５０ｇが、右リンク１７４１ｆにはノード１７５０ｈが接続されている。
【００１０】
ノード１７５０ｇの保持するインデックスキーは“１０００１１”であり、検査ビット位置１７３０ｇは５である。ノード１７５０ｇの左ポインタ１７４０ｇはノード１７５０ａを、右ポインタ１７４１ｇはノード１７５０ｇを指している。
【００１１】
ノード１７５０ｈの保持するインデックスキーは“１０１１００”であり、検査ビット位置１７３０ｈは３である。ノード１７５０ｈの左ポインタ１７４０ｈはノード１７５０ｆを、右ポインタ１７４１ｈはノード１７５０ｈを指している。
【００１２】
図３２の例では、ルートノード１７５０ａからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が１であるか０であるか判定を行い、１であれば右リンクをたどり、０であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば（図３２において点線で示されたこの逆戻りのリンクをバックリンクという）、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【００１３】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は１回ですむことなどのメリットがあるが、各ノードからの２つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【００１４】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献１に開示された技術がある。下記特許文献１に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【００１５】
しかしながら、下記特許文献１に開示されたものにおいても、１つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを１つとしたため、例えば図３２に示したパトリシアツリーの最下段の部分である左ポインタ１７４０ｃ、右ポインタ１７４１ｈ等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【００１６】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願２００６−１８７８２７において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のとき
は前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を提案した。
【００１７】
上記出願においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。
【００１８】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願２００６−２９３６１９において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの最大値／最小値を求める手法等を提案した。
【００１９】
ところで近年において、情報処理技術の進展とともに情報サービスへの要求がさらに拡大し、より厳しいものになってきている。情報サービスを提供する上で基本となるのはデータベースの構築とそのデータベースからの情報の取出しであるが、データベースに蓄積されるデータ量はますます増大し、極めて巨大なものとなりつつある。
【００２０】
本出願人の先に提案した検索手法は、上記巨大化しつつあるデータベースの高速検索を可能とするものであるが、データベースが巨大化するとともにそれに対応するカップルドノードツリーも、従来のツリー構造のものより記憶容量が少なくてすむとはいえ、大きなものとなる。一方、各種記憶手段の記憶容量にはそれぞれ制限があり、経済的なシステムを構築するためには各種アクセス速度、記憶容量の記憶手段を組み合わせて利用する必要がある。
【００２１】
また、データベース自体も物理的に分割し、分散設置されることもありうる。
したがって、１つのカップルドノードツリーを分割し、また再結合することが必要になる。
【特許文献１】特開２００１−３５７０７０号公報
【発明の開示】
【発明が解決しようとする課題】
【００２２】
そこで本発明の目的は、カップルドノードツリーを２つに分割し、また２つのカップルドノードツリーを結合する手法を提供することである。
【課題を解決するための手段】
【００２３】
本発明の一つの態様によれば、分割点となるインデックスキーを決定する分割キーを指定し、処理元のカップルドノードツリーのインデックスキーの最小値あるいは最大値を求めてそれらインデックスキーを順次分割点となるインデックスキーまで削除し、削除したインデックスキーを処理先のカップルドノードツリーに挿入することによりカップルドノードツリーを分割するカップルドノードツリーの分割方法が提供される。
【００２４】
また、本発明の別の態様によれば、上記分割方法において処理元のカップルドノードツリーのインデックスキーの最小値あるいは最大値を順次求める処理において、前回最小値あるいは最大値を求めたときの検索経路の履歴により、検索開始ノードを設定して行う。
【００２５】
また、本発明のさらに別の態様によれば、２つのカップルドノードツリーの結合を、一方のカップルドノードツリーを上記分割方法における処理元として削除処理を行い、他方を処理先として挿入処理を行うカップルドノードツリーの結合方法が提供される。
【００２６】
また、本発明のさらに別の態様によれば、分割点となるインデックスキーを決定する分割キーを指定し、処理元カップルドノードツリーの部分木であって分割キーをその最大値あるいは最小値とするもののうちで最大の部分木のルートノードである分割ノードを求め、前記分割ノードをルートノードとする部分木である分割ノードツリーを挿入することにより新たな処理先のカップルドノードツリーを生成し、前記分割ノードツリーを前記処理元カップルドノードツリーから削除するカップルドノードツリーの分割方法が提供される。
【００２７】
また、本発明のさらに別の態様によれば、処理元のカップルドノードツリーのインデックスキーの最大値あるいは最小値と処理先のカップルドノードツリーのインデックスキーの最小値あるいは最大値との差分ビット位置に基づき処理元のカップルドノードツリーから分割して処理先に結合する部分木である分割結合ノードツリーを求め、該分割結合ノードツリーを差分ビット位置に基づいて処理先のカップルドノードツリーに結合する２つのカップルドノードツリーの結合方法を提供する。
【００２８】
さらに本発明の別の態様によれば、上記カップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるプログラムが提供される。
【発明の効果】
【００２９】
本発明によれば、簡単な処理で、効率よくカップルドノードツリーの分割／結合処理を実施することができ、カップルドノードツリーの大きさが大きくになったとしても、取り扱いを容易なものとすることができる。
【発明を実施するための最良の形態】
【００３０】
最初に、本出願人により先の上記出願において提案された、本発明の前提となるカップルドノードツリーについて、カップルドノードツリーを配列に格納する例を説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【００３１】
図１は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図１を参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【００３２】
配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが
、表記は省略している。
【００３３】
なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
【００３４】
配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。
ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
【００３５】
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
【００３６】
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
図２は、カップルドノードツリーのツリー構造を概念的に示す図である。図示の６ビットのインデックスキーは、図３２に例示されたパトリシアツリーのものと同じである。
【００３７】
符号２１０ａで示すのがルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。
ツリー構造としては、ルートノード２１０ａの下にノート対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。
【００３８】
各ノードの前に付された０あるいは１の符号は、図１において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００３９】
図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
【００４０】
ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。
【００４１】
ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノ
ード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
【００４２】
ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。
【００４３】
ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。
【００４４】
ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。
【００４５】
ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの格納された配列要素の配列番号２２１ｆが格納されている。
【００４６】
ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。
【００４７】
また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００“が格納されている。
【００４８】
以下、上述のツリーからインデックスキー“１０００１０”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
【００４９】
ノード２１０ｆの弁別ビット位置２３０ｆには５が格納されているので、検索キー“１０００１０”の弁別ビット位置が５のビット値をみると０であるから、代表ノード番号の格納された配列番号２２０ｆの配列要素に格納されたノード２１０ｇにリンクする。
【００５０】
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを読み出して検索キーと比較すると両方とも“１０００１０”であって一致している。このようにしてカップルドノードツリーを用いた検索が行
われる。
【００５１】
次に、図２を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図２の例で、ルートノード２１０ａの弁別ビット位置が０であるのは、図２に例示されたインデックスキーに０ビット目が０のものと１のものがあるからである。０ビット目が０のインデックスキーのグループはノード２１０ｂの下に分類され、０ビット目が１のインデックスキーのグループはノード２１１ｂの下に分類されている。
【００５２】
ノード２１１ｂの弁別ビット位置が２であるのは、ノード２１１ｈ、２１０ｈ、２１１ｇ、２１０ｇに格納された０ビット目が１のインデックスキーの１ビット目がすべて０で等しく、２ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
【００５３】
以下０ビット目の場合と同様に、２ビット目が１であるものはノード２１１ｆ側に分類され、２ビット目が０であるものはノード２１０ｆ側に分類される。
そして２ビット目が１であるインデックスキーは３ビット目の異なるものがあるのでノード２１１ｆの弁別ビット位置には３が格納され、２ビット目が０であるインデックスキーでは３ビット目も４ビット目も等しく５ビット目で異なるのでノード２１０ｆの弁別ビット位置には５が格納される。
【００５４】
ノード２１１ｆのリンク先においては、３ビット目が１のものと０のものがそれぞれ１つしかないことから、ノード２１０ｈ、２１１ｈはリーフノードとなり、それぞれインデックスキー２５０ｈと２５１ｈに“１０１０１１”と“１０１１００”が格納されている。
【００５５】
仮にインデックスキーの集合に“１０１１００”の代わりに“１０１１０１”か“１０１１１０”が含まれていたとしても、３ビット目までは“１０１１００”と等しいので、ノード２１１ｈに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“１０１１００”に加えて“１０１１０１”が含まれていると、ノード２１１ｈはブランチノードとなり、その弁別ビット位置は５になる。追加されるインデックスキーが“１０１１１０”であれば、弁別ビット位置は４となる。
【００５６】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“１”のノードとビット値が“０”のノードとに分岐していることから、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード２１１ｈのインデックスキー２５１ｈの“１０１１００”、ノード２１０ｈのインデックスキー２５０ｈの“１０１０１１”、・・・、ノード２１０ｃのインデックスキー２５０ｃの“０００１１１”となり降順にソートされている。
【００５７】
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“１０１１００”であればノード２１１ｈに到達することができる。また、上記説明からも想像がつくように、“１０１１０１”か“１０１１１０”を検索キーとした場合でもノード２１１ｈにたどり着き、インデックスキー２５１ｈと比較することにより検索が失敗したことが分かる。
【００５８】
また、例えば“１００１００”で検索した場合でも、ノード２１０ａ、２１１ｂ、２１０ｆのリンク経路では検索キーの３ビット目と４ビット目は使われることがなく、“１００１００”の５ビット目が０なので、“１０００１０”で検索した場合と同様にノード２１０ｇに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【００５９】
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００６０】
図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、配列３０９は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【００６１】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
次に、上述の出願において、本出願人により提案されたカップルドノードツリーを用いた基本的な検索処理、カップルドノードツリーにおける挿入削除処理、及びカップルドノードツリーに含まれるインデックスキーの最大値／最小値を求める処理等の応用処理の一部について、図４〜図１１Ｂを参照することにより、本発明を理解するために必要な範囲で紹介する。
【００６２】
図４は、本出願人による出願である上記特願２００６−２９３６１９で提案されたビット列検索の基本動作を示したフローチャートである。
まず、ステップＳ４０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後に説明する各種応用検索において行われる。
【００６３】
次に、ステップＳ４０２で、探索経路スタック３１０に取得された配列番号を格納し、ステップＳ４０３で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップＳ４０４で、読み出したノードから、ノード種別を取り出し、ステップＳ４０５で、ノード種別がブランチノードであるか否かを判定する。
【００６４】
ステップＳ４０５の判定において、読み出したノードがブランチノードである場合は、ステップＳ４０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ４０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ４０８で、ノードから代表ノード番号を取り出して、ステップＳ４０９で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、ステップＳ４０２に戻る。
【００６５】
以降、ステップＳ４０５の判定においてリーフノードと判定されてステップＳ４１０に
進むまで、ステップＳ４０２からステップＳ４０９までの処理を繰り返す。ステップＳ４１０で、リーフノードからインデックスキーを取り出して、処理を終了する。
【００６６】
図５は、本出願人による出願である上記特願２００６−２９３６１９で提案されたカップルドノードツリー（部分木を含む）に格納されたインデックスキーの最小値を求める処理を示したフローチャートである。先に述べたようなインデックスキーのツリー上の配置から、インデックスキーの最小値を求める処理は検索開始ノードからノード［０］をリーフノードに至るまでツリー上でたどることに相当する。
【００６７】
まず、ステップＳ５０１の検索開始ノードの配列番号の取得からステップＳ５０５のノード種別の判定までは、それぞれ上述の図４のステップＳ４０１からステップＳ４０５の処理と同様である。
【００６８】
ステップＳ５０５のノード種別の判定においてノード種別がブランチノードと判定されると、ステップＳ５０６に進み、ノードから配列の代表ノード番号を取り出し、ステップＳ５０７で、取り出した代表ノード番号に値「０」を加算してその結果を新たな配列番号とし、ステップＳ５０２に戻る。以降、ステップＳ５０５においてそのノードがリーフノードと判定されるまでステップＳ５０２からステップＳ５０７までの処理を繰り返し、ステップＳ５０８で、リーフノードからインデックスキーを取り出し、処理を終了する。
【００６９】
上記の図５に示す処理においては、ノード［０］をたどるため、代表ノード番号に一律「０」を加算している。すなわち、図５の処理によれば、リンク先のノードは、ノード対のうち必ずノード［０］とし、より小さい値のインデックスキーが格納されているノードのほうに分岐している。これにより、ツリー構造が先に述べたように順列構成であるカップルドノードツリーの最小のインデックスキーを取り出すことができる。
【００７０】
図６は、本出願人による出願である上記特願２００６−２９３６１９で提案されたカップルドノードツリー（部分木を含む）に格納されたインデックスキーの最大値を求める処理を示したフローチャートである。
【００７１】
インデックスキーの最大値を求める処理は、ツリー上のノードのうちノード［１］について、リーフノードに至るまで順次たどっていくことに相当する。以下、任意の部分木の最大のインデックスキーを求める処理について、上記最小のインデックスキーを求める処理と比較しながら、異なる点を中心に説明する。
【００７２】
図６に示す一連の処理のうち、ステップＳ６０１からステップＳ６０６及びステップＳ６０８については、図５のステップ５０１からステップＳ５０６及びステップＳ５０８にそれぞれ対応しており、同様の処理が実行される。図５の最小値を求める処理と異なる点は、ステップＳ６０７において、代表ノード番号に、値「１」を加算する点である。これにより、代表ノード番号が表すノード対のうち、ノード［１］に常にリンクすることとなり、リーフノードに至るまで順次ステップＳ６０２からステップＳ６０７の処理を繰り返すことにより、インデックスキーの最大値を得ることができる。
【００７３】
図４から図６に示すように、検索キーと一致するインデックスキーを検索する基本動作やインデックスキーの最小値／最大値の検索処理を実行する際には、探索経路スタック３１０に参照した配列の配列番号が順次格納されていく。
【００７４】
なお、上述の図５及び図６を参照したインデックスキーの最小値／最大値の検索処理では、カップルドノードツリーは配列に記憶されたものとして説明したが、カップルドノードツリーが配列に記憶されることは必須ではなく、ノード対を構成する２つのノードのう
ちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることによりインデックスキーの最小値／最大値の検索が可能であることは明らかである。
【００７５】
図７Ａ及び図７Ｂは、本出願人による出願である上記特願２００６−２９３６１９で提案されたカップルドノードツリーに格納されたインデックスキーの下限値を求める処理を示したフローチャートである。ここで下限値とは、指定された下限キー以上のインデックスキーの最小値である。図７Ａ及び図７Ｂに示す下限値を求める処理は、ユーザ等が指定する検索範囲について検索を行う際に、実際にはインデックスキーが取り得ない範囲については対象外とし、実際にインデックスキーが含まれる範囲について検索を行う処理に応用される。なお、図７Ａ及び図７Ｂでは、指定された下限キー及び上限キーの取得処理は省略されている。以降の各種応用検索においても同様である。
【００７６】
まず、ステップＳ７０１で、検索開始ノードの配列番号に、ルートノードの配列番号を設定し、ステップＳ７０２で最小値検索処理を行いインデックスキーの最小値を求める。そして、ステップＳ７０３で、下限キーと、ステップＳ７０２で求めた最小値との比較をし、下限キーが最小値より大きいか否かを判定する。下限キーが最小値以下の値をとる場合、ステップＳ７０４に進み、ステップＳ７０２で求めた最小値を下限値として設定し、処理を終了する。
【００７７】
ステップＳ７０３において、下限キーはステップＳ７０２で求めた最小値よりも大きいと判定された場合は、ステップＳ７０５に進み、下限キーを検索キーとして設定する。そして、ステップＳ７０６で、検索開始ノードの配列番号にルートノードの配列番号を設定して、ステップＳ７０７で、図４及び図５により説明したビット列検索方法によりインデックスキーを検索する。そして、ステップＳ７０８で、検索キーとステップＳ７０７の検索の結果得られたインデックスキーとを比較して値が一致するか否かを判定する。検索キーとインデックスキーとが等しいと判定された場合は、ステップＳ７０９に進み、検索により得られたインデックスキーを上記下限値として設定し、処理を終了する。検索キーとインデックスキーとは等しくないと判定された場合は、図７ＢのステップＳ７１０に進む。
【００７８】
ステップＳ７１０で、検索キーとインデックスキーの大小関係を判定する。ここで、検索キーがインデックスキーよりも大きい場合は、そのインデックスキーは検索キーすなわち下限キーよりも小さく、ユーザ等により指定された検索範囲に含まれないことを意味する。一方、検索キーがインデックスキーよりも小さい場合は、そのインデックスキーは指定された検索範囲に含まれることを意味する。そこで、検索キーがインデックスキーよりも小さいと判定されると、ステップＳ７１８に進み、そのインデックスキーを下限値に設定して、処理を終了する。
【００７９】
ステップＳ７１０において、検索キーがインデックスキーよりも大きいと判定されると、ステップＳ７１１に進む。ステップＳ７１１からステップＳ７１７までの処理は、昇順にインデックスキーを取り出す処理であり、ステップＳ７１１からステップＳ７１７の処理により、カップルドノードツリーに格納されているインデックスキーが順に取り出されていき、検索キーすなわち下限キーよりも大きい値をとるインデックスキーが得られると、そのインデックスキーが下限値として設定される。
【００８０】
図８Ａ及び図８Ｂは、本出願人による出願である上記特願２００６−２９３６１９で提案されたカップルドノードツリーに格納されたインデックスキーの上限値を求める処理を示したフローチャートである。ここで上限値とは、指定された上限キー以下のインデックスキーの最大値である。図８Ａ及び図８Ｂに示す上限値を求める処理は、上記下限値を求
める処理と同様に、ユーザ等が指定する検索範囲について検索を行う際に、実際にはインデックスキーが取り得ない範囲については対象外とし、実際にインデックスキーが含まれる範囲について検索を行う処理等に応用される。
【００８１】
まず、ステップＳ８０１でルートノードを検索開始ノードとして検索する処理についてはインデックスキーの下限値を求める処理と同様であり、また、ステップＳ８０２以降の処理については、上記ステップＳ７０２以降の処理とそれぞれ対応している。
【００８２】
すなわち、図７Ａ及び図７Ｂを用いて説明した下限値を求める処理においては、ステップＳ７０２以降の処理により、ユーザ等により指定された下限キーと、カップルドノードツリーに含まれるインデックスキーのうち下限キー以上で、且つ最も下限キーに近い値をとるインデックスキーを検索している。これに対し、図８Ａ及び図８Ｂに示す上限値を求める処理においては、ステップＳ８０２以降の処理により、検索範囲の上限としてユーザ等により指定された上限キー以下の値をとり、且つ上限キーに最も上限キーに近い値をとるインデックスキーを検索している。
【００８３】
図７Ａ及び図７Ｂに示す処理と比較すると、指定されたキー（下限キー／上限キー）とインデックスキーとを比較する際の大小関係（ステップＳ７０３とステップＳ７１０、及びステップＳ８０３とステップＳ８１０）や、指定されたキーを検索キーとしてカップルドノードツリーを検索する際にインデックスキーの最小値／最大値をそれぞれ求める（ステップＳ７０７及びステップＳ８０７）点、及びインデックスキーを求める順序がそれぞれ昇順／降順である（ステップＳ７１１及びステップＳ８１１以降の処理）点については逆であるが、下限値及び上限値を求めるまでの手順は基本的に上記と同様である。
【００８４】
ステップＳ８０２以降の処理について具体的に説明する。
ステップＳ８０２でカップルドノードツリーに含まれるインデックスキーの最大値を求めると、ステップＳ８０３で、ステップＳ８０２で求めた最大値と上限キーとを比較し、上限キーが最大値より大きいか否かを判定する。上限キーがインデックスキーの最大値以上であるときは、ステップＳ８０４に進み、ステップＳ８０２で求めた最大値を上限値として設定し、処理を終了する。
【００８５】
上限キーが最大値よりも小さい場合は、ステップＳ８０５に進み、上限キーを検索キーに設定する。そして、ステップＳ８０６で、検索開始ノードの配列番号としてルートノードの配列番号を設定し、ステップＳ８０７で、検索キーについての検索処理を行い、ステップＳ８０８に進む。
【００８６】
ステップＳ８０８で、検索キーとステップＳ８０７で取得したインデックスキーとが等しいか否かを判定する。ステップＳ８０８でこれらの値が等しいと判定された場合は、ステップＳ８０９に進み、ステップＳ８０７の処理で得られたインデックスキーを上記上限値に設定し、処理を終了する。ステップＳ８０８で等しくないと判定された場合は、図８ＢのステップＳ８１０に進む。
【００８７】
ステップＳ８１０で、検索キーとインデックスキーとの大小関係を判定する。ここで、検索キーがインデックスキーよりも小さい場合は、そのインデックスキーは検索キーすなわち上限キーよりも小さく、ユーザ等により指定された検索範囲に含まれないことを意味する。一方、検索キーがインデックスキーよりも大きい場合は、そのインデックスキーは指定された検索範囲に含まれることを意味する。そこで、検索キーがインデックスキーよりも大きいと判定されると、ステップＳ８１８に進み、そのインデックスキーを上限値に設定して、処理を終了する。
【００８８】
ステップＳ８１０において、検索キーがインデックスキーよりも小さいと判定されると、ステップＳ８１１に進む。ステップＳ８１１以降の処理は、降順にインデックスキーを取り出す処理であり、検索キーがインデックスキーよりも大きいと判定されるまで、ステップＳ８１０からステップＳ８１７までの処理を繰り返す。
【００８９】
次に、図９Ａ〜図９Ｃ、図１０により本出願人による出願である上記特願２００６−１８７８２７で提案されたカップルドノードツリーにおけるノード挿入処理を説明する。図９Ａ〜図９Ｃが通常の挿入処理を説明するものであり、図１０はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【００９０】
図９Ａは挿入処理の前段である検索処理の処理フローを示す図であり、図４に示した検索処理において挿入キーを検索キーとしたものに相当する。ステップＳ９０１は図４のステップＳ４０１で検索開始ノードをルートノードとしたものに相当し、ステップＳ９０２〜ステップＳ９１０の処理は図４のステップＳ４０２〜ステップＳ４１０に完全に対応するので説明は省略する。
【００９１】
図９ＡのステップＳ９１１において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図９ＢのステップＳ９１２以下の処理に進む。
【００９２】
図９Ｂは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップＳ９１２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【００９３】
ステップＳ９１３に進み、挿入キーとステップＳ９１０で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１を小さいときは値０のブール値を得る。
ステップＳ９１４に進み、ステップＳ９１２で得た代表ノードの配列番号にステップＳ９１３で得たブール値を加算した配列番号を得る。
【００９４】
ステップＳ９１５に進み、ステップＳ９１２で得た代表ノードの配列番号にステップＳ９１３で得たブール値の論理否定値を加算した配列番号を得る。
ステップＳ９１４で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップＳ９１５で得た配列番号は、そのリーフノードと対を成すブランチノードが格納される配列要素のものである。
【００９５】
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【００９６】
例えば図２のカップルドノードツリーに“０１１０１１”を挿入する場合、検索結果のインデックスキーはノード２１１ｄに格納された“０１１０１０”になる。挿入キー“０１１０１１”とノード２１１ｄに格納されたインデックスキー“０１１０１０”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値１が得られ、挿入されるノード対の代表ノード番号に１を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー“０１１０１０”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。
【００９７】
その際、インデックスキー“０１１０１０”と挿入キー“０１１０１１”とは５ビット目で異なることから、ノード２１１ｄは、弁別ビット位置を５とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【００９８】
また図２のカップルドノードツリーに“０１１００１”を挿入しようとする場合も、検索結果のインデックスキーはノード２１１ｄに格納された“０１１０１０”になる。この場合には挿入キーが小さいのでブール値０が得られ、挿入されるノード対の代表ノード番号に０を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー“０１１０１０”と挿入キー“０１１００１”とは４ビット目で異なることから、ノード２１１ｄは、弁別ビット位置を４とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。次に図９ＣのステップＳ９１６以下の処理に進む。
【００９９】
図９Ｃは図９Ｂで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
ステップＳ９１６〜ステップＳ９２３までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップＳ９２４以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【０１００】
ステップＳ９１６で、挿入キーとステップＳ９１０で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップＳ９１７に進み、ステップＳ９１６で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【０１０１】
次にステップＳ９１８に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップＳ９２４に移行し、指していなければステップＳ９１９に進む。
【０１０２】
ステップＳ９１９において、探索経路スタックのスタックポインタを１つ戻してそこにスタックされている配列番号を取り出す。
ステップＳ９２０に進み、ステップＳ９１９で取り出した配列番号の配列要素を配列からノードとして読み出す。
【０１０３】
ステップＳ９２１に進み、ステップＳ９２０で読み出したノードから、弁別ビット位置を取り出す。
次にステップＳ９２２に進み、ステップＳ９２１で取り出した弁別ビット位置がステップＳ９１７で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【０１０４】
ステップＳ９２２の判定結果が否定であれば、ステップＳ９１８に戻り、ステップＳ９１８での判定が肯定になるかステップＳ９２２での判定が肯定になるまで繰り返す。ステップＳ９２２での判定が肯定になると、ステップＳ９２３で経路探索スタックのスタックポインタを1つ進め、ステップＳ９２４以下の処理に移行する。
【０１０５】
上記ステップＳ９１６〜ステップＳ９２３で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の（最上位の
）ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。
【０１０６】
例えば図２のカップルドノードツリーに“１１１０００”を挿入するとき、検索結果のインデックスキーはノード２１０ｈに格納された“１０１０１１”になる。挿入キー“１１１０００”とノード２１０ｈに格納されたインデックスキー“１０１０１１”のビット列比較により異なるビット値となる最上位のビット位置１が得られる。得られたビット位置１と経路探索スタックに積まれた配列番号の配列要素に格納されたブランチノードの弁別ビット位置との位置関係を弁別ビット位置が上位になるまでを順次経路探索スタック逆にたどると、ルートノード２１０ａに至る。そこで探索経路スタックのポインタを１つ進め、ノード２１１ｂの配列番号を得る。挿入キー“１１１０００”はノード２１１ｂのリンク先に挿入される。
【０１０７】
また、経路探索スタック逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【０１０８】
次に、ステップＳ９２４以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップＳ９２４では探索経路スタックからスタックポインタの指す配列番号を取り出す。
【０１０９】
ステップＳ９２５において、ステップＳ９１４で得た配列番号の指す配列要素のノード種別に１（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップＳ９２６に進み、配列からステップＳ９２４で得た配列番号の配列要素を読み出す。
【０１１０】
次にステップＳ９２７において、ステップＳ９１５で得た配列番号の配列要素にステップＳ９２６で読み出した内容を書き込む。
最後にステップＳ９２８において、ステップＳ９２４で得た配列番号の指す配列要素のノード種別に０(ブランチノード）を、弁別ビット位置にステップＳ９１７で得たビット位置を、代表ノード番号にステップＳ９１２で得た配列番号を書き込み、処理を終了する。
【０１１１】
上述の図２のカップルドノードツリーに“１１１０００”を挿入する例では、取得された空ノード対のノード[0]にノード２１１ｂの内容を書き込み（ステップＳ９２７）、ノード[1]を挿入キー“１１１０００”を保持するリーフノードとする（ステップＳ９２５）。そして、ノード２１１ｂの弁別ビット位置にビット列比較により異なるビット値となる最上位のビット位置１を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号が格納される（ステップＳ９２８）。
【０１１２】
図１０は、本出願人による出願である上記特願２００６−１８７８２７で提案されたルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【０１１３】
ステップＳ１０１において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図９Ａ〜図９Ｃを用いて説明した通常の挿入処理が行われる。
【０１１４】
ステップＳ１０１での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップＳ１０２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップＳ１０３において、ステップＳ１０２で得た配列番号に０を加えた配列番号を求める。（実際には、ステップＳ１０２で取得した配列番号に等しい。)。さらにステップＳ１０４において、ステップＳ１０３で得た配列番号の配列要素に、挿入するルートノードのノード種別に１（リーフノード)とインデックスキーに挿入キーを書き込み、ステップＳ１０５で、ステップＳ１０２で取得したルートノードの配列番号を登録して処理を終了する。
【０１１５】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図１０及び図９Ａ〜図９Ｃの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【０１１６】
次に図１１Ａ、図１１Ｂを参照して、本出願人による出願である上記特願２００６−１８７８２７で提案されたカップルドノードツリーに係るインデックスキーの集合から、特定のインデックスキーを削除する処理フローを説明する。
【０１１７】
図１１Ａは、削除処理の前段である検索処理の処理フローを示す図であり、図４に示した検索処理において削除キーを検索キーとしたものに相当する。ステップＳ１１０１は図４のステップＳ４０１で検索開始ノードをルートノードとしたものに相当し、ステップＳ１１０２〜ステップＳ１１１０の処理は図４のステップＳ４０２〜ステップＳ４１０に完全に対応するので説明は省略する。
【０１１８】
図１１ＡのステップＳ１１１１において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図１１ＢのステップＳ１１１２以下の処理に進む。
【０１１９】
図１１Ｂは、削除処理の後段の処理フローを説明する図である。
まず、ステップＳ１１１２で探索経路スタックに２つ以上の配列番号が格納されているか判定する。２つ以上の配列番号が格納されていないということは、言い換えれば１つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップＳ１１１８に移行し、ステップＳ１１０１で得たルートノードの配列番号に係るノード対を削除する。次にステップＳ１１１９に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【０１２０】
ステップＳ１１１２において探索経路スタックに２つ以上の配列番号が格納されていると判定されたときはステップＳ１１１３に進み、ステップＳ１１０８で得た代表ノード番号にステップＳ１１０７で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【０１２１】
次にステップＳ１１１４において、ステップＳ１１１３で得た配列番号の配列要素の内
容を読み出し、ステップＳ１１１５において探索経路スタックのスタックポインタを１つ戻して配列番号を取り出す。
【０１２２】
次にステップＳ１１１６に進み、ステップＳ１１１４で読み出した配列要素の内容をステップＳ１１１５で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
【０１２３】
最後にステップＳ１１１７においてステップＳ１１０８で得た代表ノード番号に係るノード対を削除して処理を終了する。
以上、カップルドノードツリーの分割／結合に関する本発明の前提となる技術を説明したが、必要とあれば、上述の特許出願の明細書及び図面の記載を参照されたい。
【０１２４】
次に、本発明のカップルドノードツリーの分割／結合方法について説明をする。
ここでカップルドノードツリーの分割とは、あるビット列からなる分割キーを指定したとき、カップルドノードツリーに含まれるインデックスキーをその分割キーとの大小関係により２グループに分け、それぞれのグループに属するインデックスキーからなる２つのカップルドノードツリーを生成することである。
【０１２５】
大小関係による分割について、以下の説明では、分割キーより大きいグループと分割キー以下のグループに分割するとするが、分割キー以上のグループと分割キーより小さいグループに分割する場合でも、同様に分割／結合が可能であることは、以下の説明から容易に理解されるであろう。
【０１２６】
要するに、分割キーはカップルドノードツリーをどこで分割するかを決定するために用いられるキーである。
また、カップルドノードツリーの結合とは、２つのインデックスキーの集合に対応する２つカップルドノードツリーから２つのインデックスキーの集合の和集合に対応するカップルドノードツリーを生成することである。本発明では、２つのインデックスキーの集合の積集合は空であることを前提にしている。
【０１２７】
以下、本発明の３つの実施例について説明をするが、その説明において、カップルドノードツリーを単にツリーということがある。以下説明する実施例１、２及び３では、指定された分割キーと等しいインデックスキーが分割処理対象のツリーに含まれる必要はないが、指定された分割キーに対応するインデックスキーを分割キーとする場合には、指定された分割キーを上限キーあるいは下限キーとして、図７Ａ、図７Ｂ、図８Ａ、図８Ｂを参照して説明した検索方法により上限値あるいは下限値を求め、それを指定された分割キーに対応する新たな分割キーとすることができる。
【実施例１】
【０１２８】
本実施例１は、分割対象である処理元のツリー（以下、単に処理元ということがある。）のインデックスキーの最小値を取り出し、取り出したインデックスキーの最小値を、処理元の分割により生成される処理先のツリー（以下、単に処理先ということがある。）に挿入し、処理元のツリーからインデックスキーの最小値を削除する処理を、最小値が分割キー以下である間繰り返すことにより、分割対象である処理元のツリーから処理先のツリーを分割するものである。
【０１２９】
図１２は、本発明の実施例１におけるカップルドノードツリーの分割処理フローを説明する図である。
最初のステップＳ１２０１で指定された分割キーを処理元の分割キーとして設定する。
分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。
【０１３０】
次にステップＳ１２０２で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップＳ１２０３に進む。
ステップＳ１２０３では、処理元のツリーが登録済みか判定する。この判定結果が登録済みではないというのは処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものであり、その場合には処理を終了する。
【０１３１】
処理元のツリーが登録済みであればステップＳ１２０４に移行し、ステップＳ１２０２で検索開始ノードとして設定したルートノードより、図５に示す処理を実行してインデックスキーの最小値を得る。
【０１３２】
次にステップＳ１２０５に進み、ステップＳ１２０４で得た最小値が分割キーより大きいか判定する。最小値が分割キーより大きければ、ツリーの分割が完成しているのであるから処理を終了し、大きくなければ、以下で説明するステップＳ１２０６〜ステップＳ１２０９の処理先のツリーの生成と処理元のツリーからのノードの削除処理を実行し、ステップＳ１２０３へ戻る。
【０１３３】
ステップＳ１２０６では、ステップＳ１２０４で得られた最小値を処理先の挿入キーに設定する。
次にステップＳ１２０７で、図９Ａ〜図９Ｃ、図１０に示すツリーの生成、挿入処理により、挿入キーによる処理先のツリーの生成を実行する。
【０１３４】
続いてステップＳ１２０８で、ステップＳ１２０７における挿入キーを処理元の削除キーに設定し、ステップＳ１２０９において、図１１Ａ、図１１Ｂに示す削除処理により、処理元のツリーから削除キーを含むリーフノードを削除する。
【０１３５】
上記分割処理の説明では、処理元のインデックスキーの最小値から順に削除を行うようにしたが、同様にインデックスキーの最大値から順に削除を行うことができることは、当業者に明らかである。その場合、ステップＳ１２０４はインデックスキーの最大値を求める処理になり、ステップＳ１２０５は最大値と分割キーの大小関係の判定処理となり、ステップＳ１２０６では最大値を処理先の挿入キーに設定することになる。
【０１３６】
以上、分割処理について説明したが、結合処理も図１２に示す処理フローにより実行できる。
結合処理は、結合しようとする２つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上とすれば、先に述べた例外的な処理に該当し、処理元のツリーは削除され、処理先のツリーに結合される。なお、処理元のツリーのインデックスキーの最大値が未知の場合には、前もって図６に示す最大値検索処理により分割キーを求めることになる。
【０１３７】
そして、処理元の分割キーを処理元のツリーのインデックスキーの最大値以上とするのであるから、ステップＳ１２０５の大小比較では、分割キーが最小値より常に大きくステップＳ１２０６へ分岐するのでステップＳ１２０５を省略することができる。そうであれば、分割キーを設定する意味もないことから、結局ステップＳ１２０１も不要になり、ただ単に最小値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができる。
【０１３８】
また、分割処理について述べたように、最大値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができることも明らかである。
本実施例１は処理のロジックは簡易なものであるが、処理元のルートノードを検索開始ノードとする最小値検索を繰り返し、インデックスキー単位で挿入削除を行うため、実行時の処理ステップ数は大きくなる。
【実施例２】
【０１３９】
本実施例２は、インデックスキー単位で挿入削除を行う点では実施例１と同様であるが、挿入削除すべきインデックスキーの探索に探索経路スタックを活用し、挿入処理及び削除処理の実行時の処理ステップ数を小さくしたものである。
【０１４０】
図１３は、本発明の実施例２におけるカップルドノードツリーの分割処理フローを説明する図である。
ステップＳ１３０１からステップＳ１３０６までの処理は、図１２に示す実施例１のステップＳ１２０１からステップＳ１２０６までの処理とまったく同じであるから、説明を省略する。
【０１４１】
ステップＳ１３０７において、挿入キーにより、処理先にノードを挿入する。この処理は、図１２に示すステップＳ１２０７の挿入処理とは異なる本実施例特有のものであり、後に図１４、図１５Ａ、図１５Ｂを参照して詳細に説明する。
【０１４２】
次にステップＳ１３０８においてステップＳ１３０４で得た最小値を含むノードを、処理元の削除ノードとして設定し、ステップＳ１３０９において処理元から削除ノードを削除し、削除ノードと対をなすノードの内容が複写される処理元の親ノードを得る。
【０１４３】
続いてステップＳ１３１０で、ステップＳ１３０９で得られた処理元の親ノードを、処理元の検索開始ノードに設定し、ステップＳ１３０３に戻る。
後に説明するように、処理元の親ノードは削除ノードの直近上位のブランチノードである。削除ノードは処理元のインデックスキーの最小値を含むものであり、先に述べたインデックスキーの順序性から、次に検索する最小値は処理元の親ノードの下位にある。
【０１４４】
したがって、２回目以降のステップＳ１３０４での最小値検索の検索開始ノードはルートノードとしないで処理元の親ノードとすることにより、処理ステップ数を低減することができる。
【０１４５】
ステップＳ１３０８〜ステップＳ１３０９及び処理元の親ノードについては、後に図１６を参照して詳細に説明する。
図１４は、図１３に示すステップＳ１３０６とステップＳ１３０７に対応するノードの挿入処理フローを説明する図である。
【０１４６】
最初のステップＳ１４０１における挿入キーを処理先の挿入キーとして設定するステップは、図１３に示すステップＳ１３０６に対応する処理であり、図１３に示すステップＳ１３０４で得られた最小値を処理先の挿入キー設定エリアに設定する。
【０１４７】
次にステップＳ１４０２において、処理先が登録済みか判定する。
登録済みでなければステップＳ１４０３に移行し、ステップＳ１４０３において、挿入キーを含むノード対を処理先のルートノードに設定し、処理先のルートノードとして登録する。続いてステップＳ１４０４に進み、処理先のルートノードを挿入済みノードとして設定して処理を終了する。
【０１４８】
上記ステップＳ１４０２での判定結果が登録済みであれば、ステップＳ１４０５に移行する。ステップＳ１４０５では、挿入済みノードが設定済みであるか判定する。この判定処理は、後に説明するツリーの結合処理で必要になるものである。ツリーの分割処理では、最初の挿入処理においてステップＳ１４０４でルートノードを挿入済みノードとして設定することから、ステップＳ１４０６の判定は常に「はい」である。したがって、分割処理だけのためであれば、ステップＳ１４０５とステップＳ１４０７は必須ではない。
【０１４９】
ステップＳ１４０５での判定結果が「はい」であればステップＳ１４０６に進み、挿入済みノードとして設定されているノードを処理先の検索開始ノードとして設定し、ステップＳ１４０８に進む。
【０１５０】
ステップＳ１４０５での判定結果が「いいえ」であればステップＳ１４０７に進み、ルートノードを処理先の検索開始ノードとして設定し、ステップＳ１４０８に進む。
ステップＳ１４０８では、図６に示す最大値検索処理により、ステップＳ１４０６あるいはステップＳ１４０７で設定された検索開始ノードから処理先のインデックスキーの最大値を求める。
【０１５１】
次にステップＳ１４０９において、ステップＳ１４０１で設定された挿入キーとステップＳ１４０７で得られた最大値により、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する。
【０１５２】
続いてステップＳ１４１０に進み、ステップＳ１４０９において挿入キーを含むノード対を挿入された処理先の親ノードを挿入済みノードとして設定し、処理を終了する。
次に、上述のステップＳ１４０３とステップＳ１４０９について詳細に説明する。
【０１５３】
図１５Ａは、図１４に示すステップＳ１４０３のルートノード設定処理を説明するフロー図である。
まず、ステップＳ１５０１で配列からノード対が空の代表ノード番号を取得する。
【０１５４】
次にステップＳ１５０２において、ステップＳ１５０１で取得した代表ノード番号に値“０”を加えて得た配列番号を、挿入ノードの配列番号として設定しておく。
ステップＳ１５０３に進み、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップＳ１５０２で設定した配列番号の配列要素に格納する。
【０１５５】
次にステップＳ１５０４において、挿入ノードの配列番号をルートノードの配列番号として登録して処理を終了する。
なお、上記ステップＳ１５０１〜ステップＳ１５０４の処理は、図１０を参照して説明したカップルドノードツリーの生成処理において、ルートノードの配列番号が登録済みでない場合の、ステップＳ１０２〜ステップＳ１０５に対応するものである。
【０１５６】
図１５Ｂは、図１４に示すステップＳ１４０９の、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する処理を説明するフロー図である。図１５Ｂに示すフローは、本出願人による先の出願である特願２００６−１８７８２７で提案された挿入処理の応用であり、ステップＳ１５０５の、挿入キーと最大値をビット列として比較して上位０ビット目から見た最初の不一致ビットの位置を求め、それを差分ビット位置を格納するエリアに設定する処理は、図９Ｃに示すステップＳ９１６とステップＳ９１７の処理に対応する。
【０１５７】
ステップＳ１５０５に続いてステップＳ１５０６に進む。なお、ステップＳ１５０６〜
ステップＳ１５１２の処理は図９Ｃに示すステップＳ９１８〜ステップＳ９２３に相当し、ステップＳ１５１３〜ステップＳ１５１８の処理は図９Ｃに示すステップＳ９２４〜ステップＳ９２８に相当する。
【０１５８】
ステップＳ１５０６において、処理先の探索経路スタックのスタックポインタを１つ戻して、配列番号を取り出す。
次にステップＳ１５０７において、配列から、配列番号の指す配列要素の内容をノードとして取り出す。
【０１５９】
次にステップＳ１５０８において、ステップＳ１５０７で取り出したノードから、弁別ビット位置を取り出す。
続いてステップＳ１５０９において、ステップＳ１５０５で設定した差分ビット位置とステップＳ１５０８で取り出した差分ビット位置を比較し、弁別ビット位置が差分ビット位置より上位の位置関係か判定する。
【０１６０】
その判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係であれば、ステップＳ１５１２に進み、処理先の探索経路スタックのスタックポインタを１つ戻して配列番号を取り出し、それを親ノードの配列番号エリアに設定してステップＳ１５１３に移行する。
【０１６１】
ステップＳ１５０９での判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係でなければ、ステップＳ１５１０に進む。
ステップＳ１５１０では、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。
【０１６２】
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合には、ステップＳ１５０６に戻る。
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指している場合には、ステップＳ１５１１において処理先の探索経路スタックからスタックポインタの指す配列番号を取り出し、処理先の親ノードの配列番号を格納するエリアに設定してステップＳ１５１３に移行する。
【０１６３】
ステップＳ１５１３においては、配列からノード対が空きの代表ノード番号を取得する。
次にステップＳ１５１４において、代表ノード番号に１を加えて得た配列番号を挿入ノードの配列番号を格納するエリアに設定する。
【０１６４】
次にステップＳ１５１５において、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップＳ１５１４で設定した配列番号の配列要素に格納する。
【０１６５】
次にステップＳ１５１６において、代表ノード番号に０を加えて得た配列番号を、挿入ノードと対をなす対ノードの配列番号を格納するエリアに設定する。
次にステップＳ１５１７において、ステップＳ１５１１あるいはステップＳ１５１２で設定した処理先の親ノードの配列番号の指す配列要素の内容を読み出し、ステップＳ１５１６で設定した対ノードの配列番号の指す配列要素に格納する。
【０１６６】
次にステップＳ１５１８において、ブランチノードを形成するため、ノード種別にブランチを、弁別ビット位置にステップＳ１５０５で設定した差分ビット位置を、代表ノード番号にステップＳ１５１６で設定した対ノードの配列番号を設定し、ステップＳ１５１１
あるいはステップＳ１５１２で設定した処理先の親ノードの配列番号の指す配列要素に格納して処理を終了する。
【０１６７】
図１６は、図１３に示す処理フローにおける削除処理について説明する処理フロー例を示す図である。
最初のステップであるステップＳ１６０１は、図１３に示すステップＳ１３０８に相当するものである。削除ノードに含まれる削除キーは図１３に示すステップＳ１３０４において最小値検索により求められたものであるから、処理元の探索経路スタックには削除キーの格納された配列要素の配列番号がスタックされているので、その配列番号を読み出して削除ノードを格納するエリアに設定する。
【０１６８】
次のステップＳ１６０２では、処理元の探索経路スタックに２つ以上の配列番号が格納されているか判定される。このステップＳ１６０２以降、ステップＳ１６０８に至る処理は、図１１Ｂに示す、本出願人による先の出願である特願２００６−１８７８２７で提案された削除処理の後段の処理に対応するものである。
【０１６９】
処理元の探索経路スタックに２つ以上の配列番号が格納されていなければ、ステップＳ１６０７に移行し、ステップＳ１６０１で設定した削除ノードの配列番号の指すノード対を削除し、ステップＳ１６０８に進み、ルートノードの配列番号を削除（登録を抹消）して処理を終了する。
【０１７０】
処理元の探索経路スタックに２つ以上の配列番号が格納されていれば、ステップＳ１６０３に進み、ステップＳ１６０１で設定した削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号を格納するエリアに設定する。
【０１７１】
次にステップＳ１６０４において、処理元の探索経路スタックのスタックポインタを１つ戻して配列番号を取り出し、削除ノードの直近上位のブランチノードである処理元の親ノードの配列番号格納エリアに設定する。
【０１７２】
次にステップＳ１６０５において、ステップＳ１６０３で設定した対ノードの配列番号の指す配列要素の内容を読出し、ステップＳ１６０４で設定した処理元の親ノードの配列番号の指す配列要素に格納する。
【０１７３】
次にステップＳ１６０６において、削除ノードの配列番号の指すノード対を削除して処理を終了する。
以上、実施例２のツリー分離処理について説明したが、実施例２においても、実施例１の場合と同様にインデックスキーの最大値から順に削除を行うことができる。
【０１７４】
また、実施例１の場合と同様に分離処理の処理フローをツリーの結合処理に用いることが可能である。結合しようとする２つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上あるいは最小値以下として処理元のツリーの削除処理を行い、削除されたノードを処理先のツリーに挿入する処理を行えばよい。
【実施例３】
【０１７５】
上述の実施例１と実施例２の分割結合方法は、インデックスキー単位で挿入削除を行うものであるが、次に実施例３として、カップルドノードツリーの順序性に着目した、カップルドノードツリーのより大きい、所定の条件を満たす、部分木を単位として挿入削除を行う分割結合方法を説明する。
【０１７６】
図１７は、実施例３におけるカップルドノードツリーの分割処理フローを説明する図である。また、図３０Ａ〜図３０Ｃは、上記分割処理を実例により説明する図であり、図２に例示したカップルドノードツリーと類似したツリーを例示している。図３０Ａは分割前のツリー構造例を示し、図３０Ｂは最初の分割後のツリー構造例を示し、図３０Ｃは次の分割後のツリー構造例を示している。
【０１７７】
まず図１７に示すように、ステップＳ００１で分割キーを取得して分割キーを格納するエリアに設定する。図３０Ａの例示では、分割キーはノード２１１ｇのインデックスキー２５１ｇの“１０００１１”と等しい。なお、先に述べたように、取得する分割キーは処理元に含まれる必要はないが、後に説明するように、本実施例においては取得された分割キーにより上限値あるいは下限値を求めて処理元に含まれるインデックスキーを新たな分割キーとする必要がある。したがって、以下の説明では分割キーは処理元に含まれるものとして説明する。
【０１７８】
次にステップＳ００２で分割キーにより処理元の分割ノードを求める。分割ノードは、分割キーを最大値として含む部分木のうち最大のもの（以下、分割ノードツリーという。）のルートノードである。図３０Ａの例示では、ノード２１０ｆが分割ノードであり、点線で囲まれた部分木が分割ノードツリー２９１である。分割ノードを求める処理の詳細は後に図１８と図１９を参照して説明する。
【０１７９】
次にステップＳ００３に進み、処理先は登録済みか判定する。登録済みでなければステップＳ００４に進み、ステップＳ００２で求めた分割ノードを処理先のルートノードに設定して処理先のルートノードとして登録し、さらにステップＳ００７に移行して分割ノードツリーの削除処理を実行する。なお、ステップＳ００４の処理の詳細な説明は後に図２０を参照して行う。
【０１８０】
図３０Ａの例示では、分割処理が開始されたばかりであり、図３０Ａの（ｂ）に示すように処理先は存在せず登録されていないから、ステップＳ００４に進み、分割ノード２１０ｆの内容を処理先として新たに取得されたノード対２０１ｉの代表ノード２１０ｉに格納して処理先のルートノードに設定し、処理先のルートノードとして登録する。その結果として、図３０Ｂの（ｂ）に示すように、挿入された分割ノードツリー２９１からなる処理先のツリーが生成される。
【０１８１】
一方、図３０Ｂの（ａ）には、処理元からノード２１１ｇを分割ノードとする分割ノードツリー２９１が削除されたツリー構造が示されており、分割ノード２１０ｂをルートノードとする次の分割ノードツリー２９２が点線で囲まれて示されている。
【０１８２】
ステップＳ００３での判定結果が登録済みであればステップＳ００５に移行する。ステップＳ００５では、後記ステップＳ０１０で設定された次の分割ノードツリーの最大値である分割キーと処理先の最小値の差分ビット位置を求める。差分ビット位置を求める処理の詳細は後に図２１を参照して説明する。
【０１８３】
図３０Ｂの例示では、次の分割ノードツリー２９２の最大値はインデックスキー２５１ｃ“０１１０１０”であり、処理先の最小値はインデックスキー２５０ｇ“１０００１０”であるから、差分ビット位置は“０”である。
【０１８４】
次にステップＳ００６に進み、処理先のルートノードを挿入位置として処理先に分割ノードツリーを挿入し、ステップＳ００７に進む。
ステップＳ００７では、処理元から分割ノードツリーを削除する。そして、ステップＳ００８に進み、次の分割ノードを求める。
【０１８５】
図３０Ｃの（ｂ）の例示では、ルートノード２１０ｉを挿入位置とし、新たに取得されたノード対２０１ｊを介して次の分割ノードツリー２９２が処理先に挿入されたツリー構造が示されている。また、図３０Ｃの（ａ）には、図３０Ｂの（ａ）に示されたツリー構造から次の分割ノードツリー２９２が削除された構造が示されている。
【０１８６】
ステップＳ００６における分割ノードツリーの挿入処理、ステップＳ００７における削除処理、及びステップＳ００８における次の分割ノードを求める処理の詳細は、後にそれぞれ図２２、図２３、図２４を参照して説明する。
【０１８７】
ステップＳ００８に続いてステップＳ００９において、ステップＳ００８で分割ノードが求まったか判定される。分割ノードが求まらなければ分割処理は終了となる。
分割ノードが求まれば、ステップＳ０１０において、その分割ノードをルートノードとする部分木である分割ノードツリーの最大値を求めて次の分割キーとし、ステップＳ００５に戻って次の分割ノードツリーの挿入、削除処理及び更なる次の分割ノードを求める処理を繰り返す。
【０１８８】
ステップＳ０１０における分割ノードの最大値を求めて次の分割キーとする処理の詳細は、後に図２５を参照して説明する。
本実施例では上述のように分割ノードツリー単位で削除挿入処理が行われるため、処理ステップ数が削減される。
【０１８９】
次に、図１８と図１９を参照して図１７に示すステップＳ００２における分割ノードを求める処理を詳細に説明する。
図１８は、最初の分割ノードを求める処理フローの前段を説明する図である。
【０１９０】
図１８に示すように、ステップＳ１８０１で分割キーを検索キーとして設定し、ステップＳ１８０２で処理元のルートノードの格納された配列要素の配列番号を検索開始ノードの配列番号として設定する。
【０１９１】
次にステップＳ１８０３に進み、図４に示す検索処理を実行し、検索結果として分割キーと等しいインデックスキーを得て前段の処理を終了し、図１９に示す後段の処理に進む。
【０１９２】
後段の処理は図１９を参照して説明するが、その前に、図３０Ａを再び参照して、本実施例においては分割キーを処理元に含まれるインデックスキーとしておく必要性について説明する。
【０１９３】
いま、図３０Ａに示す処理元を分割キー“１００００１”で分割するとする。この分割キーで図１８に示すステップＳ１８０３の検索処理を実行すると、検索結果として得られるインデックスキーはインデックスキー２５１ｇの“１０００１１”である。ところが、分割点とすべきインデックスキーは、リーフノード２１１ｃに格納された、“１００００１”を上限とする上限値“０１１０１０”あるいはリーフノード２１１ｇに格納された、“１００００１”を下限とする下限値“１０００１０”であり、いずれの場合も分割キー“１００００１”で検索した結果と一致しないからである。
【０１９４】
したがって、分割ノードを求める前に、分割キーをその定義に応じて処理元に含まれるインデックスキーとして求めておく必要がある。
図１９は、最初の分割ノードを求める処理フローの後段を説明する図である。後段の処理は、処理元の探索経路スタックを遡り、最初のノード〔０〕の配列番号を求めて分割ノ
ードの配列番号として設定するものである。
【０１９５】
図１９に示すように、ステップＳ１９０１で探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。探索経路スタックのスタックポインタがルートノードの配列番号を指していれば、ステップＳ１９０６に進み、ルートノードの配列番号を分割ノードの配列番号として設定して処理を終了する。
【０１９６】
探索経路スタックのスタックポインタがルートノードの配列番号を指していなければ、ステップＳ１９０２へ進み、探索経路スタックから配列番号を取り出し、スタックポインタを１つ減らす。
【０１９７】
次にステップＳ１９０３において、ステップＳ１９０２で取り出した配列番号からこの配列番号の配列要素に配置されたノードが当該ノード対のどちら側の位置であるかを得る。
【０１９８】
そして、ステップＳ１９０４において、ステップＳ１９０３で得たノード位置がノード〔１〕側か判定する。
判定の結果がノード〔１〕側であればステップＳ１９０１の処理に戻り、ノード〔０〕側であればステップＳ１９０５に移行してステップＳ１９０２で取り出した配列番号を分割ノードの配列番号として設定して処理を終了する。
【０１９９】
図３０Ａに示す例では、ルートノード２１０ａの配列番号２２０を検索開始キーに設定して分割キー“１０００１１”により検索処理を実行すると検索結果としてのインデックスキー２５１ｇが得られ、経路探索スタックには配列番号２２０、２２０ａ＋１、２２１ｂ、２２０ｆ＋１が順次スタックされる。
【０２００】
したがって、図１９に示すステップＳ１９０１の最初の処理時には探索経路スタックのスタックポインタは配列番号２２０ｆ＋１を指しており、次にステップＳ１９０４の判定処理の結果ステップＳ１９０１に戻り、次のステップＳ１９０４では１つ遡って配列番号２２１ｂのノード２１０ｆのノード位置が判定され、ステップＳ１９０５に移行してノード２１０ｆの配列番号２２１ｂが分割ノードの配列番号として設定される。
【０２０１】
ここで、さらに分割処理について説明する前に、分割キーは分割ノードツリーの最大値であり、分割ノードツリーは分割キーを最大値とする処理元の部分木のうち最大の部分木、別の表現をすればそのルートノードの弁別ビット位置が最上位である部分木であることを説明する。
【０２０２】
今までの説明から明らかなとおり、分割ノードは、分割キーで検索を行ったときの分割キーに至るまでの経路を遡って初めてのノード〔０〕である。
分割キーをインデックスキーとして含むリーフノードがノード〔０〕であれば、そのリーフノードが分割ノード自体であり、分割ノードツリーは１つのリーフノードだけから構成される。このリーフノードと対をなすノード〔１〕側に存在するリーフノードのインデックスキーは、カップルドノードツリーの順序性によって全て分割キーより大きい。したがって、今のケースの場合、分割キーより上位のブランチノードをルートノードとする部分木においては分割キーは最大値とはなりえないから、分割キーは分割ノードツリーの最大値であり、分割ノードツリーは分割キーを最大値とする処理元の部分木のうち最大のものである。
【０２０３】
分割キーをインデックスキーとして含むリーフノードがノード〔１〕であれば、ツリーをノード〔１〕側をたどって遡っている限りは、カップルドノードツリーの順序性により
、どのノード〔１〕をルートノードとする部分木においても上記分割キーはこれらの部分木の最大値である。そして、ノード〔０〕にまで遡ったとき、それ以上上位のノードの下位には当該ノード〔０〕と対をなすノード〔１〕以下のノードが存在し、これらのノードには上記分割キーより大きいインデックスキーを含むリーフノードが存在する。
【０２０４】
したがって、上記ノード〔０〕すなわち分割ノードをルートノードとする部分木が、上記分割キーを最大値として含む最大の部分木である。
以下引き続き、分割処理の説明を、図２０以下を参照して行う。
【０２０５】
図２０は、図１７に示すステップＳ００４における処理先のルートノードの挿入処理の処理フローを説明する図である。
ステップＳ２００１において、図１７に示す処理フローのステップＳ００２で求められた分割ノードの格納された配列要素の配列番号を挿入ノードの配列番号として設定する。
【０２０６】
次にステップＳ２００３で、配列から、空のノード対の代表ノード番号を取得する。
次にステップＳ２００４で、ステップＳ２００３で取得した代表ノード番号をノード［０］の配列番号として設定する。
【０２０７】
次にステップＳ２００５において、ステップＳ２００１で設定された挿入ノードの配列番号の指す配列要素の内容を読み出して、ステップＳ２００４で設定されたノード［０］の配列番号の指す配列要素に格納する。
【０２０８】
最後にステップＳ２００９で、ノード［０］の配列番号を処理先のルートノードの配列番号として登録して、ルートノードの挿入処理を終了する。
図３０Ａ及び図３０Ｂの（ｂ）の例示では、分割ノード２１０ｆの格納された配列要素の配列番号２２１ｂが挿入ノードの配列番号に設定され、取得された空のノード対２０１ｉの代表ノード番号２２０’ がノード［０］の配列番号として設定される。
【０２０９】
そして、配列番号２２１ｂが指す配列要素の内容、すなわち分割ノード２１０ｆの内容が配列番号２２０’の指す配列要素すなわちノード２１０ｉに格納され、配列番号２２０’が処理先のルートノードの配列番号として登録される。
【０２１０】
図２１は、図１７に示すステップＳ００５における分割キーと処理先の最小値により差分ビット位置を求める処理フローを説明する図である。
図２１に示すように、ステップＳ２１０１で、処理先のルートノードの配列番号を、検索開始ノードの配列番号として設定する。
【０２１１】
次にステップＳ２１０２において、図５に示す最小値検索を実行し、処理先のインデックスキーの最小値を得る。
次にステップＳ２１０３において、図１７に示すステップＳ０１０で設定された分割キーとステップＳ２１０３で得られた最小値をビット列比較して上位０ビット目から見た最初の不一致ビット位置を求め、差分ビット位置として設定する。
【０２１２】
なお、上記ステップＳ２１０１においては、処理先のルートノードの配列番号を、検索開始ノードの配列番号として設定するものとしたが、最後に処理先に挿入された分割ノードツリーに処理先の最小値が含まれていることは明らかであるから、最後に挿入された分割ノード、例えば図３０Ｂの（ｂ）に例示した処理先においては、ノード２１０ｊの配列番号２２０ｊを検索開始ノードの配列番号として設定することにより、最小値検索の処理を軽減することができる。
【０２１３】
図２２は、図１７に示すステップＳ００６におけるルートノード以外の処理先への挿入処理の処理フローを説明する図である。
最初にステップＳ２２０１で、図１７に示す処理フローのステップＳ００８で求められた分割ノードの格納された配列要素の配列番号を、挿入ノードの配列番号として設定する。このステップＳ２２０１は図２０に示すステップＳ２００１とは、分割ノードが求められた処理ステップがステップＳ００８である点で異なるだけである。
【０２１４】
次にステップＳ２２０２において、処理先の挿入位置として、ルートノードの配列番号を設定する。
次のステップＳ２２０３〜ステップＳ２２０５は、図２０に示すルートノードの挿入処理のステップＳ２００３〜ステップＳ２００５と同様である。
【０２１５】
ステップＳ２２０３で、配列から、空のノード対の代表ノード番号を取得し、次にステップＳ２２０４で、ステップＳ２２０３で取得した代表ノード番号をノード［０］の配列番号として設定し、次にステップＳ２２０５において、ステップＳ２２０１で設定された挿入ノードの配列番号の指す配列要素の内容を読み出して、ステップＳ２２０４で設定されたノード［０］の配列番号の指す配列要素に格納する。
【０２１６】
次にステップS２２０６に進み、ステップＳ２２０３で取得した代表ノード番号に値１を加えた値を、ノード［１］の配列番号として設定する。
次にステップS２２０７において、ステップS２２０２で設定した処理先の挿入位置の配列番号の指す配列要素の内容を読み出し、ステップS２２０６で設定したノード［１］の配列番号の指す配列要素に格納する。
【０２１７】
最後にステップS２２０８において、ノード種別にブランチを、弁別ビット位置に図１７に示すステップＳ００５で求めた弁別ビット位置を、代表ノード番号にステップＳ２２０４で設定したノード［０］の配列番号を設定してブランチノードを形成し、ステップS２２０２で設定した処理先の挿入位置の配列番号の指す配列要素に格納して処理を終了する。
【０２１８】
図３０Ｂ及び図３０Ｃの例示では、分割ノード２１０ｂの格納された配列要素の配列番号２２０ａが挿入ノードの配列番号に設定され、処理先の挿入位置としてルートノード２１０ｉの配列番号２２０’が設定される。また、取得された空のノード対２０１ｊの代表ノード番号２２０ｊがノード［０］の配列番号として設定される。
【０２１９】
そして、挿入ノードの配列番号２２０ａが指す配列要素の内容、すなわち分割ノード２１０ｂの内容をノード［０］の配列番号２２０ｊの指す配列要素すなわちノード２１０ｊに格納される。
【０２２０】
一方、代表ノード番号２２０ｊに１を加えて得た値である配列番号２２０ｊ＋１の指す配列要素すなわちノード２１１ｊに、処理先の挿入位置の配列番号２２０’の指す配列要素すなわち図３０Ｂの（ｂ）に示すルートノード２１０ｉの内容を格納している。
【０２２１】
そして図３０Ｃの（ｂ）に示すルートノード２１０ｉの弁別ビット位置２３０ｉには、先に図１７のステップＳ００５に関する例示で説明した分割ノードツリー２９２の最大値であるインデックスキー２５１ｃ“０１１０１０”と処理先の最小値であるインデックスキー２５０ｇ“１０００１０”の差分ビット位置 “０”が格納されている。また、代表ノード番号には、ノード［０］の配列番号２２０ｊが格納されている。
【０２２２】
上記説明から理解されるように、挿入先が生成された後の挿入処理は、挿入先のルート
ノードの直下にブランチノード同士からなるノード対を挿入し、そのノード対のノード〔１〕以下に既存の処理先のルートノード以下の部分木を接続し、ノード〔０〕に分割ノードツリーを接続するものである。この処理により、分割ノードツリーを挿入後の挿入先の順序性が保たれることは明らかである。
【０２２３】
図２３は、図１７に示すステップＳ００７における分割ノードツリーの削除処理の処理フローを説明する図である。同じ削除処理で類似している点もあるが、図１６に示す削除処理は削除キーの格納されたリーフノードである削除ノードの削除であるのに対して、図２３に示すものは基本的にはブランチノードである分割ノードの削除であり、処理元からは該分割ノードをルートノードとする分割ブランチノードツリーが削除される。
【０２２４】
まずステップＳ２３０１において、図１７に示すステップＳ００２もしくはステップＳ００８で求めた分割ノードの配列番号を処理元の削除ノードの配列番号として設定する。
次にステップＳ２３０１で設定された削除ノードの配列番号が、処理元のルートノードの配列番号と一致するか判定する。削除ノードの配列番号が、処理元のルートノードの配列番号と一致するときは、ステップＳ２３０３に進み、処理元のルートノードの代表ノード番号の指すノード対を削除し、次にステップＳ２３０４で処理元のルートノードの配列番号の登録を抹消して処理を終了する。
【０２２５】
ステップＳ２３０２の判定処理の結果、削除ノードの配列番号が処理元のルートノードの配列番号と一致しないときは、ステップＳ２３０５に進み、ステップＳ２３０１で設定された削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号として設定する。
【０２２６】
次にステップＳ２３０６において、処理元の探索経路スタックから配列番号を取り出し、その取り出した配列番号をステップＳ２３０７において親ノードの配列番号として設定するとともに、親ノードの代表ノード番号を退避する。なお、処理元の探索経路スタックには、図１９に示すステップＳ１９０２あるいは後に説明する図２４に示すステップＳ２４０２の処理により、分割ノードの直近上位である親ノードの配列番号が格納されている。
【０２２７】
次にステップＳ２３０８において、ステップＳ２３０５で設定した対ノードの配列番号の指す配列要素の内容を読み出し、ステップＳ２３０７で設定した親ノードの配列番号の指す配列要素に格納する。
【０２２８】
最後にステップＳ２３０９において、ステップＳ２３０７で退避した親ノードの代表ノード番号の指すノード対を削除し、処理を終了する。
図２４は、図１７に示すステップＳ００８における次の分割ノードを求める処理の処理フローを説明する図である。
【０２２９】
ステップＳ２４０１において、処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指していれば「分割ノードなし」を返す。
【０２３０】
処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指していなければステップＳ２４０２に進み、探索経路スタックから配列番号を取り出し、探索経路スタックのスタックポインタを１つ減らす。
【０２３１】
次にステップＳ２４０３に進み、ステップＳ２４０２で取り出された配列番号から、その配列番号が指す配列要素に格納されたノードのノード位置を得る。
次にステップＳ２４０４において、ステップＳ２４０３で得たノード位置がノード〔０〕側であるか判定する。ノード〔０〕側であればステップＳ２４０１に戻り、ノード〔１〕側であればステップＳ２４０６に移行してＳ２４０２で取り出した配列番号から値１を減じて得たノード〔０〕の配列番号を、分割ノードの配列番号として設定して「分割ノードあり」を返す。
【０２３２】
図３０Ａ及び図３０Ｂの例示では、次の分割ノードを求める段階では処理元の経路探索スタックのスタックポインタは分割ノード２１０ｆの親ノードの配列番号である２２０ａ＋１を指しており、ノード位置がノード〔１〕側となることから、それと対を成すノード〔０〕側に位置するノード２１０ｂが次の分割ノードとなり、それの格納されている配列要素の配列番号である２２０ａが分割ノードの配列番号として設定される。
【０２３３】
また、図３０Ｂ及び図３０Ｃの例示では、さらに次の分割ノードを求める段階では処理元の経路探索スタックのスタックポインタはノード２１０ｂの親ノードであるルートノード２１０ａの配列番号２２０を指しているから、上記ステップＳ２４０１の判定処理の結果分割ノードなしを返す。すなわち、分割ノードの親ノードがルートノードになると次の分割ノードは存在しない。これは、カップルドノードツリーの順序性から見て当然である。
【０２３４】
図２５は、図１７に示すステップＳ００８で求めた分割ノードをルートノードとする分割ノードツリーの最大値を求め次の分割キーとするステップＳ０１０の処理フローを説明する図である。
【０２３５】
始めにステップＳ２５０１において、処理元の探索経路スタックのスタックポインタの値を退避する。その理由は、図１９に示すステップＳ１９０２あるいは図２４に示すステップＳ２４０２の処理によって分割ノードの親ノードの配列番号を指している処理元のスタックポインタの値が、後記ステップＳ２５０３の最大値検索によって変動し、図２３に示すステップＳ２３０６で用いることができなくなるからである。
【０２３６】
次にステップＳ２５０２において、図２４のステップＳ２４０６で設定された分割ノードの配列番号を検索開始ノードの配列番号として設定する。
そしてステップＳ２５０３において、図６に示す最大値検索を実行し、インデックスキーの最大値を求める。
【０２３７】
次にステップＳ２５０４に進み、ステップＳ２５０２で得た最大値を分割キーとして設定する。
最後にステップＳ２５０５において、ステップＳ２５０１で退避した値を処理元の探索経路スタックのスタックポインタの値として復元して処理を終了する。
【０２３８】
以上、図２４および図２５を参照して詳細に説明したところから理解されるように、図１７のステップＳ００８で求めた次の分割ノードとステップＳ０１０で求めた次の分割キーの関係は、先に説明したステップＳ００１で設定された分割キーとステップＳ００２で求めた分割ノード、あるいは分割ノードツリーの関係と同様である。
【０２３９】
上記ステップＳ０１０で求めた次の分割キーがステップＳ００８で求めた次の分割ノードをルートノードとする分割ノードツリーの最大値であることは自明である。また、ステップＳ００８で求めた次の分割ノードはノード〔０〕であるから、それより上位のノードをルートノードとする部分木は、ステップＳ０１０で求めた次の分割キーより大きいインデックスキーを格納したリーフノードを含むことも、カップルドノードツリーの順序性により明らかである。
【０２４０】
以上により、実施例３によるカップルドノードツリーの分割処理について詳細に説明しが、実施例３によれば、分割ノードツリー単位で分割処理が行われる。すなわち、分割ノードを処理元から分離し、分割ノードの対ノードを親ノードに複写することにより分割ノードツリーが処理元から削除され、分割ノードを処理先に挿入することにより分割ノードツリーの挿入が完成する。
【０２４１】
したがって、同じ配列を用いている限りは、分割ノード以外のノードについての処理は不要であり、実施例２の場合よりも処理の実行ステップ数がさらに少なくてすむ。
次に分割処理と同様に部分木単位で処理を行う実施例３によるカップルドノードツリーの結合処理を説明する。本実施例の結合処理は、実施例１及び実施例２の結合処理と大きく異なり、実施例１及び実施例２の結合処理がインデックスキー単位、言い換えればノード単位で結合処理を行うものであるのに対して、所定の条件を満たす部分木単位で処理元から分割して処理先に結合するものである。実施例１及び実施例２の結合処理では分割キーを選択することにより分割処理をそのまま適用できたのに対して、本実施例のように部分木単位で結合処理を行おうとすると、単純に分割処理を適用することができない。
【０２４２】
それは、処理元及び処理先はそれぞれの内部に格納されたインデックスキーの差分ビット位置に応じた構造を有しており、処理元自体を分割ノードツリーとしてそのまま処理先に挿入することができるとは限らないからである。
【０２４３】
図２６は、実施例３におけるカップルドノードツリーの結合処理フローを説明する図である。以下の説明では、処理先のインデックスキーは処理元のインデックスキーより大きいとするが、その逆でも同様に処理が可能であることは、下記の説明から容易に理解されるものである。
【０２４４】
図３１Ａ〜図３１Ｃは、上記結合処理を実例により説明する図であり、図２に例示したカップルドノードツリーの部分木と類似したツリーが例示されている。
図３１Ａは結合処理開始前の処理元と処理先のツリーの構造例を示す図である。図３１Ａの（ａ）には処理元が例示され、その配列番号の符号２２０ａ＋１が付された分割結合ノードとそれをルートノードとする部分木であり、結合処理の単位となる部分木である分割結合ノードツリー２９３が示されている。以後、ノードを示す符号を、そのノードを検索処理でたどったときに経路探索スタックにスタックされるそのノードが配置された配列要素の配列番号で表すことがある。
【０２４５】
図３１Ａの（ｂ）には処理先が例示され、結合位置となるノードがその配列番号の符号２２１ｆを付して示されている。また、図３１Ａには、処理元の最大値がインデックスキー２５１ｇの“１０１００１”であること、処理先の最小値がインデックスキー２５０ｈの“１０１０１１”であることも示されている。
【０２４６】
図３１Ｂは、図３１Ａに示す分割結合ノードツリー２９３を処理先に挿入し、処理元から削除したツリー構造を示す図である。図３１Ｂの（ａ）には処理元の次の分割結合ノードツリー２９４が点線で囲われて示され、最大値がインデックスキー２５１ｄの“０１１０１０”であることが示されている。図３１Ｂの（ｂ）には、処理先の結合された分割ノードツリー２９３、結合処理により追加されたノード対２０１ｋとノード２２１ｆのリンク関係がそれぞれ点線で囲われて示され、次の結合位置がノード２２１であることが示されている。
【０２４７】
図３１Ｃは、図３１Ｂに示す分割結合ノードツリー２９４を処理先に挿入し、処理元から削除したツリー構造を示す図である。図３１Ｂの（ａ）に示す処理元の次ぎ分割結合ノ
ード２２０がルートノードであるため、処理元のルートノードは削除され、図３１Ｃの（ａ）には何も表示されていない。図３１Ｃの（ｂ）には、処理先の結合された分割ノードツリー２９４、結合処理により追加されたノード対２０１ｍとノード２２１のリンク関係がそれぞれ点線で囲われて示されている。
【０２４８】
以下、図２６及び図３１Ａ〜図３１Ｃを参照して本実施例の結合処理の概要を説明する。
図２６のステップＳ２６０１において、処理元の最大値と処理先の最小値の差分ビット位置を求める。図３１Ａの例示では、処理元の最大値“１０１００１”と処理先の最小値“１０１０１１”の差分ビット位置４が求められる。差分ビット位置を求める処理の詳細は、後に図２７を参照して説明する。なお、以下の説明では、このステップＳ２６０１で求めた差分ビット位置を単に差分ビット位置ということがある。
【０２４９】
次にステップＳ２６０２で、ステップＳ２６０１で求めた差分ビット位置により、処理元の分割結合ノードを求める。図３１Ａの例示では、分割結合ノード２２０ａ＋１が求められている。この処理の詳細は、後に図２８を参照して説明する。
【０２５０】
次にステップＳ２６０３に進み、ステップＳ２６０１で求めた差分ビット位置により、ステップＳ２６０２で求めた分割結合ノードを挿入するための処理先の結合位置を求める。図３１Ａの例示では、結合位置２２１ｆが求められている。この処理の詳細は、後に図２９を参照して説明する。
【０２５１】
次にステップＳ２６０４において、ステップＳ２６０３で求めた結合位置にステップＳ２６０２で求めた分割結合ノードを挿入する。この処理は、図２２を参照して説明をした挿入処理において、ステップＳ２２０１の挿入ノードの配列番号としてステップＳ２６０２で求めた分割結合ノードの配列番号を設定し、ステップＳ２２０２の処理先の挿入位置にステップＳＳ２６０３で求めた結合位置の配列番号を設定して該挿入処理を実行することにより実現される。
【０２５２】
図３１Ａ及び図３１Ｂの例示では、図２２のステップＳ２２０１において分割結合ノード２２０ａ＋１の配列番号２２０ａ＋１が挿入ノード設定エリアに設定され、ステップＳ２２０２において挿入位置設定エリアに結合位置２２１ｆの配列番号２２１ｆが設定される。次にステップＳ２２０３において、空きのノード対２０１ｋが取得され、その代表ノード番号２２０ｋがステップＳ２２０４においてノード〔０〕の配列番号として設定される。
【０２５３】
そして、ステップＳ２２０５において、挿入ノード設定エリアに設定された配列番号２２０ａ＋１が指す配列要素の内容、すなわち分割結合ノード２２１ｂの内容を読み出して、ノード〔０〕の配列番号として設定されている配列番号２２０ｋの指す配列要素、すなわちノード２１０ｋに格納する。
【０２５４】
さらにステップＳ２２０６において、代表ノード番号２２０ｋに１を加えた値である２２０ｋ＋１をノード〔１〕の配列番号として設定する。そしてステップＳ２２０７で挿入位置として設定されている配列番号２２１ｆの指す配列要素、すなわちノード２１０ｈの内容を読み出し、ノード〔１〕の配列番号として設定された配列番号２２０ｋ＋１の指す配列要素、すなわちノード２１１ｋに格納する。
【０２５５】
最後にステップＳ２２０８において、挿入位置として設定されている配列番号２２１ｆの指す配列要素、すなわちノード２１０ｈの位置に、ノード種別に０、弁別ビット位置に図２６のステップＳ２６０１で求めた差分ビット位置４、代表ノード番号にノード〔０〕
の配列番号として設定されている配列番号２２０ｋを設定して新たなブランチノードを生成し、図３１Ｂの（ｂ）に示す結合後の処理先の構造が得られている。
【０２５６】
次に図２６によるツリー結合処理の説明に戻ると、ステップＳ２６０５において、処理元より分割結合ノードを削除する。この処理は、図２３を参照して説明した削除処理において、分割ノードを分割結合ノードと読み替えて実行することにより実現される。
【０２５７】
次にステップＳ２６０６に進み、処理元が登録されているか判定する。登録されていればステップＳ２６０１に戻って処理を繰り返し、登録されていなければ結合処理は完了したので処理を終了する。
【０２５８】
次に、本実施例の結合処理を図２７〜図２９を参照して詳細に説明する。
図２７は、図２６に示すステップＳ２６０１の差分ビット位置を求める処理の詳細な処理フローを説明する図である。まず、ステップＳ２７０１において、処理元のルートノードの配列番号を検索開始ノードの配列番号に設定する。次にステップＳ２７０２において、図６に示す検索処理により、処理元のインデックスキーの最大値を求める。
【０２５９】
次にステップＳ２７０３に進み、処理先のルートノードの配列番号を、検索開始ノードの配列番号に設定する。次にステップＳ２７０４において、図５に示す検索処理により、処理先のインデックスキーの最小値を求める。
【０２６０】
次にステップＳ２７０５において、ステップＳ２７０２で求めた最大値とステップＳ２７０４で求めた最小値のビット列比較を行い、上位０ビット目から見た最初の不一致ビットの位置を求め、差分ビット位置に設定して処理を終了する。
【０２６１】
先に述べたように、図３１Ａの例示では、処理元の最大値“１０１００１”と処理先の最小値“１０１０１１”の差分ビット位置４が求められる。そして、処理元にも処理先にも、弁別ビット位置がこの差分ビット位置と等しいブランチノードは存在しない。
【０２６２】
なぜならば、処理元の最大値より処理先の最小値が大きいことから処理元の最大値の差分ビット位置のビット値は０であり、もし、処理元のブランチノードに弁別ビット位置が差分ビット位置と等しいものがあるとすると処理元の最大値がノード〔０〕となり、最大値であることと矛盾するからである。処理先についても同様である。
【０２６３】
次に、処理元の分割結合ノードを求める処理を説明する。分割結合ノードは、処理元がルートノードだけであるという例外を除けば、最大値検索でたどったブランチノードのうち、弁別ビット位置が図２６に示すステップＳ２６０１で求めた差分ビット位置より下位であるもののうち最上位であるブランチノードである。
【０２６４】
分割結合ノードをルートノードとする処理元の部分木を分割結合ノードツリーということにすると、本実施例の結合処理は、分割結合ノードツリー単位で結合処理を行うものである。
【０２６５】
図２８は、図２６に示すステップＳ２６０２の処理元の分割結合ノードを求める処理フローを説明する図である。なお、分割結合ノードを求める処理の開始時には、処理元の探索経路スタックのスタックポインタは図２６に示すステップＳ２６０１における最大値検索の結果、インデックスキーの最大値を格納したリーフノードの配列番号を指している。
【０２６６】
ステップＳ２８０１において、処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。処理元の探索経路スタックのスタックポイン
タがルートノードの配列番号を指している場合にはステップＳ２８１０に進み、処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合にはステップＳ２８０２に進む。
【０２６７】
ステップＳ２８０２では探索経路スタックのスタックポインタを１つ戻してそのスタックポインタが指す配列番号を取り出してステップＳ２８０３に進む。
ステップＳ２８０３ではステップＳ２８０２で取り出した配列番号の指す配列要素の内容をノードとして取り出し、ステップＳ２３０４において取り出したノードの弁別ビット位置を取得する。
【０２６８】
次にステップＳ２８０５において、ステップＳ２８０４で取得した弁別ビット位置が差分ビット位置より上位の位置関係か判定する。下位であればステップＳ２８０１に戻り、上位であればステップＳ２８０９に進む。先に述べたように、上述の弁別ビット位置と差分ビット位置が等しいことはない。
【０２６９】
ステップＳ２８０９においては、処理元の探索経路スタックのスタックポインタを１つ進め、ステップＳ２８１０に移行する。
ステップＳ２８１０においては、処理元の経路探索スタックから、スタックポインタの指す配列番号を取り出し、処理元の分割結合ノードの配列番号として設定して処理を終了する。なお、以下の説明において、ここで設定された配列番号を単に分割結合ノードの配列番号ということがある。
【０２７０】
上記処理を図３１Ａ及び図３１Ｂを参照して説明すると以下のとおりである。
図３１Ａの例示においては、キーの最大値を格納したノード２１１ｇから探索経路を遡ると、始めはスタックポインタがノード２１１ｇの配列番号２２１ｂを指しているのでステップＳ２８０１の判定は「いいえ」となって、ステップＳ２８０１からの処理を繰り返し、差分ビット位置が４であることからステップＳ２８０２の処理でルートノード２１０ａまで至り、ルートノード２１０ａの弁別ビット位置が０であって差分ビット位置より上位であるからステップＳ２８０５の判定処理でステップＳ２８０９に分岐し、ステップＳ２８０９の処理により探索経路を１つ進めて分割結合ノード２２０ａ＋１が求められる。
【０２７１】
図３１Ｂの例示においては、キーの最大値を格納したノード２１１ｄから探索経路を遡ると、差分ビット位置が０であることからステップＳ２８０２の処理でルートノード２１０ａまで至り、ルートノード２１０ａの弁別ビット位置が１であって差分ビット位置より下位であるからステップＳ２８０５の判定処理でステップＳ２８０１に分岐し、ステップＳ２８０１の判定処理でルートノードと判定されてステップＳ２８１０に分岐し、ルートノード２１０ａが次の分割結合ノードとして求められる。
【０２７２】
次に、処理先の結合位置を求める処理を説明する。結合処理後の処理先には処理元のインデックスキーの最大値を格納したリーフノードが挿入されることから、差分ビット位置と等しい値の弁別ビット位置を持つブランチノードが新しく存在する。すなわち、差分ビット位置と等しい値の弁別ビット位置を持つブランチノードを最小値検索でたどった経路中に挿入することになるが、この挿入位置を処理先の結合位置とする。
【０２７３】
カップルドノードツリーにおいては、下位のブランチノードの弁別ビット位置は上位のブランチノードの弁別ビット位置より下位であることから、差分ビット位置より直近上位の弁別ビット位置を持つブランチノードの子ノードの位置かあるいは例外的に上位の弁別ビット位置を持つブランチノードがなければルートノードが結合位置となる。
【０２７４】
結合位置に挿入されたブランチノードの子ノード対のノード〔１〕側には結合前の処理
先のインデックスキーの最小値を格納したリーフノードが存在し、ノード〔０〕は分割結合ノードである。
【０２７５】
図２９は、上記処理先の結合位置を求める処理フローを説明する図である。図２９に示すように、処理先の結合位置を求める処理フローは、図２８に示す処理元の分割結合ノードを求める処理フローと同じ構造である。図２９の処理フローは処理先についてのものであり、求めるものは結合位置であることで異なるだけである。なお、処理先の結合位置を求める処理の開始時には、処理先の探索経路スタックのスタックポインタは図２６に示すステップＳ２６０１における最小値検索の結果、インデックスキーの最小値を格納したリーフノードの配列番号を指している。
【０２７６】
ステップＳ２９０１において、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指している場合にはステップＳ２９１０に進み、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合にはステップＳ２９０２に進む。
【０２７７】
ステップＳ２９０２では探索経路スタックのスタックポインタを１つ戻して配列番号を取り出してステップＳ２９０３に進む。
ステップＳ２９０３ではステップＳ２９０２で取り出した配列番号の指す配列要素の内容をノードとして取り出し、ステップＳ２９０４において、取り出したノードの弁別ビット位置を取得する。
【０２７８】
次にステップＳ２９０５において、ステップＳ２９０４で取得した弁別ビット位置が差分ビット位置より上位の位置関係か判定する。下位であればステップＳ２９０１に戻り、上位であればステップＳ２９０９に進む。先に述べたように、上述の弁別ビット位置と差分ビット位置が等しいことはない。
【０２７９】
ステップＳ２９０９においては、処理元の探索経路スタックのスタックポインタを１つ進め、ステップＳ２９１０に移行する。
ステップＳ２９１０においては、処理先の経路探索スタックから、スタックポインタの指す配列番号を取り出し、処理先の結合位置の配列番号として設定して処理を終了する。なお、以下の説明において、ここで設定された配列番号を単に結合位置の配列番号ということがある。
【０２８０】
上記処理を図３１Ａ及び図３１Ｂを参照して説明すると以下のとおりである。
図３１Ａの例示においては、キーの最小値を格納したノード２１０ｈから探索経路を遡ると、差分ビット位置が４でありステップＳ２９０４で取り出すルートノード２１０ｆの弁別ビット位置が３であることからステップＳ２９０５からステップＳ２９０９に分岐し、ステップＳ２９０９の処理により探索経路を１つ進めて結合位置の配列番号２２１ｆが求められる。
【０２８１】
図３１Ｂの例示において、キーの最小値を格納したノード２１０ｇから探索経路を遡ると、差分ビット位置が０であることからルートノード２１０ｆまで至り、ステップＳ２９０１において、ルートノードであると判定されてステップＳ２９１０に分岐し、ルートノード２１０ｆの配列番号２２１が次の結合位置の配列番号として求められる。
【０２８２】
以上により、実施例３によるカップルドノードツリーの結合処理について詳細に説明しが、実施例３によれば、分割結合ノードツリー単位で結合処理が行われる。すなわち、分割結合ノードを処理元から分離し、分割結合ノードの対ノードを親ノードに複写すること
により分割結合ノードツリーが処理元から削除され、分割結合ノードを処理先に結合することにより分割結合ノードツリーの結合が完成する。
【０２８３】
したがって、同じ配列を用いている限りは、分割結合ノード以外のノードについての処理は不要であり、実施例２の場合よりも処理の実行ステップ数がさらに少なくてすむ。
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
【０２８４】
以上に説明した本発明の実施の形態によるカップルドノードツリーの分割結合処理及びその均等物をコンピュータに実行させるプログラムにより、本発明のカップルドノードツリーの分割方法及び結合方法が実現可能であることも明らかである。
【０２８５】
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。
【図面の簡単な説明】
【０２８６】
【図１】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２】カップルドノードツリーのツリー構造を概念的に示す図である。
【図３】本発明を実施するためのハードウェア構成例を説明する図である。
【図４】ビット列検索の基本動作を示したフローチャートである。
【図５】カップルドノードツリーに格納されたインデックスキーの最小値を求める処理を示したフローチャートである。
【図６】カップルドノードツリーに格納されたインデックスキーの最大値を求める処理を示したフローチャートである。
【図７Ａ】インデックスキーの下限値を求める処理の前段を示したフローチャートである。
【図７Ｂ】インデックスキーの下限値を求める処理の後段を示したフローチャートである。
【図８Ａ】インデックスキーの上限値を求める処理の前段を示したフローチャートである。
【図８Ｂ】インデックスキーの上限値を求める処理の後段を示したフローチャートである。
【図９Ａ】挿入処理の前段である検索処理の処理フローを示す図である。
【図９Ｂ】挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
【図９Ｃ】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。
【図１０】ルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【図１１Ａ】削除処理の前段である検索処理の処理フローを示す図である。
【図１１Ｂ】削除処理の後段の処理フローを説明する図である。
【図１２】実施例１におけるカップルドノードツリーの分割処理フローを説明する図である。
【図１３】実施例２におけるカップルドノードツリーの分割処理フローを説明する図である。
【図１４】実施例２におけるノードの挿入処理フローを説明する図である。
【図１５Ａ】実施例２におけるルートノード設定処理を説明するフロー図である。
【図１５Ｂ】実施例２における親ノードに挿入キーを含むノード対を挿入する処理フローを説明する図である。
【図１６】実施例２における削除処理を説明するフロー図である。
【図１７】実施例３におけるカップルドノードツリーの分割処理フローを説明する図である。
【図１８】最初の分割ノードを求める処理フローの前段を説明する図である。
【図１９】最初の分割ノードを求める処理フローの後段を説明する図である
【図２０】処理先のルートノードの挿入処理の処理フローを説明する図である。
【図２１】分割処理での差分ビット位置を求める処理フローを説明する図である。
【図２２】ルートノード以外の挿入処理の処理フローを説明する図である。
【図２３】実施例３における削除処理の処理フローを説明する図である。
【図２４】次の分割ノードを求める処理の処理フローを説明する図である。
【図２５】分割ノードツリーの最大値を求め次の分割キーとする処理の処理フローを説明する図である。
【図２６】実施例３におけるカップルドノードツリーの結合処理フローの概要を説明する図である。
【図２７】結合処理での差分ビット位置を求める処理フローを説明する図である。
【図２８】処理元の分割結合ノードを求める処理フローを説明する図である。
【図２９】処理先の結合位置を求める処理フローを説明する図である。
【図３０Ａ】分割前のツリー構造例を説明する図である。
【図３０Ｂ】最初の分割後のツリー構造例を説明する図である。
【図３０Ｃ】次の分割後のツリー構造例を説明する図である。
【図３１Ａ】最初の結合処理前のツリー構造例を説明する図である。
【図３１Ｂ】最初の結合しょり後のツリー構造例を説明する図である。
【図３１Ｃ】次の結合処理後のツリー構造例を説明する図である。
【図３２】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【符号の説明】
【０２８７】
１０、２０、３０   配列番号
１００      配列
１０１      ノード
１０２      ノード種別
１０３      弁別ビット位置
１０４      代表ノード番号
１１１      ノード対
１１２      ノード［０］、代表ノード
１１３      ノード［１］、代表ノードと対をなすノード
１１８      インデックスキー
３０１      データ処理装置
３０２      中央処理装置
３０３      キャッシュメモリ
３０４      バス
３０５      主記憶装置
３０６      外部記憶装置
３０７      通信装置
３０８      データ格納装置
３０９      配列
３１０      探索経路スタック
【図１】
2008159025.tif 000003
【図２】
2008159025.tif 000004
【図３】
2008159025.tif 000005
【図４】
2008159025.tif 000006
【図５】
2008159025.tif 000007
【図６】
2008159025.tif 000008
【図７Ａ】
2008159025.tif 000009
【図７Ｂ】
2008159025.tif 000010
【図８Ａ】
2008159025.tif 000011
【図８Ｂ】
2008159025.tif 000012
【図９Ａ】
2008159025.tif 000013
【図９Ｂ】
2008159025.tif 000014
【図９Ｃ】
2008159025.tif 000015
【図１０】
2008159025.tif 000016
【図１１Ａ】
2008159025.tif 000017
【図１１Ｂ】
2008159025.tif 000018
【図１２】
2008159025.tif 000019
【図１３】
2008159025.tif 000020
【図１４】
2008159025.tif 000021
【図１５Ａ】
2008159025.tif 000022
【図１５Ｂ】
2008159025.tif 000023
【図１６】
2008159025.tif 000024
【図１７】
2008159025.tif 000025
【図１８】
2008159025.tif 000026
【図１９】
2008159025.tif 000027
【図２０】
2008159025.tif 000028
【図２１】
2008159025.tif 000029
【図２２】
2008159025.tif 000030
【図２３】
2008159025.tif 000031
【図２４】
2008159025.tif 000032
【図２５】
2008159025.tif 000033
【図２６】
2008159025.tif 000034
【図２７】
2008159025.tif 000035
【図２８】
2008159025.tif 000036
【図２９】
2008159025.tif 000037
【図３０Ａ】
2008159025.tif 000038
【図３０Ｂ】
2008159025.tif 000039
【図３０Ｃ】
2008159025.tif 000040
【図３１Ａ】
2008159025.tif 000041
【図３１Ｂ】
2008159025.tif 000042
【図３１Ｃ】
2008159025.tif 000043
【図３２】
2008159025.tif 000044