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

Description

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

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

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

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

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

ノード１７５０ｃから実線で接続された部分はノード１７５０ｃの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ１７４０ｃは、その欄が空欄であることを示している。点線の接続された右ポインタ１７４１ｃの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード１７５０ｃを右ポインタ１７４１ｃが指定していることを表している。ノード１７５０ｄの右ポインタ１７４１ｄはノード１７５０ｄ自身を指しており、左リンク１７４０ｄにはノード１７５０ｅが接続されている。ノード１７５０ｅの保持するインデックスキーは“０１００１０”、検査ビット位置１７３０ｅは５である。ノード１７５０ｅの左ポインタ１７４０ｅはノード１７５０ｂを、右ポインタ１７４１ｅはノード１７５０ｅを指している。

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

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

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

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

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

また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願２００６−２９３６１９において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの一般化された検索あるいはインデックスキーの最大値／最小値を求める手法及びカップルドノードツリーに格納されたインデックスキーを昇順または降順に取り出す手法等を提案した。一般化された検索手法であるカップルドノードツリーの任意のノードを検索開始ノードとする検索は、前記検索開始ノードをルートノードとするカップルドノードツリーの任意の部分木を検索対象として、検索キーによる検索を実行するものである。その検索は、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより行われ、前記リーフノードに含まれるインデックスキーが、検索結果キーとして得られる。

インデックスキーの最大値／最小値を求める手法は、代表ノードあるいは代表ノードと対を成すノード（以下、非代表ノードということがある。）のみをリーフノードに至るまでリンクするものであり、カップルドノードツリーに格納されたインデックスキーを昇順または降順に取り出す手法は、特許文献２で説明したように、インデックスキーはカップルドノードツリーにおいて、順序性をもって配置されていることを利用したものであり、検索開始ノードを前記順序性に基づいて変更しながら最小値検索または最大値検索を繰り返すものである。また、上記各出願において、カップルドノードツリーを配列に配置すること、上記提案した各検索処理における検索開始ノードからのツリー上の探索経路のノードの配列番号を探索経路スタックに順次スタックし、探索経路スタックにスタックされた配列番号を用いた処理も開示した。

また、本出願人は、特願２００７−１１４９１５において、リーフノードにインデックスキーに替えてインデックスキーを格納した記憶領域の位置情報を格納したカップルドノードツリーの構造とそれを用いた検索処理を提案した。
さらに本出願人は、特願２００８−７６９０において、複数のキーによる検索のためのカップルドノードツリーであって、複数のキーが直列に連結され、末尾のキーはユニークキーであることを条件としたキー列による検索を行うカップルドノードツリーの構造とそれを用いた検索処理を提案した。
特開２００１−３５７０７０号公報 特開２００８−０１５８７２号公報

上記特願２００８−７６９０で提案したカップルドノードツリーを用いた検索においては、キー列を構成するキー毎に順次直列的に処理を行うものであるから、キー列を構成するキーの数が増えるとそれだけ処理時間が増加する。
また地図上の地点のように２次元座標で位置が表される点を検索する場合、Ｘ座標とＹ座標について順次それぞれ検索をしているが、地図上の検索対象が増えるにつれて、その検索効率を向上させることが求められてきている。
また、３次元空間内の点を検索する場合でも、事情は同じである。

そこで本発明の目的は、複数のキーからなるキー列による検索において、検索処理の高速化をより一層高めることの可能なツリー構造とそれを用いた検索手法を提供することである。

まず、本発明によるカップルドノードツリーは、上記特願２００８−７６９０で提案したものと同様に、複数のキーからなるキー列（以下、多次元キーということがある。）を検索の対象とするが、特願２００８−７６９０で提案したものとは、末尾のキーがユニークである必要がないという点で異なる。また、上記各出願において提案したカップルドノードツリーのツリー構造は、ノード対がツリー状にリンクしたものであったが、それに対して本発明によるカップルドノードツリーのツリー構造は、隣接した記憶領域に配置される４つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたものである。本発明のブランチノードは、リンク先のノード群の１つのノードである代表ノードの位置を示す第一の位置情報を含み、リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキー自体を含み、空ノードは該空ノードが空状態であることを示す情報を含む。

既提案のノード対が代表ノードとそれと対をなすノードから構成されるのに対して、本発明のノード群の各ノードは、キー列を構成する各キーのビット値の組み合わせに対応する位置に配置される。すなわち本発明のノード群は、一次元のノード対を多次元に拡張したいわば多重カップルドノードであり、本発明のカップルドノードツリー（以下、多重カップルドノードツリーということがある。）は、従来の一次元のカップルドノードツリーを多次元のものに拡張したものである。
キー列（以下、多次元キーあるいはインデックスキーということがある。）の検索においては、ブランチノードに含まれる弁別ビット位置の検索キー列の各キーのビット値に応じたノード位置により代表ノードの属するノード群の１つのノードにリンクすることを順次繰り返すことにより実現する。

本発明によれば、検索キー列の各キーのビット値に応じたノード位置によりノード群の１つのノードにリンクするので、キー毎の分岐処理を直列に行うことがなく、ツリーの分岐の階層を小さくできるので、処理効率を向上することができる。

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

また、主としてキー列として２つのキーから構成されるものを例示して説明する。したがって、本実施態様のカップルドノードツリーをダブル・カップルドノードツリー、あるいは単にツリーということがある。また、キー列（インデックスキー）を２次元キーということがある。さらに、リーフノードにはインデックスキーの格納された記憶領域の位置情報を含むものとして説明するが、リーフノードに直接インデックスキーを格納することもできる。しかし、先の出願である特願２００７−１１４９１５において説明したように、インデックスキー（本願の場合はキー列）の長さが長くなる場合には、インデックスキーをリーフノードに格納せず他の記憶領域に格納し、リーフノードには該記憶領域の位置情報を格納することにより、ノードを格納する記憶領域を効率的に使用することができる。

図２Ａは、本発明の一実施形態における配列に格納されたダブル・カップルドノードツリーの構成例を説明する図である。上述の特願２００７−１１４９１５で提案したものとは、各ノードが空ノードであるか使用中であるかを示す情報であるノード状態を含む点のみで異なる。
本発明によれば、カップルドノードツリーのツリー構造におけるノードは、多次元キーを構成する各キーのビット値の組み合わせに対応する位置に配置されたノードから構成されるノード群であるので、ある多次元キーの集合に対して多重カップルドノードツリーを生成したとき、あるノード群のあるノード位置に対応する多次元キーが存在しないことがあり得る。したがって、ノード種別とは別にノード状態を設けてそのノード位置のノードが空であるか使用中であるかを識別するものである。

図２Ａを参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード状態１０２ａ、ノード種別１０２ｂ、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード状態１０２ａの値は１であり、ノード１０１が使用中であることを示している。ノード種別１０２ｂの値は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード群１１１の代表ノードの配列番号２０が格納されている。配列番号は上記第一の位置情報の具体例である。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。

配列番号２０の配列要素には、ノード群１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）にはノード［１］１１３が、その次の配列要素（配列番号２０＋２）にはノード［２］１１２ａが、さらにその次の配列要素（配列番号２０＋３）にはノード［３］１１３ａが格納されている。
ノード［０］１１２はノード１０１と同様にブランチノードである。ノード［０］１１２のノード状態１１４ａには１が、ノード種別１１４ｂには０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。ノード［１］１１３とノード［２］１１２ａのノード状態はともに０であり、空ノードであることを示している。
ノード［３］１１３ａは、ノード状態１１７ａ、ノード種別１１７ｂ及び参照ポインタ１１８ａで構成されている。ノード状態１１７ａ及びノード種別１１７ｂには１が格納されており、ノード［３］１１３ａがリーフノードであることを示している。参照ポインタ１１８ａには、インデックスキーの記憶領域を参照するポインタが格納されている。参照ポインタ１１８ａに格納されたデータは、上記の第二の位置情報の具体例である。以下では表記の簡略化のため、参照ポインタに格納されたデータのことも参照ポインタという。
パトリシアツリーについて先に述べたと同様に、インデックスキーと対応するレコードにアクセスするためのアクセス先情報も当然必要である。インデックスキーとアクセス先情報との対応づけは、例えば、インデックスキーを記憶している記憶領域に隣接する記憶領域に、当該インデックスキーに対応するアクセス先情報を記憶することによって行ってもよい。以下ではアクセス先情報については省略して説明する。
配列番号３０の配列要素に格納されたノード１２２、ノード１２３、ノード１２２ａ及びノード１２３ａからなるノード群１２１の内容は省略されている。

