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