JP4402120B2 - ビット列検索装置、検索方法及びプログラム - Google Patents

Description

本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する検索方法に関するものであり、特に本出願人が特願２００６−１８７８２７において提案したカップルドノードツリーを用いたビット列検索装置、検索方法及びプログラムに関するものである。

近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。

そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。

図１７は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。

図１７の例では、インデックスキー“１０００１０”を保持するノード１７５０ａがルートノードとなっており、その検査ビット位置１７３０ａは０である。ノード１７５０ａの左リンク１７４０ａにはノード１７５０ｂが接続され、右リンク１７４１ａにはノード１７５０ｆが接続されている。

ノード１７５０ｂの保持するインデックスキーは“０１００１１”であり、検査ビット位置１７３０ｂは１である。ノード１７５０ｂの左リンク１７４０ｂにはノード１７５０ｃが、右リンク１７４１ｂにはノード１７５０ｄが接続されている。ノード１７５０ｃが保持するインデックスキーは“０００１１１”、検査ビット位置１７３０ｃは３である。ノード１７５０ｄが保持するインデックスキーは“０１１０１０”、検査ビット位置１７３０ｄは２である。

ノード１７５０ｃから実線で接続された部分はノード１７５０ｃの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ１７４０ｃは、その欄が空欄であることを示している。点線の接続された右ポインタ１７４１ｃの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード１７５０ｃを右ポインタ１７４１ｃが指定していることを表している。

ノード１７５０ｄの右ポインタ１７４１ｄはノード１７５０ｄ自身を指しており、左リンク１７４０ｄにはノード１７５０ｅが接続されている。ノード１７５０ｅの保持するインデックスキーは“０１００１０”、検査ビット位置１７３０ｅは５である。ノード１７５０ｅの左ポインタ１７４０ｅはノード１７５０ｂを、右ポインタ１７４１ｅはノード１７５０ｅを指している。

また、ノード１７５０ｆの保持するインデックスキーは“１０１０１１”であり、検査ビット位置１７３０ｆは２である。ノード１７５０ｆの左リンク１７４０ｆにはノード１７５０ｇが、右リンク１７４１ｆにはノード１７５０ｈが接続されている。

ノード１７５０ｇの保持するインデックスキーは“１０００１１”であり、検査ビット位置１７３０ｇは５である。ノード１７５０ｇの左ポインタ１７４０ｇはノード１７５０ａを、右ポインタ１７４１ｇはノード１７５０ｇを指している。

ノード１７５０ｈの保持するインデックスキーは“１０１１００”であり、検査ビット位置１７３０ｈは３である。ノード１７５０ｈの左ポインタ１７４０ｈはノード１７５０ｆを、右ポインタ１７４１ｈはノード１７５０ｈを指している。

図１７の例では、ルートノード１７５０ａからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が１であるか０であるか判定を行い、１であれば右リンクをたどり、０であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば（図１７において点線で示されたこの逆戻りのリンクをバックリンクという）、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。

上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は１回ですむことなどのメリットがあるが、各ノードからの２つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。

これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献１に開示された技術がある。下記特許文献１に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。

しかしながら、下記特許文献１に開示されたものにおいても、１つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを１つとしたため、例えば図１７に示したパトリシアツリーの最下段の部分である左ポインタ１７４０ｃ、右ポインタ１７４１ｈ等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。

上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願２００６−１８７８２７において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を提案した。

上記出願においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。

また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願２００６−２９３６１９において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの最大値／最小値を求める手法等を提案した。

さらに、本出願人は、特願２００６−３１９４０７において、カップルドノードツリーの分割／結合手法を提案した。
上記３つの出願において提案した検索手法は、検索開始ノードから順次ブランチノードをたどってリーフノードに至り、リーフノードに格納されたインデックスキーを求める操作を基本とするものであり、検索履歴として検索開始ノードからリーフノードに至るノードの配置された記憶領域のアドレス情報として該ノードの格納されている配列要素の配列番号をスタックに格納している。そして、検索処理後の各種処理において、スタックに格納されたアドレス情報を基にそのアドレス情報が示す記憶領域に格納されたノードを参照して弁別ビット位置を取り出すことが行われている。

上記アドレス情報としては、カップルドノードツリーを配列に格納する場合にはその配列での配列番号を用いることができ、アドレス情報を表すビット量を削減することができるが、カップルドノードツリーの規模が大きくなるとそれに伴ってノードが実際に格納されるアドレス範囲が大きくなり、各種処理をコンピュータ上で実行するときにキャッシュミスを起こす可能性が高くなり、処理効率が低下するおそれがある。
特開２００１−３５７０７０号公報

そこで本発明の目的は、カップルドノードツリーの規模が大きくなっても、カップルドノードツリーを利用した処理の効率が低下することを少なくする手法を提供することである。

本発明によれば、基本検索や最大値あるいは最小値検索の検索処理において、検索履歴を格納する探索経路スタックにノードの配置された記憶領域のアドレス情報のみならず検索経路でたどったブランチノードの弁別ビット位置を格納する。

また、検索処理でたどったブランチノードの弁別ビット位置を探索するインデックスキーの挿入やカップルドノードツリーの分割結合処理においては、探索経路スタックから弁別ビット位置を取り出す。

本発明によれば、検索処理でたどったノードの弁別ビット位置が必要なときは、その情報を、検索履歴を格納する探索経路スタックから得ることができ、カップルドノードツリーの規模が大きくなったとしても、キャッシュミスが発生する可能性を小さくすることができる。

最初に、本出願人により先の上記出願において提案された、本発明の前提となるカップルドノードツリーについて、カップルドノードツリーを配列に格納する例を説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。

図１は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図１を参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。

配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。

なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。

配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。
ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。

したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。

なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
図２は、カップルドノードツリーのツリー構造を概念的に示す図である。図示の６ビットのインデックスキーは、図１７に例示されたパトリシアツリーのものと同じである。

符号２１０ａで示すのがルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。
ツリー構造としては、ルートノード２１０ａの下にノート対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。

各ノードの前に付された０あるいは１の符号は、図１において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。

図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。

ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。

ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキー２５０ｃを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。

ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。

ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。

ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。

ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの格納された配列要素の配列番号２２１ｆが格納されている。

ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。

また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００”が格納されている。

以下、上述のツリーからインデックスキー“１０００１０”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。

ノード２１０ｆの弁別ビット位置２３０ｆには５が格納されているので、検索キー“１０００１０”の弁別ビット位置が５のビット値をみると０であるから、代表ノード番号の格納された配列番号２２０ｆの配列要素に格納されたノード２１０ｇにリンクする。

ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを読み出して検索キーと比較すると両方とも“１０００１０”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。

次に、図２を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図２の例で、ルートノード２１０ａの弁別ビット位置が０であるのは、図２に例示されたインデックスキーに０ビット目が０のものと１のものがあるからである。０ビット目が０のインデックスキーのグループはノード２１０ｂの下に分類され、０ビット目が１のインデックスキーのグループはノード２１１ｂの下に分類されている。