ノード［０］１１２、ノード［１］１１３、ノード［２］１１２ａ、ノード［３］１１３ａ及びノード１２２、ノード１２３、ノード１２２ａ、ノード１２３ａの格納された配列要素にそれぞれ付された００、０１、１０、１１は、各ノードのノード群におけるノード位置を２進表示で示すものである。代表ノードの格納された配列要素の配列番号にノード位置を加えることにより、該ノード位置のノードの格納された配列要素の配列番号が求められる。 なお、ノード位置が００である代表ノードをノード［０］で表し、ノード位置０１、１０、１１のノードをそれぞれノード［１］、ノード「２」、ノード［３］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
ノード位置は、検索キー列で検索を行う場合にノード群のどのノードにリンクするかを示すものである。すなわち、検索キー列のうち第１のキーの弁別ビット位置にあるビット値と第２のキーの弁別ビット位置にあるビット値からなる２ビットの値を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、該ブランチノードの弁別ビット位置にある検索キー列の第１のキーのビット値と第２のキーのビット値からなる２ビットの値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード群の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。また、代表ノードのノード位置も任意の位置に決定することができることも明らかである。

図２Ｂは、本実施形態に係るダブル・カップルドノードツリーのツリー構造と２次元キー（インデックスキー）の格納領域を概念的に示す図である。
図２Ｂの（１）に示すのはダブル・カップルドノードツリーのツリー構造である。符号２１０ａで示すのがルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード群２０１ａの代表ノードとしている。
ツリー構造としては、ルートノード２１０ａの下にノード群２０１ｂが、その下層にノード群２０１ｃとノード群２０１ｆが配置され、ノード群２０１ｆの下層にはノード群２０１ｇが配置されている。ノード群２０１ｃの下にはノード群２０１ｅが配置されている。
各ノードの前に付された００、０１、１０、１１の符号は、図２Ａにおいて説明した配列要素の前に付された符号と同じでありノード位置を示す。検索キー列の各キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のインデックスキーに対応するリーフノードを見つけることになる。

図示された例では、ルートノード２１０ａのノード状態２４０ａは１、ノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード群２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
ノード群２０１ｂはノード２１０ｂ、２１１ｂ、２１２ｂ、２１３ｂで構成される。ノード位置が１１であるノード２１３ｂのノード状態２４３ｂのみが０で空ノードであることを示している。ノード位置１１のノードが空ノードであるということは、上位のブランチノード２１０ａの弁別ビット位置２３０ａに格納された値０のビット位置の第１のキーと第２のキーのビット値がともに１である２次元キーが、図２Ｂの（２）に示すインデックスキーの格納領域３１１に存在しないことを反映している。
ノード２１０ｂのノード状態２４０ｂは１で、ノード２１１ｂ、２１２ｂのノード状態もノード２１０ｂのノード状態２４０ｂと同様に１であって使用中であることを示している。それらのノードのうち、ノード２１０ｂとノード２１２ｂのノード種別２６０ｂ、２６２ｂはともに０であり、ブランチノードであることを示している。
ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード群２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。ノード２１２ｂの弁別ビット位置２３２ｂには１が格納され、リンク先の代表ノード番号にはノード群２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２２ｂが格納されている。

一方、ノード２１１ｂのノード種別２６１ｂは１でありノード２１１ｂはリーフノードであるので参照ポインタ２５１ｂを含む。参照ポインタ２５１ｂには、第１のキー２９１ｄの値が“０１１０１０”、第２のキー２９１ｄ’の値が“１０００００”というキー列（２次元キー）を格納した記憶領域を示す参照ポインタ２８１ｄが格納されている。参照ポインタ２５１ｂに格納されたデータのことも参照ポインタといい、符号２８１ｄにより表す。他のリーフノードでも同様に、参照ポインタと参照ポインタに格納されたデータを同じ参照ポインタという語で表す。また、以下の説明において、２次元キーについて、“０１１０１０：１０００００”のような表記及び２９１ｄ、２９１ｄ’のような表記を用いることがある。
ノード群２０１ｂのノード位置０１に参照ポインタ２８１ｄを格納したリーフノード２１１ｂが存在することは、参照ポインタ２８１ｄで参照するインデックスキーの、ノード群２０１ｂの直近上位のブランチノード２１０ａの弁別ビット位置２３０ａで示されるビット位置０のビット値が、第１のキー２９０ｄが“０”、第２のキー２９０ｄ’が“１”であり、そのようなビット値の組み合わせのインデックスキーがほかにないことに対応している。
一方、ノード群２０１ｂのノード位置００とノード位置１０のノードがブランチノードであるのは、ブランチノード２１０ａの弁別ビット位置２３０ａで示されるビット位置０の第１のキーと第２のキーのビット値の組み合わせが００のものと１０のインデックスキーが２つ以上存在し、ビット位置０より下位のビット位置のビット値によりそれらのインデックスキーが弁別されることに対応している。

ブランチノード２１０ｂのリンク先であるノード２１０ｃのノード状態２４０ｃには０が格納されているので、このノードは空ノードであり、ノード位置が１０のノード２１２ｃもノード状態が０であって空ノードである。ノード位置が０１のノード２１１ｃのノード状態は１、ノード種別２６１ｃは１であるのでノード２１１ｃはリーフノードである。したがって、参照ポインタ２５１ｃを含んでいる。参照ポインタ２５１ｃには、図示の例では、第１のキー２９０ｃと第２のキー２９０ｃ’からなる２次元キーが格納されている記憶領域を参照するポインタ２８０ｃが格納されている。
インデックス格納領域３１１の参照ポインタ２８０ｃが指すエントリの第１のキー２９０ｃには“０００１１１”が、第２のキー２９０ｃ’には“０１１１００”が格納されている。ノード群２０１ｃの直近上位のブランチノード２１０ｂの弁別ビット位置２３０ｂで示されるビット位置１のビット値は、第１のキー２９０ｃが“０”、第２のキー２９０ｃ’が“１”である。リーフノード２１１ｂについて説明したと同様に、そのようなビット値の組み合わせのインデックスキーがほかにないことが、ノード群２０１ｃのノード位置０１に参照ポインタ２８０ｃを格納したリーフノード２１１ｃが存在することに対応している。
ノード位置１１のノード２１３ｃのノード状態２４３ｃは１、ノード種別２６３ｃは０であるので、ノード２１３ｃはブランチノードである。弁別ビット位置２３３ｃは２であり、代表ノード番号にはノード群２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２３ｃが格納されている。

ノード群２０１ｅのノード位置００のノード２１０ｅのノード状態２４０ｅは０なのでノード２１０ｅは空ノードであり、同様にノード位置０１のノード２１１ｅも空ノードである。
ノード位置１０と１１のノード２１２ｅ、２１３ｅのノード状態２４２ｅ、２４３ｅはともに１、ノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示している。ノード２１２ｅ、２１３ｅの参照ポインタ２５２ｅ、２５３ｅにはそれぞれ、“０１１０１０：０１０１００”というキー列２９０ｅ、２９０ｅ’と、“０１１０１０：０１１０００”というキー列２９１ｅ、２９１ｅ’を格納した記憶領域への参照ポインタ２８０ｅ、２８１ｅが格納されている。

ノード群２０１ｂのブランチノード２１２ｂのリンク先であるノード群２０１ｆの代表ノードであるノード２１０ｆのノード状態２４０ｆは１、ノード位置０１のノード２１１ｆのノード状態２４１ｆも同じく１である。ノード２１０ｆのノード種別２６０ｆは０でありノード２１０ｆはブランチノードである。ノード２１０ｆの弁別ビット位置２３０ｆには２が格納されている。ノード２１０ｆの代表ノード番号にはノード群２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納されている。ノード２１１ｆのノード種別２６１ｆは１でありノード２１１ｆはリーフノードである。ノード２１１ｆの参照ポインタ２５１ｆには“１０００１０：０１００００”というキー列２９０ｇ、２９０ｇ’を格納した記憶領域への参照ポインタ２８０ｇが格納されている。
ノード位置１１のノード２１３ｆのノード状態２４３ｆは０でありノード２１３ｆは空ノードであり、同様にノード２１２ｆもノード状態２４２ｆが０であるので空ノードである。

ブランチノード２１０ｆのリンク先であるノード群２０１ｇのノード位置００のノード２１０ｇのノード状態は０であり、ノード２１０ｇが空ノードであることを示している。ノード位置０１、１０、１１のノード２１１ｇ、２１２ｇ、２１３ｇのノード状態２４１ｇ、２４２ｇ、２４３ｇは１、ノード種別２６１ｇ、２６２ｇ、２６３ｇは１であり、ノード２１１ｇ、２１２ｇ、２１３ｇはリーフノードである。ノード２１１ｇ、２１２ｇ、２１３ｇのそれぞれの参照ポインタ２５１ｇ、２５２ｇ、２５３ｇには、“１０００１１：００１１００”というキー列２９１ｇ、２９１ｇ’を格納した記憶領域への参照ポインタ２８１ｇ、“１０１１００：００１０００”というキー列２９１ｈ、２９１ｈ’を格納した記憶領域への参照ポインタ２８１ｈ、“１０１１００：００１０００”というキー列２９０ｈ、２９０ｈ’ を格納した記憶領域への参照ポインタ２８０ｈが格納されている。

