ビット列検索装置、検索方法及びプログラム
【課題】複数のキーからなるキー列による検索において、検索処理の高速化をより一層高めることの可能なツリー構造とそれを用いた検索手法を提供する。
【解決手段】4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたツリー構造を用い、インデックスキーの検索は、ブランチノードに含まれる弁別ビット位置の検索キー列の各キーのビット値に応じたノード位置により代表ノードの属するノード群の一つのノードにリンクすることを順次繰り返すことにより実現する。
【解決手段】4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたツリー構造を用い、インデックスキーの検索は、ブランチノードに含まれる弁別ビット位置の検索キー列の各キーのビット値に応じたノード位置により代表ノードの属するノード群の一つのノードにリンクすることを順次繰り返すことにより実現する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する検索処理に関するものであり、特に本出願人が特開2008−015872号公報及び特願2006−293619において提案したカップルドノードツリーを用いたタイプの検索装置、検索方法及びそのプログラムに関するものである。
【背景技術】
【0002】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【0003】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの1つとして、パトリシアツリーという木構造が知られている。
【0004】
図1は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【0005】
図1の例では、インデックスキー“100010”を保持するノード1750aがルートノードとなっており、その検査ビット位置1730aは0である。ノード1750aの左リンク1740aにはノード1750bが接続され、右リンク1741aにはノード1750fが接続されている。ノード1750bの保持するインデックスキーは“010011”であり、検査ビット位置1730bは1である。ノード1750bの左リンク1740bにはノード1750cが、右リンク1741bにはノード1750dが接続されている。ノード1750cが保持するインデックスキーは“000111”、検査ビット位置1730cは3である。ノード1750dが保持するインデックスキーは“011010”、検査ビット位置1730dは2である。
【0006】
ノード1750cから実線で接続された部分はノード1750cの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ1740cは、その欄が空欄であることを示している。点線の接続された右ポインタ1741cの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード1750cを右ポインタ1741cが指定していることを表している。ノード1750dの右ポインタ1741dはノード1750d自身を指しており、左リンク1740dにはノード1750eが接続されている。ノード1750eの保持するインデックスキーは“010010”、検査ビット位置1730eは5である。ノード1750eの左ポインタ1740eはノード1750bを、右ポインタ1741eはノード1750eを指している。
【0007】
また、ノード1750fの保持するインデックスキーは“101011”であり、検査ビット位置1730fは2である。ノード1750fの左リンク1740fにはノード1750gが、右リンク1741fにはノード1750hが接続されている。ノード1750gの保持するインデックスキーは“100011”であり、検査ビット位置1730gは5である。ノード1750gの左ポインタ1740gはノード1750aを、右ポインタ1741gはノード1750gを指している。ノード1750hの保持するインデックスキーは“101100”であり、検査ビット位置1730hは3である。ノード1750hの左ポインタ1740hはノード1750fを、右ポインタ1741hはノード1750hを指している。
【0008】
図1の例では、ルートノード1750aからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が1であるか0であるか判定を行い、1であれば右リンクをたどり、0であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば(図1において点線で示されたこの逆戻りのリンクをバックリンクという)、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【0009】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は1回ですむことなどのメリットがあるが、各ノードからの2つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【0010】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献1に開示された技術がある。下記特許文献1に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。しかしながら、下記特許文献1に開示されたものにおいても、1つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを1つとしたため、例えば図1に示したパトリシアツリーの最下段の部分である左ポインタ1740c、右ポインタ1741h等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【0011】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願2006−187827に係る下記特許文献2において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが1つのときはリーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を開示した。特許文献2においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。また、カップルドノードツリーの構成が、インデックスキーの集合により一意に規定されることも説明されている。
【0012】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願2006−293619において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの一般化された検索あるいはインデックスキーの最大値/最小値を求める手法及びカップルドノードツリーに格納されたインデックスキーを昇順または降順に取り出す手法等を提案した。一般化された検索手法であるカップルドノードツリーの任意のノードを検索開始ノードとする検索は、前記検索開始ノードをルートノードとするカップルドノードツリーの任意の部分木を検索対象として、検索キーによる検索を実行するものである。その検索は、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより行われ、前記リーフノードに含まれるインデックスキーが、検索結果キーとして得られる。
【0013】
インデックスキーの最大値/最小値を求める手法は、代表ノードあるいは代表ノードと対を成すノード(以下、非代表ノードということがある。)のみをリーフノードに至るまでリンクするものであり、カップルドノードツリーに格納されたインデックスキーを昇順または降順に取り出す手法は、特許文献2で説明したように、インデックスキーはカップルドノードツリーにおいて、順序性をもって配置されていることを利用したものであり、検索開始ノードを前記順序性に基づいて変更しながら最小値検索または最大値検索を繰り返すものである。また、上記各出願において、カップルドノードツリーを配列に配置すること、上記提案した各検索処理における検索開始ノードからのツリー上の探索経路のノードの配列番号を探索経路スタックに順次スタックし、探索経路スタックにスタックされた配列番号を用いた処理も開示した。
【0014】
また、本出願人は、特願2007−114915において、リーフノードにインデックスキーに替えてインデックスキーを格納した記憶領域の位置情報を格納したカップルドノードツリーの構造とそれを用いた検索処理を提案した。
さらに本出願人は、特願2008−7690において、複数のキーによる検索のためのカップルドノードツリーであって、複数のキーが直列に連結され、末尾のキーはユニークキーであることを条件としたキー列による検索を行うカップルドノードツリーの構造とそれを用いた検索処理を提案した。
【特許文献1】特開2001−357070号公報
【特許文献2】特開2008−015872号公報
【発明の開示】
【発明が解決しようとする課題】
【0015】
上記特願2008−7690で提案したカップルドノードツリーを用いた検索においては、キー列を構成するキー毎に順次直列的に処理を行うものであるから、キー列を構成するキーの数が増えるとそれだけ処理時間が増加する。
また地図上の地点のように2次元座標で位置が表される点を検索する場合、X座標とY座標について順次それぞれ検索をしているが、地図上の検索対象が増えるにつれて、その検索効率を向上させることが求められてきている。
また、3次元空間内の点を検索する場合でも、事情は同じである。
【0016】
そこで本発明の目的は、複数のキーからなるキー列による検索において、検索処理の高速化をより一層高めることの可能なツリー構造とそれを用いた検索手法を提供することである。
【課題を解決するための手段】
【0017】
まず、本発明によるカップルドノードツリーは、上記特願2008−7690で提案したものと同様に、複数のキーからなるキー列(以下、多次元キーということがある。)を検索の対象とするが、特願2008−7690で提案したものとは、末尾のキーがユニークである必要がないという点で異なる。また、上記各出願において提案したカップルドノードツリーのツリー構造は、ノード対がツリー状にリンクしたものであったが、それに対して本発明によるカップルドノードツリーのツリー構造は、隣接した記憶領域に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたものである。本発明のブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキー自体を含み、空ノードは該空ノードが空状態であることを示す情報を含む。
【0018】
既提案のノード対が代表ノードとそれと対をなすノードから構成されるのに対して、本発明のノード群の各ノードは、キー列を構成する各キーのビット値の組み合わせに対応する位置に配置される。すなわち本発明のノード群は、一次元のノード対を多次元に拡張したいわば多重カップルドノードであり、本発明のカップルドノードツリー(以下、多重カップルドノードツリーということがある。)は、従来の一次元のカップルドノードツリーを多次元のものに拡張したものである。
キー列(以下、多次元キーあるいはインデックスキーということがある。)の検索においては、ブランチノードに含まれる弁別ビット位置の検索キー列の各キーのビット値に応じたノード位置により代表ノードの属するノード群の1つのノードにリンクすることを順次繰り返すことにより実現する。
【発明の効果】
【0019】
本発明によれば、検索キー列の各キーのビット値に応じたノード位置によりノード群の1つのノードにリンクするので、キー毎の分岐処理を直列に行うことがなく、ツリーの分岐の階層を小さくできるので、処理効率を向上することができる。
【発明を実施するための最良の形態】
【0020】
以下、本発明を実施するための最良の形態として、カップルドノードツリーを配列に格納する例について説明する。ブランチノードが保持するリンク先の代表ノードの位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、代表ノードの位置を示す位置情報の情報量を削減することができる。
【0021】
また、主としてキー列として2つのキーから構成されるものを例示して説明する。したがって、本実施態様のカップルドノードツリーをダブル・カップルドノードツリー、あるいは単にツリーということがある。また、キー列(インデックスキー)を2次元キーということがある。さらに、リーフノードにはインデックスキーの格納された記憶領域の位置情報を含むものとして説明するが、リーフノードに直接インデックスキーを格納することもできる。しかし、先の出願である特願2007−114915において説明したように、インデックスキー(本願の場合はキー列)の長さが長くなる場合には、インデックスキーをリーフノードに格納せず他の記憶領域に格納し、リーフノードには該記憶領域の位置情報を格納することにより、ノードを格納する記憶領域を効率的に使用することができる。
【0022】
図2Aは、本発明の一実施形態における配列に格納されたダブル・カップルドノードツリーの構成例を説明する図である。上述の特願2007−114915で提案したものとは、各ノードが空ノードであるか使用中であるかを示す情報であるノード状態を含む点のみで異なる。
本発明によれば、カップルドノードツリーのツリー構造におけるノードは、多次元キーを構成する各キーのビット値の組み合わせに対応する位置に配置されたノードから構成されるノード群であるので、ある多次元キーの集合に対して多重カップルドノードツリーを生成したとき、あるノード群のあるノード位置に対応する多次元キーが存在しないことがあり得る。したがって、ノード種別とは別にノード状態を設けてそのノード位置のノードが空であるか使用中であるかを識別するものである。
【0023】
図2Aを参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード状態102a、ノード種別102b、弁別ビット位置103及び代表ノード番号104で構成されている。ノード状態102aの値は1であり、ノード101が使用中であることを示している。ノード種別102bの値は0であり、ノード101がブランチノードであることを示している。弁別ビット位置103には1が格納されている。代表ノード番号104にはリンク先のノード群111の代表ノードの配列番号20が格納されている。配列番号は上記第一の位置情報の具体例である。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。
【0024】
配列番号20の配列要素には、ノード群111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1)にはノード[1]113が、その次の配列要素(配列番号20+2)にはノード[2]112aが、さらにその次の配列要素(配列番号20+3)にはノード[3]113aが格納されている。
ノード[0]112はノード101と同様にブランチノードである。ノード[0]112のノード状態114aには1が、ノード種別114bには0が、弁別ビット位置115には3が、代表ノード番号116には30が格納されている。ノード[1]113とノード[2]112aのノード状態はともに0であり、空ノードであることを示している。
ノード[3]113aは、ノード状態117a、ノード種別117b及び参照ポインタ118aで構成されている。ノード状態117a及びノード種別117bには1が格納されており、ノード[3]113aがリーフノードであることを示している。参照ポインタ118aには、インデックスキーの記憶領域を参照するポインタが格納されている。参照ポインタ118aに格納されたデータは、上記の第二の位置情報の具体例である。以下では表記の簡略化のため、参照ポインタに格納されたデータのことも参照ポインタという。
パトリシアツリーについて先に述べたと同様に、インデックスキーと対応するレコードにアクセスするためのアクセス先情報も当然必要である。インデックスキーとアクセス先情報との対応づけは、例えば、インデックスキーを記憶している記憶領域に隣接する記憶領域に、当該インデックスキーに対応するアクセス先情報を記憶することによって行ってもよい。以下ではアクセス先情報については省略して説明する。
配列番号30の配列要素に格納されたノード122、ノード123、ノード122a及びノード123aからなるノード群121の内容は省略されている。
【0025】
ノード[0]112、ノード[1]113、ノード[2]112a、ノード[3]113a及びノード122、ノード123、ノード122a、ノード123aの格納された配列要素にそれぞれ付された00、01、10、11は、各ノードのノード群におけるノード位置を2進表示で示すものである。代表ノードの格納された配列要素の配列番号にノード位置を加えることにより、該ノード位置のノードの格納された配列要素の配列番号が求められる。 なお、ノード位置が00である代表ノードをノード[0]で表し、ノード位置01、10、11のノードをそれぞれノード[1]、ノード「2」、ノード[3]で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
ノード位置は、検索キー列で検索を行う場合にノード群のどのノードにリンクするかを示すものである。すなわち、検索キー列のうち第1のキーの弁別ビット位置にあるビット値と第2のキーの弁別ビット位置にあるビット値からなる2ビットの値を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、該ブランチノードの弁別ビット位置にある検索キー列の第1のキーのビット値と第2のキーのビット値からなる2ビットの値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード群の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。また、代表ノードのノード位置も任意の位置に決定することができることも明らかである。
【0026】
図2Bは、本実施形態に係るダブル・カップルドノードツリーのツリー構造と2次元キー(インデックスキー)の格納領域を概念的に示す図である。
図2Bの(1)に示すのはダブル・カップルドノードツリーのツリー構造である。符号210aで示すのがルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード群201aの代表ノードとしている。
ツリー構造としては、ルートノード210aの下にノード群201bが、その下層にノード群201cとノード群201fが配置され、ノード群201fの下層にはノード群201gが配置されている。ノード群201cの下にはノード群201eが配置されている。
各ノードの前に付された00、01、10、11の符号は、図2Aにおいて説明した配列要素の前に付された符号と同じでありノード位置を示す。検索キー列の各キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のインデックスキーに対応するリーフノードを見つけることになる。
【0027】
図示された例では、ルートノード210aのノード状態240aは1、ノード種別260aは0でブランチノードであることを示し、弁別ビット位置230aは0を示している。代表ノード番号は220aであり、それはノード群201bの代表ノード210bの格納された配列要素の配列番号である。
ノード群201bはノード210b、211b、212b、213bで構成される。ノード位置が11であるノード213bのノード状態243bのみが0で空ノードであることを示している。ノード位置11のノードが空ノードであるということは、上位のブランチノード210aの弁別ビット位置230aに格納された値0のビット位置の第1のキーと第2のキーのビット値がともに1である2次元キーが、図2Bの(2)に示すインデックスキーの格納領域311に存在しないことを反映している。
ノード210bのノード状態240bは1で、ノード211b、212bのノード状態もノード210bのノード状態240bと同様に1であって使用中であることを示している。それらのノードのうち、ノード210bとノード212bのノード種別260b、262bはともに0であり、ブランチノードであることを示している。
ノード210bの弁別ビット位置230bには1が格納され、リンク先の代表ノード番号にはノード群201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。ノード212bの弁別ビット位置232bには1が格納され、リンク先の代表ノード番号にはノード群201fの代表ノード210fの格納された配列要素の配列番号222bが格納されている。
【0028】
一方、ノード211bのノード種別261bは1でありノード211bはリーフノードであるので参照ポインタ251bを含む。参照ポインタ251bには、第1のキー291dの値が“011010”、第2のキー291d’の値が“100000”というキー列(2次元キー)を格納した記憶領域を示す参照ポインタ281dが格納されている。参照ポインタ251bに格納されたデータのことも参照ポインタといい、符号281dにより表す。他のリーフノードでも同様に、参照ポインタと参照ポインタに格納されたデータを同じ参照ポインタという語で表す。また、以下の説明において、2次元キーについて、“011010:100000”のような表記及び291d、291d’のような表記を用いることがある。
ノード群201bのノード位置01に参照ポインタ281dを格納したリーフノード211bが存在することは、参照ポインタ281dで参照するインデックスキーの、ノード群201bの直近上位のブランチノード210aの弁別ビット位置230aで示されるビット位置0のビット値が、第1のキー290dが“0”、第2のキー290d’が“1”であり、そのようなビット値の組み合わせのインデックスキーがほかにないことに対応している。
一方、ノード群201bのノード位置00とノード位置10のノードがブランチノードであるのは、ブランチノード210aの弁別ビット位置230aで示されるビット位置0の第1のキーと第2のキーのビット値の組み合わせが00のものと10のインデックスキーが2つ以上存在し、ビット位置0より下位のビット位置のビット値によりそれらのインデックスキーが弁別されることに対応している。
【0029】
ブランチノード210bのリンク先であるノード210cのノード状態240cには0が格納されているので、このノードは空ノードであり、ノード位置が10のノード212cもノード状態が0であって空ノードである。ノード位置が01のノード211cのノード状態は1、ノード種別261cは1であるのでノード211cはリーフノードである。したがって、参照ポインタ251cを含んでいる。参照ポインタ251cには、図示の例では、第1のキー290cと第2のキー290c’からなる2次元キーが格納されている記憶領域を参照するポインタ280cが格納されている。
インデックス格納領域311の参照ポインタ280cが指すエントリの第1のキー290cには“000111”が、第2のキー290c’には“011100”が格納されている。ノード群201cの直近上位のブランチノード210bの弁別ビット位置230bで示されるビット位置1のビット値は、第1のキー290cが“0”、第2のキー290c’が“1”である。リーフノード211bについて説明したと同様に、そのようなビット値の組み合わせのインデックスキーがほかにないことが、ノード群201cのノード位置01に参照ポインタ280cを格納したリーフノード211cが存在することに対応している。
ノード位置11のノード213cのノード状態243cは1、ノード種別263cは0であるので、ノード213cはブランチノードである。弁別ビット位置233cは2であり、代表ノード番号にはノード群201eの代表ノード210eの格納された配列要素の配列番号223cが格納されている。
【0030】
ノード群201eのノード位置00のノード210eのノード状態240eは0なのでノード210eは空ノードであり、同様にノード位置01のノード211eも空ノードである。
ノード位置10と11のノード212e、213eのノード状態242e、243eはともに1、ノード種別260e、261eはともに1であり双方ともリーフノードであることを示している。ノード212e、213eの参照ポインタ252e、253eにはそれぞれ、“011010:010100”というキー列290e、290e’と、“011010:011000”というキー列291e、291e’を格納した記憶領域への参照ポインタ280e、281eが格納されている。
【0031】
ノード群201bのブランチノード212bのリンク先であるノード群201fの代表ノードであるノード210fのノード状態240fは1、ノード位置01のノード211fのノード状態241fも同じく1である。ノード210fのノード種別260fは0でありノード210fはブランチノードである。ノード210fの弁別ビット位置230fには2が格納されている。ノード210fの代表ノード番号にはノード群201gの代表ノード210gの格納された配列要素の配列番号220fが格納されている。ノード211fのノード種別261fは1でありノード211fはリーフノードである。ノード211fの参照ポインタ251fには“100010:010000”というキー列290g、290g’を格納した記憶領域への参照ポインタ280gが格納されている。
ノード位置11のノード213fのノード状態243fは0でありノード213fは空ノードであり、同様にノード212fもノード状態242fが0であるので空ノードである。
【0032】
ブランチノード210fのリンク先であるノード群201gのノード位置00のノード210gのノード状態は0であり、ノード210gが空ノードであることを示している。ノード位置01、10、11のノード211g、212g、213gのノード状態241g、242g、243gは1、ノード種別261g、262g、263gは1であり、ノード211g、212g、213gはリーフノードである。ノード211g、212g、213gのそれぞれの参照ポインタ251g、252g、253gには、“100011:001100”というキー列291g、291g’を格納した記憶領域への参照ポインタ281g、“101100:001000”というキー列291h、291h’を格納した記憶領域への参照ポインタ281h、“101100:001000”というキー列290h、290h’ を格納した記憶領域への参照ポインタ280hが格納されている。
【0033】
図2Bの(2)には、複数のインデックスキーの記憶領域が連続して設けられる例を示し、それら連続した記憶領域全体をインデックスキーの記憶領域311として示したが、インデックスキーは連続した領域に格納されなくてもよい。また、リーフノード同士のツリー構造上での関係と、インデックスキーの記憶領域311におけるインデックスキーの配置順は無関係であってもよい。
【0034】
以下、上述のツリーから第1のキー“101100” と第2のキー“001000”からなる2次元キー(インデックスキー)を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から0、1、2、・・・とする。
まず、第1のキー“101100” と第2のキー“001000”からなるキー列を検索キー列としてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは0であるので、検索キー列の第1のキー“101100”及び第2のキー“001000”のビット位置が0のビット値をみるとそれぞれ1と0である。そこで代表ノード番号の格納された配列番号220aに2進数表示で“10”、すなわち2を加えた配列番号の配列要素に格納されたノード位置10のノード212bにリンクする。
次に、ノード212bの弁別ビット位置232bには1が格納されているので、第1のキー“101100”
及び第2のキー“001000”のビット位置が1のビット値をみるとそれぞれ0と0であるから、代表ノード番号の格納された配列番号222bの配列要素に格納されたノード210fにリンクする。
ノード210fの弁別ビット位置230fには2が格納されているので、第1のキー“101100” 及び第2のキー“001000”のビット位置が2のビット値をみるとそれぞれ1である。そこで代表ノード番号の格納された配列番号220fに2進数表示で“11”、すなわち3を加えた配列番号の配列要素に格納されたノード位置11のノード213gにリンクする。
ノード213gのノード種別263gは1でありリーフノードであることを示しているので、参照ポインタ280hにより示される記憶領域を参照し、そこに格納されたインデックスキー290h、290h’を読み出す。このようにしてカップルドノードツリーを用いた検索が行われる。読み出されたインデックスキーを検索キーと比較すると、上記の例の場合は一致していることが分かる。
【0035】
次に、図2Bを参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図2Bの例で、ルートノード210aの弁別ビット位置230aが0であるのは、インデックスキーを構成する第1のキーと第2のキーの0ビット目の組み合わせに異なるものがあるからである。第1のキーおよび第2のキーの0ビット目の組み合わせが00のインデックスキーのグループはノード位置00のノード210bの下に分類され、前記0ビット目の組み合わせが01のインデックスキーのグループはノード位置01のノード211bの下に分類され、前記0ビット目の組み合わせが10のインデックスキーのグループはノード位置10のノード212bの下に分類され、前記0ビット目の組み合わせが11のインデックスキーのグループはノード位置11のノード213bの下に分類される。
先に述べたように、第1のキーおよび第2のキーの0ビット目の組み合わせが11のインデックスキーは存在しないことから、ノード213bは空ノードとなっている。また、ノード位置01のノード211bがリーフノードであるのは、0ビット目のビット値の組み合わせが01であるインデックスキーがほかになく、0ビット目より下位のビットのビット値によりインデックスキーを弁別する必要のないことに対応している。
ノード210bの弁別ビット位置230bが1であるのは、その下位のリーフノード211c、212e、213eに対応するインデックスキーの第1のキー及び第2のキーの1ビット目より上位のビット値がすべて等しく(0ビット目の組み合わせがすべて00)、1ビット目の組み合わせに異なるものがあるという、インデックスキーの集合の性質を反映している。
同様に、ノード212bの弁別ビット位置232bが1であるのは、その下位のリーフノード211f、211g、212g、213gに対応するインデックスキーの第1のキーおよび第2のキーの1ビット目より上位のビット値がすべて等しく(0ビット目の組み合わせがすべて10)、1ビット目の組み合わせに異なるものがあるという、インデックスキーの集合の性質を反映している。
上記インデックスキーの集合の性質が反映されていることは、ノード群201c、201e、201f、201gにおいても同様である。
【0036】
仮にインデックスキーの集合に、第1のキー291h“101100”、第2のキー291h’“000100”からなるインデックスキーの代わりに第1のキー“101001”、第2のキー“000001”からなるインデックスキーが含まれていたとしても、第1のキーと第2のキーの2ビット目まではそれぞれ第1のキー291hと第2のキー291h’の2ビット目までと等しいので、ノード212gの参照ポインタ281hにより示される記憶領域に格納されるインデックスキーの値が変わるだけで、ツリー構造自体は変わることはない。しかし、第1のキー291h“101100”、第2のキー291h’“000100”からなるインデックスキーに加えて第1のキー“101100”と第2のキー“000000”
からなるインデックスキーが含まれていると、ノード212gはブランチノードとなり、その弁別ビット位置は3であり、該インデックスキーに係るリーフノードは、ノード212gのリンク先のノード群のノード位置10に配置される。
【0037】
上述のようにカップルドノードツリーの構造はインデックスキーの集合の性質を反映しているので、使用中のノードが1つだけのノード群は存在しない。ノード群のノード位置に配置されるノードは、その直近上位のブランチノードの弁別ビット位置のビット値の組み合わせで互いに弁別されるものであるから、互いに弁別される相手のノードが存在する。したがって、使用中のノードが1つだけということはありえないからである。
例えば、図2Bに示すツリーにおいて、仮にノード212eの参照ポインタ280eが指すインデックスキーがインデックスキーの格納領域311に存在せず、ノード212eが空ノードで、ノード群201eの使用中のノードが213eだけであるとすると、ブランチノード213cの弁別ビット位置233cに格納されたビット位置2のビット値により、リーフノード213cの参照ポインタ281eが指すインデックスキーを弁別する必要はない。 そのかわり、ブランチノード210bの弁別ビット位置230bに格納されたビット位置1のビット値の組み合わせ11により、リーフノード213cの参照ポインタ280cが指すインデックスキーと弁別されることになる。すなわち、リーフノード213eはノード群201cのノード位置11に配置されることになり、ノード群201eのノードは全て空となり、ノード群201eはツリー上に存在しなくなる。
また、ノード211fが空ノードの場合にも、ブランチノード210fはノード群201bのノード位置212bに配置され、ノード群201fは不要となり、削除される。
以上説明したように、カップルドノードツリーの構造は、多次元キーの集合に含まれる多次元キーを構成するキーの各ビット位置のビット値により決定される。
【0038】
検索キー列で検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キー列が“101100:000100”であれば、図2Bに示すツリーではノード212gに到達することができる。また、上記説明からも想像がつくように、“101000:000001”を検索キー列とした場合でもノード212gにたどり着き、参照ポインタ281hにより示される記憶領域に格納されたインデックスキーが検索結果キー列として得られる。
このように、カップルドノードツリーに格納されたインデックスキー(キー列)の各キーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【0039】
図3は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施される。カップルドノードツリーが配置される配列309と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック310とインデックスキーの記憶領域311を有するデータ格納装置308は、主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。図2Aの配列100は配列309の一例である。また、図2Bと同様に、インデックスキーの記憶領域311は連続した領域のように図示されているが、不連続の領域でもよいことは当然である。なお、カップルドノードツリーは配列に配置されるとして説明するため、探索経路スタック310には検索中にたどるノードが格納された配列要素の配列番号を記憶すると説明したが、一般的には、ノードの格納された記憶領域のアドレス等のノードの位置を示す情報が記憶される。
【0040】
図3の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできるし、探索経路スタック310を中央処理装置302内のハードウェアとして実現することも可能である。あるいは、配列309は外部記憶装置306に、探索経路スタック310を主記憶装置305に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。以下の説明では、先に述べた参照ポインタ等の場合と同様に、一時記憶領域に格納されたあるいは設定された値を一時記憶領域の名前で呼ぶことがある。
図3に示した例では、カップルドノードツリーのノードを格納した配列要素からなる配列309と、インデックスキーの記憶領域311とは別の領域である。したがって、リーフノードを格納した配列要素にインデックスキーが含まれる場合に比べて、図3の構成では、一般に1つの配列要素に必要な記憶領域の量が少ない。つまり、カップルドノードツリーを格納する配列309からインデックスキーの記憶領域311を分離することによって、キャッシュメモリ303へのカップルドノードツリーの読み込みにおいて1キャッシュブロックあたりに格納されるノード数を増やすことが可能となる。それにより、後述する検索処理等においてキャッシュミスの頻度が減って処理がより高速に行われるようになる。
【0041】
次に、本発明の一実施態様に係るカップルドノードツリーを用いた基本的な操作である、検索、挿入、削除について順に詳しく説明する
図4は、本発明の一実施形態におけるビット列の検索処理を示すフローチャートである。検索キー列は与えられているものとする。
まず、ステップS401において、検索開始ノードを設定する。検索開始ノードの設定は、検索開始ノードの配列番号の指定あるいは取得によりその配列番号、あるいは該配列番号のノードを図示しない検索開始ノード設定エリアに設定することにより行う。なお、上述の検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置」の1つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。検索開始ノード以外についても同様である。
【0042】
次に、ステップS402で、探索経路スタックに取得された配列番号を格納し、ステップS403で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。ステップS404aで読み出したノードからノード状態を取り出し、ステップS404bでノード状態は使用中か判定する。使用中でない、すなわち空ノードであれば、検索結果が空ノードであることを表示して検索処理を終了する。ノード状態が使用中であれば、ステップS404で、読み出したノードから、ノード種別を取り出し、ステップS405で、ノード種別がブランチノードであるか否かを判定する。
【0043】
ステップS405の判定において、読み出したノードがブランチノードである場合はステップS406に移行し、ステップS403で読み出したノードから弁別ビット位置を取り出す。次にステップS407aにおいて列位置に0を設定してステップS407bに進む。列位置は次に説明するステップS407b〜S407eのループで処理をするキーの検索キー列中の位置を示すものである。列位置の初期値をこの例では0としている。
ステップS407bでは、すべてのキーを処理済みか判定する。すべてのキーを処理済みであればステップS408に移行し、処理済みでなければステップS407cに進む。
ステップS407cにおいては、検索キー列から列位置の指すキーを取り出し、ステップS406で取り出した弁別ビット位置の指すビット値を取り出す。次にステップS407dにおいて、ノード位置と名付けるワークエリアの、列位置の指すビット位置に、ステップS407cで取り出したビット値を設定する。次にステップS407eで列位置を更新してステップS407bに戻る。上記ステップS407b〜S407eのループ処理は、リンク先のノードのノード位置を決定するものである。
【0044】
ステップS408では、ステップS403で読み出したノードから代表ノード番号を取り出し、ステップS409aに進んで、ステップS407dで設定したノード位置と代表ノード番号とを加算し、新たな配列番号として、ステップS402に戻る。
以降、ステップS405の判定においてリーフノードと判定されてステップS410aに進むまで、ステップS402からステップS409aまでの処理を繰り返す。ステップS410aでは、リーフノードから参照ポインタを取り出し、検索を終了する。なお、リーフノードに直接インデックスキーを格納する場合には、リーフノードからインデックスキーを取り出して検索を終了することになるので、以下の説明においては、「リーフノードから参照ポインタあるいはインデックスキーを取り出し」のような表記を用いることがある。
【0045】
次に、図5〜図8によりカップルドノードツリーにおけるノード挿入処理を説明する。図5〜図7Bが通常の挿入処理を説明するものであり、図8はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【0046】
図5は挿入処理の前段である検索処理の処理フローを示す図であり、図4に示した検索処理において、挿入キー列を検索キー列とし、検索開始ノードをルートノードとしたものに相当する。
まず、ステップS501aで検索開始ノードにルートノードの配列番号を設定し、ステップS501bで検索キー列に挿入キー列を設定する。インデックスキーへの参照ポインタをリーフノードに格納する実施態様においては、挿入キー列は、挿入処理の前提条件として、予めインデックスキーの格納領域のポインタを取得して、該格納領域に格納されているものとする。
次にステップS510aにおいて、検索キー列により検索開始ノードより図4に示す検索処理を行う。次にステップS510bにおいてステップS510aの検索結果を判定し、検索結果が空ノード、すなわちノード状態が使用中でなければステップS510cに進み、ステップS510aで実行した図4に示す検索処理のステップS409aで得た配列番号の指す配列要素の、ノード状態に使用中を、ノード種別にリーフを、参照ポインタに挿入キー列のポインタを書き込み、挿入処理を終了する。インデックスキーを直接リーフノードに格納する場合は、インデックスキーとして挿入キー列を書き込んで挿入処理を終了する。
【0047】
ステップS510bの判定結果がノード状態は使用中であれば、ステップS510dにおいて、ステップS510aの検索結果で得られた参照ポインタの指すキー列を取り出して比較キー列に設定する。次にステップS510eにおいて、挿入キー列と比較キー列を比較して、挿入キー列と比較キー列が完全に一致するか否かと、挿入キー列と比較キー列の差分ビット位置を得る。挿入キー列と比較キー列の差分ビット位置は、挿入キー列の各キーと比較キー列の各キーをビット列として比較し、各キーにおいて最初に異なるビット値となるビット位置のうち最上位のビット位置とする。ステップS510eの詳細は、後に図7Aを参照して説明する。
次にステップS511aにおいて、ステップS510eでの比較の結果が、挿入キー列のキーと比較キー列のキーが全て等しいものであったかを判定し、等しければ挿入キー列は既にカップルドノードツリーの参照ポインタが指す記憶領域に存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図6AのステップS512以下の処理に進む。
【0048】
図6Aは、挿入するノード群のための配列要素を準備する処理を説明する処理フロー図である。
ステップS512において、配列から空きのノード群を求め、そのノード群のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS513aにおいて、ステップS510eで得た挿入キー列と比較キー列の差分ビット位置により挿入ノード位置及び対ノード位置を得る。ステップS513aの詳細は、後に図7Bを参照して説明する。
次にステップS514aに進み、ステップS512で得た代表ノードの配列番号にステップS513aで得たノード位置を加算した配列番号を得る。次にステップS515bに進み、ステップS512で得た代表ノードの配列番号にステップS513aで得た対ノード位置を加算した配列番号を得る。後に図7Bを参照して詳細に説明するが、ステップS514aで得た配列番号は、挿入キー列をインデックスキーとして格納する記憶領域への参照ポインタを持つリーフノードが格納される配列要素の配列番号である。ステップS515bで得た配列番号は、比較キー列に設定したキー列の参照ポインタ持つリーフノードの直近上位のブランチノードが格納される配列要素のものである。つまり、前段の検索処理で得られたリーフノードに対応するインデックスキーと挿入キー列の差分ビット位置における各キーのビット値の組み合わせにより、挿入されるノード群のうちどのノード位置に挿入キー列への参照ポインタを保持するリーフノード及び前段の検索処理で得られたリーフノードの直近上位のブランチノードが格納されるかが決定される。
さらにステップS517aにおいて、ステップS510eで得た差分ビット位置を、差分ビット位置と名付けるワークエリアに設定し、図6Bに示すステップS518に進む。
【0049】
図6Bは図6Aで準備された配列要素にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
ステップS518〜ステップS523までの処理は、挿入するノード群のカップルドノードツリー上の位置を求める処理であり、ステップS524以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
ステップS518において、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップS524に移行し、指していなければステップS519に進む。
【0050】
ステップS519において、探索経路スタックのスタックポインタを1つ戻してそこにスタックされている配列番号を取り出す。
ステップS520に進み、ステップS519で取り出した配列番号の配列要素を配列からノードとして読み出す。次にステップS521において、ステップS520で読み出したノードから、弁別ビット位置を取り出し、ステップS522に進み、ステップS521で取り出した弁別ビット位置がステップS517aで設定した差分ビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
ステップS522の判定結果が否定であれば、ステップS518に戻り、ステップS518での判定が肯定になるか、ステップS522での判定が肯定になるまでステップS518〜ステップS522の処理を繰り返す。ステップS522での判定が肯定になると、ステップS523に進む。ステップS523では、探索経路スタックのスタックポインタを1つ進め、ステップS524以下の処理に移行する。
【0051】
上記ステップS518〜ステップS523で説明した処理は、挿入するノード群の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの差分ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの直近下位のブランチノードのリンク先を挿入するノード群の挿入位置とするものである。
また、探索経路スタックを逆にたどりルートノードに至った場合は、ルートノードのリンク先が挿入位置となる。
【0052】
例えば図2Bのカップルドノードツリーにインデックスキー “101000:001000”を挿入するとき、検索結果のインデックスキーは、ノード213gに対応するインデックスキー “101100:001000”になる。この例の場合、挿入キー列と比較キー列の差分ビット位置は3であり、弁別ビット位置230fは2なので、ノード210fの直近下位のノード213gのリンク先が挿入位置になる。つまり、ノード213gはブランチノードとなり、その弁別ビット位置は挿入キー列と比較キー列の差分ビット位置3となり、リンク先として挿入されるノード群のノード位置00に挿入キー列に対応するリーフノードが配置され、ノード位置10にノード213gの内容が転写されたリーフノードが配置される。
【0053】
次に、ステップS524以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップS524では探索経路スタックからスタックポインタの指す配列番号を取り出す。
ステップS525aに進み、ステップS514aで得た配列番号の指す配列要素の、ノード状態に使用中を、ノード種別にリーフを、参照ポインタに挿入キー列のポインタをあるいはインデックスキーとして挿入キー列を書き込む。
ステップS526に進み、配列からステップS524で得た配列番号の配列要素を読み出す。
次にステップS527において、ステップS515bで得た配列番号の配列要素にステップS526で読み出した内容を書き込む。
最後にステップS528aにおいて、ステップS524で得た配列番号の指す配列要素のノード状態に使用中を、ノード種別にブランチを、弁別ビット位置にステップS517aで設定した差分ビット位置を、代表ノード番号にステップS512で得た配列番号を書き込み、処理を終了する。
【0054】
図7Aは、図5に示すステップS510eの挿入キー列と比較キー列の差分ビット位置を得る処理を詳細に説明する図である。図7Aに示す処理により得られる挿入キー列と比較キー列の差分ビット位置は、下記説明から明らかなとおり、挿入キー列と比較キー列の各キーの間の差分ビット位置の最小値である。
【0055】
図に示すように、ステップS701において列位置に初期値として0を設定する。また、ステップS702において差分ビット位置に初期値として、差分ビット位置の最大値を設定する。キー列を構成するキーがnビットからなるビット列であり先頭のビット位置を0とすれば、差分ビット位置の初期値はn−1となる。
次にステップS703において、キー列のすべてのキーについて処理済みであるか判定する。処理済みであればステップS712に移行し、処理済みでなければステップS704に進む。
ステップS704では、挿入キー列から、列位置の指すキーを取り出し、挿入キーとして設定する。
ステップS705に進み、図5に示すステップS510dで設定した比較キー列から、列位置の指すキーを取り出し、比較キーとして設定する。
【0056】
次にステップS706に進み、挿入キーは比較キーと一致するか判定する。一致すれば列位置に設定した値を更新してステップS703に戻り、一致しなければ、ステップS707に移行して挿入キーと比較キーとのビット列比較を例えば排他的論理和で行い差分ビット列を得る。
ステップS708に進み、ステップS707で得た差分ビット列から、上位0ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するCPUではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
次にステップS709において、ステップS708で得たビット位置が差分ビット位置に設定された値より小さいか判定する。小さければステップS710で差分ビット位置にステップS708で得たビット位置を設定してステップS711に進み、小さくなければ直接ステップS711に進む。
【0057】
上述のステップS703〜ステップS711の処理を全てのキーについて繰り返し、すべてのキーについての処理が終了するとステップS712において、差分ビット位置に設定された値が差分ビット位置の最大値であるか判定する。最大値であれば、ステップS706での判定が全てのキーにおいて一致することであるので、完全一致を表示して処理を終了し、最大値でなければ非完全一致を表示して処理を終了する。完全一致/非完全一致の表示は、例えば1ビットのフラグを設けることにより可能である。
【0058】
図7Bは、図6Aに示すステップS513aの、挿入キー列と比較キー列の差分ビット位置の指す挿入キー列と比較キー列のビット値から、図6AのステップS512で取得され図6Bの処理により挿入位置が求められたノード群に格納するノードのノード位置を求める処理を詳細に説明する図である。
【0059】
図に示すように、ステップS713において列位置に初期値として0を設定する。次にステップS714において、キー列のすべてのキーについて処理済みであるか判定する。処理済みであればステップS721に移行し、処理済みでなければステップS715に進む。
ステップS715では、挿入キー列から列位置の指すキーを取り出し、差分ビット位置の指すビット値を取り出す。次にステップS716で、挿入ノード位置の、列位置の指すビット位置に、ステップS716で取り出したビット値を設定する。
次にステップS717に進み、比較キー列から列位置の指すキーを取り出し、差分ビット位置の指すビット値を取り出す。次にステップS718で、対ノード位置の、列位置の指すビット位置に、ステップS718で取り出したビット値を設定する。次にステップS719で列位置を更新してステップS714に戻る。
【0060】
ステップS714からステップS719までのループ処理を、キー列を構成する全てのキーについて実行すると、挿入ノード位置及び対ノード位置の全てのビット値が設定されるので処理を終了する。
【0061】
図8は、本発明の一実施形態におけるルートノードの挿入処理を含むリーフノードの挿入処理全体の処理フローを説明する図である。
ステップS551において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図5〜図6Bを用いて説明した通常の挿入処理が行われる。
ステップS551での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。この場合にもインデックスキーへの参照ポインタをリーフノードに格納する実施態様においては、挿入キー列は挿入処理の前提条件として予めインデックスキーの格納領域のポインタを取得して、その格納領域に格納されているものとする。
まず、ステップS552において、配列から空きのノード群を求め、そのノード群のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS553において、ステップS552で得た配列番号に0を加えた配列番号を求める。(実際には、ステップS552で取得した配列番号に等しい。)次にステップS554eにおいて、ステップS553で得た配列番号の配列要素すなわち挿入するルートノードに対応する配列要素の、ノード状態に使用中、ノード種別にリーフを、参照ポインタに挿入キー列のポインタをあるいはインデックスキーとして挿入キー列を書き込む。そしてステップS556では、ステップS553で取得したルートノードの配列番号を登録して処理を終了する。
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図8及び図5〜図6Bの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【0062】
次に図9A、図9Bを参照して、本発明の一実施形態におけるカップルドノードツリーから特定のインデックスキーに対応するリーフノードを削除する処理フローを説明する。
図9Aは、削除処理の前段である検索処理の処理フローを示す図であり、図4に示した検索処理において、削除キー列を検索キー列とし、検索開始ノードをルートノードとしたものに相当する。
まず、ステップS901aで検索開始ノードにルートノードの配列番号を設定し、ステップS901bで検索キー列に削除キー列を設定する。
次にステップS910aにおいて、検索キー列により検索開始ノードより図4に示す検索処理を行い、ノード状態が空でなければ参照ポインタあるいはインデックスキーを取得する。ステップS910bにおいて、ステップS910aでの検索結果のノードのノード状態が使用中であるか判定し、使用中でなければ削除失敗を返し、使用中であれば、ステップS910dに進んで参照ポインタの指すキー列あるいはインデックスキーを取り出して比較キー列に設定する。
次にステップS910eにおいて、図7Aに示す処理により削除キー列と比較キー列から差分ビット位置を得る。ステップS911においてステップS910eで実行した図7Aの処理の結果として完全一致が表示されているか、すなわち削除キー列と比較キー列のすべてのキーが等しいか判定し、等しくなければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図9BのステップS912a以下の処理に進む。
【0063】
図9Bは、削除処理の後段の処理フローを説明する図である。
まず、ステップS912aで、検索結果のノードが属するノード群に3つ以上のノードが格納されているか、すなわちノード状態が使用中であるノードが3つ以上あるか判定する。この判定は、先に図3に示すハードウェア構成例に関連して「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる」と述べたように、検索処理において得られるノード位置を記憶しておき、探索経路スタックにスタックされている配列番号と組み合わせてノード群内の各ノード位置のノード状態にアクセスすることにより行うことができる。
【0064】
ステップS912aでの判定が3つ以上のノードが格納されている、であれば、削除対象のノードを削除しても2つのノードが残ることから、ステップS912bに移行してステップS910aで実行した図4に示す検索処理のステップS409で得た配列番号、すなわち探索経路スタックに格納されている配列番号の配列要素に格納されたノードのノード状態に空を書き込み、処理を終了する。
【0065】
ステップS912aでの判定が3つ以上のノードは格納されていない、であればステップS912に移行する。先に述べたように、使用中のノードが1つだけのノード群はルートノードの属するノード群以外には存在しないことから、この場合には使用中のノードは2つであり、そのうち1つのノード状態を空にすることから、他の1つのノードを別のノード群に移し、元のノード群を削除することになる。
ステップS912では、探索経路スタックに2つ以上の配列番号が格納されているか判定する。2つ以上の配列番号が格納されていないということは、言い換えれば1つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップS918に移行し、ステップS901aで得たルートノードの配列番号に係るノード群を削除し、さらにステップS919でルートノードの配列番号の登録を抹消して、処理を終了する。
【0066】
ステップS912において探索経路スタックに2つ以上の配列番号が格納されていると判定されたときはステップS913aに進み、ノード群より、削除対象のノード以外のもう1つの使用中のノードの内容を読み出す。ステップS913aの処理の詳細は、後に図10を参照して説明する。
次にステップS915において探索経路スタックのスタックポインタを1つ戻して、配列番号を取り出し、ステップS916においてその配列番号の指す配列要素に、ステップS913aで読み出した内容を書き込む。この処理は、先に述べた他のノードを別のノード群に移すことに相当する。
続くステップS917において、ステップS910aで実行した図4に示す検索処理のステップS408で得た代表ノード番号に係るノード群を削除し、処理を終了する。
【0067】
図10は、図9Bに示すステップS913aの、ノード群より、削除対象のノード以外のもう1つの使用中のノードの内容を読み出す処理を詳細に説明する図である。
図に示すように、ステップS101でノード位置に初期値0を設定する。次にステップS102に進み、ステップS910aで実行した図4に示す検索処理のステップS408で得た代表ノード番号にノード位置に設定された値を加えて配列番号を求める。ステップS103で、配列から、ステップS102で求めた配列番号の指す配列要素をノードとして読み出し、ステップS104でその読み出したノードから、ノード状態を取り出す。
次にステップS105において、その取り出したノード状態は使用中であるか判定し、使用中でなければステップS107に進み、使用中であればステップS106に進む。
ステップS106では、ステップS102で求めた配列番号が削除対象のノードの配列番号、すなわちステップS910aで実行した図4に示す検索処理のステップS409aで得た配列番号と一致するか判定し、一致するのであればステップS107に進み、一致しなければ、削除対象のノード以外のもう1つの使用中のノードの内容をステップS103で読み出しているので、処理を終了する。
ステップS107においては、ノード位置を更新してステップS102に戻る。
【0068】
上述の説明では、ノード位置の最小値である0を初期値としてノード位置の昇順にもう1つの使用中のノードを探索しているが、探索の順番はこれに限ることなく例えば降順に探索することも可能である。また、図のステップS106において、ステップS102で求めた配列番号が削除対象のノードの配列番号と一致するか判定しているが、この判定をステップS102の直後に行うことができることは明らかである。
【0069】
次に、具体例により、本発明の一実施形態に係る削除処理と挿入処理を説明する。
図11A及び図11Bは、図2Bに例示したダブル・カップルドノードツリーにおいて、“000111:011100”を削除キー列として削除処理を行う例を説明する図である。図11Aに示したダブル・カップルドノードツリーは、ノード群201f以下のノードは記載を省略している。また、インデックスキーの格納領域311についても、ノード群201f以下のリーフノードに関するものは省略している。削除キー列“000111:011100”は、第1のキー“000111”と第2のキー“011100”から構成されるキー列であり、一時記憶領域である削除キー270に格納されている。
探索経路スタック310には配列番号が格納されており、そのスタックポインタは配列番号220b+1を指している。図中太枠で囲まれたノードが検索処理でたどられたノードであり、その配列番号がルートノード210aのものからリーフノード211cのものまで探索経路スタック310に積まれている。
【0070】
削除キー列“000111:011100”による検索処理においては、まず始めにルートノード210aの配列番号220を取得し、それを探索経路スタック310に格納する。ルートノード210aの弁別ビット位置230aが0であり、第1のキー及び第2のキーのビット位置0のビット値がともに0、であるので、代表ノード番号220aにビット値0を加えた配列番号220aが探索経路スタック310に格納される。
次に配列番号220aの指すノード210bが読み出され、ブランチノードであることが判定される。その弁別ビット位置230bが1であり、第1のキーのビット位置1のビット値が0、第2のキーのビット位置1のビット値が1であるので、代表ノード番号220bに1を加えて配列番号220b+1を得てそれを探索経路スタック310に格納する。
次にノード211cが読み出され、ノード種別261cは1であり、リーフノードであることを示している。このリーフノードに対応するインデックスキー(キー列290c、290c’)は、参照ポインタ280cにより示される記憶領域に格納されている。その記憶領域はインデックスキーの記憶領域311の一部である。そこで参照ポインタ280cの参照するインデックスキーの値は“000111:011100”であり、削除キー270に格納されたキー列と一致している。
【0071】
図11Aに示した状態において、削除対象のノード211c以外のもう1つの使用中のノード213cの内容が読み出され、その内容が、探索経路スタック310のスタックポインタを1つ戻したところに格納されている配列番号220aの配列要素(ノード210b)に書き込まれる。その後ノード群201cを削除する。ノード群が削除された配列要素は空となり、再利用可能となる。
【0072】
図11Bに示したダブル・カップルドノードツリーは、削除処理の終了後のものである。ノード210bのノード種別260b、弁別ビット位置230b、代表ノード番号220bには、括弧書きで示すように、ノード213cに格納されていた値がそのまま格納されている。また、探索経路スタック310のスタックポインタは配列番号220aを指している。
【0073】
次に、削除対象のノードが属するノード群に使用中のノードが3以上含まれる場合の削除処理の具体例を説明する。
図11C及び図11Dは、図2Bに例示したダブル・カップルドノードツリーにおいて、“011010:100000”を削除キー列として削除処理を行う例を説明する図である。図11Cに示したダブル・カップルドノードツリーは、ノード群201f以下及びノード群201c以下のノードは記載を省略している。また、インデックスキーの格納領域311についても、ノード群201f以下のリーフノードに関するものは省略している。削除キー列“011010:100000”は、第1のキー“011010”と第2のキー“100000”から構成されるキー列であり、一時記憶領域である削除キー270に格納されている。
探索経路スタック310には配列番号が格納されており、そのスタックポインタは配列番号220a+1を指している。図中太枠で囲まれたノードが検索処理でたどられたノードであり、その配列番号がルートノード210aのものからリーフノード211bのものまで探索経路スタック310に積まれている。
【0074】
削除キー列“011010:100000”による検索処理においては、まず始めにルートノード210aの配列番号220を取得し、それを探索経路スタック310に格納する。ルートノード210aの弁別ビット位置230aが0であり、第1のキー及び第2のキーのビット位置0のビット値がそれぞれ0、1であるので、代表ノード番号220aにビット値1を加えた配列番号220a+1が探索経路スタック310に格納される。配列番号220a+1の指すノード211bが読み出され、ノード種別261bは1であり、リーフノードであることを示している。このリーフノード211bに対応するインデックスキー(キー列290d、290d’)は、参照ポインタ281dにより示される記憶領域に格納されている。参照ポインタ281dの参照するインデックスキーの値は“011010:100000”であり、削除キー270に格納されたキー列と一致している。
削除対象のノード211bが属するノード群201bには使用中のノードが210b、211b、212bと3つあるので、削除対象であるノード211bのノード状態に0を書き込んで空とし、図11Dに示す削除処理後のダブル・カップルドノードツリーが得られる。
【0075】
次に、図12A及び図12Bを参照して挿入処理の具体例1を説明する。具体例1は、挿入キー列による検索結果としてインデックスキーが得られた場合、すなわち図5に示すステップS510bの判定がノード状態は使用中であるとなった場合のものである。
図12Aに示すのは、キー列“0100:0001”、“0001:0010”、“0000:0011”をインデックスキーとして参照する参照ポインタ1281b、1281c、1280cを持つカップルドノードツリーである。
インデックスキーの格納領域311内の参照ポインタ1281bの指す記憶領域には、第1のキー1291b“0100”と第2のキー1291b’“0001”からなるキー列が格納されている。同様に、参照ポインタ1281cの指す記憶領域には、第1のキー1291c“0001”と第2のキー1291c’“0010”からなるキー列が格納され、参照ポインタ1280cの指す記憶領域には、第1のキー1290c“0000”と第2のキー1290c’“0011”からなるキー列が格納されている。
これから挿入しようとする挿入キー列は図示の例では“0001:0000”である。挿入キー列は、先に述べたように、インデックスキーの格納領域311のポインタ1280dを取得して、ポインタ1280dの指す領域に、第1のキー1290d、第2のキー1290d’として格納されていることを前提としている。
【0076】
図示のツリーはノード群1201a、1201b、1201cで構成されている。
ノード群1201aの代表ノードはルートノード1210aであり、弁別ビット位置には1が保持されている。ノード群1201aの下位のノード群1201bの代表ノード1210bはブランチノードであり、弁別ビット位置には3が保持され、代表ノード1210bと同一のノード群1201bに属する使用中のノード1212bはリーフノードであり、キー列1291b、1291b’への参照ポインタ1281bが保持されている。ブランチノードであるノード1210bはノード群1201cにリンクしている。
ノード群1201cを構成する使用中のノード1211cと1212cはともにリーフノードであり、それぞれキー列1290c、1290c’とキー列1291c、1291c’への参照ポインタ1280c、1281cが格納されている。ノード1211cと1212cのノード位置はそれぞれ01と10である。
【0077】
挿入キー列の第1のキー1290dと第2のキー1290d’の1ビット目のビット値の組み合わせが00、3ビット目のビット値の組み合わせが10であることから、図示の例の場合、挿入キー列で検索をすると、ルートノード1210aからノード1210bを経由して参照ポインタ1281cの格納されたリーフノード1212cに至り、比較キー列として、1291c、1291c’ “0001:0010”が設定される。
【0078】
図12Bは、挿入処理後のカップルドノードツリーを説明する図である。図12Aに示すカップルドノードツリーに対して、挿入キー列1290d、1290d’への参照ポインタ1280dを持つリーフノード1210dと比較キー列の参照ポインタが格納されるリーフノード1212cの直近上位のブランチノード1210bの内容が転写されるノード1211dを含むノード群1201dがブランチノード1210bのリンク先として挿入されている。
挿入キー列と比較キー列の差分ビット位置は図示の場合では2であること、ブランチノード1210bの弁別ビット位置が3で差分ビット位置より大きくその直近上位のブランチノード1210aの弁別ビット位置が1で差分ビット位置より小さいことから、ノード群1201dの挿入位置は、配列番号1220bの指すノード1210bの直近下位となる。
挿入キー列の参照ポインタが格納されるリーフノード1210dが配置されるノード位置(挿入ノード位置)は、挿入キー列の差分ビット位置のビット値の組み合わせである00であり、比較キー列の参照ポインタが格納されるリーフノード1212cの直近上位のブランチノード1210bの内容が転写されるノード1211dが配置されるノード位置(対ノード位置)は、比較キー列の差分ビット位置のビット値の組み合わせである01である。
また、ブランチノード1210bの弁別ビット位置には挿入キー列と比較キー列の差分ビット位置である2が書き込まれ、代表ノード番号にはノード群1201dの代表ノード1210dの配置された配列要素の配列番号1220dが書き込まれ、図12Bに示す構成のカップルドノードツリーとなる。
【0079】
図12C及び図12Dは挿入処理の具体例2を説明する図である。具体例2は、図5に示すステップS510bの判定がノード状態は空であるとなった場合のものである。
図12Cに示す挿入処理前のカップルドノードツリーは図12Aに示すものと同一であるが、インデックスキーの格納領域311に格納された挿入キー列が“0001:0011”であって図12Aに示すものと異なり、参照ポインタ1281dの指す記憶領域に格納されている。
【0080】
挿入キー列“0001:0011”によりルートノード1210aから検索を実行すると、ブランチノード1210bを経由して空ノード1213cに至る。そこで、ノード1213のノード状態に1を書き込んで使用中とし、ノード種別にリーフノードであることを示す1を書き込み、参照ポインタに挿入キー列“0001:0011”の参照ポインタ1281dを書き込む。以上の処理により、図12Dに示す挿入処理後のカップルドノードツリーが得られる。
【0081】
図13は、3つのキーからなるキー列による検索処理に用いる、本発明の一実施形態に係るカップルドノードツリーのツリー構造を概念的に示す図である。本実施形態のキー列を3次元キー、カップルドノードツリーをトリプル・カップルドノードツリーということがある。
トリプル・カップルドノードツリーを用いた検索では、ダブル・カップルドノードツリーについて先に説明したと同様に、3次元キーを構成する各次元のキーの弁別ビット位置のビット値の組み合わせによりリンク先が決定される。したがって、ノード群には2の3乗、すなわち8個のエントリが存在する。ノード位置は000〜111の3ビットで表される。
【0082】
符号410aで示すのがルートノードである。図示の例では、ルートノード410aは配列番号420に配置されたノード群401aの代表ノードとしている。
ツリー構造としては、ルートノード410aの下にノード群401bが、その下層にノード群401cとノード群401fが配置され、ノード群401fの下層にはノード群401g、401h、401iが配置されている。ノード群401cの下にはノード群401dが、さらにその下位にノード群401eが配置されている。
各ノードの前に付された3ビットの符号はノード位置を示す。検索キー列の各キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のインデックスキーに対応するリーフノードを見つけることは、ダブル・カップルドノードツリーの場合と同様である。
【0083】
図示された例では、ルートノード410aのノード状態440aは1、ノード種別460aは0でブランチノードであることを示し、弁別ビット位置430aは0を示している。代表ノード番号は420aであり、それはノード群401bの代表ノード410bの格納された配列要素の配列番号である。
【0084】
ノード群401bはノード410b、411b、412b、413b、414b、415b、416b、417bで構成される。代表ノード410bとノード位置が111であるノード417bのノード状態447bのみが1で使用中であり、他のノードは空ノードである。ノード410bのノード種別460bとノード417のノード種別467bはともに0であり、ブランチノードであることを示している。
ノード410bの弁別ビット位置430bには1が格納され、リンク先の代表ノード番号にはノード群401cの代表ノード410cの格納された配列要素の配列番号420bが格納されている。ノード417bの弁別ビット位置437bには2が格納され、リンク先の代表ノード番号にはノード群401fの代表ノード410fの格納された配列要素の配列番号427bが格納されている。
【0085】
ブランチノード410bのリンク先である代表ノード410cが属するノード群401cの使用中であるノードはビット位置010のノード412cとビット位置110のノード416cである。ノード412cのノード種別462cは1でリーフノードであることを示し、参照ポインタ452cにはインデックスキーが記憶された記憶領域へのポインタ482cが格納されている。ノード416cのノード種別466cは0でブランチノードであることを示し、弁別ビット位置436cには2が格納され、代表ノード番号にはノード群401dの代表ノード410dの格納された配列要素の配列番号426cが格納されている。
【0086】
ブランチノード416cのリンク先である代表ノード410dが属するノード群401dの使用中であるノードはビット位置100のノード414dとビット位置111のノード417dである。ノード414dのノード種別464dは0でブランチノードであることを示し、弁別ビット位置434dには5が格納され、代表ノード番号にはノード群401eの代表ノード410eの格納された配列要素の配列番号424dが格納されている。ノード417dのノード種別467dは1でリーフノードであることを示し、参照ポインタ457dにはインデックスキーが記憶された記憶領域へのポインタ487dが格納されている。
【0087】
ブランチノード414dのリンク先である代表ノード410eが属するノード群401eの全てのノード410e〜417eはそれぞれのノード状態440e〜447eが1、ノード種別460e〜467eが1でリーフノードであり、参照ポインタ450e〜457eにはインデックスキーが記憶された記憶領域へのポインタ480e〜487eが格納されている。
【0088】
ブランチノード417bのリンク先である代表ノード410fが属するノード群401fのノード410f〜413fは、ノード410fのノード状態440fが0であるように空ノードである。ノード414fはリーフノード、ノード415f〜417fはブランチノードである。ノード414fの参照ポインタにはインデックスキーが記憶された記憶領域へのポインタ484fが格納されている。ブランチノード415fの弁別ビット位置は4であり、代表ノード番号にはノード群401gの代表ノード410gが配置された配列要素の配列番号425fが格納されている。ブランチノード416fの弁別ビット位置は5であり、代表ノード番号にはノード群401iの代表ノード410iが配置された配列要素の配列番号426fが格納されている。ブランチノード417fの弁別ビット位置は3であり、代表ノード番号にはノード群401hの代表ノード410gh配置された配列要素の配列番号427fが格納されている。
【0089】
ブランチノード415fのリンク先である代表ノード410gが属するノード群401gの使用中のノードはノード位置011のノード413gとノード位置100のノード414gだけである。ノード413gのノード種別463gとノード414gのノード種別464gはともに1であり、両ノードはリーフノードである。それぞれの参照ポインタ453gと454gには、インデックスキーが記憶された記憶領域へのポインタ483gと484gが格納されている。
【0090】
ブランチノード416fのリンク先である代表ノード410iが属するノード群401iの使用中のノードはノード位置100のノード414iとノード位置101のノード415iだけである。ノード414iのノード種別464iとノード415iのノード種別465iはともに1であり、両ノードはリーフノードである。それぞれの参照ポインタ454iと455iには、インデックスキーが記憶された記憶領域へのポインタ484iと485iが格納されている。
【0091】
ブランチノード417fのリンク先である代表ノード410hが属するノード群401hの使用中のノードはノード位置101のノード415hとノード位置111のノード417hだけである。ノード415hのノード種別465hとノード417hのノード種別467hはともに1であり、両ノードはリーフノードである。それぞれの参照ポインタ455hと457hには、インデックスキーが記憶された記憶領域へのポインタ485hと487hが格納されている。
【0092】
図13には、各リーフノードの参照ポインタで参照されるインデックスキー(3次元キー)は記載していないが、図13に記載されたルートノードからリーフノードまで、弁別ビット位置とリンク先のノード位置に注目することにより、インデックスキーの値がどの範囲のものであるかを決定することができる。
例えば、リーフノード412cの参照ポインタ482cで参照される3次元キーについて考察すると、ルートノード410aの弁別ビット位置430aが0、リンク経路のブランチノード410bのノード位置が000であることから、各次元のキーの0ビット目が0、ブランチノード410bの弁別ビット位置430bが1、リンク先のリーフノード412cのノード位置が010であることから、各キーの1ビット目のビット値は、第1のキーは0、第2のキーは1、第3のキーは0である。すなわち、リーフノード412cの参照ポインタ482cで参照される3次元キーは、“00xxxx:01xxxx:00xxxx”(xは0,1のいずれか任意の値)の値を有するものである。
他のリーフノードに関連する3次元キーについても、同様にツリーの構造から求めることが可能である。
【0093】
また、トリプル・カップルドノードツリーを用いた検索処理、挿入処理、削除処理については、ダブル・カップルドノードツリーを用いた検索処理、挿入処理、削除処理と同様に実行可能であることは当業者にとって明らかである。
さらに、2次元、あるいは3次元に限らず、次元数に応じてノード位置のビット数を増やすことにより、本発明はより高次元の多次元キーによる検索に拡張可能であることは明らかである。
【0094】
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。例えばリーフノードが、インデックスキーを格納した記憶領域の位置を示す情報に代えてインデックスキー自体を含むようにすることが可能であることは、当業者に自明である。
また、本発明のビット列検索方法を実行する装置が、カップルドノードツリーを格納する記憶手段と図4に示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
さらに、図5〜図8に示した挿入処理とその均等物をコンピュータに実行させるプログラムにより、本発明の挿入方法が実現可能であり、図9A、図9B及び図10に示した削除処理とその均等物をコンピュータに実行させるプログラムにより、本発明の削除方法が実現可能であることも明らかである。そして、それらのプログラムにより、ブランチノードとリーフノードの識別手段、ブランチノードの弁別ビット位置に応じてリンク先のノード対のどちらかにリンクする手段等がコンピュータ上に実現される。
したがって、上記プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の実施の形態に含まれる。さらに、本発明のカップルドノードツリーのデータ構造及びそのデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体も、本発明の実施の形態に含まれる。
以上詳細に説明した、本発明が提供する新しいデータ構造であるカップルドノードツリーを用いることにより、多次元キーを取り扱うことができ、より高速なビット列データの検索を行うことが可能となる。しかもビット列データの追加削除も容易に実行することができる。
【図面の簡単な説明】
【0095】
【図1】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【図2A】配列に格納されたダブル・カップルドノードツリーの構成例を説明する図である。
【図2B】ダブル・カップルドノードツリーのツリー構造を概念的に示す図である。
【図3】本発明を実施するためのハードウェア構成例を説明する図である。
【図4】本発明の一実施形態における検索処理を示すフローチャートである。
【図5】本発明の一実施形態における挿入処理の前段である検索処理の処理フローを示す図である。
【図6A】本発明の一実施形態における挿入処理における挿入するノード群のための配列要素を準備する処理フローを説明する図である。
【図6B】ノード群を挿入する位置を求め、ノード群の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。
【図7A】挿入キー列と比較キー列の差分ビット位置を得る処理フローを説明する図である。
【図7B】挿入されるノード群に格納するノードのノード位置を求める処理フローを説明する図である。
【図8】本発明の一実施形態におけるルートノードの挿入処理を含むリーフノードの挿入処理全体の処理フローを説明する図である。
【図9A】本発明の一実施形態における削除処理の前段である検索処理の処理フローを示す図である。
【図9B】本発明の一実施形態における削除処理の後段の処理フローを説明する図である。
【図10】ノード群から削除対象のノード以外の使用中のノードを求める処理フローを説明する図である。
【図11A】第1の削除処理例における削除処理前のダブル・カップルノードツリーと削除キーを説明する図である。
【図11B】第1の削除処理例における削除処理後のダブル・カップルドノードツリー例を示す図である。
【図11C】第2の削除処理例における削除処理前のダブル・カップルノードツリーと削除キーを説明する図である。
【図11D】第2の削除処理例における削除処理後のダブル・カップルドノードツリー例を示す図である。
【図12A】第1の具体例における挿入処理前のカップルドノードツリー例を示す図である。
【図12B】第1の具体例における挿入処理後のカップルドノードツリー例を示す図である。
【図12C】第2の具体例における挿入処理前のカップルドノードツリー例を示す図である。
【図12D】第2の具体例における挿入処理後のカップルドノードツリー例を示す図である。
【図13】配列に格納されたトリプル・カップルドノードツリーのツリー構造を概念的に示す図である。
【符号の説明】
【0096】
10、20、30 配列番号
100 配列
101、122、123 ノード
102a、114a、117a ノード状態
102b、114b、117b ノード種別
103、115 弁別ビット位置
104、116 代表ノード番号
111、121 ノード群
112、122 ノード[0]、ノード位置00のノード
113、123 ノード[1]、ノード位置01のノード
112a、122a ノード[2]、ノード位置10のノード
113a、123a ノード[3]、ノード位置11のノード
118a 参照ポインタ
301 データ処理装置
302 中央処理装置
303 キャッシュメモリ
304 バス
305 主記憶装置
306 外部記憶装置
307 通信装置
308 データ格納装置
309 配列
310 探索経路スタック
311 インデックスキーの格納領域
【技術分野】
【0001】
本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する検索処理に関するものであり、特に本出願人が特開2008−015872号公報及び特願2006−293619において提案したカップルドノードツリーを用いたタイプの検索装置、検索方法及びそのプログラムに関するものである。
【背景技術】
【0002】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【0003】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの1つとして、パトリシアツリーという木構造が知られている。
【0004】
図1は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【0005】
図1の例では、インデックスキー“100010”を保持するノード1750aがルートノードとなっており、その検査ビット位置1730aは0である。ノード1750aの左リンク1740aにはノード1750bが接続され、右リンク1741aにはノード1750fが接続されている。ノード1750bの保持するインデックスキーは“010011”であり、検査ビット位置1730bは1である。ノード1750bの左リンク1740bにはノード1750cが、右リンク1741bにはノード1750dが接続されている。ノード1750cが保持するインデックスキーは“000111”、検査ビット位置1730cは3である。ノード1750dが保持するインデックスキーは“011010”、検査ビット位置1730dは2である。
【0006】
ノード1750cから実線で接続された部分はノード1750cの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ1740cは、その欄が空欄であることを示している。点線の接続された右ポインタ1741cの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード1750cを右ポインタ1741cが指定していることを表している。ノード1750dの右ポインタ1741dはノード1750d自身を指しており、左リンク1740dにはノード1750eが接続されている。ノード1750eの保持するインデックスキーは“010010”、検査ビット位置1730eは5である。ノード1750eの左ポインタ1740eはノード1750bを、右ポインタ1741eはノード1750eを指している。
【0007】
また、ノード1750fの保持するインデックスキーは“101011”であり、検査ビット位置1730fは2である。ノード1750fの左リンク1740fにはノード1750gが、右リンク1741fにはノード1750hが接続されている。ノード1750gの保持するインデックスキーは“100011”であり、検査ビット位置1730gは5である。ノード1750gの左ポインタ1740gはノード1750aを、右ポインタ1741gはノード1750gを指している。ノード1750hの保持するインデックスキーは“101100”であり、検査ビット位置1730hは3である。ノード1750hの左ポインタ1740hはノード1750fを、右ポインタ1741hはノード1750hを指している。
【0008】
図1の例では、ルートノード1750aからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が1であるか0であるか判定を行い、1であれば右リンクをたどり、0であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば(図1において点線で示されたこの逆戻りのリンクをバックリンクという)、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【0009】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は1回ですむことなどのメリットがあるが、各ノードからの2つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【0010】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献1に開示された技術がある。下記特許文献1に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。しかしながら、下記特許文献1に開示されたものにおいても、1つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを1つとしたため、例えば図1に示したパトリシアツリーの最下段の部分である左ポインタ1740c、右ポインタ1741h等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【0011】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願2006−187827に係る下記特許文献2において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが1つのときはリーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を開示した。特許文献2においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。また、カップルドノードツリーの構成が、インデックスキーの集合により一意に規定されることも説明されている。
【0012】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願2006−293619において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの一般化された検索あるいはインデックスキーの最大値/最小値を求める手法及びカップルドノードツリーに格納されたインデックスキーを昇順または降順に取り出す手法等を提案した。一般化された検索手法であるカップルドノードツリーの任意のノードを検索開始ノードとする検索は、前記検索開始ノードをルートノードとするカップルドノードツリーの任意の部分木を検索対象として、検索キーによる検索を実行するものである。その検索は、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより行われ、前記リーフノードに含まれるインデックスキーが、検索結果キーとして得られる。
【0013】
インデックスキーの最大値/最小値を求める手法は、代表ノードあるいは代表ノードと対を成すノード(以下、非代表ノードということがある。)のみをリーフノードに至るまでリンクするものであり、カップルドノードツリーに格納されたインデックスキーを昇順または降順に取り出す手法は、特許文献2で説明したように、インデックスキーはカップルドノードツリーにおいて、順序性をもって配置されていることを利用したものであり、検索開始ノードを前記順序性に基づいて変更しながら最小値検索または最大値検索を繰り返すものである。また、上記各出願において、カップルドノードツリーを配列に配置すること、上記提案した各検索処理における検索開始ノードからのツリー上の探索経路のノードの配列番号を探索経路スタックに順次スタックし、探索経路スタックにスタックされた配列番号を用いた処理も開示した。
【0014】
また、本出願人は、特願2007−114915において、リーフノードにインデックスキーに替えてインデックスキーを格納した記憶領域の位置情報を格納したカップルドノードツリーの構造とそれを用いた検索処理を提案した。
さらに本出願人は、特願2008−7690において、複数のキーによる検索のためのカップルドノードツリーであって、複数のキーが直列に連結され、末尾のキーはユニークキーであることを条件としたキー列による検索を行うカップルドノードツリーの構造とそれを用いた検索処理を提案した。
【特許文献1】特開2001−357070号公報
【特許文献2】特開2008−015872号公報
【発明の開示】
【発明が解決しようとする課題】
【0015】
上記特願2008−7690で提案したカップルドノードツリーを用いた検索においては、キー列を構成するキー毎に順次直列的に処理を行うものであるから、キー列を構成するキーの数が増えるとそれだけ処理時間が増加する。
また地図上の地点のように2次元座標で位置が表される点を検索する場合、X座標とY座標について順次それぞれ検索をしているが、地図上の検索対象が増えるにつれて、その検索効率を向上させることが求められてきている。
また、3次元空間内の点を検索する場合でも、事情は同じである。
【0016】
そこで本発明の目的は、複数のキーからなるキー列による検索において、検索処理の高速化をより一層高めることの可能なツリー構造とそれを用いた検索手法を提供することである。
【課題を解決するための手段】
【0017】
まず、本発明によるカップルドノードツリーは、上記特願2008−7690で提案したものと同様に、複数のキーからなるキー列(以下、多次元キーということがある。)を検索の対象とするが、特願2008−7690で提案したものとは、末尾のキーがユニークである必要がないという点で異なる。また、上記各出願において提案したカップルドノードツリーのツリー構造は、ノード対がツリー状にリンクしたものであったが、それに対して本発明によるカップルドノードツリーのツリー構造は、隣接した記憶領域に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたものである。本発明のブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキー自体を含み、空ノードは該空ノードが空状態であることを示す情報を含む。
【0018】
既提案のノード対が代表ノードとそれと対をなすノードから構成されるのに対して、本発明のノード群の各ノードは、キー列を構成する各キーのビット値の組み合わせに対応する位置に配置される。すなわち本発明のノード群は、一次元のノード対を多次元に拡張したいわば多重カップルドノードであり、本発明のカップルドノードツリー(以下、多重カップルドノードツリーということがある。)は、従来の一次元のカップルドノードツリーを多次元のものに拡張したものである。
キー列(以下、多次元キーあるいはインデックスキーということがある。)の検索においては、ブランチノードに含まれる弁別ビット位置の検索キー列の各キーのビット値に応じたノード位置により代表ノードの属するノード群の1つのノードにリンクすることを順次繰り返すことにより実現する。
【発明の効果】
【0019】
本発明によれば、検索キー列の各キーのビット値に応じたノード位置によりノード群の1つのノードにリンクするので、キー毎の分岐処理を直列に行うことがなく、ツリーの分岐の階層を小さくできるので、処理効率を向上することができる。
【発明を実施するための最良の形態】
【0020】
以下、本発明を実施するための最良の形態として、カップルドノードツリーを配列に格納する例について説明する。ブランチノードが保持するリンク先の代表ノードの位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、代表ノードの位置を示す位置情報の情報量を削減することができる。
【0021】
また、主としてキー列として2つのキーから構成されるものを例示して説明する。したがって、本実施態様のカップルドノードツリーをダブル・カップルドノードツリー、あるいは単にツリーということがある。また、キー列(インデックスキー)を2次元キーということがある。さらに、リーフノードにはインデックスキーの格納された記憶領域の位置情報を含むものとして説明するが、リーフノードに直接インデックスキーを格納することもできる。しかし、先の出願である特願2007−114915において説明したように、インデックスキー(本願の場合はキー列)の長さが長くなる場合には、インデックスキーをリーフノードに格納せず他の記憶領域に格納し、リーフノードには該記憶領域の位置情報を格納することにより、ノードを格納する記憶領域を効率的に使用することができる。
【0022】
図2Aは、本発明の一実施形態における配列に格納されたダブル・カップルドノードツリーの構成例を説明する図である。上述の特願2007−114915で提案したものとは、各ノードが空ノードであるか使用中であるかを示す情報であるノード状態を含む点のみで異なる。
本発明によれば、カップルドノードツリーのツリー構造におけるノードは、多次元キーを構成する各キーのビット値の組み合わせに対応する位置に配置されたノードから構成されるノード群であるので、ある多次元キーの集合に対して多重カップルドノードツリーを生成したとき、あるノード群のあるノード位置に対応する多次元キーが存在しないことがあり得る。したがって、ノード種別とは別にノード状態を設けてそのノード位置のノードが空であるか使用中であるかを識別するものである。
【0023】
図2Aを参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード状態102a、ノード種別102b、弁別ビット位置103及び代表ノード番号104で構成されている。ノード状態102aの値は1であり、ノード101が使用中であることを示している。ノード種別102bの値は0であり、ノード101がブランチノードであることを示している。弁別ビット位置103には1が格納されている。代表ノード番号104にはリンク先のノード群111の代表ノードの配列番号20が格納されている。配列番号は上記第一の位置情報の具体例である。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。
【0024】
配列番号20の配列要素には、ノード群111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1)にはノード[1]113が、その次の配列要素(配列番号20+2)にはノード[2]112aが、さらにその次の配列要素(配列番号20+3)にはノード[3]113aが格納されている。
ノード[0]112はノード101と同様にブランチノードである。ノード[0]112のノード状態114aには1が、ノード種別114bには0が、弁別ビット位置115には3が、代表ノード番号116には30が格納されている。ノード[1]113とノード[2]112aのノード状態はともに0であり、空ノードであることを示している。
ノード[3]113aは、ノード状態117a、ノード種別117b及び参照ポインタ118aで構成されている。ノード状態117a及びノード種別117bには1が格納されており、ノード[3]113aがリーフノードであることを示している。参照ポインタ118aには、インデックスキーの記憶領域を参照するポインタが格納されている。参照ポインタ118aに格納されたデータは、上記の第二の位置情報の具体例である。以下では表記の簡略化のため、参照ポインタに格納されたデータのことも参照ポインタという。
パトリシアツリーについて先に述べたと同様に、インデックスキーと対応するレコードにアクセスするためのアクセス先情報も当然必要である。インデックスキーとアクセス先情報との対応づけは、例えば、インデックスキーを記憶している記憶領域に隣接する記憶領域に、当該インデックスキーに対応するアクセス先情報を記憶することによって行ってもよい。以下ではアクセス先情報については省略して説明する。
配列番号30の配列要素に格納されたノード122、ノード123、ノード122a及びノード123aからなるノード群121の内容は省略されている。
【0025】
ノード[0]112、ノード[1]113、ノード[2]112a、ノード[3]113a及びノード122、ノード123、ノード122a、ノード123aの格納された配列要素にそれぞれ付された00、01、10、11は、各ノードのノード群におけるノード位置を2進表示で示すものである。代表ノードの格納された配列要素の配列番号にノード位置を加えることにより、該ノード位置のノードの格納された配列要素の配列番号が求められる。 なお、ノード位置が00である代表ノードをノード[0]で表し、ノード位置01、10、11のノードをそれぞれノード[1]、ノード「2」、ノード[3]で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
ノード位置は、検索キー列で検索を行う場合にノード群のどのノードにリンクするかを示すものである。すなわち、検索キー列のうち第1のキーの弁別ビット位置にあるビット値と第2のキーの弁別ビット位置にあるビット値からなる2ビットの値を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、該ブランチノードの弁別ビット位置にある検索キー列の第1のキーのビット値と第2のキーのビット値からなる2ビットの値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード群の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。また、代表ノードのノード位置も任意の位置に決定することができることも明らかである。
【0026】
図2Bは、本実施形態に係るダブル・カップルドノードツリーのツリー構造と2次元キー(インデックスキー)の格納領域を概念的に示す図である。
図2Bの(1)に示すのはダブル・カップルドノードツリーのツリー構造である。符号210aで示すのがルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード群201aの代表ノードとしている。
ツリー構造としては、ルートノード210aの下にノード群201bが、その下層にノード群201cとノード群201fが配置され、ノード群201fの下層にはノード群201gが配置されている。ノード群201cの下にはノード群201eが配置されている。
各ノードの前に付された00、01、10、11の符号は、図2Aにおいて説明した配列要素の前に付された符号と同じでありノード位置を示す。検索キー列の各キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のインデックスキーに対応するリーフノードを見つけることになる。
【0027】
図示された例では、ルートノード210aのノード状態240aは1、ノード種別260aは0でブランチノードであることを示し、弁別ビット位置230aは0を示している。代表ノード番号は220aであり、それはノード群201bの代表ノード210bの格納された配列要素の配列番号である。
ノード群201bはノード210b、211b、212b、213bで構成される。ノード位置が11であるノード213bのノード状態243bのみが0で空ノードであることを示している。ノード位置11のノードが空ノードであるということは、上位のブランチノード210aの弁別ビット位置230aに格納された値0のビット位置の第1のキーと第2のキーのビット値がともに1である2次元キーが、図2Bの(2)に示すインデックスキーの格納領域311に存在しないことを反映している。
ノード210bのノード状態240bは1で、ノード211b、212bのノード状態もノード210bのノード状態240bと同様に1であって使用中であることを示している。それらのノードのうち、ノード210bとノード212bのノード種別260b、262bはともに0であり、ブランチノードであることを示している。
ノード210bの弁別ビット位置230bには1が格納され、リンク先の代表ノード番号にはノード群201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。ノード212bの弁別ビット位置232bには1が格納され、リンク先の代表ノード番号にはノード群201fの代表ノード210fの格納された配列要素の配列番号222bが格納されている。
【0028】
一方、ノード211bのノード種別261bは1でありノード211bはリーフノードであるので参照ポインタ251bを含む。参照ポインタ251bには、第1のキー291dの値が“011010”、第2のキー291d’の値が“100000”というキー列(2次元キー)を格納した記憶領域を示す参照ポインタ281dが格納されている。参照ポインタ251bに格納されたデータのことも参照ポインタといい、符号281dにより表す。他のリーフノードでも同様に、参照ポインタと参照ポインタに格納されたデータを同じ参照ポインタという語で表す。また、以下の説明において、2次元キーについて、“011010:100000”のような表記及び291d、291d’のような表記を用いることがある。
ノード群201bのノード位置01に参照ポインタ281dを格納したリーフノード211bが存在することは、参照ポインタ281dで参照するインデックスキーの、ノード群201bの直近上位のブランチノード210aの弁別ビット位置230aで示されるビット位置0のビット値が、第1のキー290dが“0”、第2のキー290d’が“1”であり、そのようなビット値の組み合わせのインデックスキーがほかにないことに対応している。
一方、ノード群201bのノード位置00とノード位置10のノードがブランチノードであるのは、ブランチノード210aの弁別ビット位置230aで示されるビット位置0の第1のキーと第2のキーのビット値の組み合わせが00のものと10のインデックスキーが2つ以上存在し、ビット位置0より下位のビット位置のビット値によりそれらのインデックスキーが弁別されることに対応している。
【0029】
ブランチノード210bのリンク先であるノード210cのノード状態240cには0が格納されているので、このノードは空ノードであり、ノード位置が10のノード212cもノード状態が0であって空ノードである。ノード位置が01のノード211cのノード状態は1、ノード種別261cは1であるのでノード211cはリーフノードである。したがって、参照ポインタ251cを含んでいる。参照ポインタ251cには、図示の例では、第1のキー290cと第2のキー290c’からなる2次元キーが格納されている記憶領域を参照するポインタ280cが格納されている。
インデックス格納領域311の参照ポインタ280cが指すエントリの第1のキー290cには“000111”が、第2のキー290c’には“011100”が格納されている。ノード群201cの直近上位のブランチノード210bの弁別ビット位置230bで示されるビット位置1のビット値は、第1のキー290cが“0”、第2のキー290c’が“1”である。リーフノード211bについて説明したと同様に、そのようなビット値の組み合わせのインデックスキーがほかにないことが、ノード群201cのノード位置01に参照ポインタ280cを格納したリーフノード211cが存在することに対応している。
ノード位置11のノード213cのノード状態243cは1、ノード種別263cは0であるので、ノード213cはブランチノードである。弁別ビット位置233cは2であり、代表ノード番号にはノード群201eの代表ノード210eの格納された配列要素の配列番号223cが格納されている。
【0030】
ノード群201eのノード位置00のノード210eのノード状態240eは0なのでノード210eは空ノードであり、同様にノード位置01のノード211eも空ノードである。
ノード位置10と11のノード212e、213eのノード状態242e、243eはともに1、ノード種別260e、261eはともに1であり双方ともリーフノードであることを示している。ノード212e、213eの参照ポインタ252e、253eにはそれぞれ、“011010:010100”というキー列290e、290e’と、“011010:011000”というキー列291e、291e’を格納した記憶領域への参照ポインタ280e、281eが格納されている。
【0031】
ノード群201bのブランチノード212bのリンク先であるノード群201fの代表ノードであるノード210fのノード状態240fは1、ノード位置01のノード211fのノード状態241fも同じく1である。ノード210fのノード種別260fは0でありノード210fはブランチノードである。ノード210fの弁別ビット位置230fには2が格納されている。ノード210fの代表ノード番号にはノード群201gの代表ノード210gの格納された配列要素の配列番号220fが格納されている。ノード211fのノード種別261fは1でありノード211fはリーフノードである。ノード211fの参照ポインタ251fには“100010:010000”というキー列290g、290g’を格納した記憶領域への参照ポインタ280gが格納されている。
ノード位置11のノード213fのノード状態243fは0でありノード213fは空ノードであり、同様にノード212fもノード状態242fが0であるので空ノードである。
【0032】
ブランチノード210fのリンク先であるノード群201gのノード位置00のノード210gのノード状態は0であり、ノード210gが空ノードであることを示している。ノード位置01、10、11のノード211g、212g、213gのノード状態241g、242g、243gは1、ノード種別261g、262g、263gは1であり、ノード211g、212g、213gはリーフノードである。ノード211g、212g、213gのそれぞれの参照ポインタ251g、252g、253gには、“100011:001100”というキー列291g、291g’を格納した記憶領域への参照ポインタ281g、“101100:001000”というキー列291h、291h’を格納した記憶領域への参照ポインタ281h、“101100:001000”というキー列290h、290h’ を格納した記憶領域への参照ポインタ280hが格納されている。
【0033】
図2Bの(2)には、複数のインデックスキーの記憶領域が連続して設けられる例を示し、それら連続した記憶領域全体をインデックスキーの記憶領域311として示したが、インデックスキーは連続した領域に格納されなくてもよい。また、リーフノード同士のツリー構造上での関係と、インデックスキーの記憶領域311におけるインデックスキーの配置順は無関係であってもよい。
【0034】
以下、上述のツリーから第1のキー“101100” と第2のキー“001000”からなる2次元キー(インデックスキー)を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から0、1、2、・・・とする。
まず、第1のキー“101100” と第2のキー“001000”からなるキー列を検索キー列としてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは0であるので、検索キー列の第1のキー“101100”及び第2のキー“001000”のビット位置が0のビット値をみるとそれぞれ1と0である。そこで代表ノード番号の格納された配列番号220aに2進数表示で“10”、すなわち2を加えた配列番号の配列要素に格納されたノード位置10のノード212bにリンクする。
次に、ノード212bの弁別ビット位置232bには1が格納されているので、第1のキー“101100”
及び第2のキー“001000”のビット位置が1のビット値をみるとそれぞれ0と0であるから、代表ノード番号の格納された配列番号222bの配列要素に格納されたノード210fにリンクする。
ノード210fの弁別ビット位置230fには2が格納されているので、第1のキー“101100” 及び第2のキー“001000”のビット位置が2のビット値をみるとそれぞれ1である。そこで代表ノード番号の格納された配列番号220fに2進数表示で“11”、すなわち3を加えた配列番号の配列要素に格納されたノード位置11のノード213gにリンクする。
ノード213gのノード種別263gは1でありリーフノードであることを示しているので、参照ポインタ280hにより示される記憶領域を参照し、そこに格納されたインデックスキー290h、290h’を読み出す。このようにしてカップルドノードツリーを用いた検索が行われる。読み出されたインデックスキーを検索キーと比較すると、上記の例の場合は一致していることが分かる。
【0035】
次に、図2Bを参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図2Bの例で、ルートノード210aの弁別ビット位置230aが0であるのは、インデックスキーを構成する第1のキーと第2のキーの0ビット目の組み合わせに異なるものがあるからである。第1のキーおよび第2のキーの0ビット目の組み合わせが00のインデックスキーのグループはノード位置00のノード210bの下に分類され、前記0ビット目の組み合わせが01のインデックスキーのグループはノード位置01のノード211bの下に分類され、前記0ビット目の組み合わせが10のインデックスキーのグループはノード位置10のノード212bの下に分類され、前記0ビット目の組み合わせが11のインデックスキーのグループはノード位置11のノード213bの下に分類される。
先に述べたように、第1のキーおよび第2のキーの0ビット目の組み合わせが11のインデックスキーは存在しないことから、ノード213bは空ノードとなっている。また、ノード位置01のノード211bがリーフノードであるのは、0ビット目のビット値の組み合わせが01であるインデックスキーがほかになく、0ビット目より下位のビットのビット値によりインデックスキーを弁別する必要のないことに対応している。
ノード210bの弁別ビット位置230bが1であるのは、その下位のリーフノード211c、212e、213eに対応するインデックスキーの第1のキー及び第2のキーの1ビット目より上位のビット値がすべて等しく(0ビット目の組み合わせがすべて00)、1ビット目の組み合わせに異なるものがあるという、インデックスキーの集合の性質を反映している。
同様に、ノード212bの弁別ビット位置232bが1であるのは、その下位のリーフノード211f、211g、212g、213gに対応するインデックスキーの第1のキーおよび第2のキーの1ビット目より上位のビット値がすべて等しく(0ビット目の組み合わせがすべて10)、1ビット目の組み合わせに異なるものがあるという、インデックスキーの集合の性質を反映している。
上記インデックスキーの集合の性質が反映されていることは、ノード群201c、201e、201f、201gにおいても同様である。
【0036】
仮にインデックスキーの集合に、第1のキー291h“101100”、第2のキー291h’“000100”からなるインデックスキーの代わりに第1のキー“101001”、第2のキー“000001”からなるインデックスキーが含まれていたとしても、第1のキーと第2のキーの2ビット目まではそれぞれ第1のキー291hと第2のキー291h’の2ビット目までと等しいので、ノード212gの参照ポインタ281hにより示される記憶領域に格納されるインデックスキーの値が変わるだけで、ツリー構造自体は変わることはない。しかし、第1のキー291h“101100”、第2のキー291h’“000100”からなるインデックスキーに加えて第1のキー“101100”と第2のキー“000000”
からなるインデックスキーが含まれていると、ノード212gはブランチノードとなり、その弁別ビット位置は3であり、該インデックスキーに係るリーフノードは、ノード212gのリンク先のノード群のノード位置10に配置される。
【0037】
上述のようにカップルドノードツリーの構造はインデックスキーの集合の性質を反映しているので、使用中のノードが1つだけのノード群は存在しない。ノード群のノード位置に配置されるノードは、その直近上位のブランチノードの弁別ビット位置のビット値の組み合わせで互いに弁別されるものであるから、互いに弁別される相手のノードが存在する。したがって、使用中のノードが1つだけということはありえないからである。
例えば、図2Bに示すツリーにおいて、仮にノード212eの参照ポインタ280eが指すインデックスキーがインデックスキーの格納領域311に存在せず、ノード212eが空ノードで、ノード群201eの使用中のノードが213eだけであるとすると、ブランチノード213cの弁別ビット位置233cに格納されたビット位置2のビット値により、リーフノード213cの参照ポインタ281eが指すインデックスキーを弁別する必要はない。 そのかわり、ブランチノード210bの弁別ビット位置230bに格納されたビット位置1のビット値の組み合わせ11により、リーフノード213cの参照ポインタ280cが指すインデックスキーと弁別されることになる。すなわち、リーフノード213eはノード群201cのノード位置11に配置されることになり、ノード群201eのノードは全て空となり、ノード群201eはツリー上に存在しなくなる。
また、ノード211fが空ノードの場合にも、ブランチノード210fはノード群201bのノード位置212bに配置され、ノード群201fは不要となり、削除される。
以上説明したように、カップルドノードツリーの構造は、多次元キーの集合に含まれる多次元キーを構成するキーの各ビット位置のビット値により決定される。
【0038】
検索キー列で検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キー列が“101100:000100”であれば、図2Bに示すツリーではノード212gに到達することができる。また、上記説明からも想像がつくように、“101000:000001”を検索キー列とした場合でもノード212gにたどり着き、参照ポインタ281hにより示される記憶領域に格納されたインデックスキーが検索結果キー列として得られる。
このように、カップルドノードツリーに格納されたインデックスキー(キー列)の各キーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【0039】
図3は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施される。カップルドノードツリーが配置される配列309と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック310とインデックスキーの記憶領域311を有するデータ格納装置308は、主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。図2Aの配列100は配列309の一例である。また、図2Bと同様に、インデックスキーの記憶領域311は連続した領域のように図示されているが、不連続の領域でもよいことは当然である。なお、カップルドノードツリーは配列に配置されるとして説明するため、探索経路スタック310には検索中にたどるノードが格納された配列要素の配列番号を記憶すると説明したが、一般的には、ノードの格納された記憶領域のアドレス等のノードの位置を示す情報が記憶される。
【0040】
図3の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできるし、探索経路スタック310を中央処理装置302内のハードウェアとして実現することも可能である。あるいは、配列309は外部記憶装置306に、探索経路スタック310を主記憶装置305に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。以下の説明では、先に述べた参照ポインタ等の場合と同様に、一時記憶領域に格納されたあるいは設定された値を一時記憶領域の名前で呼ぶことがある。
図3に示した例では、カップルドノードツリーのノードを格納した配列要素からなる配列309と、インデックスキーの記憶領域311とは別の領域である。したがって、リーフノードを格納した配列要素にインデックスキーが含まれる場合に比べて、図3の構成では、一般に1つの配列要素に必要な記憶領域の量が少ない。つまり、カップルドノードツリーを格納する配列309からインデックスキーの記憶領域311を分離することによって、キャッシュメモリ303へのカップルドノードツリーの読み込みにおいて1キャッシュブロックあたりに格納されるノード数を増やすことが可能となる。それにより、後述する検索処理等においてキャッシュミスの頻度が減って処理がより高速に行われるようになる。
【0041】
次に、本発明の一実施態様に係るカップルドノードツリーを用いた基本的な操作である、検索、挿入、削除について順に詳しく説明する
図4は、本発明の一実施形態におけるビット列の検索処理を示すフローチャートである。検索キー列は与えられているものとする。
まず、ステップS401において、検索開始ノードを設定する。検索開始ノードの設定は、検索開始ノードの配列番号の指定あるいは取得によりその配列番号、あるいは該配列番号のノードを図示しない検索開始ノード設定エリアに設定することにより行う。なお、上述の検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置」の1つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。検索開始ノード以外についても同様である。
【0042】
次に、ステップS402で、探索経路スタックに取得された配列番号を格納し、ステップS403で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。ステップS404aで読み出したノードからノード状態を取り出し、ステップS404bでノード状態は使用中か判定する。使用中でない、すなわち空ノードであれば、検索結果が空ノードであることを表示して検索処理を終了する。ノード状態が使用中であれば、ステップS404で、読み出したノードから、ノード種別を取り出し、ステップS405で、ノード種別がブランチノードであるか否かを判定する。
【0043】
ステップS405の判定において、読み出したノードがブランチノードである場合はステップS406に移行し、ステップS403で読み出したノードから弁別ビット位置を取り出す。次にステップS407aにおいて列位置に0を設定してステップS407bに進む。列位置は次に説明するステップS407b〜S407eのループで処理をするキーの検索キー列中の位置を示すものである。列位置の初期値をこの例では0としている。
ステップS407bでは、すべてのキーを処理済みか判定する。すべてのキーを処理済みであればステップS408に移行し、処理済みでなければステップS407cに進む。
ステップS407cにおいては、検索キー列から列位置の指すキーを取り出し、ステップS406で取り出した弁別ビット位置の指すビット値を取り出す。次にステップS407dにおいて、ノード位置と名付けるワークエリアの、列位置の指すビット位置に、ステップS407cで取り出したビット値を設定する。次にステップS407eで列位置を更新してステップS407bに戻る。上記ステップS407b〜S407eのループ処理は、リンク先のノードのノード位置を決定するものである。
【0044】
ステップS408では、ステップS403で読み出したノードから代表ノード番号を取り出し、ステップS409aに進んで、ステップS407dで設定したノード位置と代表ノード番号とを加算し、新たな配列番号として、ステップS402に戻る。
以降、ステップS405の判定においてリーフノードと判定されてステップS410aに進むまで、ステップS402からステップS409aまでの処理を繰り返す。ステップS410aでは、リーフノードから参照ポインタを取り出し、検索を終了する。なお、リーフノードに直接インデックスキーを格納する場合には、リーフノードからインデックスキーを取り出して検索を終了することになるので、以下の説明においては、「リーフノードから参照ポインタあるいはインデックスキーを取り出し」のような表記を用いることがある。
【0045】
次に、図5〜図8によりカップルドノードツリーにおけるノード挿入処理を説明する。図5〜図7Bが通常の挿入処理を説明するものであり、図8はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【0046】
図5は挿入処理の前段である検索処理の処理フローを示す図であり、図4に示した検索処理において、挿入キー列を検索キー列とし、検索開始ノードをルートノードとしたものに相当する。
まず、ステップS501aで検索開始ノードにルートノードの配列番号を設定し、ステップS501bで検索キー列に挿入キー列を設定する。インデックスキーへの参照ポインタをリーフノードに格納する実施態様においては、挿入キー列は、挿入処理の前提条件として、予めインデックスキーの格納領域のポインタを取得して、該格納領域に格納されているものとする。
次にステップS510aにおいて、検索キー列により検索開始ノードより図4に示す検索処理を行う。次にステップS510bにおいてステップS510aの検索結果を判定し、検索結果が空ノード、すなわちノード状態が使用中でなければステップS510cに進み、ステップS510aで実行した図4に示す検索処理のステップS409aで得た配列番号の指す配列要素の、ノード状態に使用中を、ノード種別にリーフを、参照ポインタに挿入キー列のポインタを書き込み、挿入処理を終了する。インデックスキーを直接リーフノードに格納する場合は、インデックスキーとして挿入キー列を書き込んで挿入処理を終了する。
【0047】
ステップS510bの判定結果がノード状態は使用中であれば、ステップS510dにおいて、ステップS510aの検索結果で得られた参照ポインタの指すキー列を取り出して比較キー列に設定する。次にステップS510eにおいて、挿入キー列と比較キー列を比較して、挿入キー列と比較キー列が完全に一致するか否かと、挿入キー列と比較キー列の差分ビット位置を得る。挿入キー列と比較キー列の差分ビット位置は、挿入キー列の各キーと比較キー列の各キーをビット列として比較し、各キーにおいて最初に異なるビット値となるビット位置のうち最上位のビット位置とする。ステップS510eの詳細は、後に図7Aを参照して説明する。
次にステップS511aにおいて、ステップS510eでの比較の結果が、挿入キー列のキーと比較キー列のキーが全て等しいものであったかを判定し、等しければ挿入キー列は既にカップルドノードツリーの参照ポインタが指す記憶領域に存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図6AのステップS512以下の処理に進む。
【0048】
図6Aは、挿入するノード群のための配列要素を準備する処理を説明する処理フロー図である。
ステップS512において、配列から空きのノード群を求め、そのノード群のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS513aにおいて、ステップS510eで得た挿入キー列と比較キー列の差分ビット位置により挿入ノード位置及び対ノード位置を得る。ステップS513aの詳細は、後に図7Bを参照して説明する。
次にステップS514aに進み、ステップS512で得た代表ノードの配列番号にステップS513aで得たノード位置を加算した配列番号を得る。次にステップS515bに進み、ステップS512で得た代表ノードの配列番号にステップS513aで得た対ノード位置を加算した配列番号を得る。後に図7Bを参照して詳細に説明するが、ステップS514aで得た配列番号は、挿入キー列をインデックスキーとして格納する記憶領域への参照ポインタを持つリーフノードが格納される配列要素の配列番号である。ステップS515bで得た配列番号は、比較キー列に設定したキー列の参照ポインタ持つリーフノードの直近上位のブランチノードが格納される配列要素のものである。つまり、前段の検索処理で得られたリーフノードに対応するインデックスキーと挿入キー列の差分ビット位置における各キーのビット値の組み合わせにより、挿入されるノード群のうちどのノード位置に挿入キー列への参照ポインタを保持するリーフノード及び前段の検索処理で得られたリーフノードの直近上位のブランチノードが格納されるかが決定される。
さらにステップS517aにおいて、ステップS510eで得た差分ビット位置を、差分ビット位置と名付けるワークエリアに設定し、図6Bに示すステップS518に進む。
【0049】
図6Bは図6Aで準備された配列要素にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
ステップS518〜ステップS523までの処理は、挿入するノード群のカップルドノードツリー上の位置を求める処理であり、ステップS524以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
ステップS518において、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップS524に移行し、指していなければステップS519に進む。
【0050】
ステップS519において、探索経路スタックのスタックポインタを1つ戻してそこにスタックされている配列番号を取り出す。
ステップS520に進み、ステップS519で取り出した配列番号の配列要素を配列からノードとして読み出す。次にステップS521において、ステップS520で読み出したノードから、弁別ビット位置を取り出し、ステップS522に進み、ステップS521で取り出した弁別ビット位置がステップS517aで設定した差分ビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
ステップS522の判定結果が否定であれば、ステップS518に戻り、ステップS518での判定が肯定になるか、ステップS522での判定が肯定になるまでステップS518〜ステップS522の処理を繰り返す。ステップS522での判定が肯定になると、ステップS523に進む。ステップS523では、探索経路スタックのスタックポインタを1つ進め、ステップS524以下の処理に移行する。
【0051】
上記ステップS518〜ステップS523で説明した処理は、挿入するノード群の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの差分ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの直近下位のブランチノードのリンク先を挿入するノード群の挿入位置とするものである。
また、探索経路スタックを逆にたどりルートノードに至った場合は、ルートノードのリンク先が挿入位置となる。
【0052】
例えば図2Bのカップルドノードツリーにインデックスキー “101000:001000”を挿入するとき、検索結果のインデックスキーは、ノード213gに対応するインデックスキー “101100:001000”になる。この例の場合、挿入キー列と比較キー列の差分ビット位置は3であり、弁別ビット位置230fは2なので、ノード210fの直近下位のノード213gのリンク先が挿入位置になる。つまり、ノード213gはブランチノードとなり、その弁別ビット位置は挿入キー列と比較キー列の差分ビット位置3となり、リンク先として挿入されるノード群のノード位置00に挿入キー列に対応するリーフノードが配置され、ノード位置10にノード213gの内容が転写されたリーフノードが配置される。
【0053】
次に、ステップS524以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップS524では探索経路スタックからスタックポインタの指す配列番号を取り出す。
ステップS525aに進み、ステップS514aで得た配列番号の指す配列要素の、ノード状態に使用中を、ノード種別にリーフを、参照ポインタに挿入キー列のポインタをあるいはインデックスキーとして挿入キー列を書き込む。
ステップS526に進み、配列からステップS524で得た配列番号の配列要素を読み出す。
次にステップS527において、ステップS515bで得た配列番号の配列要素にステップS526で読み出した内容を書き込む。
最後にステップS528aにおいて、ステップS524で得た配列番号の指す配列要素のノード状態に使用中を、ノード種別にブランチを、弁別ビット位置にステップS517aで設定した差分ビット位置を、代表ノード番号にステップS512で得た配列番号を書き込み、処理を終了する。
【0054】
図7Aは、図5に示すステップS510eの挿入キー列と比較キー列の差分ビット位置を得る処理を詳細に説明する図である。図7Aに示す処理により得られる挿入キー列と比較キー列の差分ビット位置は、下記説明から明らかなとおり、挿入キー列と比較キー列の各キーの間の差分ビット位置の最小値である。
【0055】
図に示すように、ステップS701において列位置に初期値として0を設定する。また、ステップS702において差分ビット位置に初期値として、差分ビット位置の最大値を設定する。キー列を構成するキーがnビットからなるビット列であり先頭のビット位置を0とすれば、差分ビット位置の初期値はn−1となる。
次にステップS703において、キー列のすべてのキーについて処理済みであるか判定する。処理済みであればステップS712に移行し、処理済みでなければステップS704に進む。
ステップS704では、挿入キー列から、列位置の指すキーを取り出し、挿入キーとして設定する。
ステップS705に進み、図5に示すステップS510dで設定した比較キー列から、列位置の指すキーを取り出し、比較キーとして設定する。
【0056】
次にステップS706に進み、挿入キーは比較キーと一致するか判定する。一致すれば列位置に設定した値を更新してステップS703に戻り、一致しなければ、ステップS707に移行して挿入キーと比較キーとのビット列比較を例えば排他的論理和で行い差分ビット列を得る。
ステップS708に進み、ステップS707で得た差分ビット列から、上位0ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するCPUではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
次にステップS709において、ステップS708で得たビット位置が差分ビット位置に設定された値より小さいか判定する。小さければステップS710で差分ビット位置にステップS708で得たビット位置を設定してステップS711に進み、小さくなければ直接ステップS711に進む。
【0057】
上述のステップS703〜ステップS711の処理を全てのキーについて繰り返し、すべてのキーについての処理が終了するとステップS712において、差分ビット位置に設定された値が差分ビット位置の最大値であるか判定する。最大値であれば、ステップS706での判定が全てのキーにおいて一致することであるので、完全一致を表示して処理を終了し、最大値でなければ非完全一致を表示して処理を終了する。完全一致/非完全一致の表示は、例えば1ビットのフラグを設けることにより可能である。
【0058】
図7Bは、図6Aに示すステップS513aの、挿入キー列と比較キー列の差分ビット位置の指す挿入キー列と比較キー列のビット値から、図6AのステップS512で取得され図6Bの処理により挿入位置が求められたノード群に格納するノードのノード位置を求める処理を詳細に説明する図である。
【0059】
図に示すように、ステップS713において列位置に初期値として0を設定する。次にステップS714において、キー列のすべてのキーについて処理済みであるか判定する。処理済みであればステップS721に移行し、処理済みでなければステップS715に進む。
ステップS715では、挿入キー列から列位置の指すキーを取り出し、差分ビット位置の指すビット値を取り出す。次にステップS716で、挿入ノード位置の、列位置の指すビット位置に、ステップS716で取り出したビット値を設定する。
次にステップS717に進み、比較キー列から列位置の指すキーを取り出し、差分ビット位置の指すビット値を取り出す。次にステップS718で、対ノード位置の、列位置の指すビット位置に、ステップS718で取り出したビット値を設定する。次にステップS719で列位置を更新してステップS714に戻る。
【0060】
ステップS714からステップS719までのループ処理を、キー列を構成する全てのキーについて実行すると、挿入ノード位置及び対ノード位置の全てのビット値が設定されるので処理を終了する。
【0061】
図8は、本発明の一実施形態におけるルートノードの挿入処理を含むリーフノードの挿入処理全体の処理フローを説明する図である。
ステップS551において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図5〜図6Bを用いて説明した通常の挿入処理が行われる。
ステップS551での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。この場合にもインデックスキーへの参照ポインタをリーフノードに格納する実施態様においては、挿入キー列は挿入処理の前提条件として予めインデックスキーの格納領域のポインタを取得して、その格納領域に格納されているものとする。
まず、ステップS552において、配列から空きのノード群を求め、そのノード群のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS553において、ステップS552で得た配列番号に0を加えた配列番号を求める。(実際には、ステップS552で取得した配列番号に等しい。)次にステップS554eにおいて、ステップS553で得た配列番号の配列要素すなわち挿入するルートノードに対応する配列要素の、ノード状態に使用中、ノード種別にリーフを、参照ポインタに挿入キー列のポインタをあるいはインデックスキーとして挿入キー列を書き込む。そしてステップS556では、ステップS553で取得したルートノードの配列番号を登録して処理を終了する。
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図8及び図5〜図6Bの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【0062】
次に図9A、図9Bを参照して、本発明の一実施形態におけるカップルドノードツリーから特定のインデックスキーに対応するリーフノードを削除する処理フローを説明する。
図9Aは、削除処理の前段である検索処理の処理フローを示す図であり、図4に示した検索処理において、削除キー列を検索キー列とし、検索開始ノードをルートノードとしたものに相当する。
まず、ステップS901aで検索開始ノードにルートノードの配列番号を設定し、ステップS901bで検索キー列に削除キー列を設定する。
次にステップS910aにおいて、検索キー列により検索開始ノードより図4に示す検索処理を行い、ノード状態が空でなければ参照ポインタあるいはインデックスキーを取得する。ステップS910bにおいて、ステップS910aでの検索結果のノードのノード状態が使用中であるか判定し、使用中でなければ削除失敗を返し、使用中であれば、ステップS910dに進んで参照ポインタの指すキー列あるいはインデックスキーを取り出して比較キー列に設定する。
次にステップS910eにおいて、図7Aに示す処理により削除キー列と比較キー列から差分ビット位置を得る。ステップS911においてステップS910eで実行した図7Aの処理の結果として完全一致が表示されているか、すなわち削除キー列と比較キー列のすべてのキーが等しいか判定し、等しくなければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図9BのステップS912a以下の処理に進む。
【0063】
図9Bは、削除処理の後段の処理フローを説明する図である。
まず、ステップS912aで、検索結果のノードが属するノード群に3つ以上のノードが格納されているか、すなわちノード状態が使用中であるノードが3つ以上あるか判定する。この判定は、先に図3に示すハードウェア構成例に関連して「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる」と述べたように、検索処理において得られるノード位置を記憶しておき、探索経路スタックにスタックされている配列番号と組み合わせてノード群内の各ノード位置のノード状態にアクセスすることにより行うことができる。
【0064】
ステップS912aでの判定が3つ以上のノードが格納されている、であれば、削除対象のノードを削除しても2つのノードが残ることから、ステップS912bに移行してステップS910aで実行した図4に示す検索処理のステップS409で得た配列番号、すなわち探索経路スタックに格納されている配列番号の配列要素に格納されたノードのノード状態に空を書き込み、処理を終了する。
【0065】
ステップS912aでの判定が3つ以上のノードは格納されていない、であればステップS912に移行する。先に述べたように、使用中のノードが1つだけのノード群はルートノードの属するノード群以外には存在しないことから、この場合には使用中のノードは2つであり、そのうち1つのノード状態を空にすることから、他の1つのノードを別のノード群に移し、元のノード群を削除することになる。
ステップS912では、探索経路スタックに2つ以上の配列番号が格納されているか判定する。2つ以上の配列番号が格納されていないということは、言い換えれば1つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップS918に移行し、ステップS901aで得たルートノードの配列番号に係るノード群を削除し、さらにステップS919でルートノードの配列番号の登録を抹消して、処理を終了する。
【0066】
ステップS912において探索経路スタックに2つ以上の配列番号が格納されていると判定されたときはステップS913aに進み、ノード群より、削除対象のノード以外のもう1つの使用中のノードの内容を読み出す。ステップS913aの処理の詳細は、後に図10を参照して説明する。
次にステップS915において探索経路スタックのスタックポインタを1つ戻して、配列番号を取り出し、ステップS916においてその配列番号の指す配列要素に、ステップS913aで読み出した内容を書き込む。この処理は、先に述べた他のノードを別のノード群に移すことに相当する。
続くステップS917において、ステップS910aで実行した図4に示す検索処理のステップS408で得た代表ノード番号に係るノード群を削除し、処理を終了する。
【0067】
図10は、図9Bに示すステップS913aの、ノード群より、削除対象のノード以外のもう1つの使用中のノードの内容を読み出す処理を詳細に説明する図である。
図に示すように、ステップS101でノード位置に初期値0を設定する。次にステップS102に進み、ステップS910aで実行した図4に示す検索処理のステップS408で得た代表ノード番号にノード位置に設定された値を加えて配列番号を求める。ステップS103で、配列から、ステップS102で求めた配列番号の指す配列要素をノードとして読み出し、ステップS104でその読み出したノードから、ノード状態を取り出す。
次にステップS105において、その取り出したノード状態は使用中であるか判定し、使用中でなければステップS107に進み、使用中であればステップS106に進む。
ステップS106では、ステップS102で求めた配列番号が削除対象のノードの配列番号、すなわちステップS910aで実行した図4に示す検索処理のステップS409aで得た配列番号と一致するか判定し、一致するのであればステップS107に進み、一致しなければ、削除対象のノード以外のもう1つの使用中のノードの内容をステップS103で読み出しているので、処理を終了する。
ステップS107においては、ノード位置を更新してステップS102に戻る。
【0068】
上述の説明では、ノード位置の最小値である0を初期値としてノード位置の昇順にもう1つの使用中のノードを探索しているが、探索の順番はこれに限ることなく例えば降順に探索することも可能である。また、図のステップS106において、ステップS102で求めた配列番号が削除対象のノードの配列番号と一致するか判定しているが、この判定をステップS102の直後に行うことができることは明らかである。
【0069】
次に、具体例により、本発明の一実施形態に係る削除処理と挿入処理を説明する。
図11A及び図11Bは、図2Bに例示したダブル・カップルドノードツリーにおいて、“000111:011100”を削除キー列として削除処理を行う例を説明する図である。図11Aに示したダブル・カップルドノードツリーは、ノード群201f以下のノードは記載を省略している。また、インデックスキーの格納領域311についても、ノード群201f以下のリーフノードに関するものは省略している。削除キー列“000111:011100”は、第1のキー“000111”と第2のキー“011100”から構成されるキー列であり、一時記憶領域である削除キー270に格納されている。
探索経路スタック310には配列番号が格納されており、そのスタックポインタは配列番号220b+1を指している。図中太枠で囲まれたノードが検索処理でたどられたノードであり、その配列番号がルートノード210aのものからリーフノード211cのものまで探索経路スタック310に積まれている。
【0070】
削除キー列“000111:011100”による検索処理においては、まず始めにルートノード210aの配列番号220を取得し、それを探索経路スタック310に格納する。ルートノード210aの弁別ビット位置230aが0であり、第1のキー及び第2のキーのビット位置0のビット値がともに0、であるので、代表ノード番号220aにビット値0を加えた配列番号220aが探索経路スタック310に格納される。
次に配列番号220aの指すノード210bが読み出され、ブランチノードであることが判定される。その弁別ビット位置230bが1であり、第1のキーのビット位置1のビット値が0、第2のキーのビット位置1のビット値が1であるので、代表ノード番号220bに1を加えて配列番号220b+1を得てそれを探索経路スタック310に格納する。
次にノード211cが読み出され、ノード種別261cは1であり、リーフノードであることを示している。このリーフノードに対応するインデックスキー(キー列290c、290c’)は、参照ポインタ280cにより示される記憶領域に格納されている。その記憶領域はインデックスキーの記憶領域311の一部である。そこで参照ポインタ280cの参照するインデックスキーの値は“000111:011100”であり、削除キー270に格納されたキー列と一致している。
【0071】
図11Aに示した状態において、削除対象のノード211c以外のもう1つの使用中のノード213cの内容が読み出され、その内容が、探索経路スタック310のスタックポインタを1つ戻したところに格納されている配列番号220aの配列要素(ノード210b)に書き込まれる。その後ノード群201cを削除する。ノード群が削除された配列要素は空となり、再利用可能となる。
【0072】
図11Bに示したダブル・カップルドノードツリーは、削除処理の終了後のものである。ノード210bのノード種別260b、弁別ビット位置230b、代表ノード番号220bには、括弧書きで示すように、ノード213cに格納されていた値がそのまま格納されている。また、探索経路スタック310のスタックポインタは配列番号220aを指している。
【0073】
次に、削除対象のノードが属するノード群に使用中のノードが3以上含まれる場合の削除処理の具体例を説明する。
図11C及び図11Dは、図2Bに例示したダブル・カップルドノードツリーにおいて、“011010:100000”を削除キー列として削除処理を行う例を説明する図である。図11Cに示したダブル・カップルドノードツリーは、ノード群201f以下及びノード群201c以下のノードは記載を省略している。また、インデックスキーの格納領域311についても、ノード群201f以下のリーフノードに関するものは省略している。削除キー列“011010:100000”は、第1のキー“011010”と第2のキー“100000”から構成されるキー列であり、一時記憶領域である削除キー270に格納されている。
探索経路スタック310には配列番号が格納されており、そのスタックポインタは配列番号220a+1を指している。図中太枠で囲まれたノードが検索処理でたどられたノードであり、その配列番号がルートノード210aのものからリーフノード211bのものまで探索経路スタック310に積まれている。
【0074】
削除キー列“011010:100000”による検索処理においては、まず始めにルートノード210aの配列番号220を取得し、それを探索経路スタック310に格納する。ルートノード210aの弁別ビット位置230aが0であり、第1のキー及び第2のキーのビット位置0のビット値がそれぞれ0、1であるので、代表ノード番号220aにビット値1を加えた配列番号220a+1が探索経路スタック310に格納される。配列番号220a+1の指すノード211bが読み出され、ノード種別261bは1であり、リーフノードであることを示している。このリーフノード211bに対応するインデックスキー(キー列290d、290d’)は、参照ポインタ281dにより示される記憶領域に格納されている。参照ポインタ281dの参照するインデックスキーの値は“011010:100000”であり、削除キー270に格納されたキー列と一致している。
削除対象のノード211bが属するノード群201bには使用中のノードが210b、211b、212bと3つあるので、削除対象であるノード211bのノード状態に0を書き込んで空とし、図11Dに示す削除処理後のダブル・カップルドノードツリーが得られる。
【0075】
次に、図12A及び図12Bを参照して挿入処理の具体例1を説明する。具体例1は、挿入キー列による検索結果としてインデックスキーが得られた場合、すなわち図5に示すステップS510bの判定がノード状態は使用中であるとなった場合のものである。
図12Aに示すのは、キー列“0100:0001”、“0001:0010”、“0000:0011”をインデックスキーとして参照する参照ポインタ1281b、1281c、1280cを持つカップルドノードツリーである。
インデックスキーの格納領域311内の参照ポインタ1281bの指す記憶領域には、第1のキー1291b“0100”と第2のキー1291b’“0001”からなるキー列が格納されている。同様に、参照ポインタ1281cの指す記憶領域には、第1のキー1291c“0001”と第2のキー1291c’“0010”からなるキー列が格納され、参照ポインタ1280cの指す記憶領域には、第1のキー1290c“0000”と第2のキー1290c’“0011”からなるキー列が格納されている。
これから挿入しようとする挿入キー列は図示の例では“0001:0000”である。挿入キー列は、先に述べたように、インデックスキーの格納領域311のポインタ1280dを取得して、ポインタ1280dの指す領域に、第1のキー1290d、第2のキー1290d’として格納されていることを前提としている。
【0076】
図示のツリーはノード群1201a、1201b、1201cで構成されている。
ノード群1201aの代表ノードはルートノード1210aであり、弁別ビット位置には1が保持されている。ノード群1201aの下位のノード群1201bの代表ノード1210bはブランチノードであり、弁別ビット位置には3が保持され、代表ノード1210bと同一のノード群1201bに属する使用中のノード1212bはリーフノードであり、キー列1291b、1291b’への参照ポインタ1281bが保持されている。ブランチノードであるノード1210bはノード群1201cにリンクしている。
ノード群1201cを構成する使用中のノード1211cと1212cはともにリーフノードであり、それぞれキー列1290c、1290c’とキー列1291c、1291c’への参照ポインタ1280c、1281cが格納されている。ノード1211cと1212cのノード位置はそれぞれ01と10である。
【0077】
挿入キー列の第1のキー1290dと第2のキー1290d’の1ビット目のビット値の組み合わせが00、3ビット目のビット値の組み合わせが10であることから、図示の例の場合、挿入キー列で検索をすると、ルートノード1210aからノード1210bを経由して参照ポインタ1281cの格納されたリーフノード1212cに至り、比較キー列として、1291c、1291c’ “0001:0010”が設定される。
【0078】
図12Bは、挿入処理後のカップルドノードツリーを説明する図である。図12Aに示すカップルドノードツリーに対して、挿入キー列1290d、1290d’への参照ポインタ1280dを持つリーフノード1210dと比較キー列の参照ポインタが格納されるリーフノード1212cの直近上位のブランチノード1210bの内容が転写されるノード1211dを含むノード群1201dがブランチノード1210bのリンク先として挿入されている。
挿入キー列と比較キー列の差分ビット位置は図示の場合では2であること、ブランチノード1210bの弁別ビット位置が3で差分ビット位置より大きくその直近上位のブランチノード1210aの弁別ビット位置が1で差分ビット位置より小さいことから、ノード群1201dの挿入位置は、配列番号1220bの指すノード1210bの直近下位となる。
挿入キー列の参照ポインタが格納されるリーフノード1210dが配置されるノード位置(挿入ノード位置)は、挿入キー列の差分ビット位置のビット値の組み合わせである00であり、比較キー列の参照ポインタが格納されるリーフノード1212cの直近上位のブランチノード1210bの内容が転写されるノード1211dが配置されるノード位置(対ノード位置)は、比較キー列の差分ビット位置のビット値の組み合わせである01である。
また、ブランチノード1210bの弁別ビット位置には挿入キー列と比較キー列の差分ビット位置である2が書き込まれ、代表ノード番号にはノード群1201dの代表ノード1210dの配置された配列要素の配列番号1220dが書き込まれ、図12Bに示す構成のカップルドノードツリーとなる。
【0079】
図12C及び図12Dは挿入処理の具体例2を説明する図である。具体例2は、図5に示すステップS510bの判定がノード状態は空であるとなった場合のものである。
図12Cに示す挿入処理前のカップルドノードツリーは図12Aに示すものと同一であるが、インデックスキーの格納領域311に格納された挿入キー列が“0001:0011”であって図12Aに示すものと異なり、参照ポインタ1281dの指す記憶領域に格納されている。
【0080】
挿入キー列“0001:0011”によりルートノード1210aから検索を実行すると、ブランチノード1210bを経由して空ノード1213cに至る。そこで、ノード1213のノード状態に1を書き込んで使用中とし、ノード種別にリーフノードであることを示す1を書き込み、参照ポインタに挿入キー列“0001:0011”の参照ポインタ1281dを書き込む。以上の処理により、図12Dに示す挿入処理後のカップルドノードツリーが得られる。
【0081】
図13は、3つのキーからなるキー列による検索処理に用いる、本発明の一実施形態に係るカップルドノードツリーのツリー構造を概念的に示す図である。本実施形態のキー列を3次元キー、カップルドノードツリーをトリプル・カップルドノードツリーということがある。
トリプル・カップルドノードツリーを用いた検索では、ダブル・カップルドノードツリーについて先に説明したと同様に、3次元キーを構成する各次元のキーの弁別ビット位置のビット値の組み合わせによりリンク先が決定される。したがって、ノード群には2の3乗、すなわち8個のエントリが存在する。ノード位置は000〜111の3ビットで表される。
【0082】
符号410aで示すのがルートノードである。図示の例では、ルートノード410aは配列番号420に配置されたノード群401aの代表ノードとしている。
ツリー構造としては、ルートノード410aの下にノード群401bが、その下層にノード群401cとノード群401fが配置され、ノード群401fの下層にはノード群401g、401h、401iが配置されている。ノード群401cの下にはノード群401dが、さらにその下位にノード群401eが配置されている。
各ノードの前に付された3ビットの符号はノード位置を示す。検索キー列の各キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のインデックスキーに対応するリーフノードを見つけることは、ダブル・カップルドノードツリーの場合と同様である。
【0083】
図示された例では、ルートノード410aのノード状態440aは1、ノード種別460aは0でブランチノードであることを示し、弁別ビット位置430aは0を示している。代表ノード番号は420aであり、それはノード群401bの代表ノード410bの格納された配列要素の配列番号である。
【0084】
ノード群401bはノード410b、411b、412b、413b、414b、415b、416b、417bで構成される。代表ノード410bとノード位置が111であるノード417bのノード状態447bのみが1で使用中であり、他のノードは空ノードである。ノード410bのノード種別460bとノード417のノード種別467bはともに0であり、ブランチノードであることを示している。
ノード410bの弁別ビット位置430bには1が格納され、リンク先の代表ノード番号にはノード群401cの代表ノード410cの格納された配列要素の配列番号420bが格納されている。ノード417bの弁別ビット位置437bには2が格納され、リンク先の代表ノード番号にはノード群401fの代表ノード410fの格納された配列要素の配列番号427bが格納されている。
【0085】
ブランチノード410bのリンク先である代表ノード410cが属するノード群401cの使用中であるノードはビット位置010のノード412cとビット位置110のノード416cである。ノード412cのノード種別462cは1でリーフノードであることを示し、参照ポインタ452cにはインデックスキーが記憶された記憶領域へのポインタ482cが格納されている。ノード416cのノード種別466cは0でブランチノードであることを示し、弁別ビット位置436cには2が格納され、代表ノード番号にはノード群401dの代表ノード410dの格納された配列要素の配列番号426cが格納されている。
【0086】
ブランチノード416cのリンク先である代表ノード410dが属するノード群401dの使用中であるノードはビット位置100のノード414dとビット位置111のノード417dである。ノード414dのノード種別464dは0でブランチノードであることを示し、弁別ビット位置434dには5が格納され、代表ノード番号にはノード群401eの代表ノード410eの格納された配列要素の配列番号424dが格納されている。ノード417dのノード種別467dは1でリーフノードであることを示し、参照ポインタ457dにはインデックスキーが記憶された記憶領域へのポインタ487dが格納されている。
【0087】
ブランチノード414dのリンク先である代表ノード410eが属するノード群401eの全てのノード410e〜417eはそれぞれのノード状態440e〜447eが1、ノード種別460e〜467eが1でリーフノードであり、参照ポインタ450e〜457eにはインデックスキーが記憶された記憶領域へのポインタ480e〜487eが格納されている。
【0088】
ブランチノード417bのリンク先である代表ノード410fが属するノード群401fのノード410f〜413fは、ノード410fのノード状態440fが0であるように空ノードである。ノード414fはリーフノード、ノード415f〜417fはブランチノードである。ノード414fの参照ポインタにはインデックスキーが記憶された記憶領域へのポインタ484fが格納されている。ブランチノード415fの弁別ビット位置は4であり、代表ノード番号にはノード群401gの代表ノード410gが配置された配列要素の配列番号425fが格納されている。ブランチノード416fの弁別ビット位置は5であり、代表ノード番号にはノード群401iの代表ノード410iが配置された配列要素の配列番号426fが格納されている。ブランチノード417fの弁別ビット位置は3であり、代表ノード番号にはノード群401hの代表ノード410gh配置された配列要素の配列番号427fが格納されている。
【0089】
ブランチノード415fのリンク先である代表ノード410gが属するノード群401gの使用中のノードはノード位置011のノード413gとノード位置100のノード414gだけである。ノード413gのノード種別463gとノード414gのノード種別464gはともに1であり、両ノードはリーフノードである。それぞれの参照ポインタ453gと454gには、インデックスキーが記憶された記憶領域へのポインタ483gと484gが格納されている。
【0090】
ブランチノード416fのリンク先である代表ノード410iが属するノード群401iの使用中のノードはノード位置100のノード414iとノード位置101のノード415iだけである。ノード414iのノード種別464iとノード415iのノード種別465iはともに1であり、両ノードはリーフノードである。それぞれの参照ポインタ454iと455iには、インデックスキーが記憶された記憶領域へのポインタ484iと485iが格納されている。
【0091】
ブランチノード417fのリンク先である代表ノード410hが属するノード群401hの使用中のノードはノード位置101のノード415hとノード位置111のノード417hだけである。ノード415hのノード種別465hとノード417hのノード種別467hはともに1であり、両ノードはリーフノードである。それぞれの参照ポインタ455hと457hには、インデックスキーが記憶された記憶領域へのポインタ485hと487hが格納されている。
【0092】
図13には、各リーフノードの参照ポインタで参照されるインデックスキー(3次元キー)は記載していないが、図13に記載されたルートノードからリーフノードまで、弁別ビット位置とリンク先のノード位置に注目することにより、インデックスキーの値がどの範囲のものであるかを決定することができる。
例えば、リーフノード412cの参照ポインタ482cで参照される3次元キーについて考察すると、ルートノード410aの弁別ビット位置430aが0、リンク経路のブランチノード410bのノード位置が000であることから、各次元のキーの0ビット目が0、ブランチノード410bの弁別ビット位置430bが1、リンク先のリーフノード412cのノード位置が010であることから、各キーの1ビット目のビット値は、第1のキーは0、第2のキーは1、第3のキーは0である。すなわち、リーフノード412cの参照ポインタ482cで参照される3次元キーは、“00xxxx:01xxxx:00xxxx”(xは0,1のいずれか任意の値)の値を有するものである。
他のリーフノードに関連する3次元キーについても、同様にツリーの構造から求めることが可能である。
【0093】
また、トリプル・カップルドノードツリーを用いた検索処理、挿入処理、削除処理については、ダブル・カップルドノードツリーを用いた検索処理、挿入処理、削除処理と同様に実行可能であることは当業者にとって明らかである。
さらに、2次元、あるいは3次元に限らず、次元数に応じてノード位置のビット数を増やすことにより、本発明はより高次元の多次元キーによる検索に拡張可能であることは明らかである。
【0094】
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。例えばリーフノードが、インデックスキーを格納した記憶領域の位置を示す情報に代えてインデックスキー自体を含むようにすることが可能であることは、当業者に自明である。
また、本発明のビット列検索方法を実行する装置が、カップルドノードツリーを格納する記憶手段と図4に示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
さらに、図5〜図8に示した挿入処理とその均等物をコンピュータに実行させるプログラムにより、本発明の挿入方法が実現可能であり、図9A、図9B及び図10に示した削除処理とその均等物をコンピュータに実行させるプログラムにより、本発明の削除方法が実現可能であることも明らかである。そして、それらのプログラムにより、ブランチノードとリーフノードの識別手段、ブランチノードの弁別ビット位置に応じてリンク先のノード対のどちらかにリンクする手段等がコンピュータ上に実現される。
したがって、上記プログラム、及びプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の実施の形態に含まれる。さらに、本発明のカップルドノードツリーのデータ構造及びそのデータ構造を有するデータを記録したコンピュータ読み取り可能な記録媒体も、本発明の実施の形態に含まれる。
以上詳細に説明した、本発明が提供する新しいデータ構造であるカップルドノードツリーを用いることにより、多次元キーを取り扱うことができ、より高速なビット列データの検索を行うことが可能となる。しかもビット列データの追加削除も容易に実行することができる。
【図面の簡単な説明】
【0095】
【図1】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【図2A】配列に格納されたダブル・カップルドノードツリーの構成例を説明する図である。
【図2B】ダブル・カップルドノードツリーのツリー構造を概念的に示す図である。
【図3】本発明を実施するためのハードウェア構成例を説明する図である。
【図4】本発明の一実施形態における検索処理を示すフローチャートである。
【図5】本発明の一実施形態における挿入処理の前段である検索処理の処理フローを示す図である。
【図6A】本発明の一実施形態における挿入処理における挿入するノード群のための配列要素を準備する処理フローを説明する図である。
【図6B】ノード群を挿入する位置を求め、ノード群の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。
【図7A】挿入キー列と比較キー列の差分ビット位置を得る処理フローを説明する図である。
【図7B】挿入されるノード群に格納するノードのノード位置を求める処理フローを説明する図である。
【図8】本発明の一実施形態におけるルートノードの挿入処理を含むリーフノードの挿入処理全体の処理フローを説明する図である。
【図9A】本発明の一実施形態における削除処理の前段である検索処理の処理フローを示す図である。
【図9B】本発明の一実施形態における削除処理の後段の処理フローを説明する図である。
【図10】ノード群から削除対象のノード以外の使用中のノードを求める処理フローを説明する図である。
【図11A】第1の削除処理例における削除処理前のダブル・カップルノードツリーと削除キーを説明する図である。
【図11B】第1の削除処理例における削除処理後のダブル・カップルドノードツリー例を示す図である。
【図11C】第2の削除処理例における削除処理前のダブル・カップルノードツリーと削除キーを説明する図である。
【図11D】第2の削除処理例における削除処理後のダブル・カップルドノードツリー例を示す図である。
【図12A】第1の具体例における挿入処理前のカップルドノードツリー例を示す図である。
【図12B】第1の具体例における挿入処理後のカップルドノードツリー例を示す図である。
【図12C】第2の具体例における挿入処理前のカップルドノードツリー例を示す図である。
【図12D】第2の具体例における挿入処理後のカップルドノードツリー例を示す図である。
【図13】配列に格納されたトリプル・カップルドノードツリーのツリー構造を概念的に示す図である。
【符号の説明】
【0096】
10、20、30 配列番号
100 配列
101、122、123 ノード
102a、114a、117a ノード状態
102b、114b、117b ノード種別
103、115 弁別ビット位置
104、116 代表ノード番号
111、121 ノード群
112、122 ノード[0]、ノード位置00のノード
113、123 ノード[1]、ノード位置01のノード
112a、122a ノード[2]、ノード位置10のノード
113a、123a ノード[3]、ノード位置11のノード
118a 参照ポインタ
301 データ処理装置
302 中央処理装置
303 キャッシュメモリ
304 バス
305 主記憶装置
306 外部記憶装置
307 通信装置
308 データ格納装置
309 配列
310 探索経路スタック
311 インデックスキーの格納領域
【特許請求の範囲】
【請求項1】
ルートノードと、該ルートの下層に、隣接した記憶領域であるノード位置に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、該ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキーを含み、前記空ノードは該空ノードが空状態であることを示す情報を含むカップルドノードツリーを用いたビット列検索装置において、
前記インデックスキーは2つ以上のキーの列であり、前記ブランチノードは、ビット列検索を行う検索キー列中のキーの弁別ビット位置をさらに含み、
前記カップルドノードツリーの空ノード以外の任意のノードを検索開始ノードとして、前記ブランチノードにおいて、前記検索キー列の各キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じて、前記代表ノードの属するリンク先のノード群の1つのノード位置に配置されたノードにリンクすることを順次繰り返し、
前記リーフノードに至った場合は、前記リーフノードに含まれる前記第二の位置情報が示す記憶領域に格納されたインデックスキーあるいは前記リーフノードに含まれるインデックスキーを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果キー列とし、
前記空ノードに至った場合は該空ノードを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果空ノードとする、
ことを特徴とするビット列検索装置。
【請求項2】
配列を備え、前記カップルドノードツリーは該配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項1記載のビット列検索装置。
【請求項3】
スタックを備え、前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次前記スタックに保持されていくことを特徴とする請求項2記載のビット列検索装置。
【請求項4】
ルートノードと、該ルートの下層に、隣接した記憶領域であるノード位置に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、該ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキーを含み、前記空ノードは該空ノードが空状態であることを示す情報を含むカップルドノードツリーを用いたビット列検索方法において、
前記インデックスキーは2つ以上のキーの列であり、前記ブランチノードは、ビット列検索を行う検索キー列中のキーの弁別ビット位置をさらに含み、
前記カップルドノードツリーの空ノード以外の任意のノードを検索開始ノードとして、前記ブランチノードにおいて、前記検索キー列の各キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じて、前記代表ノードの属するリンク先のノード群の1つのノード位置に配置されたノードにリンクすることを順次繰り返し、
前記リーフノードに至った場合は、前記リーフノードに含まれる前記第二の位置情報が示す記憶領域に格納されたインデックスキーあるいは前記リーフノードに含まれるインデックスキーを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果キー列とし、
前記空ノードに至った場合は該空ノードを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果空ノードとする、
ことを特徴とするビット列検索方法。
【請求項5】
前記カップルドノードツリーは配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項4記載のビット列検索方法。
【請求項6】
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次スタックに保持されていくことを特徴とする請求項5記載のビット列検索方法。
【請求項7】
請求項4記載のビット列検索方法で用いるカップルドノードツリーに、新たなインデックスキーが格納された記憶領域の位置を示す前記第二の位置情報あるいは該新たなインデックスキーを含むリーフノードを挿入するリーフノード挿入方法において、
前記新たなインデックスキーを前記検索キー列とし、前記カップルドノードツリーのルートノードを検索開始ノードとして、ルートノードからリーフノードあるいは空ノードに至るリンク経路を記憶しながら請求項4記載のビット列検索方法によりビット列検索を実行する検索ステップと、
前記検索ステップにおいて前記検索結果空ノードが得られた場合は、
該検索結果空ノードに前記挿入されるリーフノードの内容を書き込むことにより該リーフノードを挿入するステップと、
前記検索ステップにおいて前記検索結果キー列が得られた場合は、
前記検索キー列と前記検索結果キー列のキーのビット値をキー毎に比較して最初に異なるビット値となるビット位置の最小値である差分ビット位置を取得する差分ビット位置取得ステップと、
前記リンク経路上のブランチノードの弁別ビット位置と前記差分ビット位置取得ステップで取得した前記差分ビット位置との相対的位置関係により、挿入される前記リーフノードを含むノード群の挿入位置を決定する挿入位置決定ステップと、
前記検索キー列の各キーの前記差分ビット位置のビット値の組み合わせにより、挿入される前記リーフノードを含む前記ノード群のどのノード位置に前記挿入されるリーフノードを配置するかを決定するノード位置決定ステップと、
前記第二の位置情報として前記新たなインデックスキーを格納する記憶領域の位置を示す情報をあるいは前記新たなインデックスキーを前記リーフノードに格納することによりリーフノードを生成ステップと、
を含むことを特徴とするリーフノード挿入方法。
【請求項8】
前記カップルドノードツリーは配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項7記載のリーフノード挿入方法。
【請求項9】
前記ルートノードの格納された配列要素の配列番号及び前記ルートノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次スタックに保持されていくことを特徴とする請求項8記載のリーフノード挿入方法。
【請求項10】
請求項4記載のビット列検索方法で用いるカップルドノードツリーから、指定された前記インデックスキーが格納された記憶領域の位置を示す前記第二の位置情報あるいは該インデックスキーを含む削除対象のリーフノードを削除する、リーフノード削除方法において、
前記指定されたインデックスキーを検索キー列とし、前記カップルドノードツリーのルートノードを検索開始ノードとして請求項4記載のビット列検索方法により前記検索結果キー列を取得し、
前記第二の位置情報として前記検索結果キー列を格納する記憶領域の位置を示す情報あるいはインデックスキーとして前記検索結果キー列を含む前記削除対象のリーフノードと同一のノード群に3つ以上のノードが配置されているか判定し、
3つ以上のノードが配置されていれば前記削除対象のリーフノードを空ノードとすることにより該リーフノードを削除し、
前記同一のノード群に2つのノードが配置されていれば、前記削除対象のリーフノード以外のもう1つのノードを、前記削除対象のリーフノードのリンク元のブランチノードに格納し、前記削除対象のリーフノードが配置されたノード群を削除することにより前記削除対象のリーフノードを削除する、
ことを特徴とするリーフノード削除方法。
【請求項11】
前記カップルドノードツリーは配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項10記載のリーフノード削除方法。
【請求項12】
前記ルートノードの格納された配列要素の配列番号及び前記ルートノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次スタックに保持されていくことを特徴とする請求項13記載のリーフノード削除方法。
【請求項13】
請求項4〜12いずれか1項に記載の方法をコンピュータに実行させるためのプログラム。
【請求項14】
請求項4〜12いずれか1項に記載の方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項15】
ビット列検索に用いるツリー状のデータ構造であって、
該ツリーは、ルートノードと、該ルートの下層に、隣接した記憶領域であるノード位置に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群、からなり、
前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、該ツリーのノードが2つ以上のときは前記ブランチノードであり、
前記ブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキーを含み、前記空ノードは該空ノードが空状態であることを示す情報を含み、
前記インデックスキーは2つ以上のキーの列であり、前記ブランチノードは、ビット列検索を行う検索キー列中のキーの弁別ビット位置をさらに含み、
前記ツリーの空ノード以外の任意のノードを検索開始ノードとして、前記ブランチノードにおいて、前記検索キー列の各キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じて、前記代表ノードの属するリンク先のノード群の1つのノード位置に配置されたノードにリンクすることを順次繰り返し、前記リーフノードに至った場合は、前記リーフノードに含まれる前記第二の位置情報が示す記憶領域に格納されたインデックスキーあるいは前記リーフノードに含まれるインデックスキーを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果キー列とする、前記検索キー列による検索の実行を可能とすることを特徴とするデータ構造。
【請求項16】
前記データ構造は配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項15記載のデータ構造。
【請求項17】
請求項15又は請求項16に記載されたデータ構造を有するデータが記録されたコンピュータ読み取り可能な記録媒体。
【請求項1】
ルートノードと、該ルートの下層に、隣接した記憶領域であるノード位置に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、該ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキーを含み、前記空ノードは該空ノードが空状態であることを示す情報を含むカップルドノードツリーを用いたビット列検索装置において、
前記インデックスキーは2つ以上のキーの列であり、前記ブランチノードは、ビット列検索を行う検索キー列中のキーの弁別ビット位置をさらに含み、
前記カップルドノードツリーの空ノード以外の任意のノードを検索開始ノードとして、前記ブランチノードにおいて、前記検索キー列の各キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じて、前記代表ノードの属するリンク先のノード群の1つのノード位置に配置されたノードにリンクすることを順次繰り返し、
前記リーフノードに至った場合は、前記リーフノードに含まれる前記第二の位置情報が示す記憶領域に格納されたインデックスキーあるいは前記リーフノードに含まれるインデックスキーを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果キー列とし、
前記空ノードに至った場合は該空ノードを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果空ノードとする、
ことを特徴とするビット列検索装置。
【請求項2】
配列を備え、前記カップルドノードツリーは該配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項1記載のビット列検索装置。
【請求項3】
スタックを備え、前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次前記スタックに保持されていくことを特徴とする請求項2記載のビット列検索装置。
【請求項4】
ルートノードと、該ルートの下層に、隣接した記憶領域であるノード位置に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群がツリー状にリンクしたビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、該ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキーを含み、前記空ノードは該空ノードが空状態であることを示す情報を含むカップルドノードツリーを用いたビット列検索方法において、
前記インデックスキーは2つ以上のキーの列であり、前記ブランチノードは、ビット列検索を行う検索キー列中のキーの弁別ビット位置をさらに含み、
前記カップルドノードツリーの空ノード以外の任意のノードを検索開始ノードとして、前記ブランチノードにおいて、前記検索キー列の各キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じて、前記代表ノードの属するリンク先のノード群の1つのノード位置に配置されたノードにリンクすることを順次繰り返し、
前記リーフノードに至った場合は、前記リーフノードに含まれる前記第二の位置情報が示す記憶領域に格納されたインデックスキーあるいは前記リーフノードに含まれるインデックスキーを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果キー列とし、
前記空ノードに至った場合は該空ノードを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果空ノードとする、
ことを特徴とするビット列検索方法。
【請求項5】
前記カップルドノードツリーは配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項4記載のビット列検索方法。
【請求項6】
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次スタックに保持されていくことを特徴とする請求項5記載のビット列検索方法。
【請求項7】
請求項4記載のビット列検索方法で用いるカップルドノードツリーに、新たなインデックスキーが格納された記憶領域の位置を示す前記第二の位置情報あるいは該新たなインデックスキーを含むリーフノードを挿入するリーフノード挿入方法において、
前記新たなインデックスキーを前記検索キー列とし、前記カップルドノードツリーのルートノードを検索開始ノードとして、ルートノードからリーフノードあるいは空ノードに至るリンク経路を記憶しながら請求項4記載のビット列検索方法によりビット列検索を実行する検索ステップと、
前記検索ステップにおいて前記検索結果空ノードが得られた場合は、
該検索結果空ノードに前記挿入されるリーフノードの内容を書き込むことにより該リーフノードを挿入するステップと、
前記検索ステップにおいて前記検索結果キー列が得られた場合は、
前記検索キー列と前記検索結果キー列のキーのビット値をキー毎に比較して最初に異なるビット値となるビット位置の最小値である差分ビット位置を取得する差分ビット位置取得ステップと、
前記リンク経路上のブランチノードの弁別ビット位置と前記差分ビット位置取得ステップで取得した前記差分ビット位置との相対的位置関係により、挿入される前記リーフノードを含むノード群の挿入位置を決定する挿入位置決定ステップと、
前記検索キー列の各キーの前記差分ビット位置のビット値の組み合わせにより、挿入される前記リーフノードを含む前記ノード群のどのノード位置に前記挿入されるリーフノードを配置するかを決定するノード位置決定ステップと、
前記第二の位置情報として前記新たなインデックスキーを格納する記憶領域の位置を示す情報をあるいは前記新たなインデックスキーを前記リーフノードに格納することによりリーフノードを生成ステップと、
を含むことを特徴とするリーフノード挿入方法。
【請求項8】
前記カップルドノードツリーは配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項7記載のリーフノード挿入方法。
【請求項9】
前記ルートノードの格納された配列要素の配列番号及び前記ルートノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次スタックに保持されていくことを特徴とする請求項8記載のリーフノード挿入方法。
【請求項10】
請求項4記載のビット列検索方法で用いるカップルドノードツリーから、指定された前記インデックスキーが格納された記憶領域の位置を示す前記第二の位置情報あるいは該インデックスキーを含む削除対象のリーフノードを削除する、リーフノード削除方法において、
前記指定されたインデックスキーを検索キー列とし、前記カップルドノードツリーのルートノードを検索開始ノードとして請求項4記載のビット列検索方法により前記検索結果キー列を取得し、
前記第二の位置情報として前記検索結果キー列を格納する記憶領域の位置を示す情報あるいはインデックスキーとして前記検索結果キー列を含む前記削除対象のリーフノードと同一のノード群に3つ以上のノードが配置されているか判定し、
3つ以上のノードが配置されていれば前記削除対象のリーフノードを空ノードとすることにより該リーフノードを削除し、
前記同一のノード群に2つのノードが配置されていれば、前記削除対象のリーフノード以外のもう1つのノードを、前記削除対象のリーフノードのリンク元のブランチノードに格納し、前記削除対象のリーフノードが配置されたノード群を削除することにより前記削除対象のリーフノードを削除する、
ことを特徴とするリーフノード削除方法。
【請求項11】
前記カップルドノードツリーは配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項10記載のリーフノード削除方法。
【請求項12】
前記ルートノードの格納された配列要素の配列番号及び前記ルートノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号が、順次スタックに保持されていくことを特徴とする請求項13記載のリーフノード削除方法。
【請求項13】
請求項4〜12いずれか1項に記載の方法をコンピュータに実行させるためのプログラム。
【請求項14】
請求項4〜12いずれか1項に記載の方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項15】
ビット列検索に用いるツリー状のデータ構造であって、
該ツリーは、ルートノードと、該ルートの下層に、隣接した記憶領域であるノード位置に配置される4つ以上のノードであってブランチノード、リーフノードあるいは空ノードの組から構成されるノード群、からなり、
前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、該ツリーのノードが2つ以上のときは前記ブランチノードであり、
前記ブランチノードは、リンク先のノード群の1つのノードである代表ノードの位置を示す第一の位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを格納した記憶領域の位置を示す第二の位置情報あるいはインデックスキーを含み、前記空ノードは該空ノードが空状態であることを示す情報を含み、
前記インデックスキーは2つ以上のキーの列であり、前記ブランチノードは、ビット列検索を行う検索キー列中のキーの弁別ビット位置をさらに含み、
前記ツリーの空ノード以外の任意のノードを検索開始ノードとして、前記ブランチノードにおいて、前記検索キー列の各キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じて、前記代表ノードの属するリンク先のノード群の1つのノード位置に配置されたノードにリンクすることを順次繰り返し、前記リーフノードに至った場合は、前記リーフノードに含まれる前記第二の位置情報が示す記憶領域に格納されたインデックスキーあるいは前記リーフノードに含まれるインデックスキーを、前記検索開始ノードをルートノードとする前記カップルドノードツリーの任意の部分木の前記検索キー列による検索結果である検索結果キー列とする、前記検索キー列による検索の実行を可能とすることを特徴とするデータ構造。
【請求項16】
前記データ構造は配列に記憶され、前記第一の位置情報は、該第一の位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項15記載のデータ構造。
【請求項17】
請求項15又は請求項16に記載されたデータ構造を有するデータが記録されたコンピュータ読み取り可能な記録媒体。
【図1】
【図2A】
【図2B】
【図3】
【図4】
【図5】
【図6A】
【図6B】
【図7A】
【図7B】
【図8】
【図9A】
【図9B】
【図10】
【図11A】
【図11B】
【図11C】
【図11D】
【図12A】
【図12B】
【図12C】
【図12D】
【図13】
【図2A】
【図2B】
【図3】
【図4】
【図5】
【図6A】
【図6B】
【図7A】
【図7B】
【図8】
【図9A】
【図9B】
【図10】
【図11A】
【図11B】
【図11C】
【図11D】
【図12A】
【図12B】
【図12C】
【図12D】
【図13】
【公開番号】特開2009−277164(P2009−277164A)
【公開日】平成21年11月26日(2009.11.26)
【国際特許分類】
【出願番号】特願2008−130242(P2008−130242)
【出願日】平成20年5月18日(2008.5.18)
【出願人】(506235616)株式会社エスグランツ (32)
【Fターム(参考)】
【公開日】平成21年11月26日(2009.11.26)
【国際特許分類】
【出願日】平成20年5月18日(2008.5.18)
【出願人】(506235616)株式会社エスグランツ (32)
【Fターム(参考)】
[ Back to top ]