ノード２１１ｂの弁別ビット位置が２であるのは、ノード２１１ｈ、２１０ｈ、２１１ｇ、２１０ｇに格納された０ビット目が１のインデックスキーの１ビット目がすべて０で等しく、２ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。

以下０ビット目の場合と同様に、２ビット目が１であるものはノード２１１ｆ側に分類され、２ビット目が０であるものはノード２１０ｆ側に分類される。
そして２ビット目が１であるインデックスキーは３ビット目の異なるものがあるのでノード２１１ｆの弁別ビット位置には３が格納され、２ビット目が０であるインデックスキーでは３ビット目も４ビット目も等しく５ビット目で異なるのでノード２１０ｆの弁別ビット位置には５が格納される。

ノード２１１ｆのリンク先においては、３ビット目が１のものと０のものがそれぞれ１つしかないことから、ノード２１０ｈ、２１１ｈはリーフノードとなり、それぞれインデックスキー２５０ｈと２５１ｈに“１０１０１１”と“１０１１００”が格納されている。

仮にインデックスキーの集合に“１０１１００”の代わりに“１０１１０１”か“１０１１１０”が含まれていたとしても、３ビット目までは“１０１１００”と等しいので、ノード２１１ｈに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“１０１１００”に加えて“１０１１０１”が含まれていると、ノード２１１ｈはブランチノードとなり、その弁別ビット位置は５になる。追加されるインデックスキーが“１０１１１０”であれば、弁別ビット位置は４となる。

以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“１”のノードとビット値が“０”のノードとに分岐していることから、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード２１１ｈのインデックスキー２５１ｈの“１０１１００”、ノード２１０ｈのインデックスキー２５０ｈの“１０１０１１”、・・・、ノード２１０ｃのインデックスキー２５０ｃの“０００１１１”となり降順にソートされている。

すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“１０１１００”であればノード２１１ｈに到達することができる。また、上記説明からも想像がつくように、“１０１１０１”か“１０１１１０”を検索キーとした場合でもノード２１１ｈにたどり着き、インデックスキー２５１ｈと比較することにより検索が失敗したことが分かる。

また、例えば“１００１００”で検索した場合でも、ノード２１０ａ、２１１ｂ、２１０ｆのリンク経路では検索キーの３ビット目と４ビット目は使われることがなく、“１００１００”の５ビット目が０なので、“１０００１０”で検索した場合と同様にノード２１０ｇに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。

図３は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。データ格納装置３０８は、カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号のほかノード内の情報を記憶する探索経路スタック３１０を有する。このデータ格納装置３０８は主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。

図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、配列３０９は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。

また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
次に、上述の出願において本出願人により提案された、カップルドノードツリーを用いた基本的な検索処理、カップルドノードツリーにおける挿入削除処理、カップルドノードツリーに含まれるインデックスキーの最大値／最小値を求める処理等の応用処理、及びカップルドノードツリーの分割／結合処理において、検索履歴を格納するスタックに、ノードの配置された記憶領域のアドレス情報のみならず各種処理で用いるブランチノードの弁別ビット位置を格納し、それを利用する本発明を説明する。

図４Ａは、本発明のビット列検索の基本動作を示すフローチャートである。図４Ａに示すフローチャートは、本出願人による出願である上記特願２００６−２９３６１９で提案されたビット列検索の基本動作を示すフローチャートにおいて、探索経路スタック３１０に弁別ビット位置を格納するステップＳ４０６ａの処理を追加したものである。

まず、ステップＳ４０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列要素は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後に説明する各種応用検索において行われる。

次に、ステップＳ４０２で、探索経路スタック３１０に取得された配列番号を格納し、ステップＳ４０３で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップＳ４０４で、読み出したノードから、ノード種別を取り出し、ステップＳ４０５で、ノード種別がブランチノードであるか否かを判定する。

ステップＳ４０５の判定において、読み出したノードがブランチノードである場合は、ステップＳ４０６に進み、ノードから弁別ビット位置についての情報を取り出す。
次にステップＳ４０６ａで、ステップＳ４０６で取り出した弁別ビット位置を探索経路スタック３１０に格納するとともに、ステップＳ４０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ４０８で、ノードから代表ノード番号を取り出して、ステップＳ４０９で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号を得て、ステップＳ４０２に戻る。

以降、ステップＳ４０５の判定においてリーフノードと判定されてステップＳ４１０に進むまで、ステップＳ４０２からステップＳ４０９までの処理を繰り返す。ステップＳ４１０で、リーフノードからインデックスキーを取り出して、処理を終了する。

図４Ｂは、図４Ａのフローチャートにより示した本実施形態に係るビット列検索の基本動作を、図２に例示したカップルドノードツリーにより説明する図である。
図４Ｂにおいては、カップルドノードツリー、検索キー設定エリア２７０及び探索経路スタック３１０が示されている。以下、図４Ｂを用いてカップルドノードツリー上の参照されるノード及び探索経路スタック３１０の状態について説明する。

なお、図４Ｂにおいては、図２に示すカップルドノードツリーのうち、図４Ａの処理を説明するために必要な一部分のみを示し、残りのノード（代表ノード番号２２１ｂ以下のノード）については省略している。以降の説明においてカップルドノードツリー上の参照されるノードを説明するための図面についても同様である。

まず、検索を開始するノードの配列番号として、配列番号２２０が設定されたとする。このとき、対応する配列番号２２０が探索経路スタック３１０にプッシュされると共に、配列要素の各種情報が参照される。

配列に格納された情報に基づいて、配列番号２２０のノードがブランチノードであってインデックスキーが格納されていないと認識されると、さらにその配列番号２２０の配列に格納されている情報（代表ノード番号や弁別ビット位置）等を参照して、次に参照すべき配列番号が算出される。

ここでは、まず配列番号２２０を探索経路スタック３１０に格納し、配列番号２２０のノード２１０ａからノード種別２６０ａを取り出す。取り出したノード種別２６０ａは図示のとおり“０”であってノード２１０ａがブランチノードであることを示しているため、ノード２１０ａから弁別ビット位置２３０ａの値“０”を取り出し、探索経路スタック３１０に配列番号２２０とともに格納する。

さらに、検索キー設定エリア２７０の検索キー“０１１０１０”における弁別ビット位置０のビット値“０”を取り出す。そして、ノード２１０ａに格納されている代表ノード番号２２０ａの値を取り出して、先に検索キーの弁別ビット位置から取り出したビット値“０”を加算して得られた配列番号２２０ａを探索経路スタック３１０に格納する。

続いて、配列番号２２０ａのノードからノード種別２６０ｂを読み出すと、配列番号２２０ａのノード２１０ｂはブランチノードであることが判定され、ノード２１０ｂの弁別ビット位置２３０ｂの値“１”を探索経路スタック３１０に格納し、弁別ビット位置１に対応するビット値を検索キー“０１１０１０”から取り出すと、値は“１”である。そこで、ノード２１０ｂの代表ノード番号２２０ｂに得られたビット値“１”を加算して、探索経路スタック３１０に２２０ｂ＋１を格納する。