図２Ｂの（２）には、複数のインデックスキーの記憶領域が連続して設けられる例を示し、それら連続した記憶領域全体をインデックスキーの記憶領域３１１として示したが、インデックスキーは連続した領域に格納されなくてもよい。また、リーフノード同士のツリー構造上での関係と、インデックスキーの記憶領域３１１におけるインデックスキーの配置順は無関係であってもよい。

以下、上述のツリーから第１のキー“１０１１００” と第２のキー“００１０００”からなる２次元キー（インデックスキー）を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、第１のキー“１０１１００” と第２のキー“００１０００”からなるキー列を検索キー列としてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー列の第１のキー“１０１１００”及び第２のキー“００１０００”のビット位置が０のビット値をみるとそれぞれ１と０である。そこで代表ノード番号の格納された配列番号２２０ａに２進数表示で“１０”、すなわち２を加えた配列番号の配列要素に格納されたノード位置１０のノード２１２ｂにリンクする。
次に、ノード２１２ｂの弁別ビット位置２３２ｂには１が格納されているので、第１のキー“１０１１００”
及び第２のキー“００１０００”のビット位置が１のビット値をみるとそれぞれ０と０であるから、代表ノード番号の格納された配列番号２２２ｂの配列要素に格納されたノード２１０ｆにリンクする。
ノード２１０ｆの弁別ビット位置２３０ｆには２が格納されているので、第１のキー“１０１１００” 及び第２のキー“００１０００”のビット位置が２のビット値をみるとそれぞれ１である。そこで代表ノード番号の格納された配列番号２２０ｆに２進数表示で“１１”、すなわち３を加えた配列番号の配列要素に格納されたノード位置１１のノード２１３ｇにリンクする。
ノード２１３ｇのノード種別２６３ｇは１でありリーフノードであることを示しているので、参照ポインタ２８０ｈにより示される記憶領域を参照し、そこに格納されたインデックスキー２９０ｈ、２９０ｈ’を読み出す。このようにしてカップルドノードツリーを用いた検索が行われる。読み出されたインデックスキーを検索キーと比較すると、上記の例の場合は一致していることが分かる。

次に、図２Ｂを参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図２Ｂの例で、ルートノード２１０ａの弁別ビット位置２３０ａが０であるのは、インデックスキーを構成する第１のキーと第２のキーの０ビット目の組み合わせに異なるものがあるからである。第１のキーおよび第２のキーの０ビット目の組み合わせが００のインデックスキーのグループはノード位置００のノード２１０ｂの下に分類され、前記０ビット目の組み合わせが０１のインデックスキーのグループはノード位置０１のノード２１１ｂの下に分類され、前記０ビット目の組み合わせが１０のインデックスキーのグループはノード位置１０のノード２１２ｂの下に分類され、前記０ビット目の組み合わせが１１のインデックスキーのグループはノード位置１１のノード２１３ｂの下に分類される。
先に述べたように、第１のキーおよび第２のキーの０ビット目の組み合わせが１１のインデックスキーは存在しないことから、ノード２１３ｂは空ノードとなっている。また、ノード位置０１のノード２１１ｂがリーフノードであるのは、０ビット目のビット値の組み合わせが０１であるインデックスキーがほかになく、０ビット目より下位のビットのビット値によりインデックスキーを弁別する必要のないことに対応している。
ノード２１０ｂの弁別ビット位置２３０ｂが１であるのは、その下位のリーフノード２１１ｃ、２１２ｅ、２１３ｅに対応するインデックスキーの第１のキー及び第２のキーの１ビット目より上位のビット値がすべて等しく（０ビット目の組み合わせがすべて００）、１ビット目の組み合わせに異なるものがあるという、インデックスキーの集合の性質を反映している。
同様に、ノード２１２ｂの弁別ビット位置２３２ｂが１であるのは、その下位のリーフノード２１１ｆ、２１１ｇ、２１２ｇ、２１３ｇに対応するインデックスキーの第１のキーおよび第２のキーの１ビット目より上位のビット値がすべて等しく（０ビット目の組み合わせがすべて１０）、１ビット目の組み合わせに異なるものがあるという、インデックスキーの集合の性質を反映している。
上記インデックスキーの集合の性質が反映されていることは、ノード群２０１ｃ、２０１ｅ、２０１ｆ、２０１ｇにおいても同様である。

仮にインデックスキーの集合に、第１のキー２９１ｈ“１０１１００”、第２のキー２９１ｈ’“０００１００”からなるインデックスキーの代わりに第１のキー“１０１００１”、第２のキー“０００００１”からなるインデックスキーが含まれていたとしても、第１のキーと第２のキーの２ビット目まではそれぞれ第１のキー２９１ｈと第２のキー２９１ｈ’の２ビット目までと等しいので、ノード２１２ｇの参照ポインタ２８１ｈにより示される記憶領域に格納されるインデックスキーの値が変わるだけで、ツリー構造自体は変わることはない。しかし、第１のキー２９１ｈ“１０１１００”、第２のキー２９１ｈ’“０００１００”からなるインデックスキーに加えて第１のキー“１０１１００”と第２のキー“００００００”
からなるインデックスキーが含まれていると、ノード２１２ｇはブランチノードとなり、その弁別ビット位置は３であり、該インデックスキーに係るリーフノードは、ノード２１２ｇのリンク先のノード群のノード位置１０に配置される。

上述のようにカップルドノードツリーの構造はインデックスキーの集合の性質を反映しているので、使用中のノードが１つだけのノード群は存在しない。ノード群のノード位置に配置されるノードは、その直近上位のブランチノードの弁別ビット位置のビット値の組み合わせで互いに弁別されるものであるから、互いに弁別される相手のノードが存在する。したがって、使用中のノードが１つだけということはありえないからである。
例えば、図２Ｂに示すツリーにおいて、仮にノード２１２ｅの参照ポインタ２８０ｅが指すインデックスキーがインデックスキーの格納領域３１１に存在せず、ノード２１２ｅが空ノードで、ノード群２０１ｅの使用中のノードが２１３ｅだけであるとすると、ブランチノード２１３ｃの弁別ビット位置２３３ｃに格納されたビット位置２のビット値により、リーフノード２１３ｃの参照ポインタ２８１ｅが指すインデックスキーを弁別する必要はない。 そのかわり、ブランチノード２１０ｂの弁別ビット位置２３０ｂに格納されたビット位置１のビット値の組み合わせ１１により、リーフノード２１３ｃの参照ポインタ２８０ｃが指すインデックスキーと弁別されることになる。すなわち、リーフノード２１３ｅはノード群２０１ｃのノード位置１１に配置されることになり、ノード群２０１ｅのノードは全て空となり、ノード群２０１ｅはツリー上に存在しなくなる。
また、ノード２１１ｆが空ノードの場合にも、ブランチノード２１０ｆはノード群２０１ｂのノード位置２１２ｂに配置され、ノード群２０１ｆは不要となり、削除される。
以上説明したように、カップルドノードツリーの構造は、多次元キーの集合に含まれる多次元キーを構成するキーの各ビット位置のビット値により決定される。

検索キー列で検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キー列が“１０１１００：０００１００”であれば、図２Ｂに示すツリーではノード２１２ｇに到達することができる。また、上記説明からも想像がつくように、“１０１０００：０００００１”を検索キー列とした場合でもノード２１２ｇにたどり着き、参照ポインタ２８１ｈにより示される記憶領域に格納されたインデックスキーが検索結果キー列として得られる。
このように、カップルドノードツリーに格納されたインデックスキー（キー列）の各キーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。

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

図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、配列３０９は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。以下の説明では、先に述べた参照ポインタ等の場合と同様に、一時記憶領域に格納されたあるいは設定された値を一時記憶領域の名前で呼ぶことがある。
図３に示した例では、カップルドノードツリーのノードを格納した配列要素からなる配列３０９と、インデックスキーの記憶領域３１１とは別の領域である。したがって、リーフノードを格納した配列要素にインデックスキーが含まれる場合に比べて、図３の構成では、一般に１つの配列要素に必要な記憶領域の量が少ない。つまり、カップルドノードツリーを格納する配列３０９からインデックスキーの記憶領域３１１を分離することによって、キャッシュメモリ３０３へのカップルドノードツリーの読み込みにおいて１キャッシュブロックあたりに格納されるノード数を増やすことが可能となる。それにより、後述する検索処理等においてキャッシュミスの頻度が減って処理がより高速に行われるようになる。

次に、本発明の一実施態様に係るカップルドノードツリーを用いた基本的な操作である、検索、挿入、削除について順に詳しく説明する
図４は、本発明の一実施形態におけるビット列の検索処理を示すフローチャートである。検索キー列は与えられているものとする。
まず、ステップＳ４０１において、検索開始ノードを設定する。検索開始ノードの設定は、検索開始ノードの配列番号の指定あるいは取得によりその配列番号、あるいは該配列番号のノードを図示しない検索開始ノード設定エリアに設定することにより行う。なお、上述の検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置」の１つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。検索開始ノード以外についても同様である。

