(57)【要約】【課題】カップルドノードツリーの規模が大きくなっても、カップルドノードツリーの分割／結合処理の効率が低下することを少なくする。【解決手段】分割／結合処理で用いる検索処理において、検索履歴を格納する探索経路スタックに、検索経路でたどったブランチノードを順次格納する。その際ブランチノードの代表ノード番号は、リンク先がノード［１］であれば１を加算した値に変更する。探索経路スタックにブランチノードを格納することにより、検索処理においてキャッシュのヒット率を上げることができ、処理効率を高めることができる。【選択図】図４Ｂ
2010198632.tif 000002
【特許請求の範囲】
【請求項１】
ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有するツリーの構成要素としてのノード対と、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときはブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである前記代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは非代表ノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成されたカップルドノードツリーをコンピュータが分割する、カップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割するインデックスキーを決定する分割キーを取得する分割キー取得ステップと、
前記処理元カップルドノードツリーのルートノードを検索開始ノードとして、該検索開始ノードから前記ノード対を構成する２つのノードのうち代表ノードのみ、あるいは非代表ノードのみをリンクしてリーフノードに至ることにより、該リーフノードに格納されたインデックスキーを前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値として求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノードをスタックに順次格納する、処理元最小値あるいは最大値取得ステップと、
前記分割キーと前記最小値あるいは最大値との大小を比較し、該最小値が前記分割キーより大きければあるいは該最大値が前記分割キーより小ければ処理を終了する比較ステップと、
前記比較の結果、該最小値が前記分割キーより大きくなければあるいは該最大値が前記分割キーより小さくなければ、
該最小値あるいは該最大値をインデックスキーとして挿入する処理先カップルドノードツリーが存在していない場合は、該最小値あるいは該最大値をインデックスキーとして含むリーフノードをルートノードとする処理先カップルドノードツリーを生成し、前記処理先カップルドノードツリーが存在している場合は、該処理先カップルドノードツリーに該最小値あるいは該最大値のインデックスキーを挿入して新たな処理先カップルドノードツリーを生成する生成ステップと、
前記処理元カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記比較ステップ、前記生成ステップ及び前記削除ステップを前記処理元最小値あるいは最大値取得ステップで取得された最小値あるいは最大値が前記分割キーより大きくなるまであるいは小さくなるまで繰り返すことを特徴とするカップルドノードツリーの分割方法。
【請求項２】
請求項１に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号からなる代表ノード番号であり、
前記スタックには、弁別ビット位置の値が０より小さい値である終端ノードが仮想的なブランチノードとして最初に格納され、
前記生成ステップは、
前記処理先カップルドノードツリーが存在している場合は、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値を前記処理先カップルドノードツリーの挿入キーとして設定して、
前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である処理先親ノードを決定し、
該処理先親ノードをブランチノードとし、その代表ノード番号を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの分割方法。
【請求項３】
請求項２に記載のカップルドノードツリーの分割方法において、
前記生成ステップで決定した前記処理先親ノードを、検索開始ノードとして設定するステップを含み、
前記処理先最大値あるいは最小値取得ステップは、該設定された検索開始ノードからノード対を構成する２つのノードのうち非代表ノードのみ、あるいは代表ノードのみをリンクしてリーフノードに至ることにより、該リーフノードに格納されたインデックスキーを前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値として求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノードをスタックに順次格納するものであることを特徴とするカップルドノードツリーの分割方法。
【請求項４】
ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有するツリーの構成要素としてのノード対と、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときはブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである前記代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された２つのカップルドノードツリーをコンピュータが結合する、カップルドノードツリーの結合方法において、
前記２つのカップルドノードツリーの一方の処理元カップルドノードツリーのルートノードを検索開始ノードとして、該検索開始ノードから前記ノード対を構成する２つのノードのうち代表ノードのみ、あるいは非代表ノードのみをリンクしてリーフノードに至ることにより、該リーフノードに格納されたインデックスキーを前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値として求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノードをスタックに順次格納する、処理元最小値あるいは最大値取得ステップと、
前記２つのカップルドノードツリーの他方の処理先カップルドノードツリーに前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値のインデックスキーを挿入する挿入ステップと、
前記処理元カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記挿入ステップ及び前記削除ステップを前記処理元カップルドノードツリーがすべて削除されるまで繰り返すことを特徴とするカップルドノードツリーの結合方法。
【請求項５】
請求項４に記載のカップルドノードツリーの結合方法において、
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号からなる代表ノード番号であり、
前記スタックには、弁別ビット位置の値が０より小さい値である終端ノードが仮想的なブランチノードとして最初に格納され、
前記挿入ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値を前記処理先カップルドノードツリーの挿入キーとして設定し、
前記処理先カップルドノードツリーのルートノードを検索開始ノードとして、該検索開始ノードから前記ノード対を構成する２つのノードのうち非代表ノードのみ、あるいは代表ノードのみをリンクしてリーフノードに至ることにより、該リーフノードに格納されたインデックスキーを前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値として求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノードをスタックに順次格納する、処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である処理先親ノードを決定し、
該処理先親ノードをブランチノードとし、その代表ノード番号を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの結合方法。
【請求項６】
ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有するツリーの構成要素としてのノード対と、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときはブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである前記代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは非代表ノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成されたカップルドノードツリーをコンピュータが分割する、カップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割する分割キーを取得する分割キー取得ステップと、
該分割キーを前記検索キーとし、前記処理元カップルドノードツリーのルートノードを前記検索開始ノードとして、前記処理元カップルドノードツリーから検索結果キーとして前記分割キーを得るとともに、前記ルートノードから該分割キーをインデックスキーとして含むリーフノードに至るまでたどったリンク経路のブランチノードの前記代表ノードの位置を示す位置情報を弁別ビット位置の検索キーのビット値に応じたリンク先のノードの位置を示す位置情報に変更して該ブランチノードをスタックに順次格納する検索ステップと、
前記スタックに格納されたブランチノードの位置情報が、前記代表ノードの位置を示す位置情報となるまで、あるいは前記非代表ノードの位置を示す位置情報となるまで順次ブランチノードを読み出し、該読み出したブランチノードの前記代表ノードの位置を示す位置情報あるいは前記非代表ノードの位置を示す位置情報の記憶領域に配置されたノードを分割ノードとして求める分割ノード取得ステップと、
前記分割ノードをルートノードとする部分木である分割ノードツリーを挿入する処理先カップルドノードツリーが存在していない場合は、該分割ノードツリーを処理先カップルドノードツリーとして処理先カップルドノードツリーを生成し、前記処理先カップルドノードツリーが存在している場合は、該分割ノードツリーを該処理先カップルドノードツリーに挿入することにより新たな処理先カップルドノードツリーを生成するする生成ステップと、
前記分割ノードツリーを前記処理元カップルドノードツリーから削除する削除ステップ
を含むことを特徴とするカップルドノードツリーの分割方法。
【請求項７】
請求項６に記載のカップルドノードツリーの分割方法において、
前記スタックに格納された、前記分割ノードより前に格納されたブランチノードの前記代表ノードの位置を示す位置情報あるいは前記非代表ノードの位置を示す位置情報が、前記非代表ノードの位置を示す位置情報となるまで、あるいは前記代表ノードの位置を示す位置情報となるまで順次ブランチノードを読み出し、該読み出したブランチノードの前記非代表ノードの位置を示す位置情報あるいは前記代表ノードの位置を示す位置情報の記憶領域に格納されたノードと対をなすノードを次の分割ノードとして取得する次分割ノード取得ステップを備え、
前記分割ノードを前記次の分割ノードとして前記生成ステップと前記削除ステップを実行することを特徴とするカップルドノードツリーの分割方法。
【請求項８】
請求項６又は請求項７に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記スタックには、弁別ビット位置の値が０より小さい値である終端ノードが仮想的なブランチノードとして最初に格納されることを特徴とするカップルドノードツリーの分割方法。
【請求項９】
ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有するツリーの構成要素としてのノード対と、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときはブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである前記代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された２つのカップルドノードツリーをコンピュータが結合する、カップルドノードツリーの結合方法において、
前記２つのカップルドノードツリーの一方の処理元カップルドノードツリーのルートノードを検索開始ノードとして、該検索開始ノードから前記ノード対を構成する２つのノードのうち非代表ノードのみ、あるいは代表ノードのみをリンクしてリーフノードに至ることにより、該リーフノードに格納されたインデックスキーを前記処理元カップルドノードツリーのインデックスキーの最大値あるいは最小値として求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノードの前記代表ノードの位置を示す位置情報をリンク先の非代表ノードあるいは代表ノードの位置を示す位置情報にして該ブランチノードを処理元のスタックに順次格納する、処理元最大値あるいは最小値取得ステップと、
前記２つのカップルドノードツリーの他方の処理先カップルドノードツリーのルートノードを検索開始ノードとして、該検索開始ノードから前記ノード対を構成する２つのノードのうち代表ノードのみ、あるいは非代表ノードのみをリンクしてリーフノードに至ることにより、該リーフノードに格納されたインデックスキーを前記処理先カップルドノードツリーのインデックスキーの最小値あるいは最大値として求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノードの前記代表ノードの位置を示す位置情報をリンク先の代表ノードあるいは非代表ノードの位置を示す位置情報にして該ブランチノードを処理先のスタックに順次格納する、処理先最小値あるいは最大値取得ステップと、
前記処理元最大値あるいは最小値取得ステップで求めた処理元カップルドノードツリーのインデックスキーの最大値と前記処理先最小値あるいは最大値取得ステップで求めた処理先カップルドノードツリーのインデックスキーの最小値の差分ビット位置、
あるいは前記処理元最大値あるいは最小値取得ステップで求めた処理元カップルドノードツリーのインデックスキーの最小値と前記処理先最小値あるいは最大値取得ステップで求めた処理先カップルドノードツリーのインデックスキーの最大値の差分ビット位置を求める差分ビット位置取得ステップと、
前記差分ビット位置取得ステップで求めた差分ビット位置に基づき前記処理元から分割して処理先に結合する部分木のルートノードである分割結合ノードを求める分割結合ノード取得ステップと、
前記差分ビット位置取得ステップで求めた差分ビット位置に基づき分割結合ノード取得ステップで求めた分割結合ノードを結合する処理先の結合位置を求める結合位置取得ステップと、
前記分割結合ノード取得ステップで求めた分割結合ノードを前記結合位置取得ステップで求めた処理先の結合位置に挿入する挿入ステップと、
前記分割結合ノード取得ステップで求めた分割結合ノードを前記処理元カップルドノードツリーから削除する削除ステップと、
を備え、
前記分割結合ノードを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最大値あるいは最小値取得ステップ、前記処理先最小値あるいは最大値取得ステップ、前記差分ビット位置取得ステップ、前記分割結合ノード取得ステップ、前記結合位置取得ステップ、前記挿入ステップ及び前記削除ステップを、前記処理元カップルドノードツリーがすべて削除されるまで繰り返すことを特徴とするカップルドノードツリーの結合方法。
【請求項１０】
請求項９に記載のカップルドノードツリーの結合方法において、
前記分割結合ノード取得ステップは、前記処理元のスタックに格納されたブランチノードを、該ブランチノードの弁別ビット位置が前記差分ビット位置より上位になるまで取り出し、該取り出したブランチノードのリンク先の非代表ノードあるいは代表ノードの位置を示す位置情報の記憶領域に格納されたノードを分割結合ノードとして求め、
前記結合位置取得ステップは、前記処理先のスタックに格納されたブランチノードを、該ブランチノードの弁別ビット位置が前記差分ビット位置より上位になるまで取り出し、該取り出したブランチノードのリンク先の代表ノードあるいは非代表ノードの位置を示す位置情報の記憶領域に格納されたノードを結合位置として求めることを特徴とするカップルドノードツリーの結合方法。
【請求項１１】
請求項９又は請求項１０に記載のカップルドノードツリーの結合方法において、
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記処理元のスタック及び処理先のスタックには、弁別ビット位置の値が０より小さい値である終端ノードが仮想的なブランチノードとして最初に格納されることを特徴とするカップルドノードツリーの結合方法。
【請求項１２】
請求項１〜請求項１１のいずれか１項に記載の方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１３】
請求項１〜請求項１１のいずれか１項に記載の方法をコンピュータに実行させるためのプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビット列の集合から所望のビット列を検索する検索装置、検索方法及びプログラムに関するものであり、特にビット列を記憶するデータ構造に工夫をして、検索速度等の向上を図る技術分野のものであり、特に、本出願人が特願２００６−１８７８２７及び特願２００６−３１９９４０７において提案したカップルドノードツリーの分割／結合方法に関するものである。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【０００３】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【０００４】
図１は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【０００５】
図１の例では、インデックスキー“１０００１０”を保持するノード１７５０ａがルートノードとなっており、その検査ビット位置は０である。ノード１７５０ａの左リンク１７４０ａにはノード１７５０ｂが接続され、右リンク１７４１ａにはノード１７５０ｆが接続されている。
【０００６】
ノード１７５０ｂの保持するインデックスキーは“０１００１１”であり、検査ビット位置１７３０ｂは１である。ノード１７５０ｂの左リンク１７４０ｂにはノード１７５０ｃが、右リンク１７４１ｂにはノード１７５０ｄが接続されている。ノード１７５０ｃが保持するインデックスキーは“０００１１１”、検査ビット位置は３である。ノード１７５０ｄが保持するインデックスキーは“０１１０１０”、検査ビット位置は２である。
【０００７】
ノード１７５０ｃから実線で接続された部分はノード１７５０ｃの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ１７４０ｃは、その欄が空欄であることを示している。点線の接続された右ポインタ１７４１ｃの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード１７５０ｃを右ポインタが指定していることを表している。
【０００８】
ノード１７５０ｄの右ポインタ１７４１ｄはノード１７５０ｄ自身を指しており、左リンク１７４０ｄにはノード１７５０ｅが接続されている。ノード１７５０ｅの保持するインデックスキーは“０１００１０”、検査ビット位置は５である。ノード１７５０ｅの左ポインタ１７４０ｅはノード１７５０ｂを、右ポインタ１７４１ｅはノード１７５０ｅを指している。
【０００９】
また、ノード１７５０ｆの保持するインデックスキーは“１０１０１１”であり、検査ビット位置１７３０ｆは２である。ノード１７５０ｆの左リンク１７４０ｆにはノード１７５０ｇが、右リンク１７４１ｆにはノード１７５０ｈが接続されている。
【００１０】
ノード１７５０ｇの保持するインデックスキーは“１０００１１”であり、検査ビット位置１７３０ｇは５である。ノード１７５０ｇの左ポインタ１７４０ｇはノード１７５０ａを、右ポインタ１７４１ｇはノード１７５０ｇを指している。
【００１１】
ノード１７５０ｈの保持するインデックスキーは“１０１１００”であり、検査ビット位置１７３０ｈは３である。ノード１７５０ｈの左ポインタ１７４０ｈはノード１７５０ｆを、右ポインタ１７４１ｈはノード１７５０ｈを指している。
【００１２】
図１の例では、ルートノード１７５０ａからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が１であるか０であるか判定を行い、１であれば右リンクをたどり、０であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば（図１において点線で示されたこの逆戻りのリンクをバックリンクという）、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【００１３】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は１回ですむことなどのメリットがあるが、各ノードからの２つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【００１４】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献１に開示された技術がある。下記特許文献１に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【００１５】
しかしながら、下記特許文献１に開示されたものにおいても、１つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを１つとしたため、例えば図１に示したパトリシアツリーの最下段の部分である左ポインタ１７４０ｃ、右ポインタ１７４１ｈ等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【００１６】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願２００６−１８７８２７において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を提案した。
上記出願においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。
【００１７】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願２００６−２９３６１９において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの最大値／最小値を求める手法等を提案した。
【００１８】
さらに、本出願人は、特願２００６−３１９４０７において、カップルドノードツリーの分割／結合手法を提案した。
上記３つの出願において提案した検索手法は、検索開始ノードから順次ブランチノードをたどってリーフノードに至り、リーフノードに格納されたインデックスキーを求める操作を基本とするものであり、検索履歴として検索開始ノードからリーフノードに至る探索経路のノードの位置情報をスタックに格納している。そして、スタックに格納された位置情報を基にその位置情報が示す位置に格納されたノードを参照することが行われている。
【００１９】
上記位置情報としては、カップルドノードツリーを配列に格納する場合にはその配列での配列番号を用いることができ、位置情報を表すビット量を削減することができる。
さらに本出願人は、特願２００７−１３２１１において、前記スタックに探索経路中のブランチノードの弁別ビット位置を格納することにより処理効率を向上させることも提案している。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２００１−３５７０７０号公報
【発明の概要】
【発明が解決しようとする課題】
【００２１】
今後データベースがますます巨大化していく傾向があることから、データベースのなお一層の効率的な処理が求められている。そこで本発明は、カップルドノードツリーを用いた各種検索処理のさらなる高速化を可能とし、それによりカップルドノードツリーの分割処理と結合処理を高速化する手法を提供することを目的とする。
【課題を解決するための手段】
【００２２】
本発明の１つの態様によれば、カップルドノードツリーを用いた基本検索や最大値あるいは最小値検索等の各種検索処理において、検索履歴を格納する探索経路スタックに探索経路のブランチノードを格納する。そして、上述の基本検索や最大値あるいは最小値検索等の各種検索処理を用いて、カップルドノードツリーの分割処理と結合処理が行われる。
【００２３】
また、本発明の別の態様によれば、弁別ビット位置の値が０より小さい値である終端ノードが仮想的なブランチノードとして探索経路スタックに最初に格納される。
【発明の効果】
【００２４】
本発明によれば、検索処理でたどったブランチノードの内容が必要なときは、その内容を、検索履歴を格納する探索経路スタックから得ることができ、カップルドノードツリーの規模が大きくなったとしても、キャッシュミスが発生する可能性を小さくすることができ、カップルドノードツリーの分割処理と結合処理の高速化を図ることができる。
【図面の簡単な説明】
【００２５】
【図１】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【図２Ａ】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２Ｂ】カップルドノードツリーのツリー構造を概念的に示す図である。
【図３】本発明を実施するためのハードウェア構成例を説明する図である。
【図４Ａ】本実施形態に係る基本検索の処理の概略を説明する図である。
【図４Ｂ】基本検索の処理フローを説明する図である。
【図４Ｃ】カップルドノードツリーによる基本検索例を説明する図である。
【図５Ａ】挿入処理の前段である検索処理の処理フローを示す図である。
【図５Ｂ】挿入するノード対のための配列要素を準備する処理を説明するフロー図である。
【図５Ｃ】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理を説明するフロー図である。
【図６Ａ】ルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【図６Ｂ】ルートノードに挿入キーを含むリーフノードを設定する処理フローを説明する図である。
【図７Ａ】削除処理の前段である検索処理の処理フローを示す図である。
【図７Ｂ】削除処理の後段の処理フローを説明する図である。
【図８Ａ】カップルドノードツリーに格納されたインデックスキーの最小値を求める処理フローの概要を説明する図である。
【図８Ｂ】インデックスキーの最小値を得る検索処理の詳細を説明するフロー図である。
【図８Ｃ】カップルドノードツリーによる最小値検索例を説明する図である。
【図９Ａ】カップルドノードツリーに格納されたインデックスキーの最大値を求める処理フローの概要を説明する図である。
【図９Ｂ】インデックスキーの最大値を得る検索処理の詳細を説明するフロー図である。
【図９Ｃ】カップルドノードツリーによる最大値検索例を説明する図である。
【図１０Ａ】下限値検索の前段の処理フローを説明する図である。
【図１０Ｂ】下限値検索の後段の処理フローを説明する図である。
【図１０Ｃ】カップルドノードツリーによる下限値検索例を説明する図である。
【図１１Ａ】上限値検索の前段の処理フローを説明する図である。
【図１１Ｂ】上限値検索の後段の処理フローを説明する図である。
【図１１Ｃ】カップルドノードツリーによる上限値検索例を説明する図である。
【図１２Ａ】本実施形態に係るカップルドノードツリーの分割処理の第１の実施例における処理先の初期設定等に関する前段の処理を説明するフロー図である。
【図１２Ｂ】第１の実施例における分割処理の後段の処理を説明するフロー図である。
【図１３Ａ】第２の実施例における分割処理の前段の処理を説明するフロー図である。
【図１３Ｂ】第２の実施例における分割処理の後段の処理を説明するフロー図である。
【図１４】第２の実施例におけるノードの挿入処理を説明するフロー図である。
【図１５】第２の実施例における処理元の削除処理を説明する図である。
【図１６Ａ】第３の実施例における分割処理の前段の処理を説明するフロー図である。
【図１６Ｂ】第３の実施例における分割処理の後段の処理を説明するフロー図である。
【図１７Ａ】最初の分割ノードを求める処理の前段の処理を説明するフロー図である。
【図１７Ｂ】最初の分割ノードを求める処理の後段の処理を説明するフロー図である。
【図１８Ａ】処理先のルートノードの挿入処理を説明するフロー図である。
【図１８Ｂ】ルートノード以外の挿入処理を説明するフロー図である。
【図１９】次の分割ノードを求める処理の処理フローを説明する図である。
【図２０】分割ノードツリーの最大値を求め次の分割キーとする処理の処理フローを説明する図である。
【図２１】分割ノードツリーの削除処理の処理フローを説明する図である。
【図２２Ａ】分割前のツリー構造例を説明する図である。
【図２２Ｂ】最初の分割後のツリー構造例を説明する図である。
【図２２Ｃ】次の分割後のツリー構造例を説明する図である。
【図２３Ａ】第３の実施例におけるカップルドノードツリーの結合処理における初期処理の処理フローを説明する図である。
【図２３Ｂ】結合処理における処理元をすべて処理先に結合するまでのループ処理の処理フローを説明する図である。
【図２４】処理元の分割結合ノードを求める処理フローを説明する図である。
【図２５】処理先の結合位置を求める処理フローを説明する図である。
【図２６Ａ】最初の結合処理前のツリー構造例を説明する図である。
【図２６Ｂ】最初の結合処理後のツリー構造例を説明する図である。
【図２６Ｃ】次の結合処理後のツリー構造例を説明する図である。
【図２７Ａ】本実施形態におけるカップルドノードツリーの任意の部分木に格納されたインデックスキーを昇順に取り出す処理を説明するフロー図である。
【図２７Ｂ】インデックスキーを昇順に取り出す処理例を説明する図である。
【図２８Ａ】本実施形態におけるカップルドノードツリーの任意の部分木に格納されたインデックスキーを降順に取り出す処理を説明するフロー図である。
【図２８Ｂ】インデックスキーを降順に取り出す処理例を説明する図である。
【図２９Ａ】本実施形態における範囲指定昇順取り出し処理の初期処理を説明するフロー図である。
【図２９Ｂ】範囲指定昇順取り出し処理のループ処理を説明するフロー図である。
【図２９Ｃ】インデックスキーの範囲を指定して昇順に取り出す処理例を説明する図である。
【図３０Ａ】本実施形態における範囲指定降順取り出し処理の初期処理を説明するフロー図である。
【図３０Ｂ】範囲指定降順取り出し処理のループ処理を説明するフロー図である。
【図３０Ｃ】インデックスキーの範囲を指定して降順に取り出す処理例を説明する図である。
【図３１Ａ】本実施形態の前方一致検索の処理フローを説明する図である。
【図３１Ｂ】前方一致検索の検索例を説明する図である。
【発明を実施するための形態】
【００２６】
最初に、本出願人により先の上記出願において提案された、本発明の前提となるカップルドノードツリーについて、カップルドノードツリーを配列に格納する例を説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【００２７】
図２Ａは、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図２Ａを参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【００２８】
配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
【００２９】
なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
【００３０】
ノード［０］１１２及びノード［１］１１３の前に付された符号０，１は、そのノードがノード対のどちらの配列要素に格納されているかを示すノード位置である。例えばノード［０］については偶数番号の配列の配列要素に格納する等により、配列番号からノード位置を求めることができる。すなわち、その場合は、配列番号が偶数であればその配列番号のノードのノード位置は０であり、配列番号が奇数であればその配列番号のノードのノード位置は１である。
【００３１】
配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。
ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付されたノード位置０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものと考えることができる。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１をノード位置として、代表ノード番号で指定されるノード対のうちの該ノード位置のノードにリンクする。
【００３２】
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
【００３３】
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
図２Ｂは、カップルドノードツリーのツリー構造を概念的に示す図である。図示の６ビットのインデックスキーは、図１に例示されたパトリシアツリーのものと同じである。
【００３４】
符号２１０ａで示すのがルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。
ツリー構造としては、ルートノード２１０ａの下にノード対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。
【００３５】
各ノードの前に付された０あるいは１の符号は、図２Ａにおいて説明した配列要素の前に付された符号と同じであり、ノード位置を示す。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００３６】
図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
【００３７】
ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。
【００３８】
ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
【００３９】
ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。
【００４０】
ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。
【００４１】
ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。
【００４２】
ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの格納された配列要素の配列番号２２１ｆが格納されている。
【００４３】
ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。
【００４４】
また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００“が格納されている。
【００４５】
以下、上述のツリーからインデックスキー“１０００１０”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
【００４６】
ノード２１０ｆの弁別ビット位置２３０ｆには５が格納されているので、検索キー“１０００１０”の弁別ビット位置が５のビット値をみると０であるから、代表ノード番号の格納された配列番号２２０ｆの配列要素に格納されたノード２１０ｇにリンクする。
【００４７】
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを読み出して検索キーと比較すると両方とも“１０００１０”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【００４８】
次に、図２Ｂを参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図２Ｂの例で、ルートノード２１０ａの弁別ビット位置が０であるのは、図２Ｂに例示されたインデックスキーに０ビット目が０のものと１のものがあるからである。０ビット目が０のインデックスキーのグループはノード２１０ｂの下に分類され、０ビット目が１のインデックスキーのグループはノード２１１ｂの下に分類されている。
【００４９】
ノード２１１ｂの弁別ビット位置が２であるのは、ノード２１１ｈ、２１０ｈ、２１１ｇ、２１０ｇに格納された０ビット目が１のインデックスキーの１ビット目がすべて０で等しく、２ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
【００５０】
以下０ビット目の場合と同様に、２ビット目が１であるものはノード２１１ｆ側に分類され、２ビット目が０であるものはノード２１０ｆ側に分類される。
そして２ビット目が１であるインデックスキーは３ビット目の異なるものがあるのでノード２１１ｆの弁別ビット位置には３が格納され、２ビット目が０であるインデックスキーでは３ビット目も４ビット目も等しく５ビット目で異なるのでノード２１０ｆの弁別ビット位置には５が格納される。
【００５１】
ノード２１１ｆのリンク先においては、３ビット目が１のものと０のものがそれぞれ１つしかないことから、ノード２１０ｈ、２１１ｈはリーフノードとなり、それぞれインデックスキー２５０ｈと２５１ｈに“１０１０１１”と“１０１１００”が格納されている。
【００５２】
仮にインデックスキーの集合に“１０１１００”の代わりに“１０１１０１”か“１０１１１０”が含まれていたとしても、３ビット目までは“１０１１００”と等しいので、ノード２１１ｈに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“１０１１００”に加えて“１０１１０１”が含まれていると、ノード２１１ｈはブランチノードとなり、その弁別ビット位置は５になる。追加されるインデックスキーが“１０１１１０”であれば、弁別ビット位置は４となる。
【００５３】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“１”のノードとビット値が“０”のノードとに分岐していることから、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード２１１ｈのインデックスキー２５１ｈの“１０１１００”、ノード２１０ｈのインデックスキー２５０ｈの“１０１０１１”、・・・、ノード２１０ｃのインデックスキー２５０ｃの“０００１１１”となり降順にソートされている。
【００５４】
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“１０１１００”であればノード２１１ｈに到達することができる。また、上記説明からも想像がつくように、“１０１１０１”か“１０１１１０”を検索キーとした場合でもノード２１１ｈにたどり着き、インデックスキー２５１ｈと比較することにより同一のビット列からなるインデックスキーの検索が失敗したことが分かる。
【００５５】
また、例えば“１００１００”で検索した場合でも、ノード２１０ａ、２１１ｂ、２１０ｆのリンク経路では検索キーの３ビット目と４ビット目は使われることがなく、“１００１００”の５ビット目が０なので、“１０００１０”で検索した場合と同様にノード２１０ｇに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【００５６】
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００５７】
図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、配列３０９は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【００５８】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
以下、本実施形態に係る上記のカップルドノードツリーに格納されたインデックスキーの各種検索、カップルドノードツリーの生成、及び分割・結合について説明する。
【００５９】
先ず、図４Ａ、図４Ｂ及び図４Ｃを参照して、基本的な検索処理について説明する。
図４Ａは、本実施形態に係る基本検索の処理の概略を説明する図である。図４Ｂは、基本検索の処理フローを説明する図である。図４Ｃは、カップルドノードツリーによる基本検索例を説明する図であり、図２Ｂに例示したカップルドノードツリーのうち検索例に関係する部分及び探索経路スタックと各種ワークエリアが示されている。
【００６０】
図４Ａに示すように、ステップＳ４０１において、検索開始ノードを設定する。検索開始ノードの設定は、検索開始ノードの配列番号の指定あるいは取得によりその配列番号、あるいは該配列番号のノードを図示しない検索開始ノード設定エリアに設定することにより行う。なお、上述の検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置」の一つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。
【００６１】
上述のステップＳ４０１において、カップルドノードツリー全体からインデックスキーを検索する場合はルートノードが検索開始ノードとして設定されるが、後に説明する各種応用検索においては、カップルドノードツリーのあるノードが検索開始ノードとして指定され、その指定された検索開始ノードをルートノードとする部分木からインデックスキーを検索する場合がある。
【００６２】
次にステップＳ４０２において、探索経路スタックに終端ノードを格納する。終端ノードは探索経路スタックのボトムを示すための仮想的なブランチノードであり、ノード種別は他のブランチノードと区別するために“１”としている。弁別ビット位置は０より小さい値である“−１”としている。弁別ビット位置の桁数は、インデックスキーの桁数に対して充分あるものとする。なお、弁別ビット位置が“−１”であることで終端ノードであると識別できるので、ノード種別を“１”とすることは必須ではない。
【００６３】
終端ノードの代表ノード番号は、オール０の終端ノード［０］とオール１の終端ノード［１］がある。代表ノード番号がドントケアの場合は単に終端ノードと表記する。そして、代表ノードが偶数の配列番号の配列要素に格納されるとすると、終端ノード［０］のノード位置は０、終端ノード［１］のノード位置は１である。なお、終端ノード［０］と終端ノード［１］の代表ノード番号は、ノード位置０とノード位置１が識別できれば、必ずしもオール０、あるいはオール１である必要はない。
【００６４】
次にステップＳ４０３において検索キーを設定し、ステップＳ４０４に進み、ステップＳ４０３で設定された検索キーにより、ステップＳ４０１で設定された検索開始ノードから配列を検索し、インデックスキーを得る。このインデックスキーを得る検索処理の詳細を、次に図４Ｂを参照して説明する。
【００６５】
図４Ｂに示すように、ステップＳ４０５において、検索開始ノードの属するノード対の代表ノードの配列番号を代表ノード番号設定エリアに設定する。
図４Ｃの例示では、検索開始ノードがルートノードであるノード２１０ａであり、ノード対２０１ａの代表ノードすなわちノード２１０ａの配列番号２２０が代表ノード番号設定エリア２８０に設定される。もし、検索開始ノードがノード２１１ｃであれば、ノード対２０１ｃの代表ノード２１０ｃの配列番号２２０ｂが代表ノード番号設定エリア２８０に設定される。
【００６６】
次にステップＳ４０６において、ノード位置設定エリアに、検索開始ノードがノード対においてどちらに位置するかを示すノード位置を設定する。図４Ｃの例示では、ノード位置として、ノード位置設定エリア２９０にノード２１０ａのノード位置“０”が設定される。
【００６７】
図４Ｃの探索経路スタック３１０に示すように、終端ノードのノード種別は“１”であり、弁別ビット位置は全てのビットが“１”であることから、“−１”となる。
以上のステップＳ４０５及びステップＳ４０６からなる初期設定に続いて、ステップＳ４０７以降のループ処理に移行する。
【００６８】
ステップＳ４０７では、配列から代表ノード番号設定エリアに設定された代表ノード番号の指す配列要素の対をノード対として読み出す。ステップＳ４０７の最初の処理では、ステップＳ４０５で初期設定された代表ノード番号の指すノード対が読み出される。図４Ｃの例示では、代表ノード番号として配列番号２２０が設定されていることから、ノード対２０１ａが読み出される。
【００６９】
次にステップＳ４０８において、読み出されたノード対からノード位置設定エリアに設定されたノード位置の指すノードを取り出す。ステップＳ４０８の最初の処理では、ステップＳ４０６で初期設定されたノード位置の指すノードが取り出される。図４Ｃの例示では、ノード位置“０”が設定されていることから、ノード対２０１ａの２つのノードのうち、ノード２１０ａが読み出される。
【００７０】
次にステップＳ４０９において、ステップＳ４０８で取り出されたノードから、ノード種別を取り出し、ステップＳ４１０に進む。
ステップＳ４１０では、ステップＳ４０９で取り出したノード種別がブランチノードのものか判定する。
【００７１】
ノード種別がブランチノードのものでなければ、ステップＳ４０８で取り出されたノードはリーフノードであり、ステップＳ４１６に進み、ノードからインデックスキーを検索結果として取り出し、処理を終了する。
【００７２】
ステップＳ４１０での判定結果が肯定的で、ステップＳ４０９で取り出したノード種別がブランチノードのものであれば、ステップＳ４１１〜ステップＳ４１５の代表ノード番号設定エリア及びノード位置設定エリアの更新処理と探索経路スタックへのノードの格納処理を経てステップＳ４０７に戻り、このループ処理をステップＳ４１０での判定処理によりリーフノードが取り出されたことを確認するまで繰り返す。
【００７３】
ステップＳ４１１では、ステップＳ４０８で取り出されたノードから弁別ビット位置を取り出す。
次にステップＳ４１２において、検索キーからステップＳ４１１で取り出した弁別ビット位置の指すビット値を、ノード位置として設定する。図４Ｃの例示では、検索キー設定エリア２７０に設定された値が“０１１０１０”であることから、最初のループ処理として弁別ビット位置“０”が取り出され、検索キー“０１１０１０”の０ビット目の“０”がノード位置設定エリア２９０に設定される。
【００７４】
次にステップＳ４１３において、ノードから代表ノード番号を取り出して代表ノード番号設定エリアに設定する。
次にステップＳ４１４に進み、代表ノード番号設定エリアに設定されている代表ノード番号にノード位置を加えた値をステップＳ４０８で取り出されたノードの代表ノード番号に格納し、ステップＳ４１５で該ノードを探索経路スタックに格納してステップＳ４０７に戻る。図４Ｃの例示では、代表ノード番号２２０ａが取り出されて代表ノード番号設定エリア２８０に設定され、２２０ａ＋０＝２２０ａがノード２１０ａの代表ノード番号に格納され、そのノードが探索経路スタック３１０にスタックされる。
【００７５】
処理がステップＳ４０７に戻ると、図４Ｃの例示では、代表ノード番号２２０ａの指すノード対２０１ｂを読み出し、ノード位置設定エリア２９０に設定された“０”の指すノード２１０ｂを取り出してそこから弁別ビット位置“１”を取り出し、検索キー“０１１０１０”の１ビット目のビット値“１”をノード位置設定エリア２９０に設定する。さらに代表ノード番号２２０ｂを取り出して代表ノード番号設定エリア２８０に設定し、代表ノード番号２２０ｂ＋ノード位置“１”をその代表ノード番号に格納したノード２１０ｂを探索経路スタック３１０にスタックする。
【００７６】
引き続きステップＳ４０７に戻り、代表ノード番号設定エリア２８０に設定された２２０ｂの指すノード対２０１ｃを読み出し、ノード位置設定エリア２９０に設定された“１”の指すノード２１１ｃを取り出してそこから弁別ビット位置“２”を取り出し、検索キー“０１１０１０”の２ビット目のビット値“１”をノード位置設定エリア２９０に設定する。さらに代表ノード番号２２１ｃを取り出して代表ノード番号設定エリア２８０に設定し、代表ノード番号２２１ｃ＋ノード位置“１”をその代表ノード番号に格納したノード２１１ｃを探索経路スタック３１０にスタックする。
【００７７】
再びステップＳ４０７に戻り、代表ノード番号設定エリア２８０に設定された２２１ｃの指すノード対２０１ｄを読み出し、ノード位置設定エリア２９０に設定された“１”の指すノード２１１ｄを取り出してそこからノード種別２６１ｄを取り出す。すると、ノード種別２６１ｄは“１”であることからこのノードはリーフノードであることが判定され、インデックスキー“０１１０１０”が得られる。
【００７８】
以上、本実施形態に係る基本検索処理について説明したが、基本検索だけのためであれば探索経路スタックにノードをスタックする必要はない。しかし、後に説明する各種処理動作においては、基本検索における検索開始ノードからリーフノードに至るリンク経路の履歴情報を活用するため、リンク経路のノードを探索経路スタックに格納するものとして説明した。
【００７９】
また、図４Ｃの例示では、検索の結果、検索キーと同一のインデックスキーが得られたが、検索キーと同一のインデックスキーがカップルドノードツリーに存在しなくても、ブランチノードの弁別ビット位置と該弁別ビット位置が指す検索キーのビット値により次にリンク先のノード位置が求められ、最終的にはリーフノードに至ることから、検索結果としてのインデックスキーを求めることができる。
【００８０】
そして、検索キーと検索結果としてのインデックスキーとは、リンク経路の全てのブランチノードの弁別ビット位置のビット値が互いに等しいものであることは、上記説明から明らかである。
【００８１】
次に、図５Ａ〜図５Ｃ、図６Ａ、図６Ｂにより本実施形態に係るカップルドノードツリーにおけるノード挿入処理を説明する。図５Ａ〜図５Ｃが通常の挿入処理を説明するものであり、図６Ａ、図６Ｂはルートノードの挿入処理を含んだ挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ルートノードの挿入処理を含んだノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【００８２】
図５Ａは挿入処理の前段である検索処理の処理フローを示す図であり、図４Ａに示した検索処理において、検索開始ノードをルートノードとし、挿入しようとするノードのインデックスキーである挿入キーを検索キーとしたものに相当する。すなわち、ステップＳ５０１は図４ＡのステップＳ４０１で検索開始ノードをルートノードとしたものに相当し、ステップＳ５０３は図４ＡのＳ４０３ステップで挿入キーを検索キーとしたものに相当する。さらにＳ５０２、ステップＳ５０４の処理は図４ＡのステップＳ４０２、ステップＳ４０４の処理に完全に対応するので説明は省略する。
【００８３】
図５ＡのステップＳ５１１において挿入キーと検索結果として得られたインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図５ＢのステップＳ５１２以下の処理に進む。
【００８４】
図５Ｂは、挿入するノード対のための配列要素とその挿入位置を準備する処理を説明するフロー図である。
ステップＳ５１２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得して、代表ノード番号として設定する。
【００８５】
ステップＳ５１３に進み、挿入キーとステップＳ５０４で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１を小さいときは値０のブール値を得てノード位置に設定する。
【００８６】
ステップＳ５１４に進み、ステップＳ５１２で設定した代表ノード番号にステップＳ５１３で得たブール値を加算した配列番号を挿入ノードの配列番号として設定する。
ステップＳ５１５に進み、ステップＳ５１２で設定した代表ノード番号にステップＳ５１３で得たブール値の論理否定値を加算した配列番号を対ノードの配列番号として設定する。
【００８７】
ステップＳ５１４で設定した配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップＳ５１５で得た配列番号は、そのリーフノードと対をなすノードが格納される配列要素のものである。
【００８８】
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【００８９】
ステップＳ５１６で、挿入キーとステップＳ５０４で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップＳ５１７に進み、ステップＳ５１６で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置である差分ビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い差分ビット位置を得ることも可能である。
【００９０】
例えば図２Ｂのカップルドノードツリーに“０１１０１１”を挿入する場合、検索結果のインデックスキーはノード２１１ｄに格納された“０１１０１０”になる。挿入キー“０１１０１１”とノード２１１ｄに格納されたインデックスキー“０１１０１０”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値１が得られ、挿入されるノード対の代表ノード番号に１を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー“０１１０１０”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。
【００９１】
その際、インデックスキー“０１１０１０”と挿入キー“０１１０１１”とは５ビット目が差分ビット位置となることから、ノード２１１ｄは、弁別ビット位置を５とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【００９２】
また図２Ｂのカップルドノードツリーに“０１１００１”を挿入しようとする場合も、検索結果のインデックスキーはノード２１１ｄに格納された“０１１０１０”になる。この場合には挿入キーが小さいのでブール値０が得られ、挿入されるノード対の代表ノード番号に０を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー“０１１０１０”と挿入キー“０１１００１”とは４ビット目が差分ビット位置であることから、ノード２１１ｄは、弁別ビット位置を４とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【００９３】
次に図５ＣのステップＳ５１８以下の処理に進む。
図５Ｃは図５Ｂで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理を説明するフロー図である。
【００９４】
ステップＳ５１８〜ステップＳ５２４までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップＳ５２５以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【００９５】
ステップＳ５１８において、現在取り出されているノードを退避する。最初に退避されるノードはステップＳ５０４で取り出されたリーフノードである。
次にステップＳ５１９に進み、探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタを１つ戻す。
【００９６】
ステップＳ５２０に進み、ステップＳ５１９で取り出したノードから、弁別ビット位置を取り出す。
次にステップＳ５２１に進み、ステップＳ５２０で取り出した弁別ビット位置がステップＳ５１７で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【００９７】
ステップＳ５２１の判定結果が否定であれば、ステップＳ５１８に戻り、ステップＳ５１８において、ステップＳ５１９で取り出したノードを退避して、以下ステップＳ５２１での判定が肯定になるまで繰り返す。ステップＳ５２１での判定が肯定になると、ステップＳ５２２に進む。
【００９８】
ステップＳ５２２では、ステップＳ５１９で取り出したノードは終端ノードであるか判定する。終端ノードでなければ、ステップＳ５２３に移行し、ステップＳ５１９で取り出したノードから代表ノード番号を取り出し、親ノードの配列番号として設定してステップ５２５に進む。終端ノードであれば、ステップＳ５２４に移行し、ルートノードの配列番号を親ノードの配列番号として設定してステップ５２５に進む。ここで親ノードとは、そのリンク先が、ステップＳ５１２で取得され挿入されるノード対となるノードであって、挿入されるノード対の直近上位のノードである。
【００９９】
上記ステップＳ５１８〜ステップＳ５２４で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの差分ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードを親ノードとしてそのリンク先を挿入するノード対の挿入位置とするものである。
【０１００】
例えば図２Ｂのカップルドノードツリーに“１１１０００”を挿入するとき、その３ビット目が０であることから、検索結果のインデックスキーはノード２１０ｈに格納された“１０１０１１”になる。挿入キー“１１１０００”とノード２１０ｈに格納されたインデックスキー“１０１０１１”のビット列比較により差分ビット位置１が得られる。得られたビット位置１と探索経路スタックに積まれたブランチノードの弁別ビット位置との位置関係を弁別ビット位置が上位になるまで順次探索経路スタック３１０を逆にたどると、ルートノード２１０ａに至る。探索経路スタック３１０に格納されたルートノード２１０ａの代表ノード番号は、図４Ｂに示すステップＳ４１４においてノード位置を加えた値が設定されている。したがって、ルートノード２１０ａから代表ノード番号２２０ａ＋１を取り出し、親ノードの配列番号に設定する（ステップＳ５２３）。すなわち、親ノードの配列番号として、ノード２１１ｂの配列番号を得る。ノード２１１ｂの内容はステップＳ５２７で書き換えられ、挿入キー“１１１０００”は書き換えられたノード２１１ｂのリンク先に挿入される。
【０１０１】
また、探索経路スタックを逆にたどり終端ノードに至るということは、ルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということであり、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となる。すなわち、ルートノードが親ノードとなる。そして、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【０１０２】
なお、終端ノードが探索経路スタックから取り出されたときは、その弁別ビット位置は先に述べたように“−１”であるから、ステップＳ５２１の判定は「はい」になり、ステップＳ５２２の判定処理に移行する。
【０１０３】
次に、ステップＳ５２５以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップＳ５２５において、ステップＳ５１４で設定した挿入ノードの配列番号の指す配列要素のノード種別に１（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップＳ５２６に進み、ステップＳ５１８で退避したノードを読み出し、ステップＳ５１５で設定した対ノードの配列番号の配列要素に読み出した内容を書き込む。
【０１０４】
最後にステップＳ５２７において、親ノードの配列番号の指す配列要素のノード種別に０(ブランチノード）を、弁別ビット位置にステップＳ５１７で設定した差分ビット位置を、代表ノード番号にステップＳ５１２で設定した代表ノード番号を書き込み、処理を終了する。
【０１０５】
上述の図２Ｂのカップルドノードツリーに“１１１０００”を挿入する例では、取得された空ノード対のノード[０]に退避したノード２１１ｂの内容を書き込み（ステップＳ５２６）、ノード[１]を挿入キー“１１１０００”を保持するリーフノードとする（ステップＳ５２５）。そして、ノード２１１ｂの弁別ビット位置にビット列比較により異なるビット値となる最上位のビット位置である差分ビット位置１を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号が格納される（ステップＳ５２７）。
【０１０６】
以上の処理により、カップルドノードツリーへの新しいインデックスキーを格納したリーフノードの挿入が完了する。
図６Ａは、本実施形態に係るルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【０１０７】
ステップＳ６０１において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、ステップＳ６０２に移行して図５Ａ〜図５Ｃを用いて説明した通常の挿入処理が行われる。
【０１０８】
ステップＳ６０１での判定が登録済みでなければ、ステップＳ６０３、ステップＳ６０４の処理に移行し、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
【０１０９】
ステップＳ６０３では、ルートノードに挿入キーを含むリーフノードを設定する。ステップＳ６０３の処理の詳細は、図６Ｂを参照して後に説明する。
次にステップＳ６０４に進み、ルートノードの配列番号として挿入ノードの配列番号を登録して処理を終了する。
【０１１０】
図６Ｂは、ルートノードに挿入キーを含むリーフノードを設定する処理フローを説明する図である。
まず、ステップＳ６０５において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップＳ６０６において、ステップＳ６０５で得た配列番号に０を加えた配列番号を求め、挿入ノードの配列番号として設定する。（実際には、ステップＳ６０５で取得した配列番号に等しい。)。さらにステップＳ６０７において、ステップＳ６０６で設定した挿入ノードの配列番号のさす配列要素のノード種別に１（リーフノード)とインデックスキーに挿入キーを格納して処理を終了する。
【０１１１】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図６Ａ、図６Ｂ及び図５Ａ〜図５Ｃの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【０１１２】
次に図７Ａ、図７Ｂを参照して、本実施形態に係る、カップルドノードツリーから特定のインデックスキーを削除する処理フローを説明する。
図７Ａは、削除処理の前段である検索処理の処理フローを示す図であり、図４Ａ、図４Ｂに示した検索処理において削除キーを検索キーとし、検索開始ノードをルートノードとしたものに類似したものである。しかし、本実施形態の削除処理では、探索経路スタックは用いず、１つ分のノードを退避する退避ノードを用いる点で先に説明した検索処理と異なる。
【０１１３】
後の説明で分かるように、削除処理では、探索経路は１つさかのぼるだけでよいのでスタックを用いる必要はないので、そのかわりにノードを退避するノード退避エリアとそのノードの配列番号を退避する親ノード配列番号退避エリアを用いる。
【０１１４】
以下、ノード退避エリアに設定したノードを退避ノードといい、ノード退避エリアにノードを退避することを退避ノードにノードを設定すると表記することがある。また、親ノード配列番号退避エリアに退避した配列番号を親ノードの配列番号といい、親ノード配列番号退避エリアに配列番号を退避することを、親ノードに配列番号を設定すると表記することがある。
【０１１５】
図７Ａに示すように、まずステップＳ７０１において、代表ノード番号としてルートノードの配列番号を設定する。
次にステップＳ７０２において、ノード位置としてルートノードのノード位置を設定する。
【０１１６】
さらにステップＳ７０３において、退避ノードに終端ノードを設定する。
以上で初期設定を終了し、ステップＳ７０４〜ステップＳ７１２のループ処理と、ステップＳ７０７での判定結果によりループから抜け出した後の処理であるステップＳ７１３とステップＳ７１４を実行する。
【０１１７】
上記ループ処理のうち、ステップＳ７０４からステップＳ７０７のノード種別の判定処理は、図４Ｂに示すステップＳ４０７からステップ４１０と全く同じであるので、説明を省略する。
【０１１８】
ステップＳ７０７の判定結果が、ノード種別がブランチノードのものであった場合は、ステップＳ７０８〜ステップＳ７１２を経てステップＳ７０４に戻る、ループ処理が実行される。
【０１１９】
ステップＳ７０８及びステップＳ７０９の処理は探索経路スタックを用いることの代わりの処理であり、ステップＳ７０８において、ステップＳ７０５で取り出したノードを退避ノードに設定する。
【０１２０】
ステップＳ７０９においては、代表ノード番号設定エリアに設定されている代表ノード番号にノード位置設定エリアに設定されているノード位置を加えた値の配列番号を親ノードに設定する。ここで親ノードに設定した配列番号が、ステップＳ７０８で退避したノードが格納された配列要素の配列番号であることは、明らかである。
【０１２１】
次のステップＳ７１０〜ステップＳ７１２の処理は、図４ＢのステップＳ４１１〜ステップＳ４１３の処理と完全に対応するので説明は省略する。なお、図４Ｂに示すステップＳ４１４、ステップＳ４１５に対応するステップは、探索経路スタックを用いないことから、本実施形態の削除処理には存在しない。
【０１２２】
上述のループ処理によるリンクの結果、リーフノードに至りステップＳ７０７での判定が否定的なものとなると、ステップＳ７１３に分岐し、リーフノードからインデックスキーを取り出す。
【０１２３】
次にステップＳ７１４において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図７ＢのステップＳ７１５以下の処理に進む。
【０１２４】
図７Ｂは、削除処理の後段の処理フローを説明する図である。
まず、ステップＳ７１５でノード退避エリアに退避したノードが終端ノードであるか判定する。退避したノードが終端ノードであるということは、ルートノードがリーフノードであるということである。その場合はステップＳ７１９に移行し、ステップＳ７０１で設定した代表ノード番号の指すノード対、すなわちルートノードの配列番号の指すノード対を削除する。次にステップＳ７２０に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【０１２５】
ステップＳ７１５において退避したノードは終端ノードではないと判定されたときはステップＳ７１６に進み、ステップＳ７０４で読み出したノード対から、ステップＳ７１１で設定したノード位置のビット値を反転して得たノード位置の指すノードを取り出す。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードを取り出すものである。
【０１２６】
次にステップＳ７１７において、ステップＳ７１６で取り出したノードの内容を読み出し、ステップＳ７０９で設定した親ノードの配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノード（親ノード）を上記リーフノードと対をなすノードに置き換えるものである。
【０１２７】
最後にステップＳ７１８においてステップＳ７１２で設定した代表ノード番号の指すノード対を削除して処理を終了する。
次に図８Ａ、図８Ｂ及び図８Ｃを参照して、本実施形態に係る、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの最小値を求める最小値検索処理を説明する。
【０１２８】
図８Ａは、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの最小値を求める処理フローの概要を説明する図である。先に述べたようなインデックスキーのツリー上の配置から、インデックスキーの最小値を求める処理は検索開始ノードからノード［０］をリーフノードに至るまでツリー上でたどることに相当する。つまり、図４Ａ、図４Ｂに示す基本検索において、ノード位置が常に“０”である検索を行うことに相当する。すなわちビット値が全て“０”である検索キーで検索することに相当する。
【０１２９】
図８Ａに示すステップＳ８０１とステップＳ８０２は図４Ａに示すステップＳ４０１とステップＳ４０２に相当するものであり、上述のとおり、ノード位置は“０”に固定されているとすることができるので、検索キーを設定してそのビット値による分岐を行う必要がない。したがって、ステップＳ４０３に相当するステップは省略することができる。
次のステップＳ８０４において、ステップＳ８０１で設定された検索開始ノードから配列を検索し、インデックスキーの最小値を得る。このインデックスキーの最小値を得る検索処理の詳細を、次に図８Ｂを参照して説明する。
【０１３０】
図８Ｂに示すように、ステップＳ８０５において、検索開始ノードの属するノード対の代表ノードの配列番号を代表ノード番号設定エリアに設定する。
次にステップＳ８０６において、ノード位置設定エリアに、検索開始ノードがノード対においてどちらに位置するかを示すノード位置を設定する。
【０１３１】
次にステップＳ８０７に進み、配列から代表ノード番号設定エリアに設定された代表ノード番号の指す配列要素の対をノード対として読み出す。
次にステップＳ８０８において、読み出されたノード対からステップＳ８０６においてノード位置設定エリアに設定されたノード位置の指すノードを取り出す。
【０１３２】
次にステップＳ８０９において、ステップＳ８０８あるいは後述のステップＳ８１７で取り出されたードから、ノード種別を取り出し、ステップＳ８１０に進む。
ステップＳ８１０では、ステップＳ８０９で取り出したノード種別がブランチノードのものか判定する。
【０１３３】
ノード種別がブランチノードのものでなければ、ステップＳ８０８あるいはステップＳ８１７で取り出されたノードはリーフノードであり、ステップＳ８１８に進み、ノードからインデックスキーを検索結果、すなわち最小値として取り出し、処理を終了する。
【０１３４】
ステップＳ８１０での判定結果が肯定的で、ステップＳ８０９で取り出したノード種別がブランチノードのものであれば、ステップＳ８１３、ステップＳ８１５〜ステップＳ８１７の処理を経てステップＳ８０９に戻り、このループ処理をステップＳ８１０での判定処理によりリーフノードが取り出されたことを確認するまで繰り返す。
【０１３５】
ステップＳ８１３では、ノードから代表ノード番号を取り出して代表ノード番号設定エリアに設定する。
次にステップＳ８１５でノードを探索経路スタックに格納する。
【０１３６】
次にステップＳ８１６に進み、配列から代表ノード番号設定エリアに設定された代表ノード番号の指す配列要素の対をノード対として読み出す。
次にステップＳ８１７において、ステップＳ８１６で読み出されたノード対から、ノード［０］であるノードを取り出し、ステップＳ８０９に戻る。そして上述のとおり、ステップＳ８１０での判定処理によりリーフノードが取り出されたことを確認するまでステップＳ８０９〜ステップＳ８１７の処理を繰り返す。
【０１３７】
図８Ｃは、カップルドノードツリーによる最小値検索例を説明する図であり、図２Ｂに例示したカップルドノードツリーのうち最小値検索に関係するルートノード２１０ａとノード２１０ｂ以下の階層の部分木が示されている。
【０１３８】
初期設定において、検索開始ノードとしてルートノード２１０ａ、代表ノード番号として配列番号２２０が設定され、探索経路スタック３１０には終端ノードが格納される。さらにルートノード２１０ａのノード位置０が設定される。
【０１３９】
次に代表ノード番号として設定された配列番号２２０の指すノード対２０１ａから初期設定されたノード位置の指すノード２１０ａを取り出してノード種別２６０ａの判定を行い、ブランチノードであるので代表ノード番号２２０ａを取り出して代表ノード番号設定エリアに設定するとともに、ノード２１０ａを探索経路スタック３１０に格納する。
【０１４０】
次に代表ノード番号２２０ａの指すノード対２０１ｂからノード[０]であるノード２１０ｂを取り出してノード種別２６０ｂの判定を行い、ブランチノードであるので代表ノード番号２２０ｂを取り出して代表ノード番号設定エリアに設定するとともに、ノード２１０ｂを探索経路スタック３１０に格納する。
【０１４１】
さらに代表ノード番号２２０ｂの指すノード対２０１ｃからノード[０]であるノード２１０ｃを取り出してノード種別２６０ｃの判定を行い、リーフノードであるのでインデックスキー“０００１１１”を最小値として取り出すものである。
【０１４２】
上述の例では、検索開始ノードはノード位置が０であるルートノードであったが、検索開始ノードを２１１ｃとすると、代表ノード番号として２２０ｂ、ノード位置として１が初期設定され、ノード対２０１ｃが読み出されてそこからノード２１１ｃが取り出される。
【０１４３】
次に図９Ａ、図９Ｂ及び図９Ｃを参照して、本実施形態に係る、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの最大値を求める最大値検索処理を説明する。
【０１４４】
この最大値検索処理は、先に説明した最小値検索処理といわば双対の関係にある処理であり、以下の説明から明らかなとおり、最小値検索における値“０”を“１”に置き換えたものに相当する。
【０１４５】
図９Ａは、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの最大値を求める処理フローの概要を説明する図である。先に述べたようなインデックスキーのツリー上の配置から、インデックスキーの最大値を求める処理は検索開始ノードからノード［１］をリーフノードに至るまでツリー上でたどることに相当する。つまり、図４Ａ、図４Ｂに示す基本検索において、ノード位置が常に“１”である検索を行うことに相当する。すなわちビット値が全て“１”である検索キーで検索することに相当する。
【０１４６】
図９Ａに示すステップＳ９０１とステップＳ９０２は図４Ａに示すステップＳ４０１とステップＳ４０２に相当するものであり、上述のとおり、ノード位置は“１”に固定されているとすることができるので、検索キーを設定してそのビット値による分岐を行う必要がない。したがって、ステップＳ４０３に相当するステップは省略することができる。
次のステップＳ９０４において、ステップＳ９０１で設定された検索開始ノードから配列を検索し、インデックスキーの最大値を得る。このインデックスキーの最大値を得る検索処理の詳細を、次に図９Ｂを参照して説明する。
【０１４７】
図９Ｂに示すように、ステップＳ９０５において、検索開始ノードの属するノード対の代表ノードの配列番号を代表ノード番号設定エリアに設定する。
次にステップＳ９０６において、ノード位置設定エリアに、検索開始ノードがノード対においてどちらに位置するかを示すノード位置を設定する。
【０１４８】
次にステップＳ９０７に進み、配列から代表ノード番号設定エリアに設定された代表ノード番号の指す配列要素の対をノード対として読み出す。
次にステップＳ９０８において、読み出されたノード対からステップＳ９０６においてノード位置設定エリアに設定されたノード位置の指すノードを取り出す。
【０１４９】
次にステップＳ９０９において、ステップＳ９０８あるいは後述のステップＳ９１７で取り出されたードから、ノード種別を取り出し、ステップＳ９１０に進む。
ステップＳ９１０では、ステップＳ９０９で取り出したノード種別がブランチノードのものか判定する。
【０１５０】
ノード種別がブランチノードのものでなければ、ステップＳ９０８あるいはステップＳ９１７で取り出されたノードはリーフノードであり、ステップＳ９１８に進み、ノードからインデックスキーを検索結果、すなわち最大値として取り出し、処理を終了する。
【０１５１】
ステップＳ９１０での判定結果が肯定的で、ステップＳ９０９で取り出したノード種別がブランチノードのものであれば、ステップＳ９１３〜ステップＳ９１７の処理を経てステップＳ９０９に戻り、このループ処理をステップＳ９１０での判定処理によりリーフノードが取り出されたことを確認するまで繰り返す。
【０１５２】
ステップＳ９１３では、ノードから代表ノード番号を取り出して代表ノード番号設定エリアに設定する。
次にステップＳ９１４に進み、代表ノード番号設定エリアに設定されている代表ノード番号に１を加えた値をノードの代表ノード番号に格納し、ステップＳ９１５で該ノードを探索経路スタックに格納する。
【０１５３】
次にステップＳ９１６に進み、配列から代表ノード番号設定エリアに設定された代表ノード番号の指す配列要素の対をノード対として読み出す。
次にステップＳ９１７において、ステップＳ９１６で読み出されたノード対から、ノード［１］であるノードを取り出し、ステップＳ９０９に戻る。そして上述のとおり、ステップＳ９１０での判定処理によりリーフノードが取り出されたことを確認するまでステップＳ９０９〜ステップＳ９１７の処理を繰り返す。
【０１５４】
図９Ｃは、カップルドノードツリーによる最大値検索例を説明する図であり、図２Ｂに例示したカップルドノードツリーのうち最大値検索に関係するルートノード２１０ａとノード２１１ｂ以下の階層の部分木が示されている。
【０１５５】
初期設定において、検索開始ノードとしてルートノード２１０ａ、代表ノード番号として配列番号２２０が設定され、探索経路スタック３１０には終端ノードが格納される。さらにルートノード２１０ａのノード位置０が設定される。
【０１５６】
次に代表ノード番号として設定された配列番号２２０の指すノード対２０１ａから初期設定されたノード位置の指すノード２１０ａを取り出してノード種別２６０ａの判定を行い、ブランチノードであるので代表ノード番号２２０ａを取り出して代表ノード番号設定エリアに設定するとともに、その代表ノード番号を２１０ａ＋１に設定したノード２１０ａを探索経路スタック３１０に格納する。
【０１５７】
次に代表ノード番号２２０ａの指すノード対２０１ｂからノード[１]であるノード２１１ｂを取り出してノード種別２６１ｂの判定を行い、ブランチノードであるので代表ノード番号２２１ｂを取り出して代表ノード番号設定エリアに設定するとともに、代表ノード番号に２２１ｂ＋１を格納したノード２１１ｂを探索経路スタック３１０に格納する。
【０１５８】
さらに代表ノード番号２２１ｂの指すノード対２０１ｆからノード[１]であるノード２１１ｆを取り出してノード種別２６１ｆの判定を行い、ブランチノードであるので代表ノード番号２２１ｆを取り出して代表ノード番号設定エリアに設定するとともに、代表ノード番号に２２１ｆ＋１を格納したノード２１１ｆを探索経路スタック３１０に格納する。
【０１５９】
さらに代表ノード番号２２１ｆの指すノード対２０１ｈからノード[１]であるノード２１１ｈを取り出してノード種別２６１ｈの判定を行い、リーフノードであるのでインデックスキー“１０１１００”を最大値として取り出すものである。
【０１６０】
以上、本実施形態に係る最小値・最大値検索処理について説明したが、最小値・最大値検索だけのためであれば、基本検索の場合と同様に探索経路スタックにノードをスタックする必要はない。しかし、後に説明する各種処理動作においては、最小値・最大値検索における検索開始ノードからリーフノードに至るリンク経路の履歴情報を活用するため、リンク経路のノードを探索経路スタックに格納するものとして説明した。
【０１６１】
次に図１０Ａ、図１０Ｂ及び図１０Ｃを参照して、本実施形態に係る、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの下限値を求める下限値検索処理を説明する。ここで下限値とは、指定された下限キー以上のインデックスキーの最小値である。
【０１６２】
図１０Ａ及び図１０Ｂは、カップルドノードツリーに格納されたインデックスキーの下限値を求める処理を示したフローチャートである。図１０Ａ及び図１０Ｂに示す下限値を求める処理は、ユーザ等が指定する検索範囲について検索を行う際に、実際にはインデックスキーが取り得ない範囲については対象外とし、実際にインデックスキーが含まれる範囲について検索を行う処理に応用される。なお、図１０Ａ及び図１０Ｂでは、指定された下限キーの取得処理は省略されている。以降の各種応用検索においても同様である。
【０１６３】
まず、ステップＳ１００１で、検索開始ノードを設定する。先に図４Ａに示す基本検索の説明で述べたように、検索開始ノードの設定は、検索開始ノードの配列番号の指定あるいは取得によりその配列番号、あるいは該配列番号のノードを図示しない検索開始ノード設定エリアに設定することにより行う。上述の点は、後に説明する他の応用検索においても同様である。
【０１６４】
次にステップＳ１００２において、探索経路スタックに、終端ノードを格納する。
ステップＳ１００３では、図８Ｂに示す最小値検索処理を行いインデックスキーの最小値を求める。そして、ステップＳ１００４で、下限キーと、ステップＳ１００３で求めた最小値との比較をし、最小値が下限キー以上であるかを判定する。最小値が下限キー以上の値をとる場合、ステップＳ１００５に進み、ステップＳ１００３で求めた最小値を下限値として設定し、処理を終了する。
【０１６５】
ステップＳ１００４において、ステップＳ１００２で求めた最小値が下限キーよりも小さいと判定された場合は、ステップＳ１００６で探索経路スタックに終端ノード［０］を格納し、ステップＳ１００７に進む。
【０１６６】
ステップＳ１００７で下限キーを検索キーとして設定する。次にステップＳ１００８で、該検索キーによりステップＳ１００１で設定した検索開始ノードを検索開始ノードとして、図４Ｂを参照して説明したビット列検索方法により配列を検索し、インデックスキーを得る。
【０１６７】
そして、ステップＳ１００９で、検索キーとステップＳ１００８の検索の結果得られたインデックスキーとを比較して値が一致するか否かを判定する。検索キーとインデックスキーが等しいと判定された場合は、ステップＳ１０１０に進み、検索により得られたインデックスキーを上記下限値として設定し、処理を終了する。
【０１６８】
検索キーとインデックスキーが等しくないと判定された場合は、図１０Ｂに示すステップＳ１０１１に進む。
ステップＳ１０１１では、検索キーとインデックスキーの大小関係を判定する。インデックスキーが、検索キーすなわち下限キーよりも小さい場合は、そのインデックスキーは、ユーザ等により指定された検索範囲に含まれないことを意味する。
【０１６９】
一方、インデックスキーが検索キーよりも大きい場合は、そのインデックスキーは指定された検索範囲に含まれることを意味する。そこで、インデックスキーが検索キーよりも大きいと判定されると、ステップＳ１０１９に進み、そのインデックスキーを下限値に設定して、処理を終了する。
【０１７０】
一方、ステップＳ１０１１において、インデックスキーが検索キーよりも小さいと判定されると、ステップＳ１０１２に進む。ステップＳ１０１２からステップＳ１０１８までの処理は、カップルドノードツリーの順序性に基づいて昇順にインデックスキーを取り出す処理である。先に述べたとおり、カップルドノードツリーにおいて、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、そこに格納されているインデックスキーは降順にソートされている。
【０１７１】
したがって、昇順にインデックスキーを取り出すには、ノード対をなすノードのうちノード［０］側及びツリーの深さを優先させてノードから順次リーフノードをたどり、各リーフノードからインデックスキーを取り出していけばよい。
【０１７２】
ステップＳ１０１２からステップＳ１０１８の処理により、カップルドノードツリーに格納されているインデックスキーが順に取り出されていき、検索キーすなわち下限キーよりも大きい値をとるインデックスキーが得られると、そのインデックスキーが下限値として設定される。
【０１７３】
まず、ステップＳ１０１２で、探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタの値を１つ減らす。最初のステップＳ１０１２での探索経路スタックの状態は、ステップＳ１００８の検索処理を実行したときの状態である。
【０１７４】
次にステップＳ１０１３において、取り出したノードの代表番号から取り出したノードのノード位置を得る。
次にステップＳ１０１４に進み、ステップＳ１０１３で得たノード位置がノード［１］側であるか判定する。ノード［１］側であればステップＳ１０１２に戻り、ノード［０］側であればステップＳ１０１５に進む。
【０１７５】
ステップＳ１０１５では、ステップＳ１０１２で取り出したノードが終端ノードであるか判定する。該ノードが終端ノードであれば、下限値は存在しないことになり、検索失敗として処理を終了する。この場合は例外的処理であり、下限値を求める対象であるカップルドノードツリーが下限キーより小さいインデックスキーを格納したリーフノードだけから構成されている場合である。
【０１７６】
ステップＳ１０１５での判定が「終端ノードではない」であれば、ステップＳ１０１６に進み、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ１０１２で取り出したノードの代表ノード番号を設定する。
【０１７７】
さらにステップＳ１０１７で、検索開始ノードのノード位置として、値１を設定してステップＳ１０１８に進み、図８Ｂに示す最小値検索を実行し、インデックスキーの最小値を取得し、ステップＳ１０１１の下限キーとインデックスキーの大小の判定処理に戻る。
【０１７８】
上述のステップＳ１０１６とステップＳ１０１７の処理は、図８Ｂに示すステップＳ８０５とステップＳ８０６に対応した処理である。ステップＳ１０１６で、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ１０１２で取り出したノードの代表ノード番号を設定し、ステップＳ８０５において、該設定されたステップＳ１０１２で取り出したノードの代表ノード番号が、代表ノード番号設定エリアに設定される。同様に、ステップＳ１０１７で、検索開始ノードのノード位置として、値１を設定し、ステップＳ８０６において、該設定された値１をノード位置設定エリアに設定する。
【０１７９】
以上説明したステップＳ１０１１〜ステップＳ１０１８のループ処理によりインデックスキーを昇順に取り出し、検索キー（下限キー）より大きいものが得られたとき、ステップＳ１０１９に分岐し、それが下限値として設定される。
【０１８０】
図１０Ｃは、カップルドノードツリーによる下限値検索例を説明する図であり、図１０Ｃ（ａ）には、図２Ｂに例示したカップルドノードツリーのうち下限値検索例に関係するルートノード２１０ａとノード２１０ｂ以下の階層の部分木と検索キー設定エリア２７０が示されており、検索キー設定エリア２７０には下限キー“０１０１００”が設定されている。図１０Ｃ（ｂ）には、下限キーによる検索後の下限値検索による探索経路スタック３１０の状態遷移（１）、（２）、（３）が示されている。
【０１８１】
上述のステップＳ１００８における下限キー“０１０１００”によるルートノード２１０ａを検索開始ノードとする検索を実行すると、図１０Ｃ（ａ）に太枠で示すように、ノード２１０ａ、ノード２１０ｂ、ノード２１１ｃ、ノード２１０ｄをたどり、リーフノードであるノード２１０ｅに至り、インデックスキー“０１００１０”が得られる。
【０１８２】
上記検索を実行すると、図１０Ｃ（ｂ）の（１）に示すように探索経路スタック３１０には、終端ノード［０］とノード２１０ａからノード２１０ｄまでの探索経路のブランチノードが順次格納され、図示しないスタックポインタはノード２１０ｄを指している。そして、分岐先ノードのノード位置が“１”であるノード２１０ｂの代表ノード番号は１加算され、２２０ｂ＋１となっている。
【０１８３】
図１０Ｃ（ａ）に示すように、ノード２１０ｅが下限値の探索開始ノードとなり、ノード２１０ｅに格納されたインデックスキー“０１００１０”と下限キー“０１０１００”の大小比較が図１０Ｂに示すステップＳ１０１１で実行される。インデックスキー“０１００１０”が下限キー“０１０１００”より小さいので、探索経路スタック３１０からノード２１０ｄが取り出され、スタックポインタの指すノードは、図１０Ｃ（ｂ）の（２）に示すようにノード２１０ｄからノード２１１ｃに変わる。
【０１８４】
ノード２１０ｄの代表ノード番号２２０ｄからはノード位置“０”が検出される。したがって、代表ノード番号２２０ｄを、図８Ｂに示す最小値検索における代表ノード番号と、ノード位置に値“１”を設定して最小値検索を実行する。すると、図１０Ｃ（ｂ）の（２）に示すように、配列番号が２２０ｄ＋１であるリーフノード２１１ｅのインデックスキー“０１００１１”が取り出される。このインデックスキーも下限キーより小さいこと、ノード２１１ｃの代表ノード番号２２１ｃからはノード位置“０”が検出されるから、代表ノード番号２２１ｃを、図８Ｂに示す最小値検索における代表ノード番号と、ノード位置に値“１”を設定して再び最小値検索を実行する。すると、図１０Ｃ（ｂ）の（３）に示すように、配列番号が２２１ｃ＋１であるリーフノード２１１ｄのインデックスキー“０１１０１０”が取り出される。そして、下限キーとの大小比較から、このインデックスキーが下限値として求められる。
【０１８５】
次に図１１Ａ、図１１Ｂ及び図１１Ｃを参照して、本実施形態に係る、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの上限値を求める上限値検索処理を説明する。ここで上限値とは、指定された上限キー以下のインデックスキーの最大値である。
【０１８６】
図１１Ａ及び図１１Ｂは、カップルドノードツリーに格納されたインデックスキーの上限値を求める処理を示したフローチャートである。図１１Ａ及び図１１Ｂに示す上限値を求める処理は、先に説明した下限値検索と同様に、ユーザ等が指定する検索範囲について検索を行う際に、実際にはインデックスキーが取り得ない範囲については対象外とし、実際にインデックスキーが含まれる範囲について検索を行う処理に応用される。
【０１８７】
この上限値検索処理は、先に説明した下限値検索処理といわば双対の関係にある処理であり、以下の説明から明らかなとおり、下限値検索におけるノード位置０と１を逆にし、最小値を最大値に置き換え、大小関係を逆にしたものに相当する。
【０１８８】
まず、ステップＳ１１０１で、検索開始ノードを設定する。次にステップＳ１１０２において、探索経路スタックに、終端ノードを格納する。
ステップＳ１１０３では、図９Ｂに示す最大値検索処理を行いインデックスキーの最大値を求める。そして、ステップＳ１１０４で、上限キーと、ステップＳ１１０３で求めた最大値との比較をし、最大値が上限キー以下であるかを判定する。最大値が上限キー以下の値をとる場合、ステップＳ１１０５に進み、ステップＳ１１０３で求めた最大値を上限値として設定し、処理を終了する。
【０１８９】
ステップＳ１１０４において、ステップＳ１１０２で求めた最大値が上限キーよりも大きいと判定された場合は、ステップＳ１１０６で探索経路スタックに終端ノード［１］を格納し、ステップＳ１１０７に進む。
【０１９０】
ステップＳ１１０７で上限キーを検索キーとして設定する。次にステップＳ１１０８で、該検索キーによりステップＳ１１０１で設定した検索開始ノードを検索開始ノードとして、図４Ｂを参照して説明したビット列検索方法により配列を検索し、インデックスキーを得る。
【０１９１】
そして、ステップＳ１１０９で、検索キーとステップＳ１１０８の検索の結果得られたインデックスキーとを比較して値が一致するか否かを判定する。検索キーとインデックスキーが等しいと判定された場合は、ステップＳ１１１０に進み、検索により得られたインデックスキーを上記上限値として設定し、処理を終了する。
【０１９２】
検索キーとインデックスキーが等しくないと判定された場合は、図１１Ｂに示すステップＳ１１１１に進む。
ステップＳ１１１１では、検索キーとインデックスキーの大小関係を判定する。インデックスキーが、検索キーすなわち上限キーよりも大きい場合は、そのインデックスキーは、ユーザ等により指定された検索範囲に含まれないことを意味する。
【０１９３】
一方、インデックスキーが検索キーよりも小さい場合は、そのインデックスキーは指定された検索範囲に含まれることを意味する。そこで、インデックスキーが検索キーよりも小さいと判定されると、ステップＳ１１１９に進み、そのインデックスキーを上限値に設定して、処理を終了する。
【０１９４】
一方、ステップＳ１１１１において、インデックスキーが検索キーよりも大きいと判定されると、ステップＳ１１１２に進む。ステップＳ１１１２からステップＳ１１１８までの処理は、カップルドノードツリーの順序性に基づいて降順にインデックスキーを取り出す処理である。先に述べたとおり、カップルドノードツリーにおいて、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、そこに格納されているインデックスキーは降順にソートされている。
【０１９５】
したがって、降順にインデックスキーを取り出すには、ノード対をなすノードのうちノード［１］側及びツリーの深さを優先させてノードから順次リーフノードをたどり、各リーフノードからインデックスキーを取り出していけばよい。
【０１９６】
ステップＳ１１１２からステップＳ１１１８の処理により、カップルドノードツリーに格納されているインデックスキーが順に取り出されていき、検索キーすなわち上限キーよりも小さい値をとるインデックスキーが得られると、そのインデックスキーが上限値として設定される。
【０１９７】
まず、ステップＳ１１１２で、探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタの値を１つ減らす。最初のステップＳ１１１２での探索経路スタックの状態は、ステップＳ１１０８の検索処理を実行したときの状態である。
【０１９８】
次にステップＳ１１１３において、取り出したノードの代表番号から取り出したノードのノード位置を得る。
次にステップＳ１１１４に進み、ステップＳ１１１３で得たノード位置がノード［０］側であるか判定する。ノード［０］側であればステップＳ１１１２に戻り、ノード［１］側であればステップＳ１１１５に進む。
【０１９９】
ステップＳ１１１５では、ステップＳ１１１２で取り出したノードが終端ノードであるか判定する。該ノードが終端ノードであれば、上限値は存在しないことになり、検索失敗として処理を終了する。この場合は例外的処理であり、上限値を求める対象であるカップルドノードツリーが上限キーより大きいインデックスキーを格納したリーフノードだけから構成されている場合である。
【０２００】
ステップＳ１１１５での判定が「終端ノードではない」であれば、ステップＳ１１１６に進み、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ１１１２で取り出したノードの代表ノード番号を設定する。
【０２０１】
さらにステップＳ１１１７で、検索開始ノードのノード位置として、値０を設定してステップＳ１１１８に進み、図９Ｂに示す最大値検索を実行し、インデックスキーの最大値を取得し、ステップＳ１１１１の上限キーとインデックスキーの大小の判定処理に戻る。
【０２０２】
上述のステップＳ１１１６とステップＳ１１１７の処理は、図９Ｂに示すステップＳ９０５とステップＳ９０６に対応した処理である。ステップＳ１１１６で、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ１１１２で取り出したノードの代表ノード番号を設定し、ステップＳ９０５において、該設定されたステップＳ１１１２で取り出したノードの代表ノード番号が、代表ノード番号設定エリアに設定される。同様に、ステップＳ１１１７で、検索開始ノードのノード位置として、値０を設定し、ステップＳ９０６において、該設定された値０をノード位置設定エリアに設定する。
【０２０３】
以上説明したステップＳ１１１１〜ステップＳ１１１８のループ処理によりインデックスキーを降順に取り出し、検索キー（上限キー）より小さいものが得られたとき、ステップＳ１１１９に分岐し、それが上限値として設定される。
【０２０４】
図１１Ｃは、カップルドノードツリーによる上限値検索例を説明する図であり、図１１Ｃ（ａ）には、図２Ｂに例示したカップルドノードツリーのうち上限値検索例に関係するルートノード２１０ａとノード２１１ｂ以下の階層の部分木と検索キー設定エリア２７０が示されており、検索キー設定エリア２７０には上限キー“１０１００１”が設定されている。図１１Ｃ（ｂ）には、上限キーによる検索後の上限値検索による探索経路スタック３１０の状態遷移（１）、（２）が示されている。
【０２０５】
上述のステップＳ１１０８における上限キー“１０１００１”によるルートノード２１０ａを検索開始ノードとする検索を実行すると、図１１Ｃ（ａ）に太枠で示すように、ノード２１０ａ、ノード２１１ｂ、ノード２１１ｆをたどり、リーフノードであるノード２１０ｈに至り、インデックスキー“１０１０１１”が得られる。
【０２０６】
上記検索を実行すると、図１１Ｃ（ｂ）の（１）に示すように探索経路スタック３１０には、終端ノード［１］とノード２１０ａからノード２１１ｆまでの探索経路のブランチノードが順次格納され、図示しないスタックポインタはノード２１１ｆを指している。そして、分岐先ノードのノード位置が“１”であるノード２１０ａ、ノード２１０ｂの代表ノード番号は１加算され、それぞれ２２０ａ＋１、２２０ｂ＋１となっている。
【０２０７】
図１１Ｃ（ａ）に示すように、ノード２１０ｈが上限値の探索開始ノードとなり、ノード２１０ｈに格納されたインデックスキー“１０１０１１”と上限キー“１０１００１”の大小比較が図１１Ｂに示すステップＳ１１１１で実行される。インデックスキー“１０１０１１”が上限キー“１０１００１”より大きいので、探索経路スタック３１０からノード２１１ｆが取り出され、スタックポインタの指すノードは、図１１Ｃ（ｂ）の（１）に矢印で示すようにノード２１１ｆからノード２１１ｂに変わる。
【０２０８】
ノード２１１ｆの代表ノード番号２２１ｆからはノード位置“０”が検出されるので、図１１Ｂに示すステップＳ１１１４からステップＳ１１１２へのループ処理が実行される。そして、ステップＳ１１１２でノード２１１ｂが取り出され、スタックポインタは、図１１Ｃ（ｂ）の（１）から（２）への点線による矢印に示すように、ノード２１０ａを指す。ノード２１１ｂの代表ノード番号２２１ｂ＋１からはノード位置“１”が検出される。
【０２０９】
したがって、探索経路スタック３１０に格納されたノード２１１ｂの代表ノード番号２２１ｂ＋１から１を減算した２２１ｂを、図９Ｂに示す最大値検索における代表ノード番号と、ノード位置に値“０”を設定して最大値検索を実行する。すると、図１１Ｃ（ｂ）の（２）に示すように、配列番号が２２０ｆ＋１であるリーフノード２１１ｇのインデックスキー“１０００１１”が取り出される。そして、上限キーとの大小比較から、このインデックスキーが上限値として求められる。
【０２１０】
次に、本実施形態に係る、カップルドノードツリーの分割／結合処理について説明をする。
ここでカップルドノードツリーの分割とは、あるビット列からなる分割キーを指定したとき、カップルドノードツリーに含まれるインデックスキーをその分割キーとの大小関係により２グループに分け、それぞれのグループに属するインデックスキーからなる２つのカップルドノードツリーを生成することである。
【０２１１】
大小関係による分割について、以下の説明では、分割キーより大きいグループと分割キー以下のグループに分割するとするが、分割キー以上のグループと分割キーより小さいグループに分割する場合でも、同様に分割／結合が可能であることは、以下の説明から容易に理解されるであろう。
【０２１２】
要するに、分割キーはカップルドノードツリーをどこで分割するかを決定するために用いられるキーである。
また、カップルドノードツリーの結合とは、２つのインデックスキーの集合に対応する２つカップルドノードツリーから２つのインデックスキーの集合の和集合に対応するカップルドノードツリーを生成することである。本発明では、２つのインデックスキーの集合の積集合は空であることを前提にしている。
【０２１３】
以下、カップルドノードツリーの分割／結合処理として３つの実施例を説明するが、その説明において、カップルドノードツリーを単にツリーということがある。
第１の実施例は、分割対象である処理元のツリー（以下、単に処理元ということがある。）のインデックスキーの最小値を取り出し、取り出したインデックスキーの最小値を、処理元の分割により生成される処理先のツリー（以下、単に処理先ということがある。）に挿入し、処理元のツリーからインデックスキーの最小値を削除する処理を、最小値が分割キー以下である間繰り返すことにより、分割対象である処理元のツリーから処理先のツリーを分割するものである。
【０２１４】
図１２Ａ及び図１２Ｂを参照して、第１の実施例におけるカップルドノードツリーの分割処理フローを説明する。
図１２Ａは、第１の実施例における分割処理の前段の処理である処理先の初期設定等に関する処理を説明する図である。
【０２１５】
最初のステップＳ１２０１で指定された分割キーを処理元の分割キーとして設定する。分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。
【０２１６】
次にステップＳ１２０２で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップＳ１２０２ａで処理元の探索経路スタックに終端ノードを格納してステップＳ１２０３に進む。
【０２１７】
ステップＳ１２０３では、処理元の検索開始ノード、すなわちステップＳ１２０２で検索開始ノードに設定したルートノードから図８Ｂに示す最小値検索を行い、最小値を求める。
【０２１８】
次にステップＳ１２０４において、該最小値が分割キーより大であるか判定する。処理元の最小値が最初から分割キーより大であれば分割キー以下のインデックスキーは処理元に含まれないことからここで処理は終了となる。以上の初期処理は第２、第３の分割処理においても同様である。
【０２１９】
ステップＳ１２０３の最小値検索で得られた最小値が分割キーより小さければ、ステップＳ１２０５に進み、該最小値を処理先の挿入処理における挿入キーに設定する。
次にステップＳ１２０６において、図６Ｂに示す、ルートノードに挿入キーを含むリーフノード（挿入ノード）を設定する処理を実行する。そして、ステップＳ１２０７に進み、処理先のルートノードの配列番号として、挿入ノードの配列番号を登録し、ステップＳ１２０８で処理先の検索開始ノードとして、処理先のルートノードを設定することにより、処理先の初期設定を完了させ、引き続いて、図１２Ｂに示すステップＳ１２０９に移行する。
【０２２０】
図１２Ｂは、第１の実施例における分割処理の後段の処理を説明する図である。
図１２Ｂに示すように、ステップＳ１２０９において、ステップＳ１２０５あるいは後述のステップＳ１２１４における挿入キーを処理元の削除処理における削除キーに設定し、ステップＳ１２１０において、図７Ａ、図７Ｂに示す削除処理により、処理元のツリーから削除キーを含むリーフノードを削除する。
【０２２１】
次のステップＳ１２１１では、処理元のツリーが登録済みか判定する。この判定結果が登録済みではないというのは処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものであり、その場合には処理を終了する。
【０２２２】
処理元のツリーが登録済みであればステップＳ１２１２に移行し、ステップＳ１２０２で検索開始ノードとして設定したルートノードを最小値検索の検索開始ノードとして、図８Ａに示す最小値検索処理を実行してインデックスキーの最小値を得る。
【０２２３】
次にステップＳ１２１３に進み、ステップＳ１２１２で得た最小値が分割キーより大であるか判定する。最小値が分割キーより大であれば、ツリーの分割が完成しているのであるから処理を終了し、以下であれば、ステップＳ１２１４に移行する。
【０２２４】
ステップＳ１２１４では、ステップＳ１２１２で得られた最小値を処理先の挿入処理における挿入キーに設定する。
次にステップＳ１２１５で、図５Ａ、図５Ｂに示すツリーの挿入処理により、挿入キーによる処理先へのノードの挿入を実行し、処理元のツリーからのノードの削除処理であるステップＳ１２０９、ステップＳ１２１０へ戻る。
【０２２５】
以上のステップＳ１２０９〜ステップＳ１２１５のループ処理を、ステップＳ１２１３において、ステップＳ１２１２で得た最小値が分割キーより大であると判定されるまで繰り返すことにより、ツリーの分割が実現される。
【０２２６】
上記分割処理の説明では、処理元のインデックスキーの最小値から順に削除を行うようにしたが、同様にインデックスキーの最大値から順に削除を行うことができることは、当業者に明らかである。その場合、ステップＳ１２０３とステップＳ１２１２はインデックスキーの最大値を求める処理になり、ステップＳ１２０４とステップＳ１２１３は最大値と分割キーの大小関係の判定処理となり、ステップＳ１２１４では最大値を処理先の挿入キーに設定することになる。
【０２２７】
以上、分割処理について説明したが、結合処理も図１２Ａ及び図１２Ｂに示す処理フローに基づいて実行できる。
結合処理は、結合しようとする２つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上とすれば、先に述べた例外的な処理に該当し、処理元のツリーは削除され、処理先のツリーに結合される。なお、処理元のツリーのインデックスキーの最大値が未知の場合には、前もって図９Ａに示す最大値検索処理により分割キーを求めることになる。
【０２２８】
そして、処理先は既に登録済みであることから、ステップＳ１２０５〜ステップＳ１２０７は省略することができ、処理元の分割キーを処理元のツリーのインデックスキーの最大値以上とするのであるから、ステップＳ１２０４及びステップＳ１２１３の大小比較では、分割キーが最小値より常に大きくステップＳ１２０５あるいはステップＳ１２１４へ分岐するのでステップＳ１２０４及びステップＳ１２１３を省略することができる。そうであれば、分割キーを設定する意味もないことから、結局ステップＳ１２０１も不要になり、ただ単に最小値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができる。
【０２２９】
また、分割処理について述べたように、最大値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができることも明らかである。
本実施例は処理のロジックは簡易なものであるが、処理元のルートノードを検索開始ノードとする最小値検索を繰り返し、インデックスキー単位で挿入削除を行うため、実行時の処理ステップ数は大きくなる。
【０２３０】
次に本実施形態に係る分割／結合処理の第２の実施例について説明する。
本実施例は、インデックスキー単位で挿入削除を行う点では第１の実施例と同様であるが、挿入削除すべきインデックスキーの探索に探索経路スタックを活用し、挿入処理及び削除処理の実行時の処理ステップ数を小さくしたものである。
【０２３１】
図１３Ａ及び図１３Ｂを参照して、第２の実施例におけるカップルドノードツリーの分割処理フローを説明する。
図１３Ａは、第２の実施例における分割処理の前段の処理である初期設定に関する処理を説明する図である。
【０２３２】
最初のステップＳ１３０１で指定された分割キーを処理元の分割キーとして設定する。第１の実施例について述べたように、分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。
【０２３３】
次にステップＳ１３０２で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップＳ１３０２ａに進み、処理元の探索経路スタックに、終端ノードを格納する。
【０２３４】
次にステップＳ１３０３で、処理元の検索開始ノード、すなわちステップＳ１３０２で検索開始ノードに設定したルートノードから図８Ｂに示す最小値検索を行い、最小値を求める。
【０２３５】
次にステップＳ１３０４において、該最小値が分割キーより大であるか判定する。処理元の最小値が最初から分割キーより大であれば分割キー以下のインデックスキーは処理元に含まれないことからここで処理は終了となる。
【０２３６】
ステップＳ１３０３の最小値検索で得られた最小値が分割キー以下であれば、ステップＳ１３０６〜ステップＳ１３１０の処理先の初期設定処理に進む。
ステップＳ１３０６において、ステップＳ１３０３で得た最小値を挿入キーとして設定する。次にステップＳ１３０７において、図６Ｂに示す、ルートノードに挿入キーを含むリーフノード（挿入ノード）を設定する処理を実行する。そして、ステップＳ１３０８に進み、処理先のルートノードの配列番号として、挿入ノードの配列番号を登録し、ステップＳ１３０９で処理先の検索開始ノードとして、処理先のルートノードを設定する。さらにステップＳ１３１０において、処理先の探索経路スタックに終端ノードを格納して処理先の初期設定処理を完了し、図１３Ｂに示すステップＳ１３１１以降の後段の処理に移行する。
【０２３７】
図１３Ｂは、第２の実施例におけるカップルドノードツリーの分割処理の後段を説明する図である。
ステップＳ１３１１において、処理元から削除ノードを削除し、後に削除ノードと対をなすノードの内容が複写される該ノードの親ノード（処理元の親ノード）を得る。ステップＳ１３１１の処理及び削除ノードと処理元の親ノードについては、後に図１５を参照して詳細に説明する。
【０２３８】
次にステップＳ１３１２において、処理元が登録済みか判定する。実施例１の場合と同様に、処理元が登録済みでなければ処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものであり、その場合には処理を終了する。
【０２３９】
処理元が登録済みであれば、ステップＳ１３１３に進み、処理元の検索開始ノードにステップＳ１３１１で得た処理元の親ノードを設定し、ステップＳ１３１４に進んで、図８Ｂに示す最小値検索を実行して最小値を得る。
【０２４０】
後に説明するように、処理元の親ノードは削除ノードの直近上位のブランチノードである。削除ノードは処理元のインデックスキーの最小値を含むものであり、先に述べたインデックスキーの順序性から、次に検索する最小値は処理元の親ノードの下位にある。したがって、ステップＳ１３１４での最小値検索の検索開始ノードはルートノードとしないで処理元の親ノードとすることにより、処理ステップ数を低減することができる。
【０２４１】
次にステップＳ１３１５において、ステップＳ１３１４で得られた最小値が分割キーより大か判定する。最小値が分割キーより大であれば、ツリーの分割が完成しているのであるから処理を終了し、以下であればステップＳ１３１６に進む。
【０２４２】
ステップＳ１３１６において、処理先の検索開始ノードより、図９Ｂに示す最大値検索を実行し、最大値を得る。処理先の検索開始ノードは、最初の処理ではステップＳ１３０９で設定された処理先のルートノードであり、それ以降は後述のステップＳ１３１８で設定される。
【０２４３】
次にステップＳ１３１７に進み、ステップ１３０３あるいは後述のステップＳ１３１４で得た最小値とステップＳ１３１６で得た最大値により、挿入するノード対の処理先の親ノードを求め、処理先の該親ノードに該最小値を含むノード対を挿入する。この処理は、図１２Ｂに示すステップＳ１２１５の挿入処理とは異なる本実施例特有のものであり、ステップＳ１３１７の処理及び処理先の親ノードについて、後に図１４を参照して詳細に説明する。
【０２４４】
次にステップＳ１３１８において、処理先の検索開始ノードに処理先の親ノードを設定し、ステップＳ１３１１に戻る。
以上のステップＳ１３１１〜ステップＳ１３１８のループ処理を、ステップＳ１３１５において、ステップＳ１３１４で得た最小値が分割キーより大であると判定されるまで繰り返すことにより、ツリーの分割が実現される。
【０２４５】
図１４は、図１３Ｂに示すステップＳ１３１７に対応する処理先のノード対の挿入処理フローを説明する図である。
図１４に示すように、ステップＳ１４０１で配列からノード対が空の代表ノードの配列番号を取得し、代表ノード番号として設定する。
【０２４６】
次にステップＳ１４０２において、ステップＳ１４０１で設定した代表ノード番号に値“１”を加えて得た配列番号を挿入ノードの配列番号として設定し、ステップＳ１４０３において、代表ノード番号に値“０”を加えて得た配列番号を挿入ノードと対をなす対ノードの配列番号として設定する。
【０２４７】
次にステップＳ１４０４において、図１３Ｂに示すステップＳ１３１４で得た最小値である挿入キーとステップＳ１３１６で得た最大値をビット列として比較して上位０ビット目から見た最初の不一致ビットの位置を求め、それを差分ビット位置格納エリアに設定する。
【０２４８】
次にステップＳ１４０５に進み、図５Ｃに示すステップＳ５１８以降の、ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理を実行して処理を終了する。
【０２４９】
上述のステップＳ１４０１〜ステップＳ１４０４の処理は、図５Ｂに示すステップＳ５１２〜ステップＳ５１７からなる、挿入するノード対のための配列要素を準備する処理に相当するものである。また、図１３Ｂに示すステップＳ１３１６の処理先の最大値検索は、図５Ａに示す挿入処理の前段である、処理先の検索処理に相当する。本実施例の場合、処理元の最小値は常に処理先の最大値より大きいから、ステップＳ５１３で設定されるとすればブール値は１であるから、ステップＳ１４０２での挿入ノードの配列番号設定は、ステップＳ１４０１で設定した代表ノード番号に値１を加えたものになる。
【０２５０】
以上の挿入するノード対のための配列要素を準備する処理の後、ステップＳ１４０５の処理により挿入処理が完了する。
図１５は、図１３Ｂに示すステップＳ１３１１に対応する処理元の削除処理を説明する図である。
【０２５１】
最初のステップＳ１５０１において、処理元の探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタを１つ戻す。ここで処理元の探索経路スタックには、図１３Ａに示すステップＳ１３０３あるいは図１３Ｂに示すステップＳ１３１４で実行した最小値検索によりノードが格納されており、スタックポインタは、最小値が格納されたリーフノードの直近上位のブランチノードあるいは終端ノード（ルートノードがリーフノードの場合）を指している。
【０２５２】
次のステップＳ１５０２では、ステップＳ１５０１で取り出したノードが終端ノードであるか判定する。該ノードが終端ノードであれば、ステップＳ１５１１に移行し、ルートノードの配列番号の指すノード対を削除し、ステップＳ１５１２において、ルートノードの配列番号の登録を抹消して「処理元の登録なし」を返す。
【０２５３】
ステップＳ１５０１で取り出したノードが終端ノードでなければ、ステップＳ１５０３に進み、ステップＳ１５０１で取り出したノードの代表ノード番号を削除ノードの配列番号として設定する。つまり、削除ノードは最小値が格納されたリーフノードである。
【０２５４】
次にステップＳ１５０４に進み、処理元の探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタを１つ戻す。ここで処理元の探索経路スタックのスタックポインタは、最小値が格納されたリーフノードの直近上位のブランチノードのさらに直近上位のブランチノードあるいは終端ノード（ブランチノードがルートノードのみのとき）を指している。
【０２５５】
次にステップＳ１５０５において、該取り出したノードが終端ノードか判定する。
ステップＳ１５０４で取り出したノードが終端ノードでなければ、ステップＳ１５０６に分岐し、該ノードから代表ノード番号を取り出し、処理元の親ノードの配列番号を格納するエリアに設定するとともに、該親ノードの代表ノード番号を退避してステップＳ１５０８に進む。
【０２５６】
ステップＳ１５０４で取り出したノードが終端ノードであれば、ステップＳ１５０７に分岐し、ルートノードの配列番号を、処理元の親ノードの配列番号を格納するエリアに設定するとともに、該親ノードの代表ノード番号を退避してステップＳ１５０７ａに進む。ステップＳ１５０７ａでは、スタックポインタのアンダーフローを解消するため、処理元の探索経路スタックのスタックポインタを１つ進め、ステップＳ１５０８に進む。
【０２５７】
なお、上述のように、ステップＳ１５０４で取り出すノードは、削除ノードの２つ上位に位置するブランチノードである。したがって、このブランチノードから取り出した代表ノード番号は削除ノードの直近上位のブランチノードの格納された配列要素を指す配列番号である。すなわち、処理元の親ノードは削除ノードの直近上位のブランチノードである。また、退避した親ノードの代表ノード番号は、削除ノードの配置された配列要素の配列番号である。
【０２５８】
ステップＳ１５０８においては、削除ノードと対をなすノードの配列番号を対ノードの配列番号を格納するエリアに設定する。
次にステップＳ１５０９において、ステップＳ１５０８で設定した対ノードの配列番号の指す配列要素の内容を読出し、ステップＳ１５０６あるいはステップＳ１５０７で設定した処理元の親ノードの配列番号の指す配列要素に格納する。
【０２５９】
次にステップＳ１５１０において、退避した親ノードの代表ノード番号の指すノード対を削除して「処理元の登録あり」を返す。
上述の処理により、削除ノードと対ノードからなるノード対が削除され、削除ノードの直近上位のブランチノードである親ノードには削除ノードの対ノードの内容が格納されるとともに、該親ノードの配列番号は処理元の親ノードの配列番号を格納するエリアに設定され、図１３Ｂに示すステップＳ１３１３で次の最小値検索の検索開始ノードの設定に用いられる。
【０２６０】
以上、第２の実施例のツリー分割処理について説明したが、本実施例においても、第１の実施例の場合と同様にインデックスキーの最大値から順に削除を行うことができる。
また、第１の実施例の場合と同様に分割処理の処理フローをツリーの結合処理に用いることが可能である。結合しようとする２つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上あるいは最小値以下として処理元のツリーの削除処理を行い、削除されたノードを処理先のツリーに挿入する処理を行えばよい。
【０２６１】
次に本実施形態に係る分割／結合処理の第３の実施例について説明する。
以上説明した第１の実施例と第２の実施例の分割／結合処理は、インデックスキー単位で挿入削除を行うものであった。第３の実施例は、カップルドノードツリーの順序性に着目した、カップルドノードツリーのより大きい、所定の条件を満たす、部分木を単位として挿入削除を行うものである。
【０２６２】
図１６Ａ及び図１６Ｂは、第３の実施例におけるカップルドノードツリーの分割処理フローを説明する図である。また、図２２Ａ〜図２２Ｃは、上記分割処理を実例により説明する図であり、図２Ｂに例示したカップルドノードツリーと類似したツリーを例示している。図２２Ａは分割前のツリー構造例を示し、図２２Ｂは最初の分割後のツリー構造例を示し、図２２Ｃは次の分割後のツリー構造例を示している。なお、図２２Ａ〜図２２Ｃには、処理元の探索経路スタックとそのスタックポインタが指すノードについても記載されている。
【０２６３】
まず図１６Ａを参照して、本実施例における分割処理の前段である初期処理を説明する。
最初のステップＳ１６０１で指定された分割キーを処理元の分割キーとして設定する。第１及び第２の実施例について述べたように、分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。
【０２６４】
図２２Ａの例示では、分割キーはノード２１１ｇのインデックスキー２５１ｇの“１０００１１”と等しい。なお、先に述べたように、取得する分割キーは処理元に含まれる必要はないが、後に説明するように、本実施例においては取得された分割キーにより処理元の上限値あるいは下限値を求めて処理元に含まれるインデックスキーを新たな分割キーとする必要がある。したがって、以下の説明では分割キーは処理元に含まれるものとして説明する。
【０２６５】
次にステップＳ１６０２で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップＳ１６０２ａに進み、処理元の探索経路スタックに、終端ノードを格納する。
【０２６６】
次にステップＳ１６０３で、処理元の検索開始ノード、すなわちステップＳ１６０２で検索開始ノードに設定したルートノードから図８Ｂに示す最小値検索を行い、最小値を求める。
【０２６７】
次にステップＳ１６０４において、該最小値が分割キーより大であるか判定する。処理元の最小値が最初から分割キーより大であれば分割キー以下のインデックスキーは処理元に含まれないことからここで処理は終了となる。
【０２６８】
ステップＳ１６０３の最小値検索で得られた最小値が分割キー以下であれば、ステップＳ１６０５〜ステップＳ１６０６の処理元の初期設定処理とステップＳ１６０８〜ステップＳ１６０８ｂの処理先の初期設定処理に進む。
【０２６９】
ステップＳ１６０５においては、分割キーにより処理元の分割ノードを求める。分割ノードは、分割キーを最大値として含む部分木のうち最大のもの（以下、分割ノードツリーという。）のルートノードである。図２２Ａの例示では、図２２Ａ（ａ）の（１）に示すように、ノード２１０ｆが分割ノードであり、点線で囲まれた部分木が分割ノードツリー２９１である。ステップＳ１６０５の分割ノードを求める処理の詳細は後に図１７Ａ及び図１７Ｂを参照して説明する。
【０２７０】
次にステップＳ１６０６に進み、処理元の探索経路スタックに積まれた終端ノードを終端ノード［１］とする。ステップＳ１６０６に進んだ段階では、処理元の探索経路スタックに積まれた終端ノードは後に説明するとおり終端ノード［０］であるが、後に図１９を参照して説明する処理元の次の分割ノードを求める処理のため、終端ノード［１］に置き換えておく。
【０２７１】
次にステップＳ１６０８に進み、ステップＳ１６０５で求めた分割ノードを処理先のルートノードに設定して処理先のルートノードとして登録する。次にステップＳ１６０８ａに進み、処理先の検索開始ノードに処理先のルートノードを設定する。さらにステップＳ１６０８ｂに進み、処理先の探索経路スタックに、終端ノードを格納し、処理先に関する初期処理を完了させて前段の処理を完了し、図１６Ｂに示すステップＳ１６０９以降の処理に進む。なおステップＳ１６０８の処理の詳細な説明は後に図１８Ａを参照して行う。
【０２７２】
図２２Ａの例示では、分割処理が開始されたばかりであり、図２２Ａの（ｂ）に示すように処理先は存在せず登録されていないから、分割ノード２１０ｆの内容を処理先として新たに取得されたノード対２０１ｉの代表ノード２１０ｉに格納して処理先のルートノードに設定し、処理先のルートノードとして登録する。その結果として、図２２Ｂ（ｂ）に示すように、挿入された分割ノードツリー２９１からなる処理先のツリーが生成される。
【０２７３】
一方、図２２Ｂ（ａ）の（１）には、処理元からノード２１０ｆを分割ノードとする分割ノードツリー２９１が削除されたツリー構造が示されており、分割ノード２１０ｂをルートノードとする次の分割ノードツリー２９２が点線で囲まれて示されている。
【０２７４】
次に図１６Ｂを参照して、本実施例における分割処理の後段である分割ノードツリーの処理元からの削除と処理先への挿入を説明する。
ステップＳ１６０９では、処理元から分割ノードツリーを削除し、該ノードの親ノードを得る。
【０２７５】
図２２Ｃ（ｂ）の例示では、ルートノード２１０ｉを挿入位置とし、新たに取得されたノード対２０１ｊを介して次の分割ノードツリー２９２が処理先に挿入されたツリー構造が示されている。また、図２２Ｃ（ａ）の（１）には、図２２Ｂ（ａ）の（１）に示されたツリー構造から次の分割ノードツリー２９２が削除された構造が示されている。なおステップＳ１６０９における削除処理の詳細は、後に図２１を参照して説明する。
【０２７６】
次にステップＳ１６１０に進み、処理元が登録済みか判定し、登録済みでなければ、処理を終了する。この判定結果が登録済みではないというのは処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものである。
【０２７７】
ステップＳ１６１０の判定結果が登録済みであれば、ステップＳ１６１１に進み、処理元を検索して次の分割ノードを求める。ステップＳ１６１１における次の分割ノードを求める処理の詳細は、後に図１９を参照して説明する。
【０２７８】
ステップＳ１６１１に続いてステップＳ１６１２において、ステップＳ１６１１で分割ノードが求まったか判定する。分割ノードが求まらなければ分割処理は終了となる。
分割ノードが求まれば、ステップＳ１６１３において、その分割ノードをルートノードとする部分木である分割ノードツリーの最大値を求めて次の分割キーとする。なお、ステップＳ１６１３における分割ノードツリーの最大値を求めて次の分割キーとする処理の詳細は、後に図２０を参照して説明する。
【０２７９】
次にステップＳ１６１４において、処理先の検索開始ノードに、処理先の挿入位置のノードを設定する。直前に処理先に挿入された分割ノードツリーに処理先の最小値が含まれていることは明らかであるから、直前に挿入された分割ノード、例えば図２２Ｃ（ｂ）に例示した処理先においては、ノード２１０ｊの配列番号２２０ｊ（挿入位置）を検索開始ノードの配列番号として設定することにより、ルートノードを検索開始ノードとする場合と比べて最小値検索の処理を軽減することができる。
【０２８０】
ステップＳ１６１４の後、ステップＳ１６１５に進む。
ステップＳ１６１５では、処理先の検索開始ノードより図８Ｂに示す最小値検索によりインデックスキーの最小値を配列から得る。
【０２８１】
次にステップＳ１６１６において、ステップＳ１６１３で設定された次の分割ノードツリーの最大値である分割キーとステップＳ１６１５で得た処理先の最小値をビット列比較して上位０ビット目から見た最初の不一致ビット位置を求め、差分ビット位置として設定する。図２２Ｂの例示では、次の分割ノードツリー２９２の最大値はインデックスキー２５１ｃ“０１１０１０”であり、処理先の最小値はインデックスキー２５０ｇ“１０００１０”であるから、差分ビット位置は“０”である。
【０２８２】
次にステップＳ１６１７に進み、処理先のルートノードを挿入位置として処理先に分割ノードツリーを挿入し、ステップＳ１６０９に戻る。なおステップＳ１６１７における分割ノードツリーの挿入処理の詳細は、後に図１８Ｂを参照して説明する。
【０２８３】
以上のステップＳ１６０９〜ステップＳ１６１７のループ処理において、次の分割ノードツリーの挿入、削除処理及び更なる次の分割ノードを求める処理を、分割ノードが求められなくなるまで繰り返す。
【０２８４】
本実施例では上述のように分割ノードツリー単位で削除挿入処理が行われるため、処理ステップ数が削減される。
次に、図１７Ａ及び図１７Ｂを参照して図１６Ａに示すステップＳ１６０５における分割ノード（最初の分割ノード）を求める処理を詳細に説明する。
【０２８５】
図１７Ａは、最初の分割ノードを求める処理の前段の処理を説明するフロー図である。
図１７Ａに示すように、ステップＳ１７０１で分割キーを検索キーとして設定し、ステップＳ１７０２で処理元のルートノードを検索開始ノードとして設定する。次にステップＳ１７０３に進み、処理元の探索経路スタックに終端ノード［０］を格納する。
【０２８６】
次にステップＳ１７０４に進み、図４Ｂに示す検索処理を実行し、検索結果として分割キーと等しいインデックスキーを得て前段の処理を終了し、図１７Ｂに示す後段の処理に進む。
【０２８７】
後段の処理は図１７Ｂを参照して説明するが、その前に、図２２Ａを再び参照して、本実施例においては分割キーを処理元に含まれるインデックスキーとしておく必要性について説明する。
【０２８８】
いま、図２２Ａ（ａ）の（１）に示す処理元を分割キー“１００００１”で分割するとする。この分割キーで図１７Ａに示すステップＳ１７０４の検索処理を実行すると、検索結果として得られるインデックスキーはインデックスキー２５１ｇの“１０００１１”である。ところが、分割点とすべきインデックスキーは、リーフノード２１１ｃに格納された、“１００００１”を上限とする上限値“０１１０１０”あるいはリーフノード２１０ｇに格納された、“１００００１”を下限とする下限値“１０００１０”であり、いずれの場合も分割キー“１００００１”で検索した結果と一致しないからである。
【０２８９】
したがって、分割ノードを求める前に、図１０Ａ、図１０Ｂに示す、あるいは図１１Ａ、図１１Ｂに示す処理により下限値あるいは上限値を求め、分割キーをその定義に応じて処理元に含まれるインデックスキーとして求めておく必要がある。
【０２９０】
次に、最初の分割ノードを求める処理フローの後段の処理を説明する。
図１７Ｂは、最初の分割ノードを求める処理の後段の処理を説明するフロー図である。後段の処理は、処理元の探索経路スタックを遡り、取り出されたノードのノード位置が初めてノード［０］側となるノードを求めて、その代表ノード番号を分割ノードの配列番号として設定するものである。別の言い方をすれば、処理元の探索経路スタックを遡り、最初のノード［０］を分割ノードとするものである。
【０２９１】
図１７Ｂに示すように、ステップＳ１７０５で探索経路スタックからノードを取り出し、スタックポインタを１つ減らす。ここで最初に取り出されるノードは、処理元がルートノードだけから構成されるような例外的な場合を除いて、分割キーで検索した検索結果のインデックスキーを含むリーフノードの直近上位のブランチノードである。
【０２９２】
次にステップＳ１７０６へ進み、ノードの代表ノード番号から、この代表ノード番号の指す配列要素に配置されたノードのノード位置を得る。
次にステップＳ１７０７において、ステップＳ１７０６で得たノード位置がノード［１］側か判定する。判定の結果がノード［１］側であればステップＳ１７０５の処理に戻り、ノード［０］側であればステップＳ１７０８に進む。
【０２９３】
ステップＳ１７０８においては、ステップＳ１７０５で取り出したノードが終端ノードであるか判定する。判定の結果、終端ノードであれば、ステップＳ１７１０に進み、ルートノードの代表ノード番号を分割ノードの配列番号として設定して処理を終了する。
【０２９４】
ステップＳ１７０８の判定の結果、終端ノードでなければ、ステップＳ１７０９に進み、ステップＳ１７０５で得たノードの代表ノード番号を分割ノードの配列番号として設定して処理を終了する。
【０２９５】
図２２Ａに示す例では、ルートノード２１０ａを検索開始ノードに設定して分割キー“１０００１１”により検索処理を実行すると検索結果としてのインデックスキー２５１ｇが得られ、図２２Ａ（ａ）の（２）に示す探索経路スタック３１０には終端ノード［０］、ノード２１０ａ、２１１ｂ、２１０ｆが順次スタックされる。（ノード２１０ａ、２１０ｆの代表ノード番号は、それぞれ１加算されている。）
したがって、図１７Ｂに示すステップＳ１７０５の最初の処理時には探索経路スタックのスタックポインタはノード２１０ｆを指しており、ステップＳ１７０６では代表ノード番号２２０ｆ＋１からノード位置１が得られる。したがって、ステップＳ１７０７の判定処理の結果、ステップＳ１７０５に戻り、次のステップＳ１７０７では１つ遡ったノード２１１ｂの代表ノード番号２２１ｂからノード位置０が判定され、ステップＳ１７０８の判定を介してステップＳ１７０９に移行し、ステップＳ１７０５で取り出されたノード２１１ｂの代表ノード番号２２１ｂ、すなわちノード２１０ｆの配列番号２２１ｂが分割ノードの配列番号として設定される。そして、処理元の探索経路スタック３１０のスタックポインタは、図２２Ａ（ａ）の（２）において矢印で示すように、ノード２１０ａを指している。
【０２９６】
なお、ステップＳ１７０８での判定が終端ノードとなるのは、例えば図２２Ａに示すノード２１０ｆをルートノードとするツリーが処理元で、分割キーが“１０００１１”の場合である。この場合、２回目のステップＳ１７０７ではルートノード２１０ｆから１つ遡った終端ノード［０］の代表ノード番号からノード位置０が判定され、ステップＳ１７０８で終端ノードであると判定されてステップＳ１７１０に移行し、ルートノード２１０ｆの代表ノード番号２２０ｆ、すなわちノード２１０ｇの配列番号２２０ｆが分割ノードの配列番号として設定される。
【０２９７】
ここで、さらに分割処理について説明する前に、分割キーは分割ノードツリーの最大値であり、分割ノードツリーは分割キーを最大値とする処理元の部分木のうち最大の部分木、別の表現をすればそのルートノードの弁別ビット位置が最上位である部分木であることを説明する。
【０２９８】
今までの説明から明らかなとおり、分割ノードは、分割キーで検索を行ったときの分割キーに至るまでの経路を遡って初めてのノード［０］である。
分割キーをインデックスキーとして含むリーフノードがノード［０］であれば、そのリーフノードが分割ノード自体であり、分割ノードツリーは１つのリーフノードだけから構成される。このリーフノードと対をなすノード［１］側に存在するリーフノードのインデックスキーは、カップルドノードツリーの順序性によって全て分割キーより大きい。したがって、今のケースの場合、分割キーより上位のブランチノードをルートノードとする部分木においては、分割キーは最大値とはなりえないから、分割キーは分割ノードツリーの最大値であり、分割ノードツリーは分割キーを最大値とする処理元の部分木のうち最大のものである。
【０２９９】
分割キーをインデックスキーとして含むリーフノードがノード［１］であれば、ツリーをノード［１］側をたどって遡っている限りは、カップルドノードツリーの順序性により、どのノード［１］をルートノードとする部分木においても上記分割キーはこれらの部分木の最大値である。そして、ノード［０］にまで遡ったとき、それ以上上位のノードの下位には当該ノード［０］と対をなすノード［１］以下のノードが存在し、これらのノードには上記分割キーより大きいインデックスキーを含むリーフノードが存在する。
【０３００】
したがって、上記ノード［０］すなわち分割ノードをルートノードとする部分木が、上記分割キーを最大値として含む最大の部分木である。
以下引き続き、分割処理の説明を、図１８Ａ以下を参照して行う。
【０３０１】
図１８Ａは、図１６Ｂに示すステップＳ１６０８における処理先のルートノードの挿入処理を説明するフロー図である。
ステップＳ１８０１において、図１６Ａに示す処理フローのステップＳ１６０５、すなわち図１７Ｂに示すステップＳ１７０９あるいはステップＳ１７１０で求められた分割ノードの格納された配列要素の配列番号を挿入ノードの配列番号として設定する。
【０３０２】
次にステップＳ１８０２で、配列から、空のノード対の代表ノードの配列番号を取得する。
次にステップＳ１８０３で、ステップＳ１８０２で取得した配列番号をノード［０］の配列番号として設定する。
【０３０３】
次にステップＳ１８０４において、ステップＳ１８０１で設定された挿入ノードの配列番号の指す配列要素の内容を読み出して、ステップＳ１８０３で設定されたノード［０］の配列番号の指す配列要素に格納する。
【０３０４】
最後にステップＳ１８０５で、ノード［０］の配列番号を処理先のルートノードの配列番号として登録して、ルートノードの挿入処理を終了する。
図２２Ａ及び図２２Ｂ（ｂ）の例示では、分割ノード２１０ｆの格納された配列要素の配列番号２２１ｂが挿入ノードの配列番号に設定され、取得された空のノード対２０１ｉの代表ノードの配列番号２２０’ がノード［０］の配列番号として設定される。
【０３０５】
そして、配列番号２２１ｂが指す配列要素の内容、すなわち分割ノード２１０ｆの内容が配列番号２２０’の指す配列要素すなわちノード２１０ｉに格納され、配列番号２２０’が処理先のルートノードの配列番号として登録される。
【０３０６】
図１８Ｂは、図１６Ｂに示すステップＳ１６１７におけるルートノード以外の挿入処理を説明するフロー図である。
最初にステップＳ１８１１で、図１６Ｂに示す処理フローのステップＳ１６１１で求められた分割ノードの格納された配列要素の配列番号を、挿入ノードの配列番号として設定する。このステップＳ１８１１は図１８Ａに示すステップＳ１８０１とは、分割ノードが求められた処理ステップがステップＳ１６０５ではなくステップＳ１６１１である点で異なるだけである。
【０３０７】
次にステップＳ１８１２において、処理先の挿入位置として、処理先のルートノードの配列番号を設定する。
次のステップＳ１８１３〜ステップＳ１８１５は、図１８Ａに示すルートノードの挿入処理のステップＳ１８０２〜ステップＳ１８０４と同様である。
【０３０８】
ステップＳ１８１３で、配列から、空のノード対の代表ノードの配列番号を取得し、次にステップＳ１８１４で、ステップＳ１８１３で取得した配列番号をノード［０］の配列番号として設定し、次にステップＳ１８１５において、ステップＳ１８１１で設定された挿入ノードの配列番号の指す配列要素の内容を読み出して、ステップＳ１８１４で設定されたノード［０］の配列番号の指す配列要素に格納する。
【０３０９】
次にステップＳ１８１６に進み、ステップＳ１８１３で取得した配列番号に値１を加えた値を、ノード［１］の配列番号として設定する。
次にステップＳ１８１７において、ステップＳ１８１２で設定した処理先の挿入位置の配列番号の指す配列要素の内容を読み出し、ステップＳ１８１６で設定したノード［１］の配列番号の指す配列要素に格納する。
【０３１０】
最後にステップＳ１８１８において、ノード種別にブランチを、弁別ビット位置に図１６Ｂに示すステップＳ１６１６で求めた差分ビット位置を、代表ノード番号にステップＳ１８１４で設定したノード［０］の配列番号を設定してブランチノードを形成し、ステップＳ１８１２で設定した処理先の挿入位置の配列番号の指す配列要素に格納して処理を終了する。
【０３１１】
図２２Ｂ及び図２２Ｃ（ｂ）の例示では、分割ノード２１０ｂの格納された配列要素の配列番号２２０ａが挿入ノードの配列番号に設定され、処理先の挿入位置としてルートノード２１０ｉの配列番号２２０’が設定される。また、取得された空のノード対２０１ｊの代表ノードの配列番号２２０ｊがノード［０］の配列番号として設定される。
【０３１２】
そして、挿入ノードの配列番号２２０ａが指す配列要素の内容、すなわち分割ノード２１０ｂの内容をノード［０］の配列番号２２０ｊの指す配列要素にノード２１０ｊとして格納される。
【０３１３】
一方、配列番号２２０ｊに１を加えて得た値である配列番号２２０ｊ＋１の指す配列要素すなわちノード２１１ｊに、処理先の挿入位置の配列番号２２０’の指す配列要素すなわち図２２Ｂ（ｂ）に示すルートノード２１０ｉの内容を格納している。
【０３１４】
そして図２２Ｃ（ｂ）に示すルートノード２１０ｉの弁別ビット位置２３０ｉには、先に図１６ＢのステップＳ１６１６に関する例示で説明した分割ノードツリー２９２の最大値であるインデックスキー２５１ｃ“０１１０１０”と処理先の最小値であるインデックスキー２５０ｇ“１０００１０”の差分ビット位置
“０”が格納されている。また、代表ノード番号には、ノード［０］の配列番号２２０ｊが格納されている。
【０３１５】
上記説明から理解されるように、挿入先が生成された後の挿入処理は、挿入先のルートノードの直下にブランチノード同士からなるノード対を挿入し、そのノード対のノード［１］以下に既存の処理先のルートノード以下の部分木を接続し、ノード［０］に分割ノードツリーを接続するものである。この処理により、分割ノードツリーを挿入後の挿入先の順序性が保たれることは明らかである。
【０３１６】
図１９は、図１６Ｂに示すステップＳ１６１１における次の分割ノードを求める処理の処理フローを説明する図である。
ステップＳ１９０１において、探索経路スタックからノードを取り出し、探索経路スタックのスタックポインタを１つ減らす。スタックポインタの初期値は、図１６Ｂに示すステップＳ１６０９の削除処理終了時のものであり、後に図２１を参照した削除処理の説明で明らかになるとおり、分割ノード（削除処理においては削除ノード）の２つ上位のノードを指している。
【０３１７】
次にステップＳ１９０２に進み、ステップＳ１９０１で取り出されたノードの代表ノード番号から、その代表ノード番号が指す配列要素に格納されたノードのノード位置を得る。
【０３１８】
次にステップＳ１９０３において、ステップＳ１９０２で得たノード位置がノード［０］側であるか判定する。ノード［０］側であればステップＳ１９０１に戻り、ノード［１］側であればステップＳ１９０４に移行する。
【０３１９】
ステップＳ１９０４では、ノードが終端ノードか判定する。ノードが終端ノードであれば「分割ノードなし」を返す。
ノードが終端ノードでなければ、ステップＳ１９０５に進み、Ｓ１９０１で取り出したノードの代表ノード番号から値１を減じて得たノード［０］の配列番号を、分割ノードの配列番号として設定して「分割ノードあり」を返す。
【０３２０】
図２２Ａ及び図２２Ｂの例示では、次の分割ノードを求める段階では処理元の探索経路スタック３１０のスタックポインタは、先に述べたように、図２２Ａ（ａ）の（３）に示すとおり、分割ノード２１０ｆの２つ上位のルートノード２１０ａを指しており、探索経路スタック３１０に格納されたルートノード２１０ａの代表ノード番号には２２０ａ＋１が設定されていることから、ノード位置がノード［１］側となり、それと対を成すノード［０］側に位置するノード２１０ｂが次の分割ノードとなり、それの格納されている配列要素の配列番号である２２０ａが分割ノードの配列番号として設定される。
【０３２１】
なお、図２２Ａ（ａ）の（３）に示すように、探索経路スタック３１０に格納された終端ノードは、図１６Ａに示すステップＳ１６０６において、終端ノード［０］から終端ノード［１］に変更されている。
【０３２２】
また、図２２Ｂ及び図２２Ｃの例示では、さらに次の分割ノードを求める段階では処理元の探索経路スタック３１０のスタックポインタは図２２Ｂ（ａ）の（３）に示すように、終端ノード［１］を指しているから、ステップＳ１９０３からステップＳ１９０４に進み、ステップＳ１９０４の判定により分割ノードなしを返す。すなわち、分割ノードの親ノードがルートノードになると次の分割ノードは存在しない。これは、カップルドノードツリーの順序性から見て当然である。
【０３２３】
図２０は、図１６Ｂに示すステップＳ１６１１で求めた分割ノードをルートノードとする分割ノードツリーの最大値を求め次の分割キーとするステップＳ１６１３の処理フローを説明する図である。
【０３２４】
始めにステップＳ２００１において、処理元の探索経路スタックのスタックポインタの値を退避する。その理由は、図１９に示すステップＳ１９０１の処理によって分割ノードの２つ上位のノードを指している処理元のスタックポインタの値が、後述のステップＳ２００３の最大値検索によって変動し、後述の図２１に示すステップＳ２１０４で用いることができなくなるからである。
【０３２５】
次にステップＳ２００２において、図１９に示すステップＳ１９０５で設定された分割ノードの配列番号を検索開始ノードの配列番号として設定する。
そしてステップＳ２００３において、図９Ｂに示す最大値検索を実行し、インデックスキーの最大値を求める。
【０３２６】
次にステップＳ２００４に進み、ステップＳ２００３で得た最大値を分割キーとして設定する。
最後にステップＳ２００５において、ステップＳ２００１で退避した値を処理元の探索経路スタックのスタックポインタの値として復元して処理を終了する。
【０３２７】
図２２Ｂ（ａ）の例示では（１）に示すように、分割ノード２１０ｂを検索開始ノードとして最大値検索を行い、最大値としてインデックスキー２５１ｃ“０１１０１０”が求められている。その際、探索経路スタック３１０のスタックポインタは退避復元され、図２２Ｂ（ａ）の（３）に示す探索経路スタックのスタックポインタは、図２２Ｂ（ａ）の（２）に示すノードと同一のノードを指している。
【０３２８】
以上、図１９及び図２０を参照して詳細に説明したところから理解されるように、図１６Ｂに示すステップＳ１６１１で求めた次の分割ノードとステップＳ１６１３で求めた次の分割キーの関係は、先に説明した図１６Ａに示すステップＳ１６０１で設定された分割キーとステップＳ１６０５で求めた分割ノード、あるいは分割ノードツリーの関係と同様である。
【０３２９】
上記ステップＳ１６１３で求めた次の分割キーは、ステップＳ１６１１で求めた次の分割ノードをルートノードとする分割ノードツリーの最大値である。また、ステップＳ１６１１で求めた次の分割ノードはノード［０］であるから、それより上位のノードをルートノードとする部分木は、ステップＳ１６１３で求めた次の分割キーより大きいインデックスキーを格納したリーフノードを含むことも、カップルドノードツリーの順序性により明らかである。
【０３３０】
図２１は、図１６Ｂに示すステップＳ１６０９における分割ノードツリーの削除処理の処理フローを説明する図である。同じ削除処理で類似している点もあるが、図１５に示す削除処理は削除キーの格納されたリーフノードである削除ノードの削除であるのに対して、図２１に示すものは基本的にはブランチノードである分割ノードの削除であり、処理元からは該分割ノードをルートノードとする分割ブランチノードツリーが削除される。
【０３３１】
まずステップＳ２１０１において、図１６Ａに示すステップＳ１６０５もしくは図１６Ｂに示すステップＳ１６１１で求めた分割ノードの配列番号を処理元の削除ノードの配列番号として設定する。
【０３３２】
次にステップＳ２１０２において、ステップＳ２１０１で設定された削除ノードの配列番号が、処理元のルートノードの配列番号と一致するか判定する。削除ノードの配列番号が、処理元のルートノードの配列番号と一致するときは、ステップＳ２１１１に進み、処理元のルートノードの配列番号の指すノード対を削除し、次にステップＳ２１１２で処理元のルートノードの配列番号の登録を抹消し、「処理元の登録なし」を返して処理を終了する。
【０３３３】
ステップＳ２１０２の判定処理の結果、削除ノードの配列番号が処理元のルートノードの配列番号と一致しないときは、ステップＳ２１０４に進み、処理元の探索経路スタックからスタックポインタの指すノードを取り出す。なお、該スタックポインタは、図１７Ｂに示すステップＳ１７０５あるいは図１９に示すステップＳ１９０１の処理により、分割ノードの２つ上位であるノードが格納されている。
【０３３４】
次にステップＳ２１０５において、該取り出したノードが終端ノードか判定する。該取り出したノードが終端ノードでないと判定されると、ステップＳ２１０６に進み、親ノードの配列番号として該取り出したノードの代表番号を設定するとともに、親ノードの代表ノード番号を退避してステップＳ２１０８に進む。
【０３３５】
ステップＳ２１０５で、ステップＳ２１０４で取り出したノードが終端ノードであると判定されると、ステップＳ２１０７に進み、親ノードの配列番号としてルートノードの配列番号を設定するとともに、親ノードの代表ノード番号を退避してステップＳ２１０８に進む。
【０３３６】
ステップＳ２１０８では、ステップＳ２１０１で配列番号の設定された削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号として設定する。
次にステップＳ２１０９において、ステップＳ２１０８で設定した対ノードの配列番号の指す配列要素の内容を読み出し、ステップＳ２１０６あるいはステップＳ２１０７で設定した親ノードの配列番号の指す配列要素に格納する。
【０３３７】
最後にステップＳ２１１０において、ステップＳ２１０６あるいはステップＳ２１０７で退避した親ノードの代表ノード番号の指すノード対を削除し、「処理元の登録あり」を返して処理を終了する。
【０３３８】
図２２Ａの（１）の例示では、分割ノード２１０ｆの配列番号２２１ｂが、図示しない削除ノード設定エリアに削除ノード２１０ｆの配列番号として設定され、また図２２Ａの（３）に示すように、探索経路スタックからノード２１０ａを取り出す。この際、図に示すように、スタックポインタの更新は行わない。そして、図２１に示すステップＳ２１０６において、親ノードの配列番号に代表ノード番号２２０ａ＋１を設定するとともに、親ノード２１１ｂの代表ノード番号２２１ｂを退避する。
【０３３９】
次に対ノードの配列番号に削除ノード２１０ｆと対をなすノード２１１ｆの配列番号２２１ｂ＋１を設定し、処理元の親ノードの配列番号２２０ａ＋１が指す配列要素に、対ノード２１１ｆの配列番号２２１ｂ＋１の指す配列要素の内容、すなわちノード２１１ｆの内容を格納する。その結果が、図２２Ｂの（１）のノード２１１ｂに示されている。
【０３４０】
同様に、図２２Ｂの（１）の例示では、分割ノード２１０ｂの配列番号２２０ａが、図示しない削除ノード設定エリアに削除ノード２１０ｂの配列番号として設定され、また図２２Ｂの（３）に示すように、探索経路スタックから終端ノード［１］を取り出す。
【０３４１】
したがって、図２１に示すステップＳ２１０５の判定結果は「はい」になり、親ノードの配列番号にルートノード２１０ａの配列番号２２０を設定するとともに、親ノード２１０ａの代表ノード番号２２０ａを退避する。
【０３４２】
次に対ノードの配列番号に削除ノード２１０ｂと対をなすノード２１１ｂの配列番号２２０ａ＋１を設定し、処理元の親ノードの配列番号２２０が指す配列要素に、対ノード２１１ｂの配列番号２２０ａ＋１の指す配列要素の内容、すなわちノード２１１ｂの内容を格納する。その結果が、図２２ｃの（１）のノード２１０ａに示されている。
【０３４３】
以上により、第３の実施例によるカップルドノードツリーの分割処理について詳細に説明したが、第３の実施例によれば、分割ノードツリー単位で分割処理が行われる。すなわち、分割ノードを処理元から分離し、分割ノードの対ノードを親ノードに複写することにより分割ノードツリーが処理元から削除され、分割ノードを処理先に挿入することにより分割ノードツリーの挿入が完成する。
【０３４４】
したがって、同じ配列を用いている限りは、分割ノード以外のノードについての処理は不要であり、実施例２の場合よりも処理の実行ステップ数がさらに少なくてすむ。
次に分割処理と同様に部分木単位で処理を行う第３の実施例によるカップルドノードツリーの結合処理を説明する。本実施例の結合処理は、第１の実施例及び第２の実施例の結合処理と大きく異なり、第１の実施例及び第２の実施例の結合処理がインデックスキー単位、言い換えればノード単位で結合処理を行うものであるのに対して、所定の条件を満たす部分木単位で処理元から分割して処理先に結合するものである。第１の実施例及び第２の実施例の結合処理では分割キーを選択することにより分割処理をそのまま適用できたのに対して、本実施例のように部分木単位で結合処理を行おうとすると、単純に分割処理を適用することができない。
【０３４５】
それは、処理元及び処理先はそれぞれの内部に格納されたインデックスキーの差分ビット位置に応じた構造を有しており、処理元自体を分割ノードツリーとしてそのまま処理先に挿入することができるとは限らないからである。
【０３４６】
図２３Ａ及び図２３Ｂは、第３の実施例におけるカップルドノードツリーの結合処理フローを説明する図である。以下の説明では、処理先のインデックスキーは処理元のインデックスキーより大きいとするが、その逆でも同様に処理が可能であることは、下記の説明から容易に理解されるものである。
【０３４７】
図２６Ａ〜図２６Ｃは、上記結合処理を実例により説明する図であり、図２Ｂに例示したカップルドノードツリーの部分木と類似したツリーが例示されている。
図２６Ａは結合処理開始前の処理元と処理先のツリーの構造例を示す図である。図２６Ａの（ａ）には処理元が例示され、その配列番号の符号２２０ａ＋１が付された分割結合ノードとそれをルートノードとする部分木であり、結合処理の単位となる部分木である分割結合ノードツリー２９３が示されている。以後、ノードを示す符号を、探索経路スタックにスタックされている直近上位のノードの代表ノード番号で表すことがある。
【０３４８】
図２６Ａの（ｂ）には処理先が例示され、結合位置となるノードがその配列番号の符号２２１ｆを付して示されている。また、図２６Ａには、処理元の最大値がインデックスキー２５１ｇの“１０１００１”であること、処理先の最小値がインデックスキー２５０ｈの“１０１０１１”であることも示されている。
【０３４９】
図２６Ｂは、図２６Ａに示す分割結合ノードツリー２９３を処理先に挿入し、処理元から削除したツリー構造を示す図である。図２６Ｂの（ａ）には処理元の次の分割結合ノードツリー２９４が点線で囲われて示され、最大値がインデックスキー２５１ｄの“０１１０１０”であることが示されている。図２６Ｂの（ｂ）には、処理先の結合された分割結合ノードツリー２９３、結合処理により追加されたノード対２０１ｋとノード２２１ｆのリンク関係がそれぞれ点線で囲われて示され、次の結合位置がノード２２０’であることが示されている。
【０３５０】
図２６Ｃは、図２６Ｂに示す分割結合ノードツリー２９４を処理先に挿入し、処理元から削除したツリー構造を示す図である。図２６Ｂの（ａ）に示す処理元の次ぎの分割結合ノード２２０がルートノードであるため、処理元のルートノードは削除され、図２６Ｃの（ａ）には何も表示されていない。図２６Ｃの（ｂ）には、処理先の結合された分割結合ノードツリー２９４、結合処理により追加されたノード対２０１ｍとノード２２０’のリンク関係がそれぞれ点線で囲われて示されている。
【０３５１】
以下、図２３Ａ及び図２３Ｂ及び図２６Ａ〜図２６Ｃを参照して本実施例の結合処理の概要を説明する。
図２３Ａは、本実施例の結合処理における初期処理の処理フローを説明する図である。図に示すように、ステップＳ２３０１において、処理元の探索経路スタックに終端ノードを格納する。次に、ステップＳ２３０２において、処理先の探索経路スタックに終端ノードを格納する。
【０３５２】
次にステップＳ２３０３に進み、処理元のルートノードを処理元の検索開始ノードに設定する。そして、次のステップＳ２３０４で、処理先のルートノードを処理先の検索開始ノードに設定して初期処理を終了し、図２３Ｂに示すステップＳ２３０７に進む。
【０３５３】
図２３Ｂは、処理元をすべて処理先に結合するまでのループ処理を説明する図である。
図２３Ｂに示すように、ステップＳ２３０７において、処理元の検索開始ノードから図９Ｂに示す検索処理により、処理元のインデックスキーの最大値を求め、次にステップＳ２３０９において、処理先の検索開始ノードから図８Ｂに示す検索処理により、処理先のインデックスキーの最小値を求める。
【０３５４】
次にステップＳ２３１０において、ステップＳ２３０７で求めた最大値とステップＳ２３０９で求めた最小値のビット列比較を行い、上位０ビット目から見た最初の不一致ビットの位置を求め、差分ビット位置に設定する。
【０３５５】
先に述べたように、図２６Ａの例示では、処理元の最大値は“１０１００１”であり、処理先の最小値は“１０１０１１”であるから、差分ビット位置“４”が求められる。また、図２６Ｂの例示では、（ａ）に示す処理元の最大値は“０１１０１０”であり（ｂ）に示す処理先の最小値は“１０１０００”であるから、差分ビット位置は“０”である。なお、処理元にも処理先にも、弁別ビット位置がこの差分ビット位置と等しいブランチノードは存在しない。
【０３５６】
なぜならば、処理元の最大値より処理先の最小値が大きいことから処理元の最大値の差分ビット位置のビット値は０であり、もし、処理元のブランチノードに弁別ビット位置が差分ビット位置と等しいものがあるとすると処理元の最大値がノード［０］となり、最大値であることと矛盾するからである。処理先についても同様である。
【０３５７】
なお、以下の説明では、このステップＳ２３１０で求めた差分ビット位置を単に差分ビット位置ということがある。
次にステップＳ２３１１で、ステップＳ２３１０で求めた差分ビット位置により、処理元の分割結合ノードを求める。図２６Ａの例示では、図２６Ａの（ａ）処理元に示すように、分割結合ノード２２０ａ＋１が求められている。また、図２６Ｂの例示では、図２６Ｂの（ａ）処理元に示すように、次の分割結合ノード２２０が求められている。この処理の詳細は、後に図２４を参照して説明する。
【０３５８】
次にステップＳ２３１２に進み、差分ビット位置により、ステップＳ２３１１で求めた分割結合ノードを挿入するための処理先の結合位置を求める。図２６Ａの例示では、図２６Ａの（ｂ）処理先に示すように、結合位置２２１ｆが求められている。また、図２６Ｂの例示では、図２６Ｂの（ｂ）処理先に示すように、結合位置２２０’が求められている。この処理の詳細は、後に図２５を参照して説明する。
【０３５９】
次にステップＳ２３１３において、ステップＳ２３１２で求めた結合位置にステップＳ２３１１で求めた分割結合ノードを挿入する。この処理は、図１８Ｂを参照して説明をした挿入処理において、ステップＳ１８０１の挿入ノードの配列番号としてステップＳ２３１１で求めた分割結合ノードの配列番号を設定し、ステップＳ１８０２の処理先の挿入位置にステップＳＳ２３１２で求めた結合位置の配列番号を設定して該挿入処理を実行することにより実現される。
【０３６０】
図２６Ａ及び図２６Ｂの例示では、図１８ＢのステップＳ１８１１において分割結合ノード２２０ａ＋１の配列番号２２０ａ＋１が挿入ノード設定エリアに設定され、ステップＳ１８１２において挿入位置設定エリアに結合位置２２１ｆの配列番号２２１ｆが設定される。次にステップＳ１８１３において、空きのノード対２０１ｋが取得され、その配列番号２２０ｋがステップＳ１８１４においてノード［０］の配列番号として設定される。
【０３６１】
そして、ステップＳ１８１５において、挿入ノード設定エリアに設定された配列番号２２０ａ＋１が指す配列要素の内容、すなわち分割結合ノード２１１ｂの内容を読み出して、ノード［０］の配列番号として設定されている配列番号２２０ｋの指す配列要素、すなわちノード２１０ｋに格納する。
【０３６２】
さらにステップＳ１８１６において、配列番号２２０ｋに１を加えた値である２２０ｋ＋１をノード［１］の配列番号として設定する。そしてステップＳ１８１７で挿入位置として設定されている配列番号２２１ｆの指す配列要素、すなわちノード２１０ｈの内容を読み出し、ノード［１］の配列番号として設定された配列番号２２０ｋ＋１の指す配列要素、すなわちノード２１１ｋに格納する。
【０３６３】
最後にステップＳ１８１８において、挿入位置として設定されている配列番号２２１ｆの指す配列要素、すなわちノード２１０ｈの位置に、ノード種別に０、弁別ビット位置に図２３ＢのステップＳ２３１０で求めた差分ビット位置４、代表ノード番号にノード［０］の配列番号として設定されている配列番号２２０ｋを設定して新たなブランチノードを生成し、図２６Ｂの（ｂ）に示す結合後の処理先の構造が得られている。
【０３６４】
また、図２６Ｂ及び図２６Ｃの例示では、図２６Ｂの（ａ）に示す処理元の最大値“０１１０１０”と（ｂ）に示す処理先の最小値“１０１０００”の差分ビット位置が“０”であることから、次の分割結合ノードとしてノード２２０が設定される。図１８ＢのステップＳ１８１１において次の分割結合ノード２２０の配列番号２２０が挿入ノード設定エリアに設定され、ステップＳ１８１２において挿入位置設定エリアに結合位置２２０’の配列番号２２０’が設定される。次にステップＳ１８１３において、図２６Ｃの（ｂ）に示すように、空きのノード対２０１ｍが取得され、その配列番号２２０ｍがステップＳ１８１４においてノード［０］の配列番号として設定される。
【０３６５】
そして、ステップＳ１８１５において、挿入ノード設定エリアに設定された配列番号２２０が指す配列要素の内容、すなわち次の分割結合ノード２１０ａの内容を読み出して、ノード［０］の配列番号として設定されている配列番号２２０ｍの指す配列要素、すなわちノード２１０ｍに格納する。
【０３６６】
さらにステップＳ１８１６において、配列番号２２０ｍに１を加えた値である２２０ｍ＋１をノード［１］の配列番号として設定する。そしてステップＳ１８１７で挿入位置として設定されている配列番号２２０’の指す配列要素、すなわちノード２１０ｆの内容を読み出し、ノード［１］の配列番号として設定された配列番号２２０ｍ＋１の指す配列要素、すなわちノード２１１ｍに格納する。
【０３６７】
最後にステップＳ１８１８において、挿入位置として設定されている配列番号２２０’の指す配列要素、すなわちノード２１０ｆの位置に、ノード種別に０、弁別ビット位置に図２３ＢのステップＳ２３１０で求めた差分ビット位置“０”、代表ノード番号にノード［０］の配列番号として設定されている配列番号２２０ｍを設定して新たなブランチノードを生成し、図２６Ｂの（ｃ）に示す結合後の処理先の構造が得られている。
【０３６８】
次に図２３Ｂによるツリー結合処理の説明に戻ると、ステップＳ２３１４において、分割ノードに、ステップＳ２３１１で求めた分割結合ノードを設定し、ステップＳ２３１５に進んで処理元より削除ノードを削除し、該ノードの親ノードを得る。ステップＳ２３１５の処理は、図２１を参照して説明した削除処理を実行することにより実現される。この削除処理は、ステップＳ２３１４において分割ノードとしてステップＳ２３１１で求めた分割結合ノードを設定してから実行されるので、分割ノードを分割結合ノードと読み替えて実行したものに相当する。
【０３６９】
次にステップＳ２３１６に進み、処理元が登録されているか判定する。登録されていればステップＳ２３１７に進み、登録されていなければ結合処理は完了したので処理を終了する。
【０３７０】
ステップＳ２３１７では、ステップＳ２３１５で得た削除ノードの親ノードを処理元の検索開始ノードに設定してステップＳ２３０７に戻る。
図２６Ａ及び図２６Ｂの例示では、処理元の分割結合ノード２２０ａ＋１を求める処理が終了すると処理元の探索経路スタックのスタックポインタは終端ノードを指しているので、図２３Ｂに示すステップＳ２３１５で呼び出される図２１に示す削除処理のステップＳ２１０５の判定処理は「はい」となり、ステップＳ２１０７に進む。ステップＳ２１０７で親ノードの配列番号にルートノード２１０ａの配列番号２２０が設定され、代表ノード番号２２０ａが退避される。削除ノードには分割結合ノード２２０ａ＋１、対ノードにはノード２１０ｂが設定される。そして、配列番号２２０の配列要素にノード２１０ｂの内容が格納され、代表ノード番号２２０ａが指すノード対２０１ｂが削除されて図２６Ｂの（ａ）に示す処理先となる。
【０３７１】
図２６Ｂ及び図２６Ｃの例示では、処理元の分割結合ノード２２０を求める処理が終了すると、図２３Ｂに示すステップＳ２３１５で呼び出される図２１に示す削除処理のステップＳ２１０２の削除ノードはルートノードかの判定処理は「はい」となり、ステップＳ２１１１に進む。ステップＳ２１１１でルートノードの配列番号２２０が指すノード対２０１ａが削除され、ルートノードの配列番号の登録が抹消されて、図２６Ｃの（ａ）に示すように、処理先は消滅する。
【０３７２】
次に、本実施例の結合処理における処理元の分割結合ノードを求める処理を説明する。分割結合ノードは、処理元がルートノードだけであるという例外を除けば、最大値検索でたどったブランチノードのうち、弁別ビット位置が図２３Ｂに示すステップＳ２３１０で求めた差分ビット位置より下位であるもののうち最上位であるブランチノードである。
【０３７３】
分割結合ノードをルートノードとする処理元の部分木を分割結合ノードツリーということにすると、本実施例の結合処理は、分割結合ノードツリー単位で結合処理を行うものである。
【０３７４】
図２４は、図２３Ｂに示すステップＳ２３１１の処理元の分割結合ノードを求める処理フローを説明する図である。なお、分割結合ノードを求める処理の開始時には、処理元の探索経路スタックのスタックポインタは図２３Ｂに示すステップＳ２３０７における最大値検索の結果、インデックスキーの最大値を格納したリーフノードの直近上位のノードを指している。
【０３７５】
図２４に示すように、ステップＳ２４０１において、処理元の探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタを１つ戻し、ステップＳ２４０２に進む。
【０３７６】
ステップＳ２４０２では、ステップＳ２４０１で取り出したノードから弁別ビット位置を取得する。
次にステップＳ２４０３において、ステップＳ２４０２で取得した弁別ビット位置が差分ビット位置の値より小さいか（上位の位置関係か）を判定する。小さくなければステップＳ２４０１に戻り、小さければステップＳ２４０４に進む。先に述べたように、上述の弁別ビット位置と差分ビット位置が等しいことはない。
【０３７７】
ステップＳ２４０４においては、ステップＳ２４０１で取り出したノードが終端ノードであるか判定する。終端ノードでなければステップＳ２４０５に進み、処理元の分割結合ノードの配列番号として、ステップＳ２４０１で取り出したノードの代表ノード番号を設定して処理を終了する。
【０３７８】
ステップＳ２４０４の判定結果が終端ノードであれば、ステップＳ２４０６に進み、処理元の分割結合ノードの配列番号として、ルートノードの配列番号を設定して処理を終了する。
【０３７９】
上記処理を図２６Ａ及び図２６Ｂを参照して説明すると以下のとおりである。
図２６Ａの（ａ）処理元の例示においては、最大値検索の結果、図示しない探索経路スタックのスタックポインタがノード２１１ｂを指しているので弁別ビット位置“５”が取り出され、差分ビット位置が“４”であることからステップＳ２４０３の判定は「いいえ」となり、ステップＳ２４０１からの処理を繰り返して、ルートノード２１０ａまで至り、ルートノード２１０ａの弁別ビット位置が“０”であって差分ビット位置より上位であるからステップＳ２４０３の判定処理でステップＳ２４０４に分岐し、ステップＳ２４０５の処理により分割結合ノード２２０ａ＋１が求められる。（探索経路スタック上のルートノード２１０ａの代表ノード番号は、最大値検索を実行したのであるから２２０ａ＋１に更新されている。）
図２６Ｂの例示においては、削除ノード２１１ｂの親ノードであるルートノード２１０ａからの処理元の最大値検索により、最大値“０１１０１０”が求められ、処理先の最小値は図２６Ｂの（ｂ）に示すように“１０１０００”であるから、差分ビット位置“０”が設定される。処理元の探索経路スタックのスタックポインタはノード２１１ｃを指しているので弁別ビット位置“２”が取り出され、差分ビット位置が“０”であることからステップＳ２４０３の判定は「いいえ」となり、ステップＳ２４０１からの処理を繰り返して、ルートノード２１０ａまで至り、ルートノード２１０ａの弁別ビット位置が“０”であって差分ビット位置より小さくないから、さらにステップＳ２４０１からの処理を繰り返して、終端ノードまで至り、終端ノードの弁別ビット位置が“−１”であるからステップＳ２４０３の判定処理でステップＳ２４０４に分岐し、ステップＳ２４０４の判定処理でステップＳ２４０６に分岐し、ステップＳ２４０６の処理により次の分割結合ノード２２０が求められる。
【０３８０】
次に、処理先の結合位置を求める処理を説明する。結合処理後の処理先には処理元のインデックスキーの最大値を格納したリーフノードが挿入されることから、差分ビット位置と等しい値の弁別ビット位置を持つブランチノードが新しく存在する。すなわち、差分ビット位置と等しい値の弁別ビット位置を持つブランチノードを最小値検索でたどった経路中に挿入することになるが、この挿入位置を処理先の結合位置とする。
【０３８１】
カップルドノードツリーにおいては、下位のブランチノードの弁別ビット位置は上位のブランチノードの弁別ビット位置より下位であることから、差分ビット位置より直近上位の弁別ビット位置を持つブランチノードの子ノードの位置かあるいは例外的に上位の弁別ビット位置を持つブランチノードがなければルートノードが結合位置となる。
【０３８２】
結合位置に挿入されたブランチノードの子ノード対のノード［１］側には結合前の処理先のインデックスキーの最小値を格納したリーフノードが存在し、ノード［０］は分割結合ノードである。
【０３８３】
図２５は、上記処理先の結合位置を求める処理フローを説明する図である。図２５に示すように、処理先の結合位置を求める処理フローは、図２４に示す処理元の分割結合ノードを求める処理フローと同じ構造である。図２５の処理フローは処理先についてのものであり、求めるものは結合位置であることで異なるだけである。なお、処理先の結合位置を求める処理の開始時には、処理先の探索経路スタックのスタックポインタは図２３Ｂに示すステップＳ２３０９における最小値検索の結果、インデックスキーの最小値を格納したリーフノードの直近上位のノードを指している。
【０３８４】
図２５に示すように、ステップＳ２５０１において、処理先の探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタを１つ戻し、ステップＳ２５０２に進む。
【０３８５】
ステップＳ２５０２では、ステップＳ２５０１で取り出したノードから弁別ビット位置を取得する。
次にステップＳ２５０３において、ステップＳ２５０２で取得した弁別ビット位置が差分ビット位置の値より小さいか（上位の位置関係か）を判定する。小さくなければステップＳ２５０１に戻り、小さければステップＳ２５０４に進む。先に述べたように、上述の弁別ビット位置と差分ビット位置が等しいことはない。
【０３８６】
ステップＳ２５０４においては、ステップＳ２５０１で取り出したノードが終端ノードであるか判定する。終端ノードでなければステップＳ２５０５に進み、処理先の結合位置の配列番号として、ステップＳ２５０１で取り出したノードの代表ノード番号を設定して処理を終了する。
【０３８７】
ステップＳ２５０４の判定結果が終端ノードであれば、ステップＳ２５０６に進み、処理先の結合位置の配列番号として、ルートノードの配列番号を設定して処理を終了する。
上記処理を図２６Ａ及び図２６Ｂを参照して説明すると以下のとおりである。
【０３８８】
図２６Ａの（ｂ）処理先の例示においては、最小値検索の結果、図示しない探索経路スタックのスタックポインタがノード２１０ｆを指しているので弁別ビット位置“３”が取り出され、差分ビット位置が“４”であることから、ステップＳ２５０３の判定は「はい」になり、ステップＳ２５０４からステップＳ２５０５に分岐し、ステップＳ２５０５の処理によりノード２１０ｆの代表ノード番号２２１ｆが結合位置の配列番号として設定される。
【０３８９】
図２６Ｂの例示においては、処理元の最大値“０１１０１０”と処理先の最小値“１０１０００”の差分ビット位置が“０”であることから探索経路スタックを遡ると、終端ノードまで至り、ステップＳ２５０４において、終端ノードであると判定されてステップＳ２５０６に分岐し、ルートノード２１０ｆの配列番号２２０’が次の結合位置の配列番号として求められる。
【０３９０】
以上により、第３の実施例によるカップルドノードツリーの結合処理について詳細に説明しが、第３の実施例によれば、分割結合ノードツリー単位で結合処理が行われる。すなわち、分割結合ノードを処理元から分離し、分割結合ノードの対ノードを親ノードに複写することにより分割結合ノードツリーが処理元から削除され、分割結合ノードを処理先に結合することにより分割結合ノードツリーの結合が完成する。
【０３９１】
したがって、同じ配列を用いている限りは、分割結合ノード以外のノードについての処理は不要であり、実施例２の場合よりも処理の実行ステップ数がさらに少なくてすむ。
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
【０３９２】
次に、図２７Ａ及び図２７Ｂを参照してカップルドノードツリーに格納されたインデックスキーを昇順に取り出す処理について説明する。
図２７Ａは、カップルドノードツリーの任意の部分木に格納されたインデックスキーを昇順に取り出す処理を説明するフロー図である。インデックスキーを昇順に取り出す処理は、ノード対をなすノードのうちノード［０］側及びツリーの深さを優先させてノードから順次リーフノードをたどり、各リーフノードからインデックスキーを取り出していくことに相当する。
【０３９３】
図２７Ａに示すように、ステップＳ２７０１で検索開始ノードを設定し、ステップＳ２７０２で探索経路スタックに終端ノードを格納してステップＳ２７０３において、図８Ｂに示す最小値検索を実行し、ステップＳ２７０４に進む。
【０３９４】
ステップＳ２７０４では、ステップＳ２７０３あるいは後述のステップＳ２７１１で得た最小値であるインデックスキーを取り出す。
次にステップＳ２７０５で、探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタの値を１つ減らす。最初のステップＳ２７０５での探索経路スタックの状態は、ステップＳ２７０３の最小値検索を実行したときの状態である。
【０３９５】
次にステップＳ２７０８で、ステップＳ２７０５で取り出したノードが終端ノードであるか判定する。該ノードが終端ノードであれば、インデックスキーの取り出しが終了したのであるから処理を終了する。
【０３９６】
ステップＳ２７０８での判定が「終端ノードではない」であれば、ステップＳ２７０９に進み、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ２７０５で取り出したノードの代表ノード番号を設定する。
【０３９７】
さらにステップＳ２７１０で、検索開始ノードのノード位置として、値“１”を設定してステップＳ２７１１に進み、図８Ｂに示す最小値検索を実行し、インデックスキーの最小値を取得し、ステップＳ２７０４の最小値であるインデックスキーを取り出す処理に戻る。
【０３９８】
上記ステップＳ２７０４からステップＳ２７１１までのループ処理をステップＳ２７０８での判定が「はい」に至るまで繰り返すことにより、検索開始ノードをルートノードとする部分木のインデックスキーが昇順にとりだされる。
【０３９９】
図２７Ｂは、図２７Ａのフロー図により説明したインデックスキーを昇順に取り出す処理例を説明する図である。カップルドノードツリーは図２Ｂに例示したものであり、検索開始ノードはルートノード２１０ａである。図２７Ｂの（１）〜（８）において、インデックスキーを昇順に取り出す処理を実行する各段階における探索経路スタック３１０の状態及び取り出されるインデックスキーを示している。
【０４００】
図２７Ｂ（１）は、ルートノード２１０ａを検索開始ノードとして最小値検索処理まで実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。スタックポインタの指す位置は、終端ノードからノード２１０ｂになっている。ここでは、ノード２１０ｂの代表ノード番号２２０ｂの指すノードはリーフノード２１０ｃであるため、このノード２１０ｃのインデックスキー
“０００１１１”が取り出され、スタックポインタの指す位置は１つ減ってノード２１０ａとなる。そして、最小値検索における代表ノード番号に代表ノード番号２２０ｂを、ノード位置に値“１”を設定し、次の最小値検索を実行する。つまり、次の検索開始ノードは、代表ノード番号２２０ｂの指すノード対２０１ｃのノード［１］であるノード２１１ｃとなる。
【０４０１】
図２７Ｂ（２）は、ノード２１１ｃを検索開始ノードとして最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最小値検索の結果、探索経路スタック３１０にはノード２１０ａの上にノード２１１ｃとノード２１０ｄが格納されている。ここでは、ノード２１０ｄの代表ノード番号２２０ｄの指すノード２１０ｅはリーフノードであるため、このノード２１０ｅのインデックスキー
“０１００１０”が取り出され、スタックポインタの指す位置は１つ減ってノード２１１ｃとなる。そして、最小値検索における代表ノード番号に代表ノード番号２２０ｄを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４０２】
図２７Ｂ（３）は、代表ノード番号に代表ノード番号２２０ｄを、ノード位置に値“１”を設定して最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。ここでは、配列から取り出されたノード２１１ｅはリーフノードであるため、このノード２１１ｅのインデックスキー“０１００１１”
が取り出され、スタックポインタの指す位置は１つ減ってノード２１０ａとなる。そして、最小値検索における代表ノード番号に代表ノード番号２２１ｃを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４０３】
図２７Ｂ（４）は、代表ノード番号に代表ノード番号２２１ｃを、ノード位置に値“１”を設定して最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。ここでは、配列から取り出されたノード２１１ｄはリーフノードであるため、このノードのインデックスキー“０１１０１０”
が取り出され、スタックポインタの指す位置は１つ減って終端ノードとなる。そして、最小値検索における代表ノード番号に代表ノード番号２２０ａを、ノード位置に値“１”を設定し、次の最小値検索を実行する。つまり、次の検索開始ノードはノード２１１ｂとなる。
【０４０４】
図２７Ｂ（５）は、ノード２１１ｂを検索開始ノードとして最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最小値検索の結果、探索経路スタック３１０には終端ノードの上にノード２１１ｂとノード２１０ｆが格納されている。ここでは、ノード２１０ｆの代表ノード番号２２０ｆの指すノード２１０ｇはリーフノードであるため、このノード２１０ｇのインデックスキー“１０００１０”
が取り出され、スタックポインタの指す位置は１つ減ってノード２１１ｂとなる。そして、最小値検索における代表ノード番号に代表ノード番号２２０ｆを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４０５】
図２７Ｂ（６）は、代表ノード番号に代表ノード番号２２０ｆを、ノード位置に値“１”を設定して最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。ここでは、配列から取り出されたノード２１１ｇはリーフノードであるため、このノードのインデックスキー“１０００１１”
が取り出され、スタックポインタの指す位置は１つ減って終端ノードとなる。そして、最小値検索における代表ノード番号にノード２１１ｂの代表ノード番号２２１ｂを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４０６】
図２７Ｂ（７）は、代表ノード番号に代表ノード番号２２１ｂを、ノード位置に値“１”を設定して最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最小値検索の結果、ノード２１１ｆが終端ノードの上に格納されている。ここでは、ノード２１１ｆの代表ノード番号２２１ｆの指すノード２１０ｈはリーフノードであるため、このノード２１０ｈのインデックスキー“１０１０１１”
が取り出され、スタックポインタの指す位置は１つ減って終端ノードとなる。そして、最小値検索における代表ノード番号に代表ノード番号２２１ｆを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４０７】
図２７Ｂ（８）は、代表ノード番号に代表ノード番号２２１ｆを、ノード位置に値“１”を設定して最小値検索を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示す。ここでは、配列から取り出されたノード２１１ｈはリーフノードであるため、このノード２１１ｈのインデックスキー“１０１１００”が取り出される。そして、図２７Ａに示すステップＳ２７０８で、前回ステップＳ２７０５で探索経路スタック３１０から取り出されたノードが終端ノードであると判断され、処理を終了する。
【０４０８】
上述の説明から理解されるように、最大値であるインデックスキーが最小値検索で得られるときには、探索経路スタックから最大値であるインデックスキーを格納したリーフノードの直近上位のブランチノードが取り出されており、次に新たにノードが終端ノードの上に格納されることはないから、次の最小値検索に進む前に図２７Ａに示すステップＳ２７０５で終端ノードが取り出され、ステップＳ２７０８で終端ノードであることが判定されて処理が終了する。
【０４０９】
次に、図２８Ａ及び図２８Ｂを参照してカップルドノードツリーに格納されたインデックスキーを降順に取り出す処理について説明する。このインデックスキーの降順取り出し処理は、先に図２７Ａ及び図２７Ｂを参照して説明した昇順取り出し処理といわば双対の関係にあり、最小値検索に変えて最大値検索を行い、ノード位置を反転させたものに相当する。
【０４１０】
図２８Ａは、カップルドノードツリーの任意の部分木に格納されたインデックスキーを降順に取り出す処理を説明するフロー図である。インデックスキーを降順に取り出す処理は、ノード対をなすノードのうちノード［１］側及びツリーの深さを優先させてノードから順次リーフノードをたどり、各リーフノードからインデックスキーを取り出していくことに相当する。
【０４１１】
図２８Ａに示すように、ステップＳ２８０１で検索開始ノードを設定し、ステップＳ２８０２で探索経路スタックに終端ノードを格納してステップＳ２８０３において、図９Ｂに示す最大値検索を実行し、ステップＳ２８０４に進む。
ステップＳ２８０４では、ステップＳ２８０３あるいは後述のステップＳ２８１１で得た最大値であるインデックスキーを取り出す。
【０４１２】
次にステップＳ２８０５で、探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタの値を１つ減らす。最初のステップＳ２８０５での探索経路スタックの状態は、ステップＳ２８０３の最大値検索を実行したときの状態である。
【０４１３】
次にステップＳ２８０８で、ステップＳ２８０５で取り出したノードが終端ノードであるか判定する。該ノードが終端ノードであれば、インデックスキーの取り出しが終了したのであるから処理を終了する。
【０４１４】
ステップＳ２８０８での判定が「終端ノードではない」であれば、ステップＳ２８０９に進み、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ２８０５で取り出したノードの代表ノード番号から１を減じた値を設定する。
【０４１５】
さらにステップＳ２８１０で、検索開始ノードのノード位置として、値“０”を設定してステップＳ２８１１に進み、図９Ｂに示す最大値検索を実行し、インデックスキーの最大値を取得し、ステップＳ２８０４の最大値であるインデックスキーを取り出す処理に戻る。
【０４１６】
上記ステップＳ２８０４からステップＳ２８１１までのループ処理をステップＳ２８０８での判定が「はい」に至るまで繰り返すことにより、検索開始ノードをルートノードとする部分木のインデックスキーが降順にとりだされる。
【０４１７】
図２８Ｂは、図２８Ａのフロー図により説明したインデックスキーを降順に取り出す処理例を説明する図である。カップルドノードツリーは図２Ｂに例示したものであり、検索開始ノードはルートノード２１０ａである。図２８Ｂの（１）〜（８）において、インデックスキーを降順に取り出す処理を実行する各段階における探索経路スタック３１０の状態及び取り出されるインデックスキーを示している。
【０４１８】
図２８Ｂ（１）は、ルートノード２１０ａを検索開始ノードとして最大値検索処理まで実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。スタックポインタの指す位置は、終端ノードからノード２１１ｆになっている。ここでは、ノード２１１ｆの代表ノード番号２２１ｆ＋１の指すノード２１１ｈはリーフノードであるため、このノード２１１ｈのインデックスキー
“１０１１００”が取り出され、スタックポインタの指す位置は１つ減ってノード２１１ｂとなる。そして、最大値検索における代表ノード番号に代表ノード番号２２１ｆ＋１から１を減じた値である２２１ｆを、ノード位置に値“０”を設定し、次の最大値検索を実行する。
【０４１９】
図２８Ｂ（２）は、代表ノード番号に代表ノード番号２２１ｆを、ノード位置に値“０”を設定して最大値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。ここでは、配列から取り出されたノード２１０ｈはリーフノードであるため、このノード２１０ｈのインデックスキー
“１０１０１１”が取り出され、スタックポインタの指す位置は１つ減ってノード２１０ａとなる。そして、最大値検索における代表ノード番号に代表ノード番号２２１ｂを、ノード位置に値“０”を設定し、次の最大値検索を実行する。
【０４２０】
図２８Ｂ（３）は、代表ノード番号に代表ノード番号２２１ｂを、ノード位置に値“０”を設定して最大値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最大値検索の結果、探索経路スタック３１０には、ノード２１０ａの上にノード２１０ｆが格納されている。ここでは、ノード２１０ｆの代表ノード番号２２０ｆ＋１が指すノード２１１ｇはリーフノードであるため、このノード２１１ｇのインデックスキー“１０００１１” が取り出され、スタックポインタの指す位置は１つ減ってノード２１０ａとなる。そして、最大値検索における代表ノード番号に代表ノード番号２２０ｆを、ノード位置に値“０”を設定し、次の最大値検索を実行する。
【０４２１】
図２８Ｂ（４）は、代表ノード番号に代表ノード番号２２０ｆを、ノード位置に値“０”を設定して最大値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。ここでは、配列から取り出されたノード２１０ｇはリーフノードであるため、このノード２１０ｇのインデックスキー“１０００１０”
が取り出され、スタックポインタの指す位置は１つ減って終端ノードとなる。そして、最大値検索における代表ノード番号に代表ノード番号２２０ａを、ノード位置に値“０”を設定し、次の最大値検索を実行する。つまり、次の検索開始ノードはノード２１０ｂとなる。
【０４２２】
図２８Ｂ（５）は、ノード２１０ｂを検索開始ノードとして最大値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最大値検索の結果、探索経路スタック３１０には終端ノードの上にノード２１０ｂとノード２１１ｃが格納されている。ここでは、ノード２１１ｃの代表ノード番号２２１ｃ＋１の指すノード２１１ｄはリーフノードであるため、このノード２１１ｄのインデックスキー“０１１０１０”
が取り出され、スタックポインタの指す位置は１つ減ってノード２１０ｂとなる。そして、最大値検索における代表ノード番号に代表ノード番号２２１ｃを、ノード位置に値“０”を設定し、次の最大値検索を実行する。
【０４２３】
図２８Ｂ（６）は、代表ノード番号に代表ノード番号２２１ｃを、ノード位置に値“０”を設定して最大値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最大値検索の結果、探索経路スタック３１０にはノード２１０ｂの上にノード２１０ｄが格納されている。ここでは、ノード２１０ｄの代表ノード番号２２０ｄ＋１の指すノード２１１ｅはリーフノードであるため、このノード２１１ｅのインデックスキー“０１００１１”
が取り出され、スタックポインタの指す位置は１つ減ってノード２１０ｂとなる。そして、最大値検索における代表ノード番号にノード２１０ｄの代表ノード番号２２０ｄを、ノード位置に値“０”を設定し、次の最大値検索を実行する。
【０４２４】
図２８Ｂ（７）は、代表ノード番号に代表ノード番号２２０ｄを、ノード位置に値“０”を設定して最大値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。ここでは、配列から取り出されたノード２１０ｅはリーフノードであるため、このノード２１０ｅのインデックスキー“０１００１０”
が取り出され、スタックポインタの指す位置は１つ減って終端ノードとなる。そして、最大値検索における代表ノード番号に代表ノード番号２２０ｂを、ノード位置に値“０”を設定し、次の最大値検索を実行する。
【０４２５】
図２８Ｂ（８）は、代表ノード番号に代表ノード番号２２０ｂを、ノード位置に値“０”を設定して最大値検索を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示す。ここでは、配列から取り出されたノード２１０ｃはリーフノードであるため、このノード２１０ｃのインデックスキー“０００１１１”が取り出される。そして、図２８Ａに示すステップＳ２８０８で、前回ステップＳ２８０５で探索経路スタック３１０から取り出されたノードが終端ノードであると判断され、処理を終了する。
【０４２６】
上述の説明から理解されるように、最小値であるインデックスキーが最大値検索で得られるときには、探索経路スタックから最小値であるインデックスキーを格納したリーフノードの直近上位のブランチノードが取り出されており、次に新たにノードが終端ノードの上に格納されることはないから、次の最大値検索に進む前に図２８Ａに示すステップＳ２８０５で終端ノードが取り出され、ステップＳ２８０８で終端ノードであることが判定されて処理が終了する。
【０４２７】
次に、図２９Ａ、図２９Ｂ及び図２９Ｃを参照してカップルドノードツリーに格納されたインデックスキーを、範囲を指定して昇順に取り出す範囲指定昇順取り出し処理について説明する。
【０４２８】
図２９Ａは、範囲指定昇順取り出し処理の初期処理を説明するフロー図である。インデックスキー取り出しの範囲は、予め上限キーと下限キーで指定されているものとする。
図に示すように、ステップＳ２９０１で検索開始ノードとしてルートノードを設定する。次にステップＳ２９０２で、図１０Ａ及び図１０Ｂに示す下限値検索処理により下限キーから下限値を求め、ステップＳ２９０３で、図１１Ａ及び図１１Ｂに示す上限値検索処理により上限キーから上限値を求める。
【０４２９】
次にステップＳ２９０４において、探索経路スタックに終端ノード［０］を格納し、ステップＳ２９０５で検索キーとして上記ステップＳ２９０２で求めた下限値を設定して、ステップＳ２９０６に進む。
【０４３０】
ステップＳ２９０６では、図４Ｂに示す検索処理により、カップルドノードツリーの配置された配列を検索してインデックスキーを求め、初期処理を終了して図２９Ｂに示すステップＳ２９０７に移行する。
【０４３１】
図２９Ｂは、範囲指定昇順取り出し処理のループ処理を説明するフロー図である。
ステップＳ２９０７では、ステップＳ２９０６で得たインデックスキーあるいは後述のステップＳ２９１５で得た最小値であるインデックスキーを取り出す。
【０４３２】
次にステップＳ２９０８で、ステップＳ２９０３で求めた上限値とステップＳ２９０７で取り出したインデックスキーが等しいか判定し、等しければ上限値までのインデックスキーの昇順取り出しは完了したのであるから、処理を終了する。
【０４３３】
等しくなければ次にステップＳ２９０９で、探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタの値を１つ減らす。最初のステップＳ２９０９での探索経路スタックの状態は、ステップＳ２９０６の検索を実行したときの状態である。
【０４３４】
次にステップＳ２９１０で、取り出したノードの代表番号から取り出したノードのノード位置を得る。
次にステップＳ２９１１に進み、ステップＳ２９１０で得たノード位置がノード［１］側であるか判定する。ノード［１］側であればステップＳ２９０９に戻り、ノード［０］側であればステップＳ２９１２に進む。
【０４３５】
ステップＳ２９１２では、ステップＳ２９０９で取り出したノードが終端ノードであるか判定する。該ノードが終端ノードであれば、インデックスキーの取り出しが終了したのであるから処理を終了する。
【０４３６】
ステップＳ２９１２での判定が「終端ノードではない」であれば、ステップＳ２９１３に進み、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ２９０９で取り出したノードの代表ノード番号を設定する。
【０４３７】
さらにステップＳ２９１４で、検索開始ノードのノード位置として、値“１”を設定してステップＳ２９１５に進み、図８Ｂに示す最小値検索を実行し、インデックスキーの最小値を取得し、ステップＳ２９０７の最小値であるインデックスキーを取り出す処理に戻る。
【０４３８】
上記ステップＳ２９０７からステップＳ２９１５までのループ処理をステップＳ２９０８あるいはステップＳ２９１２での判定が「はい」に至るまで繰り返すことにより、上限キーと下限キーで指定された範囲内のインデックスキーが昇順にとりだされる。
【０４３９】
図２９Ｃは、図２９Ａ及び図２９Ｂのフロー図により説明したインデックスキーの範囲を指定して昇順に取り出す処理例を説明する図である。図２９Ｃ（ａ）には図２Ｂに例示したカップルドノードツリーと、検索キー設定エリア２７０及び第２の検索キー設定エリア２７１にそれぞれ設定された下限キー“０１０１００”と上限キー“１０１００１”とが示されている。図２９Ｃ（ｂ）の（１）〜（３）において、インデックスキーを昇順に取り出す処理を実行する各段階における探索経路スタック３１０の状態及び取り出されるインデックスキーが示されている。
【０４４０】
下限キー“０１０１００”によりノード２１１ｄに格納されたインデックスキー“０１１０１０”が下限値として求められ、ノード２１１ｄが範囲指定昇順取り出し処理の探索開始ノードとなる。また、上限キー“１０１００１”によりノード２１１ｇに格納されたインデックスキー“１０００１１”が上限値として求められ、ノード２１１ｇが範囲指定昇順取り出し処理の探索終了ノードとなる。
【０４４１】
次に上記下限値を検索キーとしてルートノード２１０ａから検索を行い、探索開始ノードのインデックスキー“０１０１００”が取り出される。このインデックスキーは探索範囲での最小値である。
【０４４２】
図２９Ｃ（ｂ）の（１）には、この取り出されたインデックスキーと検索実行結果による探索経路スタック３１０のノード格納状態が示されている。今の場合、探索経路スタック３１０には、終端ノード［０］、ノード２１０ａ、ノード２１０ｂ、ノード２１１ｃが格納されており、ノード２１０ｂとノード２１１ｃの代表ノード番号はそれぞれ１加算されている。インデックスキー“０１０１００”は上限値“１０００１１”より小さいので次の最小値検索を含むループ処理が実行される。
【０４４３】
図２９Ｃ（ｂ）の（１）に示す探索経路スタック３１０の右側の実線の矢印が示すスタックポインタの位置のノード２１０ａの代表ノード番号２２０ａが、探索経路スタック３１０をさかのぼったときの最初のノード［０］側であるので、該代表ノード番号２２０ａが最小値検索の検索開始ノードの属するノード対２０１ｂの代表ノード２１０ｂの配列番号として設定され、検索開始ノードのノード位置には値“１”が設定されて、最小値検索が行われる。スタックポインタは点線の矢印が示すように終端ノード［０］を指している。
【０４４４】
図２９Ｃ（ｂ）の（２）は、上記最小値検索を実行した段階の探索経路スタック３１０及び取り出されるインデックスキーが示されている。最小値検索により終端ノード［０］の上にノード２１１ｂとノード２１０ｆが格納されている。そして、ノード２１０ｆの代表ノード番号２２０ｆの指すノード２１０ｇはリーフノードであるのでそのインデックスキー“１０００１０”が取り出される。このインデックスキーも上限値より小さいのでさらにループ処理が続行する。
【０４４５】
図２９Ｃ（ｂ）の（３）は、代表ノード番号に代表ノード番号２２０ｆを、ノード位置に値“１”を設定して最小値検索を実行した段階の探索経路スタック３１０及び取り出されるインデックスキーが示されている。最小値検索の結果、配列から取り出されたノード２１１ｇはリーフノードであるため、このノード２１１ｇのインデックスキー“１０００１１”が取り出される。取り出されたインデックスキー“１０００１１”は上限値と等しいので、処理は終了となる。ノード２１１ｇは図２９Ｃ（ａ）に示すように、探索終了ノードであり、図２９Ｃ（ｂ）の（３）に示すように、そのインデックスキー“１０００１１”は、探索範囲の最大値である。
【０４４６】
次に、図３０Ａ、図３０Ｂ及び図３０Ｃを参照してカップルドノードツリーに格納されたインデックスキーを、範囲を指定して降順に取り出す範囲指定降順取り出し処理について説明する。このインデックスキーの範囲指定降順取り出し処理は、先に図２９Ａ〜図２９Ｃを参照して説明した範囲指定昇順取り出し処理といわば双対の関係にあり、最小値検索に変えて最大値検索を行い、ノード位置及び上限と下限を反転させたものに相当する。
【０４４７】
図３０Ａは、範囲指定降順取り出し処理の初期処理を説明するフロー図である。先に説明した範囲指定昇順取り出し処理の場合と同様にインデックスキー取り出しの範囲は、予め上限キーと下限キーで指定されているものとする。
【０４４８】
図に示すように、ステップＳ３００１で検索開始ノードとしてルートノードを設定する。次にステップＳ３００２で、図１１Ａ及び図１１Ｂに示す上限値検索処理により上限キーから上限値を求め、ステップＳ３００３で、図１０Ａ及び図１０Ｂに示す下限値検索処理により下限キーから下限値を求める。
【０４４９】
次にステップＳ３００４において、探索経路スタックに終端ノード［１］を格納し、ステップＳ３００５で検索キーとして上記ステップＳ３００２で求めた上限値を設定して、ステップＳ３００６に進む。
【０４５０】
ステップＳ３００６では、図４Ｂに示す検索処理により、カップルドノードツリーの配置された配列を検索してインデックスキーを求め、初期処理を終了して図３０Ｂに示すステップＳ３００７に移行する。
【０４５１】
図３０Ｂは、範囲指定降順取り出し処理のループ処理を説明するフロー図である。
ステップＳ３００７では、ステップＳ３００６で得たインデックスキーあるいは後述のステップＳ３０１５で得た最大値であるインデックスキーを取り出す。
【０４５２】
次にステップＳ３００８で、ステップＳ３００３で求めた下限値とステップＳ３００７で取り出したインデックスキーが等しいか判定し、等しければ下限値までのインデックスキーの降順取り出しは完了したのであるから、処理を終了する。
【０４５３】
等しくなければ次にステップＳ３００９で、探索経路スタックからスタックポインタの指すノードを取り出し、スタックポインタの値を１つ減らす。最初のステップＳ３００９での探索経路スタックの状態は、ステップＳ３００６の検索を実行したときの状態である。
【０４５４】
次にステップＳ３０１０で、取り出したノードの代表番号から取り出したノードのノード位置を得る。
次にステップＳ３０１１に進み、ステップＳ３０１０で得たノード位置がノード［０］側であるか判定する。ノード［０］側であればステップＳ３００９に戻り、ノード［１］側であればステップＳ３０１２に進む。
【０４５５】
ステップＳ３０１２では、ステップＳ３００９で取り出したノードが終端ノードであるか判定する。該ノードが終端ノードであれば、インデックスキーの取り出しが終了したのであるから処理を終了する。
【０４５６】
ステップＳ３０１２での判定が「終端ノードではない」であれば、ステップＳ３０１３に進み、検索開始ノードの属するノード対の代表ノードの配列番号として、ステップＳ３００９で取り出したノードの代表ノード番号から値“１”を減じた値を設定する。
【０４５７】
さらにステップＳ３０１４で、検索開始ノードのノード位置として、値“１”を設定してステップＳ３０１５に進み、図９Ｂに示す最大値検索を実行し、インデックスキーの最大値を取得し、ステップＳ３００７の最大値であるインデックスキーを取り出す処理に戻る。
【０４５８】
上記ステップＳ３００７からステップＳ３０１５までのループ処理をステップＳ３００８あるいはステップＳ３０１２での判定が「はい」に至るまで繰り返すことにより、上限キーと下限キーで指定された範囲内のインデックスキーが降順にとりだされる。
【０４５９】
図３０Ｃは、図３０Ａ、図３０Ｂのフロー図により説明したインデックスキーの範囲を指定して降順に取り出す処理例を説明する図である。図３０Ｃ（ａ）には図２Ｂに例示したカップルドノードツリーと、検索キー設定エリア２７０及び第２の検索キー設定エリア２７１にそれぞれ設定された上限キー“１０１００１”と下限キー“０１１００１”が示されている。図３０Ｃ（ｂ）の（１）〜（３）において、インデックスキーを降順に取り出す処理を実行する各段階における探索経路スタック３１０の状態及び取り出されるインデックスキーが示されている。
【０４６０】
上限キー“１０１００１”によりノード２１１ｇに格納されたインデックスキー“１０００１１”が上限値として求められ、ノード２１１ｇが範囲指定降順取り出し処理の探索開始ノードとなる。また、下限キー“０１１００１”によりノード２１１ｄに格納されたインデックスキー“０１１０１０”が下限値として求められ、ノード２１１ｄが範囲指定降順取り出し処理の探索終了ノードとなる。
【０４６１】
次に上記上限値を検索キーとしてルートノード２１０ａから検索を行い、探索開始ノードのインデックスキー“１０００１１”が取り出される。このインデックスキーは探索範囲での最大値である。
【０４６２】
図３０Ｃ（ｂ）の（１）には、この取り出されたインデックスキーと検索実行結果による探索経路スタック３１０のノード格納状態が示されている。今の場合、探索経路スタック３１０には、終端ノード［１］、ノード２１０ａ、ノード２１１ｂ、ノード２１０ｆが格納されており、ノード２１０ａとノード２１０ｆの代表ノード番号はそれぞれ１加算されている。インデックスキー“１０００１１”は下限値“０１１００１”より大きいので次の最大値検索を含むループ処理が実行される。
【０４６３】
図３０Ｃ（ｂ）の（１）に示す探索経路スタック３１０に格納されたノード２１０ｆの代表ノード番号２２０ｆ＋１からノード位置がノード［１］側であると判定されるので、該代表ノード番号２２０ｆ＋１から１を減算した値が最大値検索の検索開始ノードの属するノード対２０１ｇの代表ノード２１０ｇの配列番号として設定され、検索開始ノードのノード位置には値“０”が設定されて、最大値検索が行われる。
【０４６４】
図３０Ｃ（ｂ）の（２）は、上記最大値検索を実行した段階の探索経路スタック３１０及び取り出されるインデックスキーが示されている。そして、ノード２１０ｆの代表ノード番号２２０ｆの指すノード２１０ｇはリーフノードであるのでそのインデックスキー“１０００１０”が取り出される。このインデックスキーも下限値より大きいのでさらにループ処理が続行する。そして、スタックポインタは、探索経路スタック３１０の右側の実線の矢印で示すようにノード２１０ａを指しており、その代表ノード番号２２０ａ＋１から１を減算した値が次の最大値検索の検索開始ノードの属するノード対２０１ｂの代表ノード２１０ｂの配列番号として設定され、検索開始ノードのノード位置には値“０”が設定されて、最大値検索が行われる。
【０４６５】
図３０Ｃ（ｂ）の（３）は、代表ノード番号に代表ノード番号２２０ａを、ノード位置に値“０”を設定して最大値検索を実行した段階の探索経路スタック３１０及び取り出されるインデックスキーが示されている。最大値検索開始時にはスタックポインタは探索経路スタック３１０の左側の点線の矢印で示すように終端ノード［１］を指しており、最大値検索の結果、その上にノード２１０ｂとノード２１１ｃが格納されている。ノード２１１ｃの代表ノード番号２２１ｃ＋１が指しているノード２１１ｄはリーフノードであるため、このノード２１１ｄのインデックスキー“０１１０１０”が取り出される。取り出されたインデックスキー“０１１０１０”は下限値と等しいので、処理は終了となる。ノード２１１ｄは図３０Ｃ（ａ）に示すように、探索終了ノードであり、図３０Ｃ（ｂ）の（３）に示すように、そのインデックスキー“０１１０１０”は、探索範囲の最小値である。
【０４６６】
次に、カップルドノードツリーに収容されたインデックスキーの前方一致検索処理について説明する。本実施形態の前方一致検索においては、上位に有意ビットを有する前方一致キーは予め指定されているものとする。
【０４６７】
図３１Ａは、本実施形態の前方一致検索の処理フローを説明する図である。
図に示すように、ステップＳ３１０１で検索開始ノードにルートノードを設定し、ステップＳ３１０２で下限キーとして前方一致キーの無意ビットの値を“０”としたビット列のキーを設定し、ステップＳ３１０３において、ステップＳ３１０１及びステップＳ３１０２での設定に基づいて、図１０Ａ及び図１０Ｂに示す下限値検索を実行し、インデックスキーの下限値を得る。
【０４６８】
次にステップＳ３１０３ａに進み、前方一致キーの有意ビットの範囲で、前方一致キーとステップＳ３１０３で得た下限値を比較し、ステップＳ３１０３ｂで有意ビットの範囲で一致するか判定する。一致すればステップＳ３１０４に進み、一致しなければ指定された前方一致キーで取り出すインデックスキーはないことから、検索失敗として処理を終了する。上記ステップＳ３１０３ｂでの判定により、ステップＳ３１０４以下の処理では、少なくとも下限値が前方一致検索でヒットすることが保証されている。
【０４６９】
ステップＳ３１０４においては、図示しない差分ビット位置設定エリアに、前方一致キーの上位０ビット目から見た有意ビットの末尾のビット位置を設定する。
次にステップＳ３１０５に進み、探索経路スタックからノードを取り出し、探索経路スタックのスタックポインタを１つ戻す。
【０４７０】
次にステップＳ３１０６で、ステップＳ３１０５で取り出したノードの弁別ビット位置を取り出し、ステップＳ３１０７に進む。
ステップＳ３１０７では、ステップＳ３１０６で取り出した弁別ビット位置がステップＳ３１０４で設定した差分ビット位置の値より大きいか判定する。弁別ビット位置が差分ビット位置より大きければステップＳ３１０５に戻り、大きくなければステップＳ３１０８に進む。
【０４７１】
ステップＳ３１０８において、ステップＳ３１０５で取り出したノードが終端ノードか判定する。終端ノードでなければステップＳ３１０９に進み、終端ノードであればステップＳ３１１０に進む。
【０４７２】
ステップＳ３１０９においては、検索開始ノードにステップＳ３１０５で取り出したノードの代表ノード番号が指すノードを設定してステップＳ３１１１に進み、ステップＳ３１１０においては、検索開始ノードにルートノードを設定してステップＳ３１１１に進む。
【０４７３】
以上説明したステップＳ３１０５〜ステップＳ３１１０の処理は、前方一致検索でヒットするインデックスキーを格納したリーフノードを全て含み、ヒットしないインデックスキーを格納したリーフノードを含まない部分木のルートノードを、ステップＳ３１１１での検索における検索開始ノードとする処理である。
【０４７４】
前記下限値は、上記部分木の最小値であり、該部分木のルートノードはステップＳ３１０３での下限値を求める処理により、探索経路スタックに格納されていることは明らかである。
【０４７５】
そして探索経路スタックに格納されているブランチノードを読み出して弁別ビット位置を取り出し、ステップＳ３１０４で設定された差分ビット位置と比較したとき、弁別ビット位置が差分ビット位置より大きいと、その下位のリーフノードに格納されたインデックスキーは全て前方一致検索でヒットするものであるが、上位のブランチノードの下位に前方一致検索でヒットするインデックスキーを格納したリーフノードが存在する可能性がある。
【０４７６】
そこでさらにブランチノードを読み出して弁別ビット位置を取り出し、差分ビット位置と比較したとき、弁別ビット位置が差分ビット位置と等しくなれば、そのブランチノードの代表ノード番号は前記下限値を含むリーフノードが存在する側のノード位置のノードを指しており、該ノードをルートノードとする部分木は、前方一致検索でヒットするインデックスキーを格納したリーフノードを全て含み、ヒットしないインデックスキーを格納したリーフノードを含まないことが容易に理解される。
【０４７７】
差分ビット位置と等しい値の弁別ビット位置を持つブランチノードがなく、弁別ビット位置が差分ビット位置より小さいブランチノードが取り出されると、その代表ノード番号は、前記下限値を含むリーフノードが存在する側のノード位置のノードを指しており、該ノードの弁別ビット位置は差分ビット位置より大きいので、先に述べたようにその下位のリーフノードに格納されたインデックスキーは全て前方一致検索でヒットするものである。
【０４７８】
一方、前記取り出された弁別ビット位置が差分ビット位置より小さいブランチノードの代表ノード番号の指すノードと対をなすノード側に存在するリーフノードに格納されたインデックスキーには弁別ビット位置の定義から、前方一致検索でヒットするものはない。
【０４７９】
以上のことから、弁別ビット位置がステップＳ３１０４で設定された差分ビット位置以下となるブランチノードの直近下位のノード、すなわちその代表ノード番号の指すノードが前方一致検索でヒットするインデックスキーを格納したリーフノードを全て含み、ヒットしないインデックスキーを格納したリーフノードを含まない部分木のルートノードとなることが分かる。
【０４８０】
ステップＳ３１１１においては、図２７Ａに示すインデックスキーを昇順に取り出す処理により、検索開始ノードから配列を探索して昇順にインデックスキーを取り出す。
以上の処理により、カップルドノードツリーに格納されたインデックスキーのうち前方一致キーの有意ビットの範囲でビット値が等しいインデックスキーは全て取り出される。
【０４８１】
図３１Ｂは、図３１Ａのフロー図により説明した前方一致検索の検索例を説明する図である。図３１Ｂ（ａ）には、図２Ｂに例示するカップルドノードツリーのうち、本検索例に関係するルートノード２１０ａとノード２１１ｂ以下の階層の部分木と、検索キー設定エリア２７０、第２の検索キー設定エリア２７１が示されている。検索キー設定エリア２７０には前方一致キー“１０ｘｘｘｘ”が設定されており、第２の検索キー設定エリア２７１には、前方一致キーの無意ビット“ｘ”を“０”として得た下限キー“１０００００”が設定されている。
【０４８２】
なお、前方一致キーの有意ビット、無意ビットの識別には、明示的に有意ビットのビット数を指定することのほか、インデックスキーの各ビットの前に有意ビットであるか無意ビットであるかの識別ビットを付加することにより行うこともできる。
【０４８３】
図３１Ｂ（ｂ）には、下限値検索以後のインデックスキーの昇順取りだしによる探索経路スタック３１０の状態遷移（１）〜（５）と取り出されたインデックスキーが示されている。
【０４８４】
図３１Ｂ（ｂ）の（１）は、図３１Ａに示すステップＳ３１０３での下限値検索を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。スタックポインタの指す位置は、終端ノードからノード２１０ｆになっている。ここでは、ノード２１０ｆの代表ノード番号２２０ｆの指すノードはリーフノード２１０ｇであるため、このノード２１０ｇのインデックスキー
“１０００１０”が下限値として取り出されている。
【０４８５】
一方、図示されていないが、前方一致キー“１０ｘｘｘｘ”の有意ビットの末尾のビット位置“１”が差分ビット位置として設定されている。
そこで、探索経路スタック３１０に格納されたノードの弁別ビット位置がノード２１０ｆから順次差分ビット位置と比較され、ノード２１０ａが検索開始ノードの直近上位のノード（親ノード）として取り出され、その代表ノード番号２２０ａ＋１が検索開始ノード２１１ｂの配列番号として設定される。
【０４８６】
以下、図３１ＡのステップＳ３１１１に示すインデックスキーを昇順に取り出す処理、すなわち最小値検索を繰り返す処理が実行される。
図３１Ｂ（ｂ）の（２）は、ノード２１１ｂを検索開始ノードとして最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最小値検索の結果、探索経路スタック３１０には終端ノード［０］の上にノード２１１ｂとノード２１０ｆが格納されている。ここでは、ノード２１０ｆの代表ノード番号２２０ｆの指すノード２１０ｇはリーフノードであるため、このノード２１０ｇのインデックスキー
“１０００１０”が最小値として再度取り出され、スタックポインタの指す位置は１つ減ってノード２１１ｂとなる。そして、最小値検索における代表ノード番号に代表ノード番号２２０ｆを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４８７】
図３１Ｂ（ｂ）の（３）は、代表ノード番号に代表ノード番号２２０ｆを、ノード位置に値“１”を設定して最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。ここでは、配列から取り出されたノード２１１ｇはリーフノードであるため、このノード２１１ｇのインデックスキー“１０００１１”
が取り出され、スタックポインタの指す位置は１つ減って終端ノード［０］となる。そして、最小値検索における代表ノード番号に代表ノード番号２２１ｂを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４８８】
図３１Ｂ（ｂ）の（４）は、代表ノード番号に代表ノード番号２２１ｂを、ノード位置に値“１”を設定して最小値検索処理を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示している。最小値検索の結果、探索経路スタック３１０には終端ノード［０］の上にノード２１１ｆが格納されている。ここでは、ノード２１１ｆの代表ノード番号２２１ｆの指すノード２１０ｈはリーフノードであるため、このノード２１０ｈのインデックスキー
“１０１０１１”が取り出され、スタックポインタの指す位置は１つ減って終端ノード［０］となる。そして、最小値検索における代表ノード番号に代表ノード番号２２１ｆを、ノード位置に値“１”を設定し、次の最小値検索を実行する。
【０４８９】
図３１Ｂ（ｂ）の（５）は、代表ノード番号に代表ノード番号２２１ｆを、ノード位置に値“１”を設定して最小値検索を実行した段階における探索経路スタック３１０及び取り出されるインデックスキーを示す。ここでは、配列から取り出されたノード２１１ｈはリーフノードであるため、このノード２１１ｈのインデックスキー“１０１１００”が取り出される。そして、図２７Ａに示すステップＳ２７０８で、前回ステップＳ２７０５で探索経路スタック３１０から取り出されたノードが終端ノードであると判断され、処理を終了する。
【０４９０】
以上に説明した本発明の実施の形態によるカップルドノードツリーの各種検索処理、分割結合処理及びその均等物をコンピュータに実行させるプログラムにより、本発明のカップルドノードツリーの各種検索方法、分割方法及び結合方法が実現可能であることは明らかである。
【０４９１】
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。また、上述のカップルドノードツリーのツリー構造からなるデータ構造も、本発明の実施の形態に含まれる。
【図１】
2010198632.tif 000003
【図２Ａ】
2010198632.tif 000004
【図２Ｂ】
2010198632.tif 000005
【図３】
2010198632.tif 000006
【図４Ａ】
2010198632.tif 000007
【図４Ｂ】
2010198632.tif 000008
【図４Ｃ】
2010198632.tif 000009
【図５Ａ】
2010198632.tif 000010
【図５Ｂ】
2010198632.tif 000011
【図５Ｃ】
2010198632.tif 000012
【図６Ａ】
2010198632.tif 000013
【図６Ｂ】
2010198632.tif 000014
【図７Ａ】
2010198632.tif 000015
【図７Ｂ】
2010198632.tif 000016
【図８Ａ】
2010198632.tif 000017
【図８Ｂ】
2010198632.tif 000018
【図８Ｃ】
2010198632.tif 000019
【図９Ａ】
2010198632.tif 000020
【図９Ｂ】
2010198632.tif 000021
【図９Ｃ】
2010198632.tif 000022
【図１０Ａ】
2010198632.tif 000023
【図１０Ｂ】
2010198632.tif 000024
【図１０Ｃ】
2010198632.tif 000025
【図１１Ａ】
2010198632.tif 000026
【図１１Ｂ】
2010198632.tif 000027
【図１１Ｃ】
2010198632.tif 000028
【図１２Ａ】
2010198632.tif 000029
【図１２Ｂ】
2010198632.tif 000030
【図１３Ａ】
2010198632.tif 000031
【図１３Ｂ】
2010198632.tif 000032
【図１４】
2010198632.tif 000033
【図１５】
2010198632.tif 000034
【図１６Ａ】
2010198632.tif 000035
【図１６Ｂ】
2010198632.tif 000036
【図１７Ａ】
2010198632.tif 000037
【図１７Ｂ】
2010198632.tif 000038
【図１８Ａ】
2010198632.tif 000039
【図１８Ｂ】
2010198632.tif 000040
【図１９】
2010198632.tif 000041
【図２０】
2010198632.tif 000042
【図２１】
2010198632.tif 000043
【図２２Ａ】
2010198632.tif 000044
【図２２Ｂ】
2010198632.tif 000045
【図２２Ｃ】
2010198632.tif 000046
【図２３Ａ】
2010198632.tif 000047
【図２３Ｂ】
2010198632.tif 000048
【図２４】
2010198632.tif 000049
【図２５】
2010198632.tif 000050
【図２６Ａ】
2010198632.tif 000051
【図２６Ｂ】
2010198632.tif 000052
【図２６Ｃ】
2010198632.tif 000053
【図２７Ａ】
2010198632.tif 000054
【図２７Ｂ】
2010198632.tif 000055
【図２８Ａ】
2010198632.tif 000056
【図２８Ｂ】
2010198632.tif 000057
【図２９Ａ】
2010198632.tif 000058
【図２９Ｂ】
2010198632.tif 000059
【図２９Ｃ】
2010198632.tif 000060
【図３０Ａ】
2010198632.tif 000061
【図３０Ｂ】
2010198632.tif 000062
【図３０Ｃ】
2010198632.tif 000063
【図３１Ａ】
2010198632.tif 000064
【図３１Ｂ】
2010198632.tif 000065
【手続補正書】
【提出日】平成22年6月8日(2010.6.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項６
【補正方法】変更
【補正の内容】
【請求項６】
ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有するツリーの構成要素としてのノード対と、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときはブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである前記代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは非代表ノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成されたカップルドノードツリーをコンピュータが分割する、カップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割する分割キーを取得する分割キー取得ステップと、
該分割キーを前記検索キーとし、前記処理元カップルドノードツリーのルートノードを前記検索開始ノードとして、前記処理元カップルドノードツリーから検索結果キーとして前記分割キーを得るとともに、前記ルートノードから該分割キーをインデックスキーとして含むリーフノードに至るまでたどったリンク経路のブランチノードの前記代表ノードの位置を示す位置情報を弁別ビット位置の検索キーのビット値に応じたリンク先のノードの位置を示す位置情報に変更して該ブランチノードをスタックに順次格納する検索ステップと、
前記スタックに格納されたブランチノードの位置情報が、前記代表ノードの位置を示す位置情報となるまで、あるいは前記非代表ノードの位置を示す位置情報となるまで順次ブランチノードを読み出し、該読み出したブランチノードの前記代表ノードの位置を示す位置情報あるいは前記非代表ノードの位置を示す位置情報の記憶領域に配置されたノードを分割ノードとして求める分割ノード取得ステップと、
前記分割ノードをルートノードとする部分木である分割ノードツリーを挿入する処理先カップルドノードツリーが存在していない場合は、該分割ノードツリーを処理先カップルドノードツリーとして処理先カップルドノードツリーを生成し、前記処理先カップルドノードツリーが存在している場合は、該分割ノードツリーを該処理先カップルドノードツリーに挿入することにより新たな処理先カップルドノードツリーを生成する生成ステップと、
前記分割ノードツリーを前記処理元カップルドノードツリーから削除する削除ステップ
を含むことを特徴とするカップルドノードツリーの分割方法。