配列番号（２２０ｂ＋１）のノード２１１ｃから読み出したノード種別２６１ｃはブランチノードを示しているため、ノード２１１ｃの弁別ビット位置２３１ｃの値“２”を探索経路スタック３１０に格納し、弁別ビット位置２に対応するビット値を検索キー“０１１０１０”から取り出すと、値は“１”である。ノード２１１ｃの代表ノード番号２２１ｃに得られたビット値“１”を加算して得られる値２２１ｃ＋１を、探索経路スタック３１０に格納する。

配列番号（２２１ｃ＋１）のノード２１１ｄからノード種別２６１ｄを取り出すと、ノード２１１ｄはリーフノードであることがわかる。そこで、ノード２１１ｄからインデックスキー“０１１０１０”を取り出し、処理を終了する。

このように、順次検索キーのビット情報と各ノードの情報を参照していくリンク処理を実行することにより、探索経路スタック３１０には、検索開始ノードであるノード２１０ａの配列番号２２０からリーフノード２１１ｄの配列番号（２２１ｃ＋１）までと、ノー２１０ａの弁別ビット位置２３０ａからノード２２１ｃの弁別ビット位置２３１ｃまでの情報が、リンク順にプッシュされていくことになる。

次に、図５Ａ〜図５Ｃ、図６により、本発明のカップルドノードツリーにおけるノード挿入処理を説明する。図５Ａ〜図５Ｃが通常の挿入処理を説明するものであり、図６はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。

図５Ａは挿入処理の前段である検索処理の処理フローを示す図であり、図４Ａに示した検索処理において挿入キーを検索キーとしたものに相当する。ステップＳ５０１は図４ＡのステップＳ４０１で検索開始ノードをルートノードとしたものに相当し、ステップＳ５０２〜ステップＳ５１０の処理は図４ＡのステップＳ４０２〜ステップＳ４１０に完全に対応するので説明は省略する。

図５ＡのステップＳ５１１において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図５ＢのステップＳ５１２以下の処理に進む。

図５Ｂは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップＳ５１２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。

ステップＳ５１３に進み、挿入キーとステップＳ５１０で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１を小さいときは値０のブール値を得る。
ステップＳ５１４に進み、ステップＳ５１２で得た代表ノードの配列番号にステップＳ５１３で得たブール値を加算した配列番号を得る。

ステップS５１５に進み、ステップS５１２で得た代表ノードの配列番号にステップS５１３で得たブール値の論理否定値を加算した配列番号を得る。
ステップS５１４で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップS５１５で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。

つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。

例えば図２のカップルドノードツリーに“０１１０１１”を挿入する場合、検索結果のインデックスキーはノード２１１ｄに格納された“０１１０１０”になる。挿入キー“０１１０１１”とノード２１１ｄに格納されたインデックスキー“０１１０１０”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値１が得られ、挿入されるノード対の代表ノード番号に１を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー“０１１０１０”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。

その際、インデックスキー“０１１０１０”と挿入キー“０１１０１１”とは５ビット目で異なることから、ノード２１１ｄは、弁別ビット位置を５とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。

また図２のカップルドノードツリーに“０１１００１”を挿入しようとする場合も、検索結果のインデックスキーはノード２１１ｄに格納された“０１１０１０”になる。この場合には挿入キーが小さいのでブール値０が得られ、挿入されるノード対の代表ノード番号に０を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー“０１１０１０”と挿入キー“０１１００１”とは４ビット目で異なることから、ノード２１１ｄは、弁別ビット位置を４とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。

次に図５ＣのステップＳ５１６以下の処理に進む。
図５Ｃは図５Ｂで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。

ステップＳ５１６〜ステップＳ５２３までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップＳ５２４以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。

ステップＳ５１６で、挿入キーとステップＳ５１０で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップＳ５１７に進み、ステップＳ５１６で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。

次にステップＳ５１８に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップＳ５２４に移行し、指していなければステップＳ５１９ａに進む。

ステップＳ５１９ａにおいて、探索経路スタックのスタックポインタを１つ戻してそこにスタックされている弁別ビット位置を取り出す。
先の出願である上述の特願２００６−１８７８２７で提案された挿入処理においては、探索経路スタックにスタックされているのは配列番号だけであったため、配列番号を取り出して配列から該配列番号の指す配列要素に格納されたノードから弁別ビット位置を取り出すものであったが、本発明では図５Ａに示すステップＳ５０６ａで探索経路スタックに弁別ビット位置を格納しているので、配列にアクセスすることなく、弁別ビット位置を取り出すことができる。

次にステップＳ５２２に進み、ステップＳ５１９ａで取り出した弁別ビット位置がステップＳ５１７で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。

ステップS５２２の判定結果が否定であれば、ステップS５１８に戻り、ステップS５１８での判定が肯定になるかステップS５２２での判定が肯定になるまで繰り返す。ステップS５２２での判定が肯定になると、ステップS５２３で探索経路スタックのスタックポインタを1つ進め、ステップS524以下の処理に移行する。

上記ステップＳ５１６〜ステップＳ５２３で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の（最上位の）ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。

例えば図２のカップルドノードツリーに”１１１０００”を挿入するとき、検索結果のインデックスキーはノード２１０ｈに格納された”１０１０１１ ”になる。挿入キー”１１１０００”とノード２１０ｈに格納されたインデックスキー”１０１０１１”のビット列比較により異なるビット値となる最上位のビット位置１が得られる。得られたビット位置１と探索経路スタックに積まれた配列番号の配列要素に格納されたブランチノードの弁別ビット位置との位置関係を弁別ビット位置が上位になるまで順次探索経路スタックを逆にたどると、ルートノード２１０ａに至る。そこで探索経路スタックのポインタを１つ進め、ノード２１１ｂの配列番号を得る。挿入キー”１１１０００”はノード２１１ｂのリンク先に挿入される。

また、探索経路スタックを逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。

次に、ステップＳ５２４以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップＳ５２４では探索経路スタックからスタックポインタの指す配列番号を取り出す。

ステップＳ５２５において、ステップＳ５１４で得た配列番号の指す配列要素のノード種別に“１”（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップＳ５２６に進み、配列からステップＳ５２４で得た配列番号の配列要素を読み出す。