次に、ステップＳ４０２で、探索経路スタックに取得された配列番号を格納し、ステップＳ４０３で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。ステップＳ４０４ａで読み出したノードからノード状態を取り出し、ステップＳ４０４ｂでノード状態は使用中か判定する。使用中でない、すなわち空ノードであれば、検索結果が空ノードであることを表示して検索処理を終了する。ノード状態が使用中であれば、ステップＳ４０４で、読み出したノードから、ノード種別を取り出し、ステップＳ４０５で、ノード種別がブランチノードであるか否かを判定する。

ステップＳ４０５の判定において、読み出したノードがブランチノードである場合はステップＳ４０６に移行し、ステップＳ４０３で読み出したノードから弁別ビット位置を取り出す。次にステップＳ４０７ａにおいて列位置に０を設定してステップＳ４０７ｂに進む。列位置は次に説明するステップＳ４０７ｂ〜Ｓ４０７ｅのループで処理をするキーの検索キー列中の位置を示すものである。列位置の初期値をこの例では０としている。
ステップＳ４０７ｂでは、すべてのキーを処理済みか判定する。すべてのキーを処理済みであればステップＳ４０８に移行し、処理済みでなければステップＳ４０７ｃに進む。
ステップＳ４０７ｃにおいては、検索キー列から列位置の指すキーを取り出し、ステップＳ４０６で取り出した弁別ビット位置の指すビット値を取り出す。次にステップＳ４０７ｄにおいて、ノード位置と名付けるワークエリアの、列位置の指すビット位置に、ステップＳ４０７ｃで取り出したビット値を設定する。次にステップＳ４０７ｅで列位置を更新してステップＳ４０７ｂに戻る。上記ステップＳ４０７ｂ〜Ｓ４０７ｅのループ処理は、リンク先のノードのノード位置を決定するものである。

ステップＳ４０８では、ステップＳ４０３で読み出したノードから代表ノード番号を取り出し、ステップＳ４０９ａに進んで、ステップＳ４０７ｄで設定したノード位置と代表ノード番号とを加算し、新たな配列番号として、ステップＳ４０２に戻る。
以降、ステップＳ４０５の判定においてリーフノードと判定されてステップＳ４１０ａに進むまで、ステップＳ４０２からステップＳ４０９ａまでの処理を繰り返す。ステップＳ４１０ａでは、リーフノードから参照ポインタを取り出し、検索を終了する。なお、リーフノードに直接インデックスキーを格納する場合には、リーフノードからインデックスキーを取り出して検索を終了することになるので、以下の説明においては、「リーフノードから参照ポインタあるいはインデックスキーを取り出し」のような表記を用いることがある。

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

図５は挿入処理の前段である検索処理の処理フローを示す図であり、図４に示した検索処理において、挿入キー列を検索キー列とし、検索開始ノードをルートノードとしたものに相当する。
まず、ステップＳ５０１ａで検索開始ノードにルートノードの配列番号を設定し、ステップＳ５０１ｂで検索キー列に挿入キー列を設定する。インデックスキーへの参照ポインタをリーフノードに格納する実施態様においては、挿入キー列は、挿入処理の前提条件として、予めインデックスキーの格納領域のポインタを取得して、該格納領域に格納されているものとする。
次にステップＳ５１０ａにおいて、検索キー列により検索開始ノードより図４に示す検索処理を行う。次にステップＳ５１０ｂにおいてステップＳ５１０ａの検索結果を判定し、検索結果が空ノード、すなわちノード状態が使用中でなければステップＳ５１０ｃに進み、ステップＳ５１０ａで実行した図４に示す検索処理のステップＳ４０９ａで得た配列番号の指す配列要素の、ノード状態に使用中を、ノード種別にリーフを、参照ポインタに挿入キー列のポインタを書き込み、挿入処理を終了する。インデックスキーを直接リーフノードに格納する場合は、インデックスキーとして挿入キー列を書き込んで挿入処理を終了する。

ステップＳ５１０ｂの判定結果がノード状態は使用中であれば、ステップＳ５１０ｄにおいて、ステップＳ５１０ａの検索結果で得られた参照ポインタの指すキー列を取り出して比較キー列に設定する。次にステップＳ５１０ｅにおいて、挿入キー列と比較キー列を比較して、挿入キー列と比較キー列が完全に一致するか否かと、挿入キー列と比較キー列の差分ビット位置を得る。挿入キー列と比較キー列の差分ビット位置は、挿入キー列の各キーと比較キー列の各キーをビット列として比較し、各キーにおいて最初に異なるビット値となるビット位置のうち最上位のビット位置とする。ステップＳ５１０ｅの詳細は、後に図７Ａを参照して説明する。
次にステップＳ５１１ａにおいて、ステップＳ５１０ｅでの比較の結果が、挿入キー列のキーと比較キー列のキーが全て等しいものであったかを判定し、等しければ挿入キー列は既にカップルドノードツリーの参照ポインタが指す記憶領域に存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図６ＡのステップＳ５１２以下の処理に進む。

図６Ａは、挿入するノード群のための配列要素を準備する処理を説明する処理フロー図である。
ステップＳ５１２において、配列から空きのノード群を求め、そのノード群のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップＳ５１３ａにおいて、ステップＳ５１０ｅで得た挿入キー列と比較キー列の差分ビット位置により挿入ノード位置及び対ノード位置を得る。ステップＳ５１３ａの詳細は、後に図７Ｂを参照して説明する。
次にステップＳ５１４ａに進み、ステップＳ５１２で得た代表ノードの配列番号にステップＳ５１３ａで得たノード位置を加算した配列番号を得る。次にステップＳ５１５ｂに進み、ステップＳ５１２で得た代表ノードの配列番号にステップＳ５１３ａで得た対ノード位置を加算した配列番号を得る。後に図７Ｂを参照して詳細に説明するが、ステップＳ５１４ａで得た配列番号は、挿入キー列をインデックスキーとして格納する記憶領域への参照ポインタを持つリーフノードが格納される配列要素の配列番号である。ステップＳ５１５ｂで得た配列番号は、比較キー列に設定したキー列の参照ポインタ持つリーフノードの直近上位のブランチノードが格納される配列要素のものである。つまり、前段の検索処理で得られたリーフノードに対応するインデックスキーと挿入キー列の差分ビット位置における各キーのビット値の組み合わせにより、挿入されるノード群のうちどのノード位置に挿入キー列への参照ポインタを保持するリーフノード及び前段の検索処理で得られたリーフノードの直近上位のブランチノードが格納されるかが決定される。
さらにステップＳ５１７ａにおいて、ステップＳ５１０ｅで得た差分ビット位置を、差分ビット位置と名付けるワークエリアに設定し、図６Ｂに示すステップＳ５１８に進む。

図６Ｂは図６Ａで準備された配列要素にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
ステップＳ５１８〜ステップＳ５２３までの処理は、挿入するノード群のカップルドノードツリー上の位置を求める処理であり、ステップＳ５２４以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
ステップＳ５１８において、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップＳ５２４に移行し、指していなければステップＳ５１９に進む。

ステップＳ５１９において、探索経路スタックのスタックポインタを１つ戻してそこにスタックされている配列番号を取り出す。
ステップＳ５２０に進み、ステップＳ５１９で取り出した配列番号の配列要素を配列からノードとして読み出す。次にステップＳ５２１において、ステップＳ５２０で読み出したノードから、弁別ビット位置を取り出し、ステップＳ５２２に進み、ステップＳ５２１で取り出した弁別ビット位置がステップＳ５１７ａで設定した差分ビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
ステップＳ５２２の判定結果が否定であれば、ステップＳ５１８に戻り、ステップＳ５１８での判定が肯定になるか、ステップＳ５２２での判定が肯定になるまでステップＳ５１８〜ステップＳ５２２の処理を繰り返す。ステップＳ５２２での判定が肯定になると、ステップＳ５２３に進む。ステップＳ５２３では、探索経路スタックのスタックポインタを１つ進め、ステップＳ５２４以下の処理に移行する。

上記ステップＳ５１８〜ステップＳ５２３で説明した処理は、挿入するノード群の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの差分ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの直近下位のブランチノードのリンク先を挿入するノード群の挿入位置とするものである。
また、探索経路スタックを逆にたどりルートノードに至った場合は、ルートノードのリンク先が挿入位置となる。

例えば図２Ｂのカップルドノードツリーにインデックスキー “１０１０００：００１０００”を挿入するとき、検索結果のインデックスキーは、ノード２１３ｇに対応するインデックスキー “１０１１００：００１０００”になる。この例の場合、挿入キー列と比較キー列の差分ビット位置は３であり、弁別ビット位置２３０ｆは２なので、ノード２１０ｆの直近下位のノード２１３ｇのリンク先が挿入位置になる。つまり、ノード２１３ｇはブランチノードとなり、その弁別ビット位置は挿入キー列と比較キー列の差分ビット位置３となり、リンク先として挿入されるノード群のノード位置００に挿入キー列に対応するリーフノードが配置され、ノード位置１０にノード２１３ｇの内容が転写されたリーフノードが配置される。