次にステップＳ５２７において、ステップＳ５１５で得た配列番号の配列要素にステップＳ５２６で読み出した内容を書き込む。
最後にステップＳ５２８において、ステップＳ５２４で得た配列番号の指す配列要素のノード種別に“０”(ブランチノード）を、弁別ビット位置にステップＳ５１７で得たビット位置を、代表ノード番号にステップＳ５１２で得た配列番号を書き込み、処理を終了する。

上述の図２のカップルドノードツリーに“１１１０００”を挿入する例では、取得された空ノード対のノード［０］にノード２１１ｂの内容を書き込み（ステップＳ５２７）、ノード[1]を挿入キー“１１１０００”を保持するリーフノードとする（ステップＳ５２５）。そして、ノード２１１ｂの弁別ビット位置にビット列比較により異なるビット値となる最上位のビット位置１を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号が格納される（ステップＳ５２８）。

図６は、ルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。図６に示すフロー自体は、先の出願である上記特願２００６−１８７８２７で提案されたノード挿入処理全体を説明する処理フローと同様である。

ステップＳ６０１において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図５Ａ〜図５Ｃを用いて説明した通常の挿入処理が行われる。

ステップＳ６０１での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップＳ６０２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップＳ６０３において、ステップＳ６０２で得た配列番号に０を加えた配列番号を求める。（実際には、ステップＳ６０２で取得した配列番号に等しい。)。さらにステップＳ６０４において、ステップＳ６０３で得た配列番号の配列要素に、挿入するルートノードのノード種別に１（リーフノード)とインデックスキーに挿入キーを書き込み、ステップＳ６０５で、ステップＳ６０２で取得したルートノードの配列番号を登録して処理を終了する。

先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図６及び図５Ａ〜図５Ｃの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。

次に図７Ａ、図７Ｂを参照して、カップルドノードツリーに係るインデックスキーの集合から、特定のインデックスキーを削除する処理フローを説明する。図７Ａ、図７Ｂに示すフロー自体は、本出願人による出願である上記特願２００６−１８７８２７で提案された削除処理のフローと同様である。

図７Ａは、削除処理の前段である検索処理の処理フローを示す図であり、基本的には図４Ａに示した検索処理において削除キーを検索キーとしたものに相当するが、図４ＡのステップＳ４０６ａの探索経路スタックに弁別ビット位置を格納する処理は、省略されている。もし、削除処理の前段である検索処理の履歴における弁別ビット位置を頻繁に利用するような処理を引き続いて行うのであれば、探索経路スタックに弁別ビット位置を格納する処理を追加すればよい。

ステップＳ７０１は図４ＡのステップＳ４０１で検索開始ノードをルートノードとしたものに相当し、ステップＳ７０２〜ステップＳ７１０の処理は図４ＡのステップＳ４０２〜ステップＳ４１０に上述の点を除いて完全に対応するので説明は省略する。

図７ＡのステップＳ７１１において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図７ＢのステップＳ７１２以下の処理に進む。

図７Ｂは、削除処理の後段の処理フローを説明する図である。
まず、ステップＳ７１２で探索経路スタックに２つ以上の配列番号が格納されているか判定する。２つ以上の配列番号が格納されていないということは、言い換えれば１つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップＳ７１８に移行し、ステップＳ７０１で得たルートノードの配列番号に係るノード対を削除する。次にステップＳ７１９に進み、登録されていたルートノードの配列番号を削除して処理を終了する。

ステップＳ７１２において探索経路スタックに２つ以上の配列番号が格納されていると判定されたときはステップＳ７１３に進み、ステップＳ７０８で得た代表ノード番号にステップＳ７０７で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。

次にステップＳ７１４において、ステップＳ７１３で得た配列番号の配列要素の内容を読み出し、ステップＳ７１５において探索経路スタックのスタックポインタを１つ戻して配列番号を取り出す。

次にステップＳ７１６に進み、ステップＳ７１４で読み出した配列要素の内容をステップＳ７１５で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。

最後にステップＳ７１７においてステップＳ７０８で得た代表ノード番号に係るノード対を削除して処理を終了する。
図８は、本発明による、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの最小値を求める処理を示したフローチャートである。図８に示すフローチャートは、本出願人による出願である上記特願２００６−２９３６１９で提案されたインデックスキーの最小値を求めるフローチャートにおいて、ノードから弁別ビット位置を取り出す処理と探索経路スタックにノードから取り出した弁別ビット位置を格納する処理を追加したものである。

インデックスキーの最小値を求める処理は、先に述べたようなインデックスキーのツリー上の配置から、検索開始ノードからノード［０］をリーフノードに至るまでツリー上でたどることに相当する。

まず、ステップＳ８０１の検索開始ノードの配列番号の取得からステップＳ８０５のノード種別の判定までは、それぞれ上述の図４ＡのステップＳ４０１からステップＳ４０５の処理と同様である。

ステップＳ８０５のノード種別の判定においてノード種別がブランチノードと判定されると、ステップＳ８０６に進み、ノードから配列の代表ノード番号を取り出す。
次にステップＳ８０６ａに進み、ノードから弁別ビット位置を取り出し、ステップＳ８０６ｂで、その取り出した弁別ビット位置を探索経路スタックに格納する。

次にステップＳ８０７で、ステップＳ８０６において取り出した代表ノード番号に値“０”を加算してその結果を新たな配列番号とし、ステップＳ８０２に戻る。以降、ステップＳ８０５においてそのノードがリーフノードと判定されるまでステップＳ８０２からステップＳ８０７までの処理を繰り返し、ステップＳ８０８で、リーフノードからインデックスキーを取り出し、処理を終了する。

上記の図８に示す処理においては、ノード［０］をたどるため、代表ノード番号に一律に“０”を加算している。すなわち、図８の処理によれば、リンク先のノードは、ノード対のうち必ずノード［０］とし、より小さい値のインデックスキーが格納されているノードのほうに分岐している。これにより、ツリー構造が先に述べたように順列構成であるカップルドノードツリーの最小のインデックスキーを取り出すことができる。

図９は、図８のフローチャートにより示したインデックスキーの最小値を求める処理を、図２に例示したカップルドノードツリーにより説明する図である。図９は、配列番号２２０のノード２１０ａを検索開始ノードとする場合のリンク経路及び探索経路スタック３１０の状態を示す。

検索開始ノードはノード２１０ａであるから、その配列番号２２０と弁別ビット位置２３０ａのビット値“０”が探索経路スタック３１０にプッシュされ、次に代表ノード番号２２０ａにより表されるノード対２０１ｂのうちノード［０］であるノード２１０ｂにリンクしていき、その代表ノード番号２２０ａと弁別ビット位置２３０ｂのビット値“１”が探索経路スタック３１０に格納され、さらにリーフノード２１０ｃに至る。リーフノード２１０ｃのインデックスキー“０００１１１”を取り出すと、処理を終了する。

以上説明したように、探索経路スタック３１０には、ノード対のうち、ノード［０］の配列番号とブランチノードの弁別ビット位置が順次プッシュされていく。
図１０は、カップルドノードツリー（部分木を含む）に格納されたインデックスキーの最大値を求める処理を示したフローチャートである。図１０に示すフローチャートは、本出願人による出願である上記特願２００６−２９３６１９で提案されたインデックスキーの最大値を求めるフローチャートにおいて、ノードから弁別ビット位置を取り出す処理と探索経路スタックにノードから取り出した弁別ビット位置を格納する処理を追加したものである。

インデックスキーの最大値を求める処理は、ツリー上のノードのうちノード［１］について、リーフノードに至るまで順次たどっていくことに相当する。以下、任意の部分木の最大のインデックスキーを求める処理について、上記最小のインデックスキーを求める処理と比較しながら、異なる点を中心に説明する。