次に、ステップＳ５２４以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップＳ５２４では探索経路スタックからスタックポインタの指す配列番号を取り出す。
ステップＳ５２５ａに進み、ステップＳ５１４ａで得た配列番号の指す配列要素の、ノード状態に使用中を、ノード種別にリーフを、参照ポインタに挿入キー列のポインタをあるいはインデックスキーとして挿入キー列を書き込む。
ステップＳ５２６に進み、配列からステップＳ５２４で得た配列番号の配列要素を読み出す。
次にステップＳ５２７において、ステップＳ５１５ｂで得た配列番号の配列要素にステップＳ５２６で読み出した内容を書き込む。
最後にステップＳ５２８ａにおいて、ステップＳ５２４で得た配列番号の指す配列要素のノード状態に使用中を、ノード種別にブランチを、弁別ビット位置にステップＳ５１７ａで設定した差分ビット位置を、代表ノード番号にステップＳ５１２で得た配列番号を書き込み、処理を終了する。

図７Ａは、図５に示すステップＳ５１０ｅの挿入キー列と比較キー列の差分ビット位置を得る処理を詳細に説明する図である。図７Ａに示す処理により得られる挿入キー列と比較キー列の差分ビット位置は、下記説明から明らかなとおり、挿入キー列と比較キー列の各キーの間の差分ビット位置の最小値である。

図に示すように、ステップＳ７０１において列位置に初期値として０を設定する。また、ステップＳ７０２において差分ビット位置に初期値として、差分ビット位置の最大値を設定する。キー列を構成するキーがｎビットからなるビット列であり先頭のビット位置を０とすれば、差分ビット位置の初期値はｎ−１となる。
次にステップＳ７０３において、キー列のすべてのキーについて処理済みであるか判定する。処理済みであればステップＳ７１２に移行し、処理済みでなければステップＳ７０４に進む。
ステップＳ７０４では、挿入キー列から、列位置の指すキーを取り出し、挿入キーとして設定する。
ステップＳ７０５に進み、図５に示すステップＳ５１０ｄで設定した比較キー列から、列位置の指すキーを取り出し、比較キーとして設定する。

次にステップＳ７０６に進み、挿入キーは比較キーと一致するか判定する。一致すれば列位置に設定した値を更新してステップＳ７０３に戻り、一致しなければ、ステップＳ７０７に移行して挿入キーと比較キーとのビット列比較を例えば排他的論理和で行い差分ビット列を得る。
ステップＳ７０８に進み、ステップＳ７０７で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
次にステップＳ７０９において、ステップＳ７０８で得たビット位置が差分ビット位置に設定された値より小さいか判定する。小さければステップＳ７１０で差分ビット位置にステップＳ７０８で得たビット位置を設定してステップＳ７１１に進み、小さくなければ直接ステップＳ７１１に進む。

上述のステップＳ７０３〜ステップＳ７１１の処理を全てのキーについて繰り返し、すべてのキーについての処理が終了するとステップＳ７１２において、差分ビット位置に設定された値が差分ビット位置の最大値であるか判定する。最大値であれば、ステップＳ７０６での判定が全てのキーにおいて一致することであるので、完全一致を表示して処理を終了し、最大値でなければ非完全一致を表示して処理を終了する。完全一致／非完全一致の表示は、例えば１ビットのフラグを設けることにより可能である。

図７Ｂは、図６Ａに示すステップＳ５１３ａの、挿入キー列と比較キー列の差分ビット位置の指す挿入キー列と比較キー列のビット値から、図６ＡのステップＳ５１２で取得され図６Ｂの処理により挿入位置が求められたノード群に格納するノードのノード位置を求める処理を詳細に説明する図である。

図に示すように、ステップＳ７１３において列位置に初期値として０を設定する。次にステップＳ７１４において、キー列のすべてのキーについて処理済みであるか判定する。処理済みであればステップＳ７２１に移行し、処理済みでなければステップＳ７１５に進む。
ステップＳ７１５では、挿入キー列から列位置の指すキーを取り出し、差分ビット位置の指すビット値を取り出す。次にステップＳ７１６で、挿入ノード位置の、列位置の指すビット位置に、ステップＳ７１６で取り出したビット値を設定する。
次にステップＳ７１７に進み、比較キー列から列位置の指すキーを取り出し、差分ビット位置の指すビット値を取り出す。次にステップＳ７１８で、対ノード位置の、列位置の指すビット位置に、ステップＳ７１８で取り出したビット値を設定する。次にステップＳ７１９で列位置を更新してステップＳ７１４に戻る。

ステップＳ７１４からステップＳ７１９までのループ処理を、キー列を構成する全てのキーについて実行すると、挿入ノード位置及び対ノード位置の全てのビット値が設定されるので処理を終了する。

図８は、本発明の一実施形態におけるルートノードの挿入処理を含むリーフノードの挿入処理全体の処理フローを説明する図である。
ステップＳ５５１において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図５〜図６Ｂを用いて説明した通常の挿入処理が行われる。
ステップＳ５５１での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。この場合にもインデックスキーへの参照ポインタをリーフノードに格納する実施態様においては、挿入キー列は挿入処理の前提条件として予めインデックスキーの格納領域のポインタを取得して、その格納領域に格納されているものとする。
まず、ステップＳ５５２において、配列から空きのノード群を求め、そのノード群のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップＳ５５３において、ステップＳ５５２で得た配列番号に０を加えた配列番号を求める。（実際には、ステップＳ５５２で取得した配列番号に等しい。）次にステップＳ５５４ｅにおいて、ステップＳ５５３で得た配列番号の配列要素すなわち挿入するルートノードに対応する配列要素の、ノード状態に使用中、ノード種別にリーフを、参照ポインタに挿入キー列のポインタをあるいはインデックスキーとして挿入キー列を書き込む。そしてステップＳ５５６では、ステップＳ５５３で取得したルートノードの配列番号を登録して処理を終了する。
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図８及び図５〜図６Ｂの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。

次に図９Ａ、図９Ｂを参照して、本発明の一実施形態におけるカップルドノードツリーから特定のインデックスキーに対応するリーフノードを削除する処理フローを説明する。
図９Ａは、削除処理の前段である検索処理の処理フローを示す図であり、図４に示した検索処理において、削除キー列を検索キー列とし、検索開始ノードをルートノードとしたものに相当する。
まず、ステップＳ９０１ａで検索開始ノードにルートノードの配列番号を設定し、ステップＳ９０１ｂで検索キー列に削除キー列を設定する。
次にステップＳ９１０ａにおいて、検索キー列により検索開始ノードより図４に示す検索処理を行い、ノード状態が空でなければ参照ポインタあるいはインデックスキーを取得する。ステップＳ９１０ｂにおいて、ステップＳ９１０ａでの検索結果のノードのノード状態が使用中であるか判定し、使用中でなければ削除失敗を返し、使用中であれば、ステップＳ９１０ｄに進んで参照ポインタの指すキー列あるいはインデックスキーを取り出して比較キー列に設定する。
次にステップＳ９１０ｅにおいて、図７Ａに示す処理により削除キー列と比較キー列から差分ビット位置を得る。ステップＳ９１１においてステップＳ９１０ｅで実行した図７Ａの処理の結果として完全一致が表示されているか、すなわち削除キー列と比較キー列のすべてのキーが等しいか判定し、等しくなければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図９ＢのステップＳ９１２ａ以下の処理に進む。

図９Ｂは、削除処理の後段の処理フローを説明する図である。
まず、ステップＳ９１２ａで、検索結果のノードが属するノード群に３つ以上のノードが格納されているか、すなわちノード状態が使用中であるノードが３つ以上あるか判定する。この判定は、先に図３に示すハードウェア構成例に関連して「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる」と述べたように、検索処理において得られるノード位置を記憶しておき、探索経路スタックにスタックされている配列番号と組み合わせてノード群内の各ノード位置のノード状態にアクセスすることにより行うことができる。

ステップＳ９１２ａでの判定が３つ以上のノードが格納されている、であれば、削除対象のノードを削除しても２つのノードが残ることから、ステップＳ９１２ｂに移行してステップＳ９１０ａで実行した図４に示す検索処理のステップＳ４０９で得た配列番号、すなわち探索経路スタックに格納されている配列番号の配列要素に格納されたノードのノード状態に空を書き込み、処理を終了する。

ステップＳ９１２ａでの判定が３つ以上のノードは格納されていない、であればステップＳ９１２に移行する。先に述べたように、使用中のノードが１つだけのノード群はルートノードの属するノード群以外には存在しないことから、この場合には使用中のノードは２つであり、そのうち１つのノード状態を空にすることから、他の１つのノードを別のノード群に移し、元のノード群を削除することになる。
ステップＳ９１２では、探索経路スタックに２つ以上の配列番号が格納されているか判定する。２つ以上の配列番号が格納されていないということは、言い換えれば１つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップＳ９１８に移行し、ステップＳ９０１ａで得たルートノードの配列番号に係るノード群を削除し、さらにステップＳ９１９でルートノードの配列番号の登録を抹消して、処理を終了する。

ステップＳ９１２において探索経路スタックに２つ以上の配列番号が格納されていると判定されたときはステップＳ９１３ａに進み、ノード群より、削除対象のノード以外のもう１つの使用中のノードの内容を読み出す。ステップＳ９１３ａの処理の詳細は、後に図１０を参照して説明する。
次にステップＳ９１５において探索経路スタックのスタックポインタを１つ戻して、配列番号を取り出し、ステップＳ９１６においてその配列番号の指す配列要素に、ステップＳ９１３ａで読み出した内容を書き込む。この処理は、先に述べた他のノードを別のノード群に移すことに相当する。
続くステップＳ９１７において、ステップＳ９１０ａで実行した図４に示す検索処理のステップＳ４０８で得た代表ノード番号に係るノード群を削除し、処理を終了する。

図１０は、図９Ｂに示すステップＳ９１３ａの、ノード群より、削除対象のノード以外のもう１つの使用中のノードの内容を読み出す処理を詳細に説明する図である。
図に示すように、ステップＳ１０１でノード位置に初期値０を設定する。次にステップＳ１０２に進み、ステップＳ９１０ａで実行した図４に示す検索処理のステップＳ４０８で得た代表ノード番号にノード位置に設定された値を加えて配列番号を求める。ステップＳ１０３で、配列から、ステップＳ１０２で求めた配列番号の指す配列要素をノードとして読み出し、ステップＳ１０４でその読み出したノードから、ノード状態を取り出す。
次にステップＳ１０５において、その取り出したノード状態は使用中であるか判定し、使用中でなければステップＳ１０７に進み、使用中であればステップＳ１０６に進む。
ステップＳ１０６では、ステップＳ１０２で求めた配列番号が削除対象のノードの配列番号、すなわちステップＳ９１０ａで実行した図４に示す検索処理のステップＳ４０９ａで得た配列番号と一致するか判定し、一致するのであればステップＳ１０７に進み、一致しなければ、削除対象のノード以外のもう１つの使用中のノードの内容をステップＳ１０３で読み出しているので、処理を終了する。
ステップＳ１０７においては、ノード位置を更新してステップＳ１０２に戻る。

上述の説明では、ノード位置の最小値である０を初期値としてノード位置の昇順にもう１つの使用中のノードを探索しているが、探索の順番はこれに限ることなく例えば降順に探索することも可能である。また、図のステップＳ１０６において、ステップＳ１０２で求めた配列番号が削除対象のノードの配列番号と一致するか判定しているが、この判定をステップＳ１０２の直後に行うことができることは明らかである。

次に、具体例により、本発明の一実施形態に係る削除処理と挿入処理を説明する。
図１１Ａ及び図１１Ｂは、図２Ｂに例示したダブル・カップルドノードツリーにおいて、“０００１１１：０１１１００”を削除キー列として削除処理を行う例を説明する図である。図１１Ａに示したダブル・カップルドノードツリーは、ノード群２０１ｆ以下のノードは記載を省略している。また、インデックスキーの格納領域３１１についても、ノード群２０１ｆ以下のリーフノードに関するものは省略している。削除キー列“０００１１１：０１１１００”は、第１のキー“０００１１１”と第２のキー“０１１１００”から構成されるキー列であり、一時記憶領域である削除キー２７０に格納されている。
探索経路スタック３１０には配列番号が格納されており、そのスタックポインタは配列番号２２０ｂ＋１を指している。図中太枠で囲まれたノードが検索処理でたどられたノードであり、その配列番号がルートノード２１０ａのものからリーフノード２１１ｃのものまで探索経路スタック３１０に積まれている。

削除キー列“０００１１１：０１１１００”による検索処理においては、まず始めにルートノード２１０ａの配列番号２２０を取得し、それを探索経路スタック３１０に格納する。ルートノード２１０ａの弁別ビット位置２３０ａが０であり、第１のキー及び第２のキーのビット位置０のビット値がともに０、であるので、代表ノード番号２２０ａにビット値０を加えた配列番号２２０ａが探索経路スタック３１０に格納される。
次に配列番号２２０ａの指すノード２１０ｂが読み出され、ブランチノードであることが判定される。その弁別ビット位置２３０ｂが１であり、第１のキーのビット位置１のビット値が０、第２のキーのビット位置１のビット値が１であるので、代表ノード番号２２０ｂに１を加えて配列番号２２０ｂ＋１を得てそれを探索経路スタック３１０に格納する。
次にノード２１１ｃが読み出され、ノード種別２６１ｃは１であり、リーフノードであることを示している。このリーフノードに対応するインデックスキー（キー列２９０ｃ、２９０ｃ’）は、参照ポインタ２８０ｃにより示される記憶領域に格納されている。その記憶領域はインデックスキーの記憶領域３１１の一部である。そこで参照ポインタ２８０ｃの参照するインデックスキーの値は“０００１１１：０１１１００”であり、削除キー２７０に格納されたキー列と一致している。

図１１Ａに示した状態において、削除対象のノード２１１ｃ以外のもう１つの使用中のノード２１３ｃの内容が読み出され、その内容が、探索経路スタック３１０のスタックポインタを１つ戻したところに格納されている配列番号２２０ａの配列要素（ノード２１０ｂ）に書き込まれる。その後ノード群２０１ｃを削除する。ノード群が削除された配列要素は空となり、再利用可能となる。

図１１Ｂに示したダブル・カップルドノードツリーは、削除処理の終了後のものである。ノード２１０ｂのノード種別２６０ｂ、弁別ビット位置２３０ｂ、代表ノード番号２２０ｂには、括弧書きで示すように、ノード２１３ｃに格納されていた値がそのまま格納されている。また、探索経路スタック３１０のスタックポインタは配列番号２２０ａを指している。

次に、削除対象のノードが属するノード群に使用中のノードが３以上含まれる場合の削除処理の具体例を説明する。
図１１Ｃ及び図１１Ｄは、図２Ｂに例示したダブル・カップルドノードツリーにおいて、“０１１０１０：１０００００”を削除キー列として削除処理を行う例を説明する図である。図１１Ｃに示したダブル・カップルドノードツリーは、ノード群２０１ｆ以下及びノード群２０１ｃ以下のノードは記載を省略している。また、インデックスキーの格納領域３１１についても、ノード群２０１ｆ以下のリーフノードに関するものは省略している。削除キー列“０１１０１０：１０００００”は、第１のキー“０１１０１０”と第２のキー“１０００００”から構成されるキー列であり、一時記憶領域である削除キー２７０に格納されている。
探索経路スタック３１０には配列番号が格納されており、そのスタックポインタは配列番号２２０ａ＋１を指している。図中太枠で囲まれたノードが検索処理でたどられたノードであり、その配列番号がルートノード２１０ａのものからリーフノード２１１ｂのものまで探索経路スタック３１０に積まれている。

削除キー列“０１１０１０：１０００００”による検索処理においては、まず始めにルートノード２１０ａの配列番号２２０を取得し、それを探索経路スタック３１０に格納する。ルートノード２１０ａの弁別ビット位置２３０ａが０であり、第１のキー及び第２のキーのビット位置０のビット値がそれぞれ０、１であるので、代表ノード番号２２０ａにビット値１を加えた配列番号２２０ａ＋１が探索経路スタック３１０に格納される。配列番号２２０ａ＋１の指すノード２１１ｂが読み出され、ノード種別２６１ｂは１であり、リーフノードであることを示している。このリーフノード２１１ｂに対応するインデックスキー（キー列２９０ｄ、２９０ｄ’）は、参照ポインタ２８１ｄにより示される記憶領域に格納されている。参照ポインタ２８１ｄの参照するインデックスキーの値は“０１１０１０：１０００００”であり、削除キー２７０に格納されたキー列と一致している。
削除対象のノード２１１ｂが属するノード群２０１ｂには使用中のノードが２１０ｂ、２１１ｂ、２１２ｂと３つあるので、削除対象であるノード２１１ｂのノード状態に０を書き込んで空とし、図１１Ｄに示す削除処理後のダブル・カップルドノードツリーが得られる。