図１０に示す一連の処理のうち、ステップＳ１００１からステップＳ１００６ｂ及びステップＳ１００８については、図８のステップＳ８０１からステップＳ８０６ｂ及びステップＳ８０８にそれぞれ対応しており、同様の処理が実行される。図８の最小値を求める処理と異なる点は、ステップＳ１００７において、代表ノード番号に、値“１”を加算する点である。これにより、代表ノード番号が表すノード対のうち、ノード［１］に常にリンクすることとなり、リーフノードに至るまで順次ステップＳ１００２からステップＳ１００７の処理を繰り返すことにより、インデックスキーの最大値を得ることができる。

図１１は、図１０のフローチャートにより示したインデックスキーの最大値を求める処理を、図２に例示したカップルドノードツリーにより説明する図である。図１１に示すように、検索開始ノードを図９の例と同様に配列番号２２０のノード２１０ａとしている。

したがって、検索開始ノードの配列番号は配列番号２２０であり、探索経路スタック３１０には配列番号２２０がスタックされ、配列番号２２０の配列要素に格納されたノード２１０ａが読み出される。ノード２１０ａのノード種別２６０ａは“０”でありブランチノードであるから、代表ノード番号２２０ａと弁別ビット位置２３０ａを取り出し、探索経路スタック３１０に弁別ビット位置２３０ａの値“０”を格納する。

次に、最大値検索においては常にノード［１］にリンクしていくことから、代表ノード番号２２０ａに値“１”を加算した値をリンク先の配列番号としてノード２１１ｂにリンクする。そして配列番号２２０ａ＋１を探索経路スタック３１０に格納するとともに、ノード２１１ｂを読み出す。

ノード２１１ｂのノード種別２６１ｂは“０” でありブランチノードであるから、代表ノード番号２２１ｂと弁別ビット位置２３１ｂを取り出し、探索経路スタック３１０に弁別ビット位置２３１ｂの値“２”を格納する。

次に、代表ノード番号２２１ｂに値“１”を加算した値をリンク先の配列番号としてノード２１１ｆにリンクする。そして配列番号２２１ｂ＋１を探索経路スタック３１０に格納するとともに、ノード２１１ｆを読み出す。

ノード２１１ｆのノード種別２６１ｆは“０” でありブランチノードであるから、代表ノード番号２２１ｆと弁別ビット位置２３１ｆを取り出し、探索経路スタック３１０に弁別ビット位置２３１ｆの値“３”を格納する。

次に、代表ノード番号２２１ｆに値“１”を加算した値をリンク先の配列番号としてノード２１１ｈにリンクする。そして配列番号２２１ｆ＋１を探索経路スタック３１０に格納するとともに、ノード２１１ｈを読み出す。

ノード２１１ｈのノード種別２６１ｈは“１” でありリーフノードであるから、ノード２１１ｈからインデックスキー２５１ｈの値“１０１１００”を最大値として取り出し、処理を終了する。

図４Ａから図１１に示すように、検索キーと一致するインデックスキーを検索する基本動作やインデックスキーの最小値／最大値の検索処理を実行する際には、探索経路スタック３１０に参照した配列の配列番号とブランチノードの弁別ビット位置が順次格納されていく。

なお、上述の図８及び図１０を参照したインデックスキーの最小値／最大値の検索処理では、カップルドノードツリーは配列に記憶されたものとして説明したが、カップルドノードツリーが配列に記憶されることは必須ではなく、ノード対を構成する２つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることによりインデックスキーの最小値／最大値の検索が可能であることは明らかである。

次に、カップルドノードツリーの分割／結合方法について説明をする。
本発明でいうカップルドノードツリーの分割とは、あるビット列からなる分割キーを指定したとき、カップルドノードツリーに含まれるインデックスキーをその分割キーとの大小関係により２グループに分け、それぞれのグループに属するインデックスキーからなる２つのカップルドノードツリーを生成することである。

大小関係による分割について、以下の説明では、分割キーより大きいグループと分割キー以下のグループに分割するとするが、分割キー以上のグループと分割キーより小さいグループに分割する場合でも、同様に分割／結合が可能であることは、以下の説明から容易に理解されるであろう。

要するに、分割キーはカップルドノードツリーをどこで分割するかを決定するために用いられるキーである。
また、カップルドノードツリーの結合とは、２つのインデックスキーの集合に対応する２つカップルドノードツリーから２つのインデックスキーの集合の和集合に対応するカップルドノードツリーを生成することである。本発明では、２つのインデックスキーの集合の積集合は空であることを前提にしている。なお、以下の説明において、カップルドノードツリーを単にツリーということがある。

図１２は、本発明のカップルドノードツリーの第１の分割処理フローを説明する図である。図１２に示すフローのステップ構成は、本出願人による先の出願である特願２００６−３１９４０７で提案された分割処理の実施例１のフローと同じであるが、ステップの内容については異なるものが存在する。

第１の分割処理では、分割対象である処理元のツリー（以下、単に処理元ということがある。）のインデックスキーの最小値を取り出し、取り出したインデックスキーの最小値を、処理元の分割により生成される処理先のツリー（以下、単に処理先ということがある。）に挿入し、処理元のツリーからインデックスキーの最小値を削除する処理を、最小値が分割キー以下である間繰り返すことにより、分割対象である処理元のツリーから処理先のツリーを分割する。

最初のステップＳ１２０１で指定された分割キーを処理元の分割キーとして設定する。分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。

次にステップＳ１２０２で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップＳ１２０３に進む。
ステップＳ１２０３では、処理元のツリーが登録済みか判定する。この判定結果が登録済みではないというのは処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものであり、その場合には処理を終了する。

処理元のツリーが登録済みであればステップＳ１２０４に移行し、ステップＳ１２０２で検索開始ノードとして設定したルートノードより、図８に示す処理を実行してインデックスキーの最小値を得る。このとき、先に説明したように、探索経路スタックには配列番号とともに弁別ビット位置が格納される。

次にステップＳ１２０５に進み、ステップＳ１２０４で得た最小値が分割キーより大きいか判定する。最小値が分割キーより大きければ、ツリーの分割が完成しているのであるから処理を終了し、大きくなければ、以下で説明するステップＳ１２０６〜ステップＳ１２０９の処理先のツリーの生成と処理元のツリーからのノードの削除処理を実行し、ステップＳ１２０３へ戻る。

ステップＳ１２０６では、ステップＳ１２０４で得られた最小値を処理先の挿入キーに設定する。
次にステップＳ１２０７で、図５Ａ〜図５Ｃ、図６に示すツリーの生成、挿入処理により、挿入キーによる処理先のツリーの生成を実行する。

本発明のカップルドノードツリーの第１の分割処理における生成、挿入処理は、先の最小値検索処理において探索経路スタックに格納された弁別ビット位置を参照することができるので、本出願人による先の出願である特願２００６−３１９４０７で提案された分割処理の実施例１よりも処理を速くすることができる。

続いてステップＳ１２０８で、ステップＳ１２０７における挿入キーを処理元の削除キーに設定し、ステップＳ１２０９において、図７Ａ、図７Ｂに示す削除処理により、処理元のツリーから削除キーを含むリーフノードを削除する。