次に、図１２Ａ及び図１２Ｂを参照して挿入処理の具体例１を説明する。具体例１は、挿入キー列による検索結果としてインデックスキーが得られた場合、すなわち図５に示すステップＳ５１０ｂの判定がノード状態は使用中であるとなった場合のものである。
図１２Ａに示すのは、キー列“０１００：０００１”、“０００１：００１０”、“００００：００１１”をインデックスキーとして参照する参照ポインタ１２８１ｂ、１２８１ｃ、１２８０ｃを持つカップルドノードツリーである。
インデックスキーの格納領域３１１内の参照ポインタ１２８１ｂの指す記憶領域には、第１のキー１２９１ｂ“０１００”と第２のキー１２９１ｂ’“０００１”からなるキー列が格納されている。同様に、参照ポインタ１２８１ｃの指す記憶領域には、第１のキー１２９１ｃ“０００１”と第２のキー１２９１ｃ’“００１０”からなるキー列が格納され、参照ポインタ１２８０ｃの指す記憶領域には、第１のキー１２９０ｃ“００００”と第２のキー１２９０ｃ’“００１１”からなるキー列が格納されている。
これから挿入しようとする挿入キー列は図示の例では“０００１：００００”である。挿入キー列は、先に述べたように、インデックスキーの格納領域３１１のポインタ１２８０ｄを取得して、ポインタ１２８０ｄの指す領域に、第１のキー１２９０ｄ、第２のキー１２９０ｄ’として格納されていることを前提としている。

図示のツリーはノード群１２０１ａ、１２０１ｂ、１２０１ｃで構成されている。
ノード群１２０１ａの代表ノードはルートノード１２１０ａであり、弁別ビット位置には１が保持されている。ノード群１２０１ａの下位のノード群１２０１ｂの代表ノード１２１０ｂはブランチノードであり、弁別ビット位置には３が保持され、代表ノード１２１０ｂと同一のノード群１２０１ｂに属する使用中のノード１２１２ｂはリーフノードであり、キー列１２９１ｂ、１２９１ｂ’への参照ポインタ１２８１ｂが保持されている。ブランチノードであるノード１２１０ｂはノード群１２０１ｃにリンクしている。
ノード群１２０１ｃを構成する使用中のノード１２１１ｃと１２１２ｃはともにリーフノードであり、それぞれキー列１２９０ｃ、１２９０ｃ’とキー列１２９１ｃ、１２９１ｃ’への参照ポインタ１２８０ｃ、１２８１ｃが格納されている。ノード１２１１ｃと１２１２ｃのノード位置はそれぞれ０１と１０である。

挿入キー列の第１のキー１２９０ｄと第２のキー１２９０ｄ’の１ビット目のビット値の組み合わせが００、３ビット目のビット値の組み合わせが１０であることから、図示の例の場合、挿入キー列で検索をすると、ルートノード１２１０ａからノード１２１０ｂを経由して参照ポインタ１２８１ｃの格納されたリーフノード１２１２ｃに至り、比較キー列として、１２９１ｃ、１２９１ｃ’ “０００１：００１０”が設定される。

図１２Ｂは、挿入処理後のカップルドノードツリーを説明する図である。図１２Ａに示すカップルドノードツリーに対して、挿入キー列１２９０ｄ、１２９０ｄ’への参照ポインタ１２８０ｄを持つリーフノード１２１０ｄと比較キー列の参照ポインタが格納されるリーフノード１２１２ｃの直近上位のブランチノード１２１０ｂの内容が転写されるノード１２１１ｄを含むノード群１２０１ｄがブランチノード１２１０ｂのリンク先として挿入されている。
挿入キー列と比較キー列の差分ビット位置は図示の場合では２であること、ブランチノード１２１０ｂの弁別ビット位置が３で差分ビット位置より大きくその直近上位のブランチノード１２１０ａの弁別ビット位置が１で差分ビット位置より小さいことから、ノード群１２０１ｄの挿入位置は、配列番号１２２０ｂの指すノード１２１０ｂの直近下位となる。
挿入キー列の参照ポインタが格納されるリーフノード１２１０ｄが配置されるノード位置（挿入ノード位置）は、挿入キー列の差分ビット位置のビット値の組み合わせである００であり、比較キー列の参照ポインタが格納されるリーフノード１２１２ｃの直近上位のブランチノード１２１０ｂの内容が転写されるノード１２１１ｄが配置されるノード位置（対ノード位置）は、比較キー列の差分ビット位置のビット値の組み合わせである０１である。
また、ブランチノード１２１０ｂの弁別ビット位置には挿入キー列と比較キー列の差分ビット位置である２が書き込まれ、代表ノード番号にはノード群１２０１ｄの代表ノード１２１０ｄの配置された配列要素の配列番号１２２０ｄが書き込まれ、図１２Ｂに示す構成のカップルドノードツリーとなる。

図１２Ｃ及び図１２Ｄは挿入処理の具体例２を説明する図である。具体例２は、図５に示すステップＳ５１０ｂの判定がノード状態は空であるとなった場合のものである。
図１２Ｃに示す挿入処理前のカップルドノードツリーは図１２Ａに示すものと同一であるが、インデックスキーの格納領域３１１に格納された挿入キー列が“０００１：００１１”であって図１２Ａに示すものと異なり、参照ポインタ１２８１ｄの指す記憶領域に格納されている。

挿入キー列“０００１：００１１”によりルートノード１２１０ａから検索を実行すると、ブランチノード１２１０ｂを経由して空ノード１２１３ｃに至る。そこで、ノード１２１３のノード状態に１を書き込んで使用中とし、ノード種別にリーフノードであることを示す１を書き込み、参照ポインタに挿入キー列“０００１：００１１”の参照ポインタ１２８１ｄを書き込む。以上の処理により、図１２Ｄに示す挿入処理後のカップルドノードツリーが得られる。

図１３は、３つのキーからなるキー列による検索処理に用いる、本発明の一実施形態に係るカップルドノードツリーのツリー構造を概念的に示す図である。本実施形態のキー列を３次元キー、カップルドノードツリーをトリプル・カップルドノードツリーということがある。
トリプル・カップルドノードツリーを用いた検索では、ダブル・カップルドノードツリーについて先に説明したと同様に、３次元キーを構成する各次元のキーの弁別ビット位置のビット値の組み合わせによりリンク先が決定される。したがって、ノード群には２の３乗、すなわち８個のエントリが存在する。ノード位置は０００〜１１１の３ビットで表される。

符号４１０ａで示すのがルートノードである。図示の例では、ルートノード４１０ａは配列番号４２０に配置されたノード群４０１ａの代表ノードとしている。
ツリー構造としては、ルートノード４１０ａの下にノード群４０１ｂが、その下層にノード群４０１ｃとノード群４０１ｆが配置され、ノード群４０１ｆの下層にはノード群４０１ｇ、４０１ｈ、４０１ｉが配置されている。ノード群４０１ｃの下にはノード群４０１ｄが、さらにその下位にノード群４０１ｅが配置されている。
各ノードの前に付された３ビットの符号はノード位置を示す。検索キー列の各キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のインデックスキーに対応するリーフノードを見つけることは、ダブル・カップルドノードツリーの場合と同様である。

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

ノード群４０１ｂはノード４１０ｂ、４１１ｂ、４１２ｂ、４１３ｂ、４１４ｂ、４１５ｂ、４１６ｂ、４１７ｂで構成される。代表ノード４１０ｂとノード位置が１１１であるノード４１７ｂのノード状態４４７ｂのみが１で使用中であり、他のノードは空ノードである。ノード４１０ｂのノード種別４６０ｂとノード４１７のノード種別４６７ｂはともに０であり、ブランチノードであることを示している。
ノード４１０ｂの弁別ビット位置４３０ｂには１が格納され、リンク先の代表ノード番号にはノード群４０１ｃの代表ノード４１０ｃの格納された配列要素の配列番号４２０ｂが格納されている。ノード４１７ｂの弁別ビット位置４３７ｂには２が格納され、リンク先の代表ノード番号にはノード群４０１ｆの代表ノード４１０ｆの格納された配列要素の配列番号４２７ｂが格納されている。

ブランチノード４１０ｂのリンク先である代表ノード４１０ｃが属するノード群４０１ｃの使用中であるノードはビット位置０１０のノード４１２ｃとビット位置１１０のノード４１６ｃである。ノード４１２ｃのノード種別４６２ｃは１でリーフノードであることを示し、参照ポインタ４５２ｃにはインデックスキーが記憶された記憶領域へのポインタ４８２ｃが格納されている。ノード４１６ｃのノード種別４６６ｃは０でブランチノードであることを示し、弁別ビット位置４３６ｃには２が格納され、代表ノード番号にはノード群４０１ｄの代表ノード４１０ｄの格納された配列要素の配列番号４２６ｃが格納されている。

ブランチノード４１６ｃのリンク先である代表ノード４１０ｄが属するノード群４０１ｄの使用中であるノードはビット位置１００のノード４１４ｄとビット位置１１１のノード４１７ｄである。ノード４１４ｄのノード種別４６４ｄは０でブランチノードであることを示し、弁別ビット位置４３４ｄには５が格納され、代表ノード番号にはノード群４０１ｅの代表ノード４１０ｅの格納された配列要素の配列番号４２４ｄが格納されている。ノード４１７ｄのノード種別４６７ｄは１でリーフノードであることを示し、参照ポインタ４５７ｄにはインデックスキーが記憶された記憶領域へのポインタ４８７ｄが格納されている。