上記分割処理の説明では、処理元のインデックスキーの最小値から順に削除を行うようにしたが、同様にインデックスキーの最大値から順に削除を行うことができることは、当業者に明らかである。その場合、ステップＳ１２０５はインデックスキーの最大値を求める処理になり、ステップＳ１２０５は最大値と分割キーの大小関係の判定処理となり、ステップＳ１２０６では最大値を処理先の挿入キーに設定することになる。

以上、分割処理について説明したが、結合処理も図１２に示す処理フローにより実行できる。
結合処理は、結合しようとする２つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上とすれば、先に述べた例外的な処理に該当し、処理元のツリーは削除され、処理先のツリーに結合される。なお、処理元のツリーのインデックスキーの最大値が未知の場合には、前もって図１０に示す最大値検索処理により分割キーを求めることになる。

そして、処理元の分割キーを処理元のツリーのインデックスキーの最大値以上とするのであるから、ステップＳ１２０５の大小比較では、分割キーが最小値より常に大きくステップＳ１２０６へ分岐するのでステップＳ１２０５を省略することができる。そうであれば、分割キーを設定する意味もないことから、結局ステップＳ１２０２も不要になり、ただ単に最小値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができる。

また、分割処理について述べたように、最大値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができることも明らかである。
図１３は、本発明のカップルドノードツリーの第２の分割処理フローを説明する図である。図１３に示すフローのステップ構成は、本出願人による先の出願である特願２００６−３１９４０７で提案された分割処理の実施例２のフローと同じであるが、ステップの内容については異なるものが存在する。

第２の分割処理は、インデックスキー単位で挿入削除を行う点では第１の分割処理と同様であるが、挿入削除すべきインデックスキーの探索に探索経路スタックを活用し、挿入処理及び削除処理の実行時の処理ステップ数を小さくしたものである。

図１３のステップＳ１３０１からステップＳ１３０６までの処理は、図１２に示す第１の分割処理のステップＳ１２０１からステップＳ１２０６までの処理とまったく同じであるから、説明を省略する。なお、ステップＳ１３０４の最小値検索処理において、探索経路スタックには配列番号とともに弁別ビット位置が格納されることも、ステップＳ１２０４における最小値検索と同様である。

ステップＳ１３０７において、挿入キーにより、処理先にノードを挿入する。この処理は、図１２に示すステップＳ１２０７の挿入処理とは異なる第２の分割処理特有のものであり、後に図１４、図１５Ａ、図１５Ｂを参照して詳細に説明する。

次にステップＳ１３０８においてステップＳ１３０４で得た最小値を含むノードを、処理元の削除ノードとして設定し、ステップＳ１３０９において処理元から削除ノードを削除し、削除ノードと対をなすノードの内容が複写される処理元の親ノードを得る。

続いてステップＳ１３１０で、ステップＳ１３０９で得られた処理元の親ノードを、処理元の検索開始ノードに設定し、ステップＳ１３０３に戻る。
後に説明するように、処理元の親ノードは削除ノードの直近上位のブランチノードである。削除ノードは処理元のインデックスキーの最小値を含むものであり、先に述べたインデックスキーの順序性から、次に検索する最小値は処理元の親ノードの下位にある。

したがって、２回目以降のステップＳ１３０４での最小値検索の検索開始ノードはルートノードとしないで処理元の親ノードとすることにより、処理ステップ数を低減することができる。

ステップＳ１３０８〜ステップＳ１３０９及び処理元の親ノードについては、後に図１６を参照して詳細に説明する。
図１４は、図１３に示すステップＳ１３０６とステップＳ１３０７に対応するノードの挿入処理フローを説明する図である。

最初のステップＳ１４０１における挿入キーを処理先の挿入キーとして設定するステップは、図１３に示すステップＳ１３０６に対応する処理であり、図１３に示すステップＳ１３０４で得られた最小値を処理先の挿入キー設定エリアに設定する。

次にステップＳ１４０２において、処理先が登録済みか判定する。
登録済みでなければステップＳ１４０３に移行し、ステップＳ１４０３において、挿入キーを含むノード対を処理先のルートノードに設定し、処理先のルートノードとして登録する。続いてステップＳ１４０４に進み、処理先のルートノードを挿入済みノードとして設定して処理を終了する。

上記ステップＳ１４０２での判定結果が登録済みであれば、ステップＳ１４０５に移行する。ステップＳ１４０５では、挿入済みノードが設定済みであるか判定する。この判定処理は、後に説明するツリーの結合処理で必要になるものである。ツリーの分割処理では、最初の挿入処理においてステップＳ１４０４でルートノードを挿入済みノードとして設定することから、ステップＳ１４０６の判定は常に「はい」である。したがって、分割処理だけのためであれば、ステップＳ１４０５とステップＳ１４０７は必須ではない。

ステップＳ１４０５での判定結果が「はい」であればステップＳ１４０６に進み、挿入済みノードとして設定されているノードを処理先の検索開始ノードとして設定し、ステップＳ１４０８に進む。

ステップＳ１４０５での判定結果が「いいえ」であればステップＳ１４０７に進み、ルートノードを処理先の検索開始ノードとして設定し、ステップＳ１４０８に進む。
ステップＳ１４０８では、図１０に示す最大値検索処理により、ステップＳ１４０６あるいはステップＳ１４０７で設定された検索開始ノードから処理先のインデックスキーの最大値を求める。このとき、先に説明したように、探索経路スタックには配列番号とともに弁別ビット位置が格納される。

次にステップＳ１４０９において、ステップＳ１４０１で設定された挿入キーとステップＳ１４０７で得られた最大値により、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する。

続いてステップＳ１４１０に進み、ステップＳ１４０９において挿入キーを含むノード対を挿入された処理先の親ノードを挿入済みノードとして設定し、処理を終了する。
次に、上述のステップＳ１４０３とステップＳ１４０９について詳細に説明する。

図１５Ａは、図１４に示すステップＳ１４０３のルートノード設定処理を説明するフロー図である。
まず、ステップＳ１５０１で配列からノード対が空の代表ノード番号を取得する。

次にステップＳ１５０２において、ステップＳ１５０１で取得した代表ノード番号に値“０”を加えて得た配列番号を、挿入ノードの配列番号として設定しておく。
ステップＳ１５０３に進み、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップＳ１５０２で設定した配列番号の配列要素に格納する。

次にステップＳ１５０４において、挿入ノードの配列番号をルートノードの配列番号として登録して処理を終了する。
なお、上記ステップＳ１５０１〜ステップＳ１５０４の処理は、図６を参照して説明したカップルドノードツリーの生成処理において、ルートノードの配列番号が登録済みでない場合の、ステップＳ６０２〜ステップＳ６０５に対応するものである。

図１５Ｂは、図１４に示すステップＳ１４０９の、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する処理を説明するフロー図である。図１５Ｂに示すフローは、先に図５Ｃを参照して示した挿入処理の応用であり、ステップＳ１５０５の、挿入キーと最大値をビット列として比較して上位０ビット目から見た最初の不一致ビットの位置を求め、それを差分ビット位置を格納するエリアに設定する処理は、図５Ｃに示すステップＳ５１６とステップＳ５１７の処理に対応する。

ステップＳ１５０５に続いてステップＳ１５０６ａに進む。なお、ステップＳ１５０６ａ〜ステップＳ１５１２の処理ブロックは図５Ｃに示すステップＳ５１９ａ〜ステップＳ５２３からなる処理ブロックに相当し、ステップＳ１５１３〜ステップＳ１５１８の処理は図５Ｃに示すステップＳ５２４〜ステップＳ５２８に相当する。

ステップＳ１５０６ａにおいて、先の図１４に示すステップＳ１４０８の最大値検索処理における処理先の探索経路スタックのスタックポインタを１つ戻して、弁別ビット位置を取り出す。

次に、ステップＳ１５０９において、ステップＳ１５０５で設定した差分ビット位置とステップＳ１５０６ａで取り出した弁別ビット位置を比較し、弁別ビット位置が差分ビット位置より上位の位置関係か判定する。

その判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係であれば、ステップＳ１５１２に進み、処理先の探索経路スタックのスタックポインタを１つ戻して配列番号を取り出し、それを親ノードの配列番号エリアに設定してステップＳ１５１３に移行する。

ステップＳ１５０９での判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係でなければ、ステップＳ１５１０に進む。
ステップＳ１５１０では、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。

判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合には、ステップＳ１５０６に戻る。
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指している場合には、ステップＳ１５１１において処理先の探索経路スタックからスタックポインタの指す配列番号を取り出し、処理先の親ノードの配列番号を格納するエリアに設定してステップＳ１５１３に移行する。

以上説明したステップＳ１５０６ａ〜ステップＳ１５１２の処理においては、先の最大値検索処理において探索経路スタックに格納された弁別ビット位置を参照することができるので、本出願人による先の出願である特願２００６−３１９４０７で提案された分割処理の実施例２よりも処理を速くすることができる。

ステップＳ１５１３においては、配列からノード対が空きの代表ノード番号を取得する。
次にステップＳ１５１４において、代表ノード番号に１を加えて得た配列番号を挿入ノードの配列番号を格納するエリアに設定する。

次にステップＳ１５１５において、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップＳ１５１４で設定した配列番号の配列要素に格納する。

次にステップＳ１５１６において、代表ノード番号に０を加えて得た配列番号を、挿入ノードと対をなす対ノードの配列番号を格納するエリアに設定する。
次にステップＳ１５１７において、ステップＳ１５１１あるいはステップＳ１５１２で設定した処理先の親ノードの配列番号の指す配列要素の内容を読み出し、ステップＳ１５１６で設定した対ノードの配列番号の指す配列要素に格納する。

次にステップＳ１５１８において、ブランチノードを形成するため、ノード種別にブランチを、弁別ビット位置にステップＳ１５０５で設定した差分ビット位置を、代表ノード番号にステップＳ１５１６で設定した対ノードの配列番号を設定し、ステップＳ１５１１あるいはステップＳ１５１２で設定した処理先の親ノードの配列番号の指す配列要素に格納して処理を終了する。

図１６は、図１３に示す処理フローにおける削除処理について説明する処理フロー例を示す図である。
最初のステップであるステップＳ１６０１は、図１３に示すステップＳ１３０８に相当するものである。削除ノードに含まれる削除キーは図１３に示すステップＳ１３０４において最小値検索により求められたものであるから、処理元の探索経路スタックには削除キーの格納された配列要素の配列番号がスタックされているので、その配列番号により削除ノードを読み出して削除ノードを格納するエリアに設定する。

次のステップＳ１６０２では、処理元の探索経路スタックに２つ以上の配列番号が格納されているか判定される。このステップＳ１６０２以降、ステップＳ１６０８に至る処理は、図７Ｂに示す削除処理の後段の処理に対応するものである。

処理元の探索経路スタックに２つ以上の配列番号が格納されていなければ、ステップＳ１６０７に移行し、ステップＳ１６０１で設定した削除ノードの配列番号の指すノード対を削除し、ステップＳ１６０８に進み、ルートノードの配列番号を削除して処理を終了する。

処理元の探索経路スタックに２つ以上の配列番号が格納されていれば、ステップＳ１６０３に進み、削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号を格納するエリアに設定する。

次にステップＳ１６０４において、処理先の探索経路スタックのスタックポインタを１つ戻して配列番号を取り出し、削除ノードの直近上位のブランチノードである処理元の親ノードの配列番号格納エリアに設定する。

次にステップＳ１６０５において、ステップＳ１６０３で設定した対ノードの配列番号の指す配列要素の内容を読出し、ステップＳ１６０４で設定した処理元の親ノードの配列番号の指す配列要素に格納する。

次にステップＳ１６０６において、削除ノードの代表ノード番号の指すノード対を削除して処理を終了する。
以上、第２の分割処理について説明したが、第２の分割処理においても、第１の分割処理の場合と同様にインデックスキーの最大値から順に削除を行うことができる。

また、第１の分割処理の場合と同様に分割処理の処理フローをツリーの結合処理に用いることが可能である。結合しようとする２つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上あるいは最小値以下として処理元のツリーの削除処理を行い、削除されたノードを処理先のツリーに挿入する処理を行えばよい。

配列に格納されたカップルドノードツリーの構成例を説明する図である。 カップルドノードツリーのツリー構造を概念的に示す図である。 本発明を実施するためのハードウェア構成例を説明する図である。 本発明におけるビット列検索の基本動作を示すフロー図である。 本発明におけるビット列検索の基本動作をカップルドノードツリーにより説明する図である。 本発明における挿入処理の前段である検索処理の処理フローを示す図である。 挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。 ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。 本発明におけるルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。 削除処理の前段である検索処理の処理フローを示す図である。 削除処理の後段の処理フローを説明する図である。 本発明のカップルドノードツリーに格納されたインデックスキーの最小値を求める処理を示すフロー図である。 本発明のインデックスキーの最小値を求める処理をカップルドノードツリーにより説明する図である 本発明のカップルドノードツリーに格納されたインデックスキーの最大値を求める処理を示すフローチャートである。 本発明のインデックスキーの最大値を求める処理をカップルドノードツリーにより説明する図である。 カップルドノードツリーの第１の分割処理フローを説明する図である。 カップルドノードツリーの第２の分割処理フローを説明する図である。 第２の分割処理におけるノードの挿入処理フローを説明する図である。 第２の分割処理におけるルートノード設定処理を説明するフロー図である。 第２の分割処理における親ノードに挿入キーを含むノード対を挿入する処理フローを説明する図である。 第２の分割処理における削除処理を説明するフロー図である。 従来の検索で用いられるパトリシアツリーの一例を示す図である。

符号の説明