ブランチノード４１４ｄのリンク先である代表ノード４１０ｅが属するノード群４０１ｅの全てのノード４１０ｅ〜４１７ｅはそれぞれのノード状態４４０ｅ〜４４７ｅが１、ノード種別４６０ｅ〜４６７ｅが１でリーフノードであり、参照ポインタ４５０ｅ〜４５７ｅにはインデックスキーが記憶された記憶領域へのポインタ４８０ｅ〜４８７ｅが格納されている。

ブランチノード４１７ｂのリンク先である代表ノード４１０ｆが属するノード群４０１ｆのノード４１０ｆ〜４１３ｆは、ノード４１０ｆのノード状態４４０ｆが０であるように空ノードである。ノード４１４ｆはリーフノード、ノード４１５ｆ〜４１７ｆはブランチノードである。ノード４１４ｆの参照ポインタにはインデックスキーが記憶された記憶領域へのポインタ４８４ｆが格納されている。ブランチノード４１５ｆの弁別ビット位置は４であり、代表ノード番号にはノード群４０１ｇの代表ノード４１０ｇが配置された配列要素の配列番号４２５ｆが格納されている。ブランチノード４１６ｆの弁別ビット位置は５であり、代表ノード番号にはノード群４０１ｉの代表ノード４１０ｉが配置された配列要素の配列番号４２６ｆが格納されている。ブランチノード４１７ｆの弁別ビット位置は３であり、代表ノード番号にはノード群４０１ｈの代表ノード４１０ｇｈ配置された配列要素の配列番号４２７ｆが格納されている。

ブランチノード４１５ｆのリンク先である代表ノード４１０ｇが属するノード群４０１ｇの使用中のノードはノード位置０１１のノード４１３ｇとノード位置１００のノード４１４ｇだけである。ノード４１３ｇのノード種別４６３ｇとノード４１４ｇのノード種別４６４ｇはともに１であり、両ノードはリーフノードである。それぞれの参照ポインタ４５３ｇと４５４ｇには、インデックスキーが記憶された記憶領域へのポインタ４８３ｇと４８４ｇが格納されている。

ブランチノード４１６ｆのリンク先である代表ノード４１０ｉが属するノード群４０１ｉの使用中のノードはノード位置１００のノード４１４ｉとノード位置１０１のノード４１５ｉだけである。ノード４１４ｉのノード種別４６４ｉとノード４１５ｉのノード種別４６５ｉはともに１であり、両ノードはリーフノードである。それぞれの参照ポインタ４５４ｉと４５５ｉには、インデックスキーが記憶された記憶領域へのポインタ４８４ｉと４８５ｉが格納されている。

ブランチノード４１７ｆのリンク先である代表ノード４１０ｈが属するノード群４０１ｈの使用中のノードはノード位置１０１のノード４１５ｈとノード位置１１１のノード４１７ｈだけである。ノード４１５ｈのノード種別４６５ｈとノード４１７ｈのノード種別４６７ｈはともに１であり、両ノードはリーフノードである。それぞれの参照ポインタ４５５ｈと４５７ｈには、インデックスキーが記憶された記憶領域へのポインタ４８５ｈと４８７ｈが格納されている。

図１３には、各リーフノードの参照ポインタで参照されるインデックスキー（３次元キー）は記載していないが、図１３に記載されたルートノードからリーフノードまで、弁別ビット位置とリンク先のノード位置に注目することにより、インデックスキーの値がどの範囲のものであるかを決定することができる。
例えば、リーフノード４１２ｃの参照ポインタ４８２ｃで参照される３次元キーについて考察すると、ルートノード４１０ａの弁別ビット位置４３０ａが０、リンク経路のブランチノード４１０ｂのノード位置が０００であることから、各次元のキーの０ビット目が０、ブランチノード４１０ｂの弁別ビット位置４３０ｂが１、リンク先のリーフノード４１２ｃのノード位置が０１０であることから、各キーの１ビット目のビット値は、第１のキーは０、第２のキーは１、第３のキーは０である。すなわち、リーフノード４１２ｃの参照ポインタ４８２ｃで参照される３次元キーは、“００ｘｘｘｘ：０１ｘｘｘｘ：００ｘｘｘｘ”（ｘは０，１のいずれか任意の値）の値を有するものである。
他のリーフノードに関連する３次元キーについても、同様にツリーの構造から求めることが可能である。

また、トリプル・カップルドノードツリーを用いた検索処理、挿入処理、削除処理については、ダブル・カップルドノードツリーを用いた検索処理、挿入処理、削除処理と同様に実行可能であることは当業者にとって明らかである。
さらに、２次元、あるいは３次元に限らず、次元数に応じてノード位置のビット数を増やすことにより、本発明はより高次元の多次元キーによる検索に拡張可能であることは明らかである。

以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。例えばリーフノードが、インデックスキーを格納した記憶領域の位置を示す情報に代えてインデックスキー自体を含むようにすることが可能であることは、当業者に自明である。
また、本発明のビット列検索方法を実行する装置が、カップルドノードツリーを格納する記憶手段と図４に示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
さらに、図５〜図８に示した挿入処理とその均等物をコンピュータに実行させるプログラムにより、本発明の挿入方法が実現可能であり、図９Ａ、図９Ｂ及び図１０に示した削除処理とその均等物をコンピュータに実行させるプログラムにより、本発明の削除方法が実現可能であることも明らかである。そして、それらのプログラムにより、ブランチノードとリーフノードの識別手段、ブランチノードの弁別ビット位置に応じてリンク先のノード対のどちらかにリンクする手段等がコンピュータ上に実現される。
したがって、上記プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の実施の形態に含まれる。さらに、本発明のカップルドノードツリーのデータ構造及びそのデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体も、本発明の実施の形態に含まれる。
以上詳細に説明した、本発明が提供する新しいデータ構造であるカップルドノードツリーを用いることにより、多次元キーを取り扱うことができ、より高速なビット列データの検索を行うことが可能となる。しかもビット列データの追加削除も容易に実行することができる。

従来の検索で用いられるパトリシアツリーの一例を示す図である。 配列に格納されたダブル・カップルドノードツリーの構成例を説明する図である。 ダブル・カップルドノードツリーのツリー構造を概念的に示す図である。 本発明を実施するためのハードウェア構成例を説明する図である。 本発明の一実施形態における検索処理を示すフローチャートである。 本発明の一実施形態における挿入処理の前段である検索処理の処理フローを示す図である。 本発明の一実施形態における挿入処理における挿入するノード群のための配列要素を準備する処理フローを説明する図である。 ノード群を挿入する位置を求め、ノード群の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。 挿入キー列と比較キー列の差分ビット位置を得る処理フローを説明する図である。 挿入されるノード群に格納するノードのノード位置を求める処理フローを説明する図である。 本発明の一実施形態におけるルートノードの挿入処理を含むリーフノードの挿入処理全体の処理フローを説明する図である。 本発明の一実施形態における削除処理の前段である検索処理の処理フローを示す図である。 本発明の一実施形態における削除処理の後段の処理フローを説明する図である。 ノード群から削除対象のノード以外の使用中のノードを求める処理フローを説明する図である。 第１の削除処理例における削除処理前のダブル・カップルノードツリーと削除キーを説明する図である。 第１の削除処理例における削除処理後のダブル・カップルドノードツリー例を示す図である。 第２の削除処理例における削除処理前のダブル・カップルノードツリーと削除キーを説明する図である。 第２の削除処理例における削除処理後のダブル・カップルドノードツリー例を示す図である。 第１の具体例における挿入処理前のカップルドノードツリー例を示す図である。 第１の具体例における挿入処理後のカップルドノードツリー例を示す図である。 第２の具体例における挿入処理前のカップルドノードツリー例を示す図である。 第２の具体例における挿入処理後のカップルドノードツリー例を示す図である。 配列に格納されたトリプル・カップルドノードツリーのツリー構造を概念的に示す図である。

符号の説明

１０、２０、３０ 配列番号
１００ 配列
１０１、１２２、１２３ ノード
１０２ａ、１１４ａ、１１７ａ ノード状態
１０２ｂ、１１４ｂ、１１７ｂ ノード種別
１０３、１１５ 弁別ビット位置
１０４、１１６ 代表ノード番号
１１１、１２１ ノード群
１１２、１２２ ノード［０］、ノード位置００のノード
１１３、１２３ ノード［１］、ノード位置０１のノード
１１２ａ、１２２ａ ノード［２］、ノード位置１０のノード
１１３ａ、１２３ａ ノード［３］、ノード位置１１のノード
１１８ａ 参照ポインタ
３０１ データ処理装置
３０２ 中央処理装置
３０３ キャッシュメモリ
３０４ バス
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ 通信装置
３０８ データ格納装置
３０９ 配列
３１０ 探索経路スタック
３１１ インデックスキーの格納領域

Claims (15)

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

Images