１０、２０、３０ 配列番号
１００ 配列
１０１ ノード
１０２ ノード種別
１０３ 弁別ビット位置
１０４ 代表ノード番号
１１１ ノード対
１１２ ノード［０］、代表ノード
１１３ ノード［１］、代表ノードと対をなすノード
１１８ インデックスキー
３０１ データ処理装置
３０２ 中央処理装置
３０３ キャッシュメモリ
３０４ バス
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ 通信装置
３０８ データ格納装置
３０９ 配列
３１０ 探索経路スタック

Claims (10)

1. ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置において、
   前記ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーと、
   前記ノード対のどちらか一方のノードである検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出手段と、
   前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
   前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
   前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の代表ノードの位置を示す位置情報との演算によりリンク先のノード対のどちらかのノードの位置を示す位置情報を求め、該求めたノードの位置を示す位置情報により示される記憶領域から、該記憶領域に配置されたノードをリンク先ノードとして読み出すリンク手段と、
   を備え、
   前記検索開始ノード読出手段で読み出した検索開始ノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段によりリンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、
   前記インデックスキー読出手段により読み出されたインデックスキーを、前記検索開始ノードをそのルートノードとする前記カップルドノードツリーの部分木の前記検索キーによる検索結果である検索結果キーとするとともに、
   前記検索開始ノードの配置された記憶領域のアドレス情報及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの配置された記憶領域のアドレス情報と前記検索開始ノードから前記リーフノードに至るリンク経路のブランチノードの弁別ビット位置を順次スタックに格納することを特徴とするビット列検索装置。
2. 前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
   前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項１記載のビット列検索装置。
3. ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、前記ツリーに所望のビット列からなる挿入キーをインデックスキーとして格納するインデックスキー挿入方法において、
   前記ツリーは、該ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーであり、
   前記ビット列検索装置は、
   前記ノード対のどちらか一方のノードである検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出手段と、
   前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
   前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
   前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の代表ノードの位置を示す位置情報との演算によりリンク先のノード対のどちらかのノードの位置を示す位置情報を求め、該求めたノードの位置を示す位置情報により示される記憶領域から、該記憶領域に配置されたノードをリンク先ノードとして読み出すリンク手段と、
   を備え、
   前記挿入キーを前記検索キーとして、
   前記ルートノード読出手段でルートノードを読み出し、該読みだしたルートノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出すとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードの位置を示す位置情報と該ブランチノードの弁別ビット位置をスタックに順次格納する検索ステップと、
   前記検索ステップで読み出したインデックスキーと前記挿入キーの間で大小比較とビット列比較を行う比較ステップと、
   ノード対を配置する空の隣接した記憶領域の組を取得し、代表ノードが配置される記憶領域の位置を示す位置情報を取得する空ノード対取得ステップと、
   前記比較ステップにおける前記大小比較により挿入キーを含むリーフノードを前記空ノード対取得ステップで取得した空の隣接した記憶領域の組のどちらの空記憶領域に配置するかを決定するリーフノード格納位置決定ステップと、
   前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置と、前記検索ステップで順次格納されたブランチノードの弁別ビット位置との相対的位置関係により、該ブランチノードの位置を示す位置情報を読み出し、該位置情報が示す記憶領域に配置されているノードを、前記空ノード対取得ステップで取得した空の隣接した記憶領域の組に配置されるノード対のリンク元として該ノード対の挿入位置を決定するノード対挿入位置決定ステップと、
   前記リーフノード格納位置決定ステップで決定した空記憶領域に配置するリーフノードの、ノード種別を格納する領域にリーフノードであることを示すノード種別を、インデックスキーを格納する領域に前記挿入キーを書き込み、もう一方の空記憶領域に、前記ノード対挿入位置決定ステップで読み出したノードの位置を示す位置情報が示す記憶領域に配置されているノードの内容を読み出して書き込むことで挿入ノード対を生成する挿入ノード対生成ステップと、
   前記ノード対挿入位置決定ステップで読み出したノードの位置を示す位置情報が示す記憶領域に配置されているノードをブランチノードとし、そのノード種別を格納する領域にブランチノードであることを示すノード種別を、弁別ビット位置を格納する領域に前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置を、リンク先のノード対の代表ノードの位置を示す前記位置情報を格納する領域に前記空ノード対取得ステップで取得した前記位置情報を、それぞれ書き込むブランチノード生成ステップと、
   を備えたことを特徴とするインデックスキー挿入方法。
4. 前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
   前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項３記載のインデックスキー挿入方法。
5. ビット列検索装置が、ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索方法において、
   前記ツリーは、該ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーであって、
   前記ノード対のどちらか一方のノードである検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出ステップと、
   前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
   前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出ステップと、
   前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の代表ノードの位置を示す位置情報との演算によりリンク先のノード対のどちらかのノードの位置を示す位置情報を求め、該求めたノードの位置を示す位置情報により示される記憶領域から、該記憶領域に配置されたノードをリンク先ノードとして読み出すリンクステップと、
   を備え、
   前記検索開始ノード読出ステップで読み出した検索開始ノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにより前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、
   前記インデックスキー読出ステップにより読み出されたインデックスキーを、前記検索開始ノードをそのルートノードとする前記カップルドノードツリーの部分木の前記検索キーによる検索結果である検索結果キーとするとともに、
   前記検索開始ノードの配置された記憶領域のアドレス情報及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの配置された記憶領域のアドレス情報と前記検索開始ノードから前記リーフノードに至るリンク経路のブランチノードの弁別ビット位置を順次スタックに格納することを特徴とするビット列検索方法。
6. 前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
   前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項５記載のビット列検索方法。
7. ビット列検索装置が、ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索方法において、
   前記ツリーは、該ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーであって、
   前記ルートノード、あるいは、前記ノード対のどちらか一方のノード、である検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出ステップと、
   前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
   前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出ステップと、
   前記ブランチノードのリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出したリンク先のノード対の代表ノードの位置を示す位置情報により示される記憶領域に配置された代表ノードのみをリンク先ノードとして読み出す、あるいは該読み出したリンク先のノード対の代表ノードの位置を示す位置情報に基づいて演算により求める位置情報により示される記憶領域に配置された非代表ノードのみをリンク先ノードとして読み出すリンクステップと、
   を備え、
   前記検索開始ノード読出ステップで読み出した検索開始ノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにより前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、
   前記インデックスキーステップにより読み出されたインデックスキーを、前記検索開始ノードをそのルートノードとする、前記カップルドノードツリーあるいは該カップルドノードツリーの部分木の、前記検索キーによる検索結果であるインデックスキーの最大値あるいは最小値として取得するとともに、
   前記検索開始ノードの配置された記憶領域のアドレス情報及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの配置された記憶領域のアドレス情報と前記検索開始ノードから前記リーフノードに至るリンク経路のブランチノードの弁別ビット位置を順次スタックに格納することを特徴とするビット列検索方法。
8. 前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
   前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項７記載のビット列検索方法。
9. 請求項３又は請求項４記載のインデックスキー挿入方法、請求項５〜請求項８記載のビット列検索方法のいずれか１つの方法をコンピュータに実行させるためのプログラム。
10. 請求項９記載のプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
    

Images