カップルドノードツリーの分割/結合方法及びプログラム
【課題】カップルドノードツリーの規模が大きくなっても、カップルドノードツリーの分割や結合処理の効率が低下することを少なくする手法を提供する。
【解決手段】カップルドノードツリーの分割や結合処理に用いる基本検索や最大値あるいは最小値検索において、検索履歴を格納する探索経路スタックにノードの配置されたアドレス情報のみならず検索経路でたどったブランチノードの弁別ビット位置を格納する。これにより、アドレス情報によりブランチノードにアクセスすることなく、探索経路スタックから直接弁別ビット位置を読み出すことができる。
【解決手段】カップルドノードツリーの分割や結合処理に用いる基本検索や最大値あるいは最小値検索において、検索履歴を格納する探索経路スタックにノードの配置されたアドレス情報のみならず検索経路でたどったブランチノードの弁別ビット位置を格納する。これにより、アドレス情報によりブランチノードにアクセスすることなく、探索経路スタックから直接弁別ビット位置を読み出すことができる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する検索方法に関するものであり、特に本出願人が特願2006−187827及び特願2006−3199407において提案したカップルドノードツリーの分割/結合方法及びプログラムに関するものである。
【背景技術】
【0002】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【0003】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【0004】
図17は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【0005】
図17の例では、インデックスキー“100010”を保持するノード1750aがルートノードとなっており、その検査ビット位置1730aは0である。ノード1750aの左リンク1740aにはノード1750bが接続され、右リンク1741aにはノード1750fが接続されている。
【0006】
ノード1750bの保持するインデックスキーは“010011”であり、検査ビット位置1730bは1である。ノード1750bの左リンク1740bにはノード1750cが、右リンク1741bにはノード1750dが接続されている。ノード1750cが保持するインデックスキーは“000111”、検査ビット位置1730cは3である。ノード1750dが保持するインデックスキーは“011010”、検査ビット位置1730dは2である。
【0007】
ノード1750cから実線で接続された部分はノード1750cの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ1740cは、その欄が空欄であることを示している。点線の接続された右ポインタ1741cの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード1750cを右ポインタ1741cが指定していることを表している。
【0008】
ノード1750dの右ポインタ1741dはノード1750d自身を指しており、左リンク1740dにはノード1750eが接続されている。ノード1750eの保持するインデックスキーは“010010”、検査ビット位置1730eは5である。ノード1750eの左ポインタ1740eはノード1750bを、右ポインタ1741eはノード1750eを指している。
【0009】
また、ノード1750fの保持するインデックスキーは“101011”であり、検査ビット位置1730fは2である。ノード1750fの左リンク1740fにはノード1750gが、右リンク1741fにはノード1750hが接続されている。
【0010】
ノード1750gの保持するインデックスキーは“100011”であり、検査ビット位置1730gは5である。ノード1750gの左ポインタ1740gはノード1750aを、右ポインタ1741gはノード1750gを指している。
【0011】
ノード1750hの保持するインデックスキーは“101100”であり、検査ビット位置1730hは3である。ノード1750hの左ポインタ1740hはノード1750fを、右ポインタ1741hはノード1750hを指している。
【0012】
図17の例では、ルートノード1750aからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が1であるか0であるか判定を行い、1であれば右リンクをたどり、0であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば(図17において点線で示されたこの逆戻りのリンクをバックリンクという)、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【0013】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は1回ですむことなどのメリットがあるが、各ノードからの2つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【0014】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献1に開示された技術がある。下記特許文献1に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【0015】
しかしながら、下記特許文献1に開示されたものにおいても、1つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを1つとしたため、例えば図17に示したパトリシアツリーの最下段の部分である左ポインタ1740c、右ポインタ1741h等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【0016】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願2006−187827において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが1つのときはリーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を提案した。
【0017】
上記出願においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。
【0018】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願2006−293619において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの最大値/最小値を求める手法等を提案した。
【0019】
さらに、本出願人は、特願2006−319407において、カップルドノードツリーの分割/結合手法を提案した。
上記3つの出願において提案した検索手法は、検索開始ノードから順次ブランチノードをたどってリーフノードに至り、リーフノードに格納されたインデックスキーを求める操作を基本とするものであり、検索履歴として検索開始ノードからリーフノードに至るノードの配置された記憶領域のアドレス情報として該ノードの格納されている配列要素の配列番号をスタックに格納している。そして、検索処理後の各種処理において、スタックに格納されたアドレス情報を基にそのアドレス情報が示す記憶領域に格納されたノードを参照して弁別ビット位置を取り出すことが行われている。
【0020】
上記アドレス情報としては、カップルドノードツリーを配列に格納する場合にはその配列での配列番号を用いることができ、アドレス情報を表すビット量を削減することができるが、カップルドノードツリーの規模が大きくなるとそれに伴ってノードが実際に格納されるアドレス範囲が大きくなり、各種処理をコンピュータ上で実行するときにキャッシュミスを起こす可能性が高くなり、処理効率が低下するおそれがある。
【先行技術文献】
【特許文献】
【0021】
【特許文献1】特開2001−357070号公報
【発明の概要】
【発明が解決しようとする課題】
【0022】
そこで本発明の目的は、カップルドノードツリーの規模が大きくなっても、カップルドノードツリーを利用した処理の効率が低下することを少なくする手法を提供することである。
【課題を解決するための手段】
【0023】
本発明によれば、カップルドノードツリーの分割/結合処理で用いる基本検索や最大値あるいは最小値検索の検索処理において、検索履歴を格納する探索経路スタックにノードの配置された記憶領域のアドレス情報のみならず検索経路でたどったブランチノードの弁別ビット位置を格納する。
【0024】
そして、検索処理でたどったブランチノードの弁別ビット位置を探索するカップルドノードツリーの分割/結合処理においては、探索経路スタックから弁別ビット位置を取り出す。
【発明の効果】
【0025】
本発明によれば、検索処理でたどったノードの弁別ビット位置が必要なときは、その情報を、検索履歴を格納する探索経路スタックから得ることができ、カップルドノードツリーの規模が大きくなったとしても、キャッシュミスが発生する可能性を小さくすることができる。
【図面の簡単な説明】
【0026】
【図1】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図2】カップルドノードツリーのツリー構造を概念的に示す図である。
【図3】本発明を実施するためのハードウェア構成例を説明する図である。
【図4A】本発明におけるビット列検索の基本動作を示すフロー図である。
【図4B】本発明におけるビット列検索の基本動作をカップルドノードツリーにより説明する図である。
【図5A】本発明における挿入処理の前段である検索処理の処理フローを示す図である。
【図5B】挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
【図5C】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。
【図6】本発明におけるルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【図7A】削除処理の前段である検索処理の処理フローを示す図である。
【図7B】削除処理の後段の処理フローを説明する図である。
【図8】本発明のカップルドノードツリーに格納されたインデックスキーの最小値を求める処理を示すフロー図である。
【図9】本発明のインデックスキーの最小値を求める処理をカップルドノードツリーにより説明する図である
【図10】本発明のカップルドノードツリーに格納されたインデックスキーの最大値を求める処理を示すフローチャートである。
【図11】本発明のインデックスキーの最大値を求める処理をカップルドノードツリーにより説明する図である。
【図12】カップルドノードツリーの第1の分割処理フローを説明する図である。
【図13】カップルドノードツリーの第2の分割処理フローを説明する図である。
【図14】第2の分割処理におけるノードの挿入処理フローを説明する図である。
【図15A】第2の分割処理におけるルートノード設定処理を説明するフロー図である。
【図15B】第2の分割処理における親ノードに挿入キーを含むノード対を挿入する処理フローを説明する図である。
【図16】第2の分割処理における削除処理を説明するフロー図である。
【図17】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【発明を実施するための形態】
【0027】
最初に、本出願人により先の上記出願において提案された、本発明の前提となるカップルドノードツリーについて、カップルドノードツリーを配列に格納する例を説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【0028】
図1は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図1を参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード種別102、弁別ビット位置103及び代表ノード番号104で構成されている。ノード種別102は0であり、ノード101がブランチノードであることを示している。弁別ビット位置103には1が格納されている。代表ノード番号104にはリンク先のノード対の代表ノードの配列番号20が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【0029】
配列番号20の配列要素には、ノード対111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1)に代表ノードと対になるノード[1]113が格納されている。ノード[0]112のノード種別114には0が、弁別ビット位置115には3が、代表ノード番号116には30が格納されている。またノード[1]113のノード種別117には1が格納されており、ノード[1]113がリーフノードであることを示している。インデックスキー118には、“0001”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
【0030】
なお、代表ノードをノード[0]で表し、それと対になるノードをノード[1]で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
【0031】
配列番号30及び31の配列要素に格納されたノード122とノード123からなるノード対121の内容は省略されている。
ノード[0]112、ノード[1]113、ノード122、及びノード123の格納された配列要素にそれぞれ付された0あるいは1は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である0か1を代表ノード番号に加えた配列番号のノードにリンクする。
【0032】
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【0033】
図2は、カップルドノードツリーのツリー構造を概念的に示す図である。図示の6ビットのインデックスキーは、図17に例示されたパトリシアツリーのものと同じである。
符号210aで示すのがルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード対201aの代表ノードとしている。
【0034】
ツリー構造としては、ルートノード210aの下にノート対201bが、その下層にノード対201cとノード対201fが配置され、ノード対201fの下層にはノード対201hとノード対201gが配置されている。ノード対201cの下にはノード対201dが、さらにその下にはノード対201eが配置されている。
【0035】
各ノードの前に付された0あるいは1の符号は、図1において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【0036】
図示された例では、ルートノード210aのノード種別260aは0でブランチノードであることを示し、弁別ビット位置230aは0を示している。代表ノード番号は220aであり、それはノード対201bの代表ノード210bの格納された配列要素の配列番号である。
【0037】
ノード対201bはノード210bと211bで構成され、それらのノード種別260b、261bはともに0であり、ブランチノードであることを示している。ノード210bの弁別ビット位置230bには1が格納され、リンク先の代表ノード番号にはノード対201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。
【0038】
ノード210cのノード種別260cには1が格納されているので、このノードはリーフノードであり、したがって、インデックスキー250cを含んでいる。インデックスキー250cには“000111”が格納されている。一方ノード211cのノード種別261cは0、弁別ビット位置231cは2であり、代表ノード番号にはノード対201dの代表ノード210dの格納された配列要素の配列番号221cが格納されている。
【0039】
ノード210dのノード種別260dは0、弁別ビット位置230dは5であり、代表ノード番号にはノード対201eの代表ノード210eの格納された配列要素の配列番号220dが格納されている。ノード210dと対になるノード211dのノード種別261dは1であり、インデックスキー251dには“011010”が格納されている。
【0040】
ノード対201eのノード210e、211eのノード種別260e、261eはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250e、251eにはインデックスキーとして“010010”と“010011”が格納されている。
【0041】
ノード対201bのもう一方のノードであるノード211bの弁別ビット位置231bには2が格納され、リンク先の代表ノード番号にはノード対201fの代表ノード210fの格納された配列要素の配列番号221bが格納されている。
【0042】
ノード対201fのノード210f、211fのノード種別260f、261fはともに0であり双方ともブランチノードである。それぞれの弁別ビット位置230f、231fには5、3が格納されている。ノード210fの代表ノード番号にはノード対201gの代表ノード210gの格納された配列要素の配列番号220fが格納され、ノード211fの代表ノード番号にはノード対201hの代表ノードであるノード[0]210hの格納された配列要素の配列番号221fが格納されている。
【0043】
ノード対201gのノード210g、211gのノード種別260g、261gはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250g、251gには“100010”と“100011”が格納されている。
【0044】
また同じくノード対201hの代表ノードであるノード[0]210hとそれと対をなすノード[1]211hのノード種別260h、261hはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250h、251hには“101011”と“101100”が格納されている。
【0045】
以下、上述のツリーからインデックスキー“100010”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から0、1、2、・・・とする。
まず、ビット列“100010”を検索キーとしてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは0であるので、検索キー“100010”の弁別ビット位置が0のビット値をみると1である。そこで代表ノード番号の格納された配列番号220aに1を加えた配列番号の配列要素に格納されたノード211bにリンクする。ノード211bの弁別ビット位置231bには2が格納されているので、検索キー“100010”の弁別ビット位置が2のビット値をみると0であるから、代表ノード番号の格納された配列番号221bの配列要素に格納されたノード210fにリンクする。
【0046】
ノード210fの弁別ビット位置230fには5が格納されているので、検索キー“100010”の弁別ビット位置が5のビット値をみると0であるから、代表ノード番号の格納された配列番号220fの配列要素に格納されたノード210gにリンクする。
【0047】
ノード210gのノード種別260gは1でありリーフノードであることを示しているので、インデックスキー250gを読み出して検索キーと比較すると両方とも“100010”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【0048】
次に、図2を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図2の例で、ルートノード210aの弁別ビット位置が0であるのは、図2に例示されたインデックスキーに0ビット目が0のものと1のものがあるからである。0ビット目が0のインデックスキーのグループはノード210bの下に分類され、0ビット目が1のインデックスキーのグループはノード211bの下に分類されている。
【0049】
ノード211bの弁別ビット位置が2であるのは、ノード211h、210h、211g、210gに格納された0ビット目が1のインデックスキーの1ビット目がすべて0で等しく、2ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
【0050】
以下0ビット目の場合と同様に、2ビット目が1であるものはノード211f側に分類され、2ビット目が0であるものはノード210f側に分類される。
そして2ビット目が1であるインデックスキーは3ビット目の異なるものがあるのでノード211fの弁別ビット位置には3が格納され、2ビット目が0であるインデックスキーでは3ビット目も4ビット目も等しく5ビット目で異なるのでノード210fの弁別ビット位置には5が格納される。
【0051】
ノード211fのリンク先においては、3ビット目が1のものと0のものがそれぞれ1つしかないことから、ノード210h、211hはリーフノードとなり、それぞれインデックスキー250hと251hに“101011”と“101100”が格納されている。
【0052】
仮にインデックスキーの集合に“101100”の代わりに“101101”か“101110”が含まれていたとしても、3ビット目までは“101100”と等しいので、ノード211hに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“101100”に加えて“101101”が含まれていると、ノード211hはブランチノードとなり、その弁別ビット位置は5になる。追加されるインデックスキーが“101110”であれば、弁別ビット位置は4となる。
【0053】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“1”のノードとビット値が“0”のノードとに分岐していることから、ノード[1]側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード211hのインデックスキー251hの“101100”、ノード210hのインデックスキー250hの“101011”、・・・、ノード210cのインデックスキー250cの“000111”となり降順にソートされている。
【0054】
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“101100”であればノード211hに到達することができる。また、上記説明からも想像がつくように、“101101”か“101110”を検索キーとした場合でもノード211hにたどり着き、インデックスキー251hと比較することにより検索が失敗したことが分かる。
【0055】
また、例えば“100100”で検索した場合でも、ノード210a、211b、210fのリンク経路では検索キーの3ビット目と4ビット目は使われることがなく、“100100”の5ビット目が0なので、“100010”で検索した場合と同様にノード210gに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【0056】
図3は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施される。データ格納装置308は、カップルドノードツリーが配置される配列309と検索中にたどるノードが格納された配列要素の配列番号のほかノード内の情報を記憶する探索経路スタック310を有する。このデータ格納装置308は主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。
【0057】
図3の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできるし、探索経路スタック310を中央処理装置302内のハードウェアとして実現することも可能である。あるいは、配列309は外部記憶装置306に、探索経路スタック310を主記憶装置305に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【0058】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
次に、上述の出願において本出願人により提案された、カップルドノードツリーを用いた基本的な検索処理、カップルドノードツリーにおける挿入削除処理、カップルドノードツリーに含まれるインデックスキーの最大値/最小値を求める処理等の応用処理、及びカップルドノードツリーの分割/結合処理において、検索履歴を格納するスタックに、ノードの配置された記憶領域のアドレス情報のみならず各種処理で用いるブランチノードの弁別ビット位置を格納し、それを利用する本発明を説明する。
【0059】
図4Aは、本発明のビット列検索の基本動作を示すフローチャートである。図4Aに示すフローチャートは、本出願人による出願である上記特願2006−293619で提案されたビット列検索の基本動作を示すフローチャートにおいて、探索経路スタック310に弁別ビット位置を格納するステップS406aの処理を追加したものである。
【0060】
まず、ステップS401で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列要素は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後に説明する各種応用検索において行われる。
【0061】
次に、ステップS402で、探索経路スタック310に取得された配列番号を格納し、ステップS403で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップS404で、読み出したノードから、ノード種別を取り出し、ステップS405で、ノード種別がブランチノードであるか否かを判定する。
【0062】
ステップS405の判定において、読み出したノードがブランチノードである場合は、ステップS406に進み、ノードから弁別ビット位置についての情報を取り出す。
次にステップS406aで、ステップS406で取り出した弁別ビット位置を探索経路スタック310に格納するとともに、ステップS407で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップS408で、ノードから代表ノード番号を取り出して、ステップS409で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号を得て、ステップS402に戻る。
【0063】
以降、ステップS405の判定においてリーフノードと判定されてステップS410に進むまで、ステップS402からステップS409までの処理を繰り返す。ステップS410で、リーフノードからインデックスキーを取り出して、処理を終了する。
【0064】
図4Bは、図4Aのフローチャートにより示した本実施形態に係るビット列検索の基本動作を、図2に例示したカップルドノードツリーにより説明する図である。
図4Bにおいては、カップルドノードツリー、検索キー設定エリア270及び探索経路スタック310が示されている。以下、図4Bを用いてカップルドノードツリー上の参照されるノード及び探索経路スタック310の状態について説明する。
【0065】
なお、図4Bにおいては、図2に示すカップルドノードツリーのうち、図4Aの処理を説明するために必要な一部分のみを示し、残りのノード(代表ノード番号221b以下のノード)については省略している。以降の説明においてカップルドノードツリー上の参照されるノードを説明するための図面についても同様である。
【0066】
まず、検索を開始するノードの配列番号として、配列番号220が設定されたとする。このとき、対応する配列番号220が探索経路スタック310にプッシュされると共に、配列要素の各種情報が参照される。
【0067】
配列に格納された情報に基づいて、配列番号220のノードがブランチノードであってインデックスキーが格納されていないと認識されると、さらにその配列番号220の配列に格納されている情報(代表ノード番号や弁別ビット位置)等を参照して、次に参照すべき配列番号が算出される。
【0068】
ここでは、まず配列番号220を探索経路スタック310に格納し、配列番号220のノード210aからノード種別260aを取り出す。取り出したノード種別260aは図示のとおり“0”であってノード210aがブランチノードであることを示しているため、ノード210aから弁別ビット位置230aの値“0”を取り出し、探索経路スタック310に配列番号220とともに格納する。
【0069】
さらに、検索キー設定エリア270の検索キー“011010”における弁別ビット位置0のビット値“0”を取り出す。そして、ノード210aに格納されている代表ノード番号220aの値を取り出して、先に検索キーの弁別ビット位置から取り出したビット値“0”を加算して得られた配列番号220aを探索経路スタック310に格納する。
【0070】
続いて、配列番号220aのノードからノード種別260bを読み出すと、配列番号220aのノード210bはブランチノードであることが判定され、ノード210bの弁別ビット位置230bの値“1”を探索経路スタック310に格納し、弁別ビット位置1に対応するビット値を検索キー“011010”から取り出すと、値は“1”である。そこで、ノード210bの代表ノード番号220bに得られたビット値“1”を加算して、探索経路スタック310に220b+1を格納する。
【0071】
配列番号(220b+1)のノード211cから読み出したノード種別261cはブランチノードを示しているため、ノード211cの弁別ビット位置231cの値“2”を探索経路スタック310に格納し、弁別ビット位置2に対応するビット値を検索キー“011010”から取り出すと、値は“1”である。ノード211cの代表ノード番号221cに得られたビット値“1”を加算して得られる値221c+1を、探索経路スタック310に格納する。
【0072】
配列番号(221c+1)のノード211dからノード種別261dを取り出すと、ノード211dはリーフノードであることがわかる。そこで、ノード211dからインデックスキー“011010”を取り出し、処理を終了する。
【0073】
このように、順次検索キーのビット情報と各ノードの情報を参照していくリンク処理を実行することにより、探索経路スタック310には、検索開始ノードであるノード210aの配列番号220からリーフノード211dの配列番号(221c+1)までと、ノー210aの弁別ビット位置230aからノード221cの弁別ビット位置231cまでの情報が、リンク順にプッシュされていくことになる。
【0074】
次に、図5A〜図5C、図6により、本発明のカップルドノードツリーにおけるノード挿入処理を説明する。図5A〜図5Cが通常の挿入処理を説明するものであり、図6はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【0075】
図5Aは挿入処理の前段である検索処理の処理フローを示す図であり、図4Aに示した検索処理において挿入キーを検索キーとしたものに相当する。ステップS501は図4AのステップS401で検索開始ノードをルートノードとしたものに相当し、ステップS502〜ステップS510の処理は図4AのステップS402〜ステップS410に完全に対応するので説明は省略する。
【0076】
図5AのステップS511において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図5BのステップS512以下の処理に進む。
【0077】
図5Bは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップS512において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【0078】
ステップS513に進み、挿入キーとステップS510で得たインデックスキーの大小を比較し、挿入キーが大きいときは値1を小さいときは値0のブール値を得る。
ステップS514に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値を加算した配列番号を得る。
【0079】
ステップS515に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値の論理否定値を加算した配列番号を得る。
ステップS514で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップS515で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。
【0080】
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【0081】
例えば図2のカップルドノードツリーに“011011”を挿入する場合、検索結果のインデックスキーはノード211dに格納された“011010”になる。挿入キー“011011”とノード211dに格納されたインデックスキー“011010”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値1が得られ、挿入されるノード対の代表ノード番号に1を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー“011010”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。
【0082】
その際、インデックスキー“011010”と挿入キー“011011”とは5ビット目で異なることから、ノード211dは、弁別ビット位置を5とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【0083】
また図2のカップルドノードツリーに“011001”を挿入しようとする場合も、検索結果のインデックスキーはノード211dに格納された“011010”になる。この場合には挿入キーが小さいのでブール値0が得られ、挿入されるノード対の代表ノード番号に0を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー“011010”と挿入キー“011001”とは4ビット目で異なることから、ノード211dは、弁別ビット位置を4とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【0084】
次に図5CのステップS516以下の処理に進む。
図5Cは図5Bで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
【0085】
ステップS516〜ステップS523までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップS524以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【0086】
ステップS516で、挿入キーとステップS510で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップS517に進み、ステップS516で得た差分ビット列から、上位0ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するCPUではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【0087】
次にステップS518に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップS524に移行し、指していなければステップS519aに進む。
【0088】
ステップS519aにおいて、探索経路スタックのスタックポインタを1つ戻してそこにスタックされている弁別ビット位置を取り出す。
先の出願である上述の特願2006−187827で提案された挿入処理においては、探索経路スタックにスタックされているのは配列番号だけであったため、配列番号を取り出して配列から該配列番号の指す配列要素に格納されたノードから弁別ビット位置を取り出すものであったが、本発明では図5Aに示すステップS506aで探索経路スタックに弁別ビット位置を格納しているので、配列にアクセスすることなく、弁別ビット位置を取り出すことができる。
【0089】
次にステップS522に進み、ステップS519aで取り出した弁別ビット位置がステップS517で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【0090】
ステップS522の判定結果が否定であれば、ステップS518に戻り、ステップS518での判定が肯定になるかステップS522での判定が肯定になるまで繰り返す。ステップS522での判定が肯定になると、ステップS523で探索経路探索スタックのスタックポインタを1つ進め、ステップS524以下の処理に移行する。
【0091】
上記ステップS516〜ステップS523で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の(最上位の)ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。
【0092】
例えば図2のカップルドノードツリーに“111000”を挿入するとき、検索結果のインデックスキーはノード210hに格納された“101011”になる。挿入キー“111000”とノード210hに格納されたインデックスキー“101011”のビット列比較により異なるビット値となる最上位のビット位置1が得られる。得られたビット位置1と探索経路スタックに積まれた配列番号の配列要素に格納されたブランチノードの弁別ビット位置との位置関係を弁別ビット位置が上位になるまでを順次探索経路スタック逆にたどると、ルートノード210aに至る。そこで探索経路スタックのポインタを1つ進め、ノード211bの配列番号を得る。挿入キー“111000”はノード211bのリンク先に挿入される。
【0093】
また、探索経路スタック逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【0094】
次に、ステップS524以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップS524では探索経路スタックからスタックポインタの指す配列番号を取り出す。
ステップS525において、ステップS514で得た配列番号の指す配列要素のノード種別に“1”(リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップS526に進み、配列からステップS524で得た配列番号の配列要素を読み出す。
【0095】
次にステップS527において、ステップS515で得た配列番号の配列要素にステップS526で読み出した内容を書き込む。
最後にステップS528において、ステップS524で得た配列番号の指す配列要素のノード種別に“0”(ブランチノード)を、弁別ビット位置にステップS517で得たビット位置を、代表ノード番号にステップS512で得た配列番号を書き込み、処理を終了する。
【0096】
上述の図2のカップルドノードツリーに“111000”を挿入する例では、取得された空ノード対のノード[0]にノード211bの内容を書き込み(ステップS527)、ノード[1]を挿入キー“111000”を保持するリーフノードとする(ステップS525)。そして、ノード211bの弁別ビット位置にビット列比較により異なるビット値となる最上位のビット位置1を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号が格納される(ステップS528)。
【0097】
図6は、ルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。図6に示すフロー自体は、先の出願である上記特願2006−187827で提案されたノード挿入処理全体を説明する処理フローと同様である。
【0098】
ステップS601において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図5A〜図5Cを用いて説明した通常の挿入処理が行われる。
【0099】
ステップS601での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップS602において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS603において、ステップS602で得た配列番号に0を加えた配列番号を求める。(実際には、ステップS602で取得した配列番号に等しい。)。さらにステップS604において、ステップS603で得た配列番号の配列要素に、挿入するルートノードのノード種別に1(リーフノード)とインデックスキーに挿入キーを書き込み、ステップS605で、ステップS602で取得したルートノードの配列番号を登録して処理を終了する。
【0100】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図6及び図5A〜図5Cの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【0101】
次に図7A、図7Bを参照して、カップルドノードツリーに係るインデックスキーの集合から、特定のインデックスキーを削除する処理フローを説明する。図7A、図7Bに示すフロー自体は、本出願人による出願である上記特願2006−187827で提案された削除処理のフローと同様である。
【0102】
図7Aは、削除処理の前段である検索処理の処理フローを示す図であり、基本的には図4Aに示した検索処理において削除キーを検索キーとしたものに相当するが、図4AのステップS406aの探索経路スタックに弁別ビット位置を格納する処理は、省略されている。もし、削除処理の前段である検索処理の履歴における弁別ビット位置を頻繁に利用するような処理を引き続いて行うのであれば、探索経路スタックに弁別ビット位置を格納する処理を追加すればよい。
【0103】
ステップS701は図4AのステップS401で検索開始ノードをルートノードとしたものに相当し、ステップS702〜ステップS710の処理は図4AのステップS402〜ステップS410に上述の点を除いて完全に対応するので説明は省略する。
【0104】
図7AのステップS711において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図7BのステップS712以下の処理に進む。
【0105】
図7Bは、削除処理の後段の処理フローを説明する図である。
まず、ステップS712で探索経路スタックに2つ以上の配列番号が格納されているか判定する。2つ以上の配列番号が格納されていないということは、言い換えれば1つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップS718に移行し、ステップS701で得たルートノードの配列番号に係るノード対を削除する。次にステップS719に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【0106】
ステップS712において探索経路スタックに2つ以上の配列番号が格納されていると判定されたときはステップS713に進み、ステップS708で得た代表ノード番号にステップS707で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【0107】
次にステップS714において、ステップS713で得た配列番号の配列要素の内容を読み出し、ステップS715において探索経路スタックのスタックポインタを1つ戻して配列番号を取り出す。
【0108】
次にステップS716に進み、ステップS714で読み出した配列要素の内容をステップS715で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
【0109】
最後にステップS717においてステップS708で得た代表ノード番号に係るノード対を削除して処理を終了する。
【0110】
図8は、本発明による、カップルドノードツリー(部分木を含む)に格納されたインデックスキーの最小値を求める処理を示したフローチャートである。図8に示すフローチャートは、本出願人による出願である上記特願2006−293619で提案されたインデックスキーの最小値を求めるフローチャートにおいて、ノードから弁別ビット位置を取り出す処理と探索経路スタックにノードから取り出した弁別ビット位置を格納する処理を追加したものである。インデックスキーの最小値を求める処理は、先に述べたようなインデックスキーのツリー上の配置から、検索開始ノードからノード[0]をリーフノードに至るまでツリー上でたどることに相当する。
【0111】
まず、ステップS801の検索開始ノードの配列番号の取得からステップS805のノード種別の判定までは、それぞれ上述の図4AのステップS401からステップS405の処理と同様である。
【0112】
ステップS805のノード種別の判定においてノード種別がブランチノードと判定されると、ステップS806に進み、ノードから配列の代表ノード番号を取り出す。
次にステップS806aに進み、ノードから弁別ビット位置を取り出し、ステップS806bで、その取り出した弁別ビット位置を探索経路スタックに格納する。
【0113】
次にステップS807で、ステップS806において取り出した代表ノード番号に値“0”を加算してその結果を新たな配列番号とし、ステップS802に戻る。以降、ステップS805においてそのノードがリーフノードと判定されるまでステップS802からステップS807までの処理を繰り返し、ステップS808で、リーフノードからインデックスキーを取り出し、処理を終了する。
【0114】
上記の図8に示す処理においては、ノード[0]をたどるため、代表ノード番号に一律に“0”を加算している。すなわち、図8の処理によれば、リンク先のノードは、ノード対のうち必ずノード[0]とし、より小さい値のインデックスキーが格納されているノードのほうに分岐している。これにより、ツリー構造が先に述べたように順列構成であるカップルドノードツリーの最小のインデックスキーを取り出すことができる。
【0115】
図9は、図8のフローチャートにより示したインデックスキーの最小値を求める処理を、図2に例示したカップルドノードツリーにより説明する図である。図9は、配列番号220のノード210aを検索開始ノードとする場合のリンク経路及び探索経路スタック310の状態を示す。
【0116】
検索開始ノードはノード210aであるから、その配列番号220と弁別ビット位置230aのビット値“0”が探索経路スタック310にプッシュされ、次に代表ノード番号220aにより表されるノード対201bのうちノード[0]であるノード210bにリンクしていき、その代表ノード番号220aと弁別ビット位置230bのビット値“1”が探索経路スタック310に格納され、さらにリーフノード210cに至る。リーフノード210cのインデックスキー“000111”を取り出すと、処理を終了する。
【0117】
以上説明したように、探索経路スタック310には、ノード対のうち、ノード[0]の配列番号とブランチノードの弁別ビット位置が順次格納されていく。
【0118】
図10は、カップルドノードツリー(部分木を含む)に格納されたインデックスキーの最大値を求める処理を示したフローチャートである。図10に示すフローチャートは、本出願人による出願である上記特願2006−293619で提案されたインデックスキーの最大値を求めるフローチャートにおいて、ノードから弁別ビット位置を取り出す処理と探索経路スタックにノードから取り出した弁別ビット位置を格納する処理を追加したものである。
【0119】
インデックスキーの最大値を求める処理は、ツリー上のノードのうちノード[1]について、リーフノードに至るまで順次たどっていくことに相当する。以下、任意の部分木の最大のインデックスキーを求める処理について、上記最小のインデックスキーを求める処理と比較しながら、異なる点を中心に説明する。
【0120】
図10に示す一連の処理のうち、ステップS1001からステップS1006b及びステップS1008については、図8のステップS801からステップS806b及びステップS808にそれぞれ対応しており、同様の処理が実行される。図8の最小値を求める処理と異なる点は、ステップS1007において、代表ノード番号に、値“1”を加算する点である。これにより、代表ノード番号が表すノード対のうち、ノード[1]に常にリンクすることとなり、リーフノードに至るまで順次ステップS1002からステップS1007の処理を繰り返すことにより、インデックスキーの最大値を得ることができる。
【0121】
図11は、図10のフローチャートにより示したインデックスキーの最大値を求める処理を、図2に例示したカップルドノードツリーにより説明する図である。図11に示すように、検索開始ノードを図9の例と同様に配列番号220のノード210aとしている。
【0122】
したがって、検索開始ノードの配列番号は配列番号220であり、探索経路スタック310には配列番号220がスタックされ、配列番号220の配列要素に格納されたノード210aが読み出される。ノード210aのノード種別260aは“0”でありブランチノードであるから、代表ノード番号220aと弁別ビット位置230aを取り出し、探索経路スタック310に弁別ビット位置230aの値“0”を格納する。
【0123】
次に、最大値検索においては常にノード[1]にリンクしていくことから、代表ノード番号220aに値“1”を加算した値をリンク先の配列番号としてノード211bにリンクする。そして配列番号220a+1を探索経路スタック310に格納するとともに、ノード211bを読み出す。
【0124】
ノード211bのノード種別261bは“0” でありブランチノードであるから、代表ノード番号221bと弁別ビット位置231bを取り出し、探索経路スタック310に弁別ビット位置231bの値“2”を格納する。
【0125】
次に、代表ノード番号221bに値“1”を加算した値をリンク先の配列番号としてノード211fにリンクする。そして配列番号221b+1を探索経路スタック310に格納するとともに、ノード211fを読み出す。
【0126】
ノード211fのノード種別261fは“0” でありブランチノードであるから、代表ノード番号221fと弁別ビット位置231fを取り出し、探索経路スタック310に弁別ビット位置231fの値“3”を格納する。
【0127】
次に、代表ノード番号221fに値“1”を加算した値をリンク先の配列番号としてノード211hにリンクする。そして配列番号221f+1を探索経路スタック310に格納するとともに、ノード211hを読み出す。
【0128】
ノード211hのノード種別261hは“1” でありリーフノードであるから、ノード211hからインデックスキー251hの値“101100”を最大値として取り出し、処理を終了する。
【0129】
図4Aから図11に示すように、検索キーと一致するインデックスキーを検索する基本動作やインデックスキーの最小値/最大値の検索処理を実行する際には、探索経路スタック310に参照した配列の配列番号とブランチノードの弁別ビット位置が順次格納されていく。
【0130】
なお、上述の図8及び図10を参照したインデックスキーの最小値/最大値の検索処理では、カップルドノードツリーは配列に記憶されたものとして説明したが、カップルドノードツリーが配列に記憶されることは必須ではなく、ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることによりインデックスキーの最小値/最大値の検索が可能であることは明らかである。
【0131】
次に、カップルドノードツリーの分割/結合方法について説明をする。
本発明でいうカップルドノードツリーの分割とは、あるビット列からなる分割キーを指定したとき、カップルドノードツリーに含まれるインデックスキーをその分割キーとの大小関係により2グループに分け、それぞれのグループに属するインデックスキーからなる2つのカップルドノードツリーを生成することである。
【0132】
大小関係による分割について、以下の説明では、分割キーより大きいグループと分割キー以下のグループに分割するとするが、分割キー以上のグループと分割キーより小さいグループに分割する場合でも、同様に分割/結合が可能であることは、以下の説明から容易に理解されるであろう。
【0133】
要するに、分割キーはカップルドノードツリーをどこで分割するかを決定するために用いられるキーである。
また、カップルドノードツリーの結合とは、2つのインデックスキーの集合に対応する2つカップルドノードツリーから2つのインデックスキーの集合の和集合に対応するカップルドノードツリーを生成することである。本発明では、2つのインデックスキーの集合の積集合は空であることを前提にしている。なお、以下の説明において、カップルドノードツリーを単にツリーということがある。
【0134】
図12は、本発明のカップルドノードツリーの第1の分割処理フローを説明する図である。図12に示すフローのステップ構成は、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例1のフローと同じであるが、ステップの内容については異なるものが存在する。
【0135】
第1の分割処理では、分割対象である処理元のツリー(以下、単に処理元ということがある。)のインデックスキーの最小値を取り出し、取り出したインデックスキーの最小値を、処理元の分割により生成される処理先のツリー(以下、単に処理先ということがある。)に挿入し、処理元のツリーからインデックスキーの最小値を削除する処理を、最小値が分割キー以下である間繰り返すことにより、分割対象である処理元のツリーから処理先のツリーを分割する。
【0136】
最初のステップS1201で指定された分割キーを処理元の分割キーとして設定する。分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。
【0137】
次にステップS1202で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップS1203に進む。
ステップS1203では、処理元のツリーが登録済みか判定する。この判定結果が登録済みではないというのは処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものであり、その場合には処理を終了する。
【0138】
処理元のツリーが登録済みであればステップS1204に移行し、ステップS1202で検索開始ノードとして設定したルートノードより、図8に示す処理を実行してインデックスキーの最小値を得る。このとき、先に説明したように、探索経路スタックには配列番号とともに弁別ビット位置が格納される。
【0139】
次にステップS1205に進み、ステップS1204で得た最小値が分割キーより大きいか判定する。最小値が分割キーより大きければ、ツリーの分割が完成しているのであるから処理を終了し、大きくなければ、以下で説明するステップS1206〜ステップS1209の処理先のツリーの生成と処理元のツリーからのノードの削除処理を実行し、ステップS1203へ戻る。
【0140】
ステップS1206では、ステップS1204で得られた最小値を処理先の挿入キーに設定する。
次にステップS1207で、図5A〜図5C、図6に示すツリーの生成、挿入処理により、挿入キーによる処理先のツリーの生成を実行する。
【0141】
本発明のカップルドノードツリーの第1の分割処理における生成、挿入処理は、先の最小値検索処理において探索経路スタックに格納された弁別ビット位置を参照することができるので、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例1よりも処理を速くすることができる。
【0142】
続いてステップS1208で、ステップS1207における挿入キーを処理元の削除キーに設定し、ステップS1209において、図7A、図7Bに示す削除処理により、処理元のツリーから削除キーを含むリーフノードを削除する。
【0143】
上記分割処理の説明では、処理元のインデックスキーの最小値から順に削除を行うようにしたが、同様にインデックスキーの最大値から順に削除を行うことができることは、当業者に明らかである。その場合、ステップS1205はインデックスキーの最大値を求める処理になり、ステップS1205は最大値と分割キーの大小関係の判定処理となり、ステップS1206では最大値を処理先の挿入キーに設定することになる。
【0144】
以上、分割処理について説明したが、結合処理も図12に示す処理フローにより実行できる。
結合処理は、結合しようとする2つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上とすれば、先に述べた例外的な処理に該当し、処理元のツリーは削除され、処理先のツリーに結合される。なお、処理元のツリーのインデックスキーの最大値が未知の場合には、前もって図10に示す最大値検索処理により分割キーを求めることになる。
【0145】
そして、処理元の分割キーを処理元のツリーのインデックスキーの最大値以上とするのであるから、ステップS1205の大小比較では、分割キーが最小値より常に大きくステップS1206へ分岐するのでステップS1205を省略することができる。そうであれば、分割キーを設定する意味もないことから、結局ステップS1202も不要になり、ただ単に最小値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができる。
【0146】
また、分割処理について述べたように、最大値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができることも明らかである。
【0147】
図13は、本発明のカップルドノードツリーの第2の分割処理フローを説明する図である。図13に示すフローのステップ構成は、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例2のフローと同じであるが、ステップの内容については異なるものが存在する。
【0148】
第2の分割処理は、インデックスキー単位で挿入削除を行う点では第1の分割処理と同様であるが、挿入削除すべきインデックスキーの探索に探索経路スタックを活用し、挿入処理及び削除処理の実行時の処理ステップ数を小さくしたものである。
【0149】
図13のステップS1301からステップS1306までの処理は、図12に示す第1の分割処理のステップS1201からステップS1206までの処理とまったく同じであるから、説明を省略する。なお、ステップS1304の最小値検索処理において、探索経路スタックには配列番号とともに弁別ビット位置が格納されることも、ステップS1204における最小値検索と同様である。
【0150】
ステップS1307において、挿入キーにより、処理先にノードを挿入する。この処理は、図12に示すステップS1207の挿入処理とは異なる第2の分割処理特有のものであり、後に図14、図15A、図15Bを参照して詳細に説明する。
【0151】
次にステップS1308においてステップS1304で得た最小値を含むノードを、処理元の削除ノードとして設定し、ステップS1309において処理元から削除ノードを削除し、削除ノードと対をなすノードの内容が複写される処理元の親ノードを得る。
続いてステップS1310で、ステップS1309で得られた処理元の親ノードを、処理元の検索開始ノードに設定し、ステップS1303に戻る。
【0152】
後に説明するように、処理元の親ノードは削除ノードの直近上位のブランチノードである。削除ノードは処理元のインデックスキーの最小値を含むものであり、先に述べたインデックスキーの順序性から、次に検索する最小値は処理元の親ノードの下位にある。
したがって、2回目以降のステップS1304での最小値検索の検索開始ノードはルートノードとしないで処理元の親ノードとすることにより、処理ステップ数を低減することができる。
ステップS1308〜ステップS1309及び処理元の親ノードについては、後に図16を参照して詳細に説明する。
【0153】
図14は、図13に示すステップS1306とステップS1307に対応するノードの挿入処理フローを説明する図である。
【0154】
最初のステップS1401における挿入キーを処理先の挿入キーとして設定するステップは、図13に示すステップS1306に対応する処理であり、図13に示すステップS1304で得られた最小値を処理先の挿入キー設定エリアに設定する
【0155】
。
次にステップS1402において、処理先が登録済みか判定する。
登録済みでなければステップS1403に移行し、ステップS1403において、挿入キーを含むノード対を処理先のルートノードに設定し、処理先のルートノードとして登録する。続いてステップS1404に進み、処理先のルートノードを挿入済みノードとして設定して処理を終了する。
【0156】
上記ステップS1402での判定結果が登録済みであれば、ステップS1405に移行する。ステップS1405では、挿入済みノードが設定済みであるか判定する。この判定処理は、後に説明するツリーの結合処理で必要になるものである。ツリーの分割処理では、最初の挿入処理においてステップS1404でルートノードを挿入済みノードとして設定することから、ステップS1406の判定は常に「はい」である。したがって、分割処理だけのためであれば、ステップS1405とステップS1407は必須ではない。
【0157】
ステップS1405での判定結果が「はい」であればステップS1406に進み、挿入済みノードとして設定されているノードを処理先の検索開始ノードとして設定し、ステップS1408に進む。
ステップS1405での判定結果が「いいえ」であればステップS1407に進み、ルートノードを処理先の検索開始ノードとして設定し、ステップS1408に進む。
【0158】
ステップS1408では、図10に示す最大値検索処理により、ステップS1406あるいはステップS1407で設定された検索開始ノードから処理先のインデックスキーの最大値を求める。このとき、先に説明したように、探索経路スタックには配列番号とともに弁別ビット位置が格納される。
【0159】
次にステップS1409において、ステップS1401で設定された挿入キーとステップS1407で得られた最大値により、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する。
【0160】
続いてステップS1410に進み、ステップS1409において挿入キーを含むノード対を挿入された処理先の親ノードを挿入済みノードとして設定し、処理を終了する。
次に、上述のステップS1403とステップS1409について詳細に説明する。
【0161】
図15Aは、図14に示すステップS1403のルートノード設定処理を説明するフロー図である。
【0162】
まず、ステップS1501で配列からノード対が空の代表ノード番号を取得する。
次にステップS1502において、ステップS1501で取得した代表ノード番号に値“0”を加えて得た配列番号を、挿入ノードの配列番号として設定しておく。
【0163】
ステップS1503に進み、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップS1502で設定した配列番号の配列要素に格納する。
次にステップS1504において、挿入ノードの配列番号をルートノードの配列番号として登録して処理を終了する。
【0164】
なお、上記ステップS1501〜ステップS1504の処理は、図6を参照して説明したカップルドノードツリーの生成処理において、ルートノードの配列番号が登録済みでない場合の、ステップS602〜ステップS605に対応するものである。
【0165】
図15Bは、図14に示すステップS1409の、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する処理を説明するフロー図である。図15Bに示すフローは、先に図5Cを参照して示した挿入処理の応用であり、ステップS1505の、挿入キーと最大値をビット列として比較して上位0ビット目から見た最初の不一致ビットの位置を求め、それを、差分ビット位置を格納するエリアに設定する処理は、図5Cに示すステップS516とステップS517の処理に対応する。
【0166】
ステップS1505に続いてステップS1506aに進む。なお、ステップS1506a〜ステップS1512の処理ブロックは図5Cに示すステップS519a〜ステップS523からなる処理ブロックに相当し、ステップS1513〜ステップS1518の処理は図5Cに示すステップS524〜ステップS528に相当する。
【0167】
ステップS1506aにおいて、先の図14に示すステップS1408の最大値検索処理における処理先の探索経路スタックのスタックポインタを1つ戻して、弁別ビット位置を取り出す。
【0168】
次に、ステップS1509において、ステップS1505で設定した差分ビット位置とステップS1506aで取り出した弁別ビット位置を比較し、弁別ビット位置が差分ビット位置より上位の位置関係か判定する。
【0169】
その判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係であれば、ステップS1512に進み、処理先の探索経路スタックのスタックポインタを1つ戻して配列番号を取り出し、それを親ノードの配列番号エリアに設定してステップS1513に移行する。
【0170】
ステップS1509での判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係でなければ、ステップS1510に進む。
ステップS1510では、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。
【0171】
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合には、ステップS1506に戻る。
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指している場合には、ステップS1511において処理先の探索経路スタックからスタックポインタの指す配列番号を取り出し、処理先の親ノードの配列番号を格納するエリアに設定してステップS1513に移行する。
【0172】
以上説明したステップS1506a〜ステップS1512の処理においては、先の最大値検索処理において探索経路スタックに格納された弁別ビット位置を参照することができるので、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例2よりも処理を速くすることができる。
【0173】
ステップS1513においては、配列からノード対が空きの代表ノード番号を取得する。
次にステップS1514において、代表ノード番号に1を加えて得た配列番号を挿入ノードの配列番号を格納するエリアに設定する。
【0174】
次にステップS1515において、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップS1514で設定した配列番号の配列要素に格納する。
【0175】
次にステップS1516において、代表ノード番号に0を加えて得た配列番号を、挿入ノードと対をなす対ノードの配列番号を格納するエリアに設定する。
次にステップS1517において、ステップS1511あるいはステップS1512で設定した処理先の親ノードの配列番号の指す配列要素の内容を読み出し、ステップS1516で設定した対ノードの配列番号の指す配列要素に格納する。
【0176】
次にステップS1518において、ブランチノードを形成するため、ノード種別にブランチを、弁別ビット位置にステップS1505で設定した差分ビット位置を、代表ノード番号にステップS1516で設定した対ノードの配列番号を設定し、ステップS1511あるいはステップS1512で設定した処理先の親ノードの配列番号の指す配列要素に格納して処理を終了する。
【0177】
図16は、図13に示す処理フローにおける削除処理について説明する処理フロー例を示す図である。
最初のステップであるステップS1601は、図13に示すステップS1308に相当するものである。削除ノードに含まれる削除キーは図13に示すステップS1304において最小値検索により求められたものであるから、処理元の探索経路スタックには削除キーの格納された配列要素の配列番号がスタックされているので、その配列番号により削除ノードを読み出して削除ノードを格納するエリアに設定する。
【0178】
次のステップS1602では、処理元の探索経路スタックに2つ以上の配列番号が格納されているか判定される。このステップS1602以降、ステップS1608に至る処理は、図7Bに示す削除処理の後段の処理に対応するものである。
【0179】
処理元の探索経路スタックに2つ以上の配列番号が格納されていなければ、ステップS1607に移行し、ステップS1601で設定した削除ノードの配列番号の指すノード対を削除し、ステップS1608に進み、ルートノードの配列番号を削除して処理を終了する。
【0180】
処理元の探索経路スタックに2つ以上の配列番号が格納されていれば、ステップS1603に進み、削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号を格納するエリアに設定する。
【0181】
次にステップS1604において、処理先の探索経路スタックのスタックポインタを1つ戻して配列番号を取り出し、削除ノードの直近上位のブランチノードである処理元の親ノードの配列番号格納エリアに設定する。
【0182】
次にステップS1605において、ステップS1603で設定した対ノードの配列番号の指す配列要素の内容を読出し、ステップS1604で設定した処理元の親ノードの配列番号の指す配列要素に格納する。
次にステップS1606において、削除ノードの代表ノード番号の指すノード対を削除して処理を終了する。
【0183】
以上、第2の分割処理について説明したが、第2の分割処理においても、第1の分割処理の場合と同様にインデックスキーの最大値から順に削除を行うことができる。
また、第1の分割処理の場合と同様に分割処理の処理フローをツリーの結合処理に用いることが可能である。結合しようとする2つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上あるいは最小値以下として処理元のツリーの削除処理を行い、削除されたノードを処理先のツリーに挿入する処理を行えばよい。
【符号の説明】
【0184】
10、20、30 配列番号
100 配列
101 ノード
102 ノード種別
103 弁別ビット位置
104 代表ノード番号
111 ノード対
112 ノード[0]、代表ノード
113 ノード[1]、代表ノードと対をなすノード
118 インデックスキー
301 データ処理装置
302 中央処理装置
303 キャッシュメモリ
304 バス
305 主記憶装置
306 外部記憶装置
307 通信装置
308 データ格納装置
309 配列
310 探索経路スタック
【技術分野】
【0001】
本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する検索方法に関するものであり、特に本出願人が特願2006−187827及び特願2006−3199407において提案したカップルドノードツリーの分割/結合方法及びプログラムに関するものである。
【背景技術】
【0002】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【0003】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【0004】
図17は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【0005】
図17の例では、インデックスキー“100010”を保持するノード1750aがルートノードとなっており、その検査ビット位置1730aは0である。ノード1750aの左リンク1740aにはノード1750bが接続され、右リンク1741aにはノード1750fが接続されている。
【0006】
ノード1750bの保持するインデックスキーは“010011”であり、検査ビット位置1730bは1である。ノード1750bの左リンク1740bにはノード1750cが、右リンク1741bにはノード1750dが接続されている。ノード1750cが保持するインデックスキーは“000111”、検査ビット位置1730cは3である。ノード1750dが保持するインデックスキーは“011010”、検査ビット位置1730dは2である。
【0007】
ノード1750cから実線で接続された部分はノード1750cの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ1740cは、その欄が空欄であることを示している。点線の接続された右ポインタ1741cの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード1750cを右ポインタ1741cが指定していることを表している。
【0008】
ノード1750dの右ポインタ1741dはノード1750d自身を指しており、左リンク1740dにはノード1750eが接続されている。ノード1750eの保持するインデックスキーは“010010”、検査ビット位置1730eは5である。ノード1750eの左ポインタ1740eはノード1750bを、右ポインタ1741eはノード1750eを指している。
【0009】
また、ノード1750fの保持するインデックスキーは“101011”であり、検査ビット位置1730fは2である。ノード1750fの左リンク1740fにはノード1750gが、右リンク1741fにはノード1750hが接続されている。
【0010】
ノード1750gの保持するインデックスキーは“100011”であり、検査ビット位置1730gは5である。ノード1750gの左ポインタ1740gはノード1750aを、右ポインタ1741gはノード1750gを指している。
【0011】
ノード1750hの保持するインデックスキーは“101100”であり、検査ビット位置1730hは3である。ノード1750hの左ポインタ1740hはノード1750fを、右ポインタ1741hはノード1750hを指している。
【0012】
図17の例では、ルートノード1750aからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が1であるか0であるか判定を行い、1であれば右リンクをたどり、0であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば(図17において点線で示されたこの逆戻りのリンクをバックリンクという)、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【0013】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は1回ですむことなどのメリットがあるが、各ノードからの2つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【0014】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献1に開示された技術がある。下記特許文献1に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【0015】
しかしながら、下記特許文献1に開示されたものにおいても、1つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを1つとしたため、例えば図17に示したパトリシアツリーの最下段の部分である左ポインタ1740c、右ポインタ1741h等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【0016】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願2006−187827において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが1つのときはリーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を提案した。
【0017】
上記出願においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。
【0018】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願2006−293619において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの最大値/最小値を求める手法等を提案した。
【0019】
さらに、本出願人は、特願2006−319407において、カップルドノードツリーの分割/結合手法を提案した。
上記3つの出願において提案した検索手法は、検索開始ノードから順次ブランチノードをたどってリーフノードに至り、リーフノードに格納されたインデックスキーを求める操作を基本とするものであり、検索履歴として検索開始ノードからリーフノードに至るノードの配置された記憶領域のアドレス情報として該ノードの格納されている配列要素の配列番号をスタックに格納している。そして、検索処理後の各種処理において、スタックに格納されたアドレス情報を基にそのアドレス情報が示す記憶領域に格納されたノードを参照して弁別ビット位置を取り出すことが行われている。
【0020】
上記アドレス情報としては、カップルドノードツリーを配列に格納する場合にはその配列での配列番号を用いることができ、アドレス情報を表すビット量を削減することができるが、カップルドノードツリーの規模が大きくなるとそれに伴ってノードが実際に格納されるアドレス範囲が大きくなり、各種処理をコンピュータ上で実行するときにキャッシュミスを起こす可能性が高くなり、処理効率が低下するおそれがある。
【先行技術文献】
【特許文献】
【0021】
【特許文献1】特開2001−357070号公報
【発明の概要】
【発明が解決しようとする課題】
【0022】
そこで本発明の目的は、カップルドノードツリーの規模が大きくなっても、カップルドノードツリーを利用した処理の効率が低下することを少なくする手法を提供することである。
【課題を解決するための手段】
【0023】
本発明によれば、カップルドノードツリーの分割/結合処理で用いる基本検索や最大値あるいは最小値検索の検索処理において、検索履歴を格納する探索経路スタックにノードの配置された記憶領域のアドレス情報のみならず検索経路でたどったブランチノードの弁別ビット位置を格納する。
【0024】
そして、検索処理でたどったブランチノードの弁別ビット位置を探索するカップルドノードツリーの分割/結合処理においては、探索経路スタックから弁別ビット位置を取り出す。
【発明の効果】
【0025】
本発明によれば、検索処理でたどったノードの弁別ビット位置が必要なときは、その情報を、検索履歴を格納する探索経路スタックから得ることができ、カップルドノードツリーの規模が大きくなったとしても、キャッシュミスが発生する可能性を小さくすることができる。
【図面の簡単な説明】
【0026】
【図1】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図2】カップルドノードツリーのツリー構造を概念的に示す図である。
【図3】本発明を実施するためのハードウェア構成例を説明する図である。
【図4A】本発明におけるビット列検索の基本動作を示すフロー図である。
【図4B】本発明におけるビット列検索の基本動作をカップルドノードツリーにより説明する図である。
【図5A】本発明における挿入処理の前段である検索処理の処理フローを示す図である。
【図5B】挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
【図5C】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。
【図6】本発明におけるルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【図7A】削除処理の前段である検索処理の処理フローを示す図である。
【図7B】削除処理の後段の処理フローを説明する図である。
【図8】本発明のカップルドノードツリーに格納されたインデックスキーの最小値を求める処理を示すフロー図である。
【図9】本発明のインデックスキーの最小値を求める処理をカップルドノードツリーにより説明する図である
【図10】本発明のカップルドノードツリーに格納されたインデックスキーの最大値を求める処理を示すフローチャートである。
【図11】本発明のインデックスキーの最大値を求める処理をカップルドノードツリーにより説明する図である。
【図12】カップルドノードツリーの第1の分割処理フローを説明する図である。
【図13】カップルドノードツリーの第2の分割処理フローを説明する図である。
【図14】第2の分割処理におけるノードの挿入処理フローを説明する図である。
【図15A】第2の分割処理におけるルートノード設定処理を説明するフロー図である。
【図15B】第2の分割処理における親ノードに挿入キーを含むノード対を挿入する処理フローを説明する図である。
【図16】第2の分割処理における削除処理を説明するフロー図である。
【図17】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【発明を実施するための形態】
【0027】
最初に、本出願人により先の上記出願において提案された、本発明の前提となるカップルドノードツリーについて、カップルドノードツリーを配列に格納する例を説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【0028】
図1は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図1を参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード種別102、弁別ビット位置103及び代表ノード番号104で構成されている。ノード種別102は0であり、ノード101がブランチノードであることを示している。弁別ビット位置103には1が格納されている。代表ノード番号104にはリンク先のノード対の代表ノードの配列番号20が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【0029】
配列番号20の配列要素には、ノード対111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1)に代表ノードと対になるノード[1]113が格納されている。ノード[0]112のノード種別114には0が、弁別ビット位置115には3が、代表ノード番号116には30が格納されている。またノード[1]113のノード種別117には1が格納されており、ノード[1]113がリーフノードであることを示している。インデックスキー118には、“0001”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
【0030】
なお、代表ノードをノード[0]で表し、それと対になるノードをノード[1]で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
【0031】
配列番号30及び31の配列要素に格納されたノード122とノード123からなるノード対121の内容は省略されている。
ノード[0]112、ノード[1]113、ノード122、及びノード123の格納された配列要素にそれぞれ付された0あるいは1は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である0か1を代表ノード番号に加えた配列番号のノードにリンクする。
【0032】
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【0033】
図2は、カップルドノードツリーのツリー構造を概念的に示す図である。図示の6ビットのインデックスキーは、図17に例示されたパトリシアツリーのものと同じである。
符号210aで示すのがルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード対201aの代表ノードとしている。
【0034】
ツリー構造としては、ルートノード210aの下にノート対201bが、その下層にノード対201cとノード対201fが配置され、ノード対201fの下層にはノード対201hとノード対201gが配置されている。ノード対201cの下にはノード対201dが、さらにその下にはノード対201eが配置されている。
【0035】
各ノードの前に付された0あるいは1の符号は、図1において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【0036】
図示された例では、ルートノード210aのノード種別260aは0でブランチノードであることを示し、弁別ビット位置230aは0を示している。代表ノード番号は220aであり、それはノード対201bの代表ノード210bの格納された配列要素の配列番号である。
【0037】
ノード対201bはノード210bと211bで構成され、それらのノード種別260b、261bはともに0であり、ブランチノードであることを示している。ノード210bの弁別ビット位置230bには1が格納され、リンク先の代表ノード番号にはノード対201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。
【0038】
ノード210cのノード種別260cには1が格納されているので、このノードはリーフノードであり、したがって、インデックスキー250cを含んでいる。インデックスキー250cには“000111”が格納されている。一方ノード211cのノード種別261cは0、弁別ビット位置231cは2であり、代表ノード番号にはノード対201dの代表ノード210dの格納された配列要素の配列番号221cが格納されている。
【0039】
ノード210dのノード種別260dは0、弁別ビット位置230dは5であり、代表ノード番号にはノード対201eの代表ノード210eの格納された配列要素の配列番号220dが格納されている。ノード210dと対になるノード211dのノード種別261dは1であり、インデックスキー251dには“011010”が格納されている。
【0040】
ノード対201eのノード210e、211eのノード種別260e、261eはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250e、251eにはインデックスキーとして“010010”と“010011”が格納されている。
【0041】
ノード対201bのもう一方のノードであるノード211bの弁別ビット位置231bには2が格納され、リンク先の代表ノード番号にはノード対201fの代表ノード210fの格納された配列要素の配列番号221bが格納されている。
【0042】
ノード対201fのノード210f、211fのノード種別260f、261fはともに0であり双方ともブランチノードである。それぞれの弁別ビット位置230f、231fには5、3が格納されている。ノード210fの代表ノード番号にはノード対201gの代表ノード210gの格納された配列要素の配列番号220fが格納され、ノード211fの代表ノード番号にはノード対201hの代表ノードであるノード[0]210hの格納された配列要素の配列番号221fが格納されている。
【0043】
ノード対201gのノード210g、211gのノード種別260g、261gはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250g、251gには“100010”と“100011”が格納されている。
【0044】
また同じくノード対201hの代表ノードであるノード[0]210hとそれと対をなすノード[1]211hのノード種別260h、261hはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250h、251hには“101011”と“101100”が格納されている。
【0045】
以下、上述のツリーからインデックスキー“100010”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から0、1、2、・・・とする。
まず、ビット列“100010”を検索キーとしてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは0であるので、検索キー“100010”の弁別ビット位置が0のビット値をみると1である。そこで代表ノード番号の格納された配列番号220aに1を加えた配列番号の配列要素に格納されたノード211bにリンクする。ノード211bの弁別ビット位置231bには2が格納されているので、検索キー“100010”の弁別ビット位置が2のビット値をみると0であるから、代表ノード番号の格納された配列番号221bの配列要素に格納されたノード210fにリンクする。
【0046】
ノード210fの弁別ビット位置230fには5が格納されているので、検索キー“100010”の弁別ビット位置が5のビット値をみると0であるから、代表ノード番号の格納された配列番号220fの配列要素に格納されたノード210gにリンクする。
【0047】
ノード210gのノード種別260gは1でありリーフノードであることを示しているので、インデックスキー250gを読み出して検索キーと比較すると両方とも“100010”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【0048】
次に、図2を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図2の例で、ルートノード210aの弁別ビット位置が0であるのは、図2に例示されたインデックスキーに0ビット目が0のものと1のものがあるからである。0ビット目が0のインデックスキーのグループはノード210bの下に分類され、0ビット目が1のインデックスキーのグループはノード211bの下に分類されている。
【0049】
ノード211bの弁別ビット位置が2であるのは、ノード211h、210h、211g、210gに格納された0ビット目が1のインデックスキーの1ビット目がすべて0で等しく、2ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
【0050】
以下0ビット目の場合と同様に、2ビット目が1であるものはノード211f側に分類され、2ビット目が0であるものはノード210f側に分類される。
そして2ビット目が1であるインデックスキーは3ビット目の異なるものがあるのでノード211fの弁別ビット位置には3が格納され、2ビット目が0であるインデックスキーでは3ビット目も4ビット目も等しく5ビット目で異なるのでノード210fの弁別ビット位置には5が格納される。
【0051】
ノード211fのリンク先においては、3ビット目が1のものと0のものがそれぞれ1つしかないことから、ノード210h、211hはリーフノードとなり、それぞれインデックスキー250hと251hに“101011”と“101100”が格納されている。
【0052】
仮にインデックスキーの集合に“101100”の代わりに“101101”か“101110”が含まれていたとしても、3ビット目までは“101100”と等しいので、ノード211hに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“101100”に加えて“101101”が含まれていると、ノード211hはブランチノードとなり、その弁別ビット位置は5になる。追加されるインデックスキーが“101110”であれば、弁別ビット位置は4となる。
【0053】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“1”のノードとビット値が“0”のノードとに分岐していることから、ノード[1]側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード211hのインデックスキー251hの“101100”、ノード210hのインデックスキー250hの“101011”、・・・、ノード210cのインデックスキー250cの“000111”となり降順にソートされている。
【0054】
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“101100”であればノード211hに到達することができる。また、上記説明からも想像がつくように、“101101”か“101110”を検索キーとした場合でもノード211hにたどり着き、インデックスキー251hと比較することにより検索が失敗したことが分かる。
【0055】
また、例えば“100100”で検索した場合でも、ノード210a、211b、210fのリンク経路では検索キーの3ビット目と4ビット目は使われることがなく、“100100”の5ビット目が0なので、“100010”で検索した場合と同様にノード210gに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【0056】
図3は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施される。データ格納装置308は、カップルドノードツリーが配置される配列309と検索中にたどるノードが格納された配列要素の配列番号のほかノード内の情報を記憶する探索経路スタック310を有する。このデータ格納装置308は主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。
【0057】
図3の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできるし、探索経路スタック310を中央処理装置302内のハードウェアとして実現することも可能である。あるいは、配列309は外部記憶装置306に、探索経路スタック310を主記憶装置305に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【0058】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
次に、上述の出願において本出願人により提案された、カップルドノードツリーを用いた基本的な検索処理、カップルドノードツリーにおける挿入削除処理、カップルドノードツリーに含まれるインデックスキーの最大値/最小値を求める処理等の応用処理、及びカップルドノードツリーの分割/結合処理において、検索履歴を格納するスタックに、ノードの配置された記憶領域のアドレス情報のみならず各種処理で用いるブランチノードの弁別ビット位置を格納し、それを利用する本発明を説明する。
【0059】
図4Aは、本発明のビット列検索の基本動作を示すフローチャートである。図4Aに示すフローチャートは、本出願人による出願である上記特願2006−293619で提案されたビット列検索の基本動作を示すフローチャートにおいて、探索経路スタック310に弁別ビット位置を格納するステップS406aの処理を追加したものである。
【0060】
まず、ステップS401で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列要素は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後に説明する各種応用検索において行われる。
【0061】
次に、ステップS402で、探索経路スタック310に取得された配列番号を格納し、ステップS403で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップS404で、読み出したノードから、ノード種別を取り出し、ステップS405で、ノード種別がブランチノードであるか否かを判定する。
【0062】
ステップS405の判定において、読み出したノードがブランチノードである場合は、ステップS406に進み、ノードから弁別ビット位置についての情報を取り出す。
次にステップS406aで、ステップS406で取り出した弁別ビット位置を探索経路スタック310に格納するとともに、ステップS407で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップS408で、ノードから代表ノード番号を取り出して、ステップS409で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号を得て、ステップS402に戻る。
【0063】
以降、ステップS405の判定においてリーフノードと判定されてステップS410に進むまで、ステップS402からステップS409までの処理を繰り返す。ステップS410で、リーフノードからインデックスキーを取り出して、処理を終了する。
【0064】
図4Bは、図4Aのフローチャートにより示した本実施形態に係るビット列検索の基本動作を、図2に例示したカップルドノードツリーにより説明する図である。
図4Bにおいては、カップルドノードツリー、検索キー設定エリア270及び探索経路スタック310が示されている。以下、図4Bを用いてカップルドノードツリー上の参照されるノード及び探索経路スタック310の状態について説明する。
【0065】
なお、図4Bにおいては、図2に示すカップルドノードツリーのうち、図4Aの処理を説明するために必要な一部分のみを示し、残りのノード(代表ノード番号221b以下のノード)については省略している。以降の説明においてカップルドノードツリー上の参照されるノードを説明するための図面についても同様である。
【0066】
まず、検索を開始するノードの配列番号として、配列番号220が設定されたとする。このとき、対応する配列番号220が探索経路スタック310にプッシュされると共に、配列要素の各種情報が参照される。
【0067】
配列に格納された情報に基づいて、配列番号220のノードがブランチノードであってインデックスキーが格納されていないと認識されると、さらにその配列番号220の配列に格納されている情報(代表ノード番号や弁別ビット位置)等を参照して、次に参照すべき配列番号が算出される。
【0068】
ここでは、まず配列番号220を探索経路スタック310に格納し、配列番号220のノード210aからノード種別260aを取り出す。取り出したノード種別260aは図示のとおり“0”であってノード210aがブランチノードであることを示しているため、ノード210aから弁別ビット位置230aの値“0”を取り出し、探索経路スタック310に配列番号220とともに格納する。
【0069】
さらに、検索キー設定エリア270の検索キー“011010”における弁別ビット位置0のビット値“0”を取り出す。そして、ノード210aに格納されている代表ノード番号220aの値を取り出して、先に検索キーの弁別ビット位置から取り出したビット値“0”を加算して得られた配列番号220aを探索経路スタック310に格納する。
【0070】
続いて、配列番号220aのノードからノード種別260bを読み出すと、配列番号220aのノード210bはブランチノードであることが判定され、ノード210bの弁別ビット位置230bの値“1”を探索経路スタック310に格納し、弁別ビット位置1に対応するビット値を検索キー“011010”から取り出すと、値は“1”である。そこで、ノード210bの代表ノード番号220bに得られたビット値“1”を加算して、探索経路スタック310に220b+1を格納する。
【0071】
配列番号(220b+1)のノード211cから読み出したノード種別261cはブランチノードを示しているため、ノード211cの弁別ビット位置231cの値“2”を探索経路スタック310に格納し、弁別ビット位置2に対応するビット値を検索キー“011010”から取り出すと、値は“1”である。ノード211cの代表ノード番号221cに得られたビット値“1”を加算して得られる値221c+1を、探索経路スタック310に格納する。
【0072】
配列番号(221c+1)のノード211dからノード種別261dを取り出すと、ノード211dはリーフノードであることがわかる。そこで、ノード211dからインデックスキー“011010”を取り出し、処理を終了する。
【0073】
このように、順次検索キーのビット情報と各ノードの情報を参照していくリンク処理を実行することにより、探索経路スタック310には、検索開始ノードであるノード210aの配列番号220からリーフノード211dの配列番号(221c+1)までと、ノー210aの弁別ビット位置230aからノード221cの弁別ビット位置231cまでの情報が、リンク順にプッシュされていくことになる。
【0074】
次に、図5A〜図5C、図6により、本発明のカップルドノードツリーにおけるノード挿入処理を説明する。図5A〜図5Cが通常の挿入処理を説明するものであり、図6はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【0075】
図5Aは挿入処理の前段である検索処理の処理フローを示す図であり、図4Aに示した検索処理において挿入キーを検索キーとしたものに相当する。ステップS501は図4AのステップS401で検索開始ノードをルートノードとしたものに相当し、ステップS502〜ステップS510の処理は図4AのステップS402〜ステップS410に完全に対応するので説明は省略する。
【0076】
図5AのステップS511において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図5BのステップS512以下の処理に進む。
【0077】
図5Bは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップS512において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【0078】
ステップS513に進み、挿入キーとステップS510で得たインデックスキーの大小を比較し、挿入キーが大きいときは値1を小さいときは値0のブール値を得る。
ステップS514に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値を加算した配列番号を得る。
【0079】
ステップS515に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値の論理否定値を加算した配列番号を得る。
ステップS514で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップS515で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。
【0080】
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【0081】
例えば図2のカップルドノードツリーに“011011”を挿入する場合、検索結果のインデックスキーはノード211dに格納された“011010”になる。挿入キー“011011”とノード211dに格納されたインデックスキー“011010”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値1が得られ、挿入されるノード対の代表ノード番号に1を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー“011010”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。
【0082】
その際、インデックスキー“011010”と挿入キー“011011”とは5ビット目で異なることから、ノード211dは、弁別ビット位置を5とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【0083】
また図2のカップルドノードツリーに“011001”を挿入しようとする場合も、検索結果のインデックスキーはノード211dに格納された“011010”になる。この場合には挿入キーが小さいのでブール値0が得られ、挿入されるノード対の代表ノード番号に0を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー“011010”と挿入キー“011001”とは4ビット目で異なることから、ノード211dは、弁別ビット位置を4とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【0084】
次に図5CのステップS516以下の処理に進む。
図5Cは図5Bで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
【0085】
ステップS516〜ステップS523までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップS524以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【0086】
ステップS516で、挿入キーとステップS510で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップS517に進み、ステップS516で得た差分ビット列から、上位0ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するCPUではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【0087】
次にステップS518に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップS524に移行し、指していなければステップS519aに進む。
【0088】
ステップS519aにおいて、探索経路スタックのスタックポインタを1つ戻してそこにスタックされている弁別ビット位置を取り出す。
先の出願である上述の特願2006−187827で提案された挿入処理においては、探索経路スタックにスタックされているのは配列番号だけであったため、配列番号を取り出して配列から該配列番号の指す配列要素に格納されたノードから弁別ビット位置を取り出すものであったが、本発明では図5Aに示すステップS506aで探索経路スタックに弁別ビット位置を格納しているので、配列にアクセスすることなく、弁別ビット位置を取り出すことができる。
【0089】
次にステップS522に進み、ステップS519aで取り出した弁別ビット位置がステップS517で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【0090】
ステップS522の判定結果が否定であれば、ステップS518に戻り、ステップS518での判定が肯定になるかステップS522での判定が肯定になるまで繰り返す。ステップS522での判定が肯定になると、ステップS523で探索経路探索スタックのスタックポインタを1つ進め、ステップS524以下の処理に移行する。
【0091】
上記ステップS516〜ステップS523で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の(最上位の)ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。
【0092】
例えば図2のカップルドノードツリーに“111000”を挿入するとき、検索結果のインデックスキーはノード210hに格納された“101011”になる。挿入キー“111000”とノード210hに格納されたインデックスキー“101011”のビット列比較により異なるビット値となる最上位のビット位置1が得られる。得られたビット位置1と探索経路スタックに積まれた配列番号の配列要素に格納されたブランチノードの弁別ビット位置との位置関係を弁別ビット位置が上位になるまでを順次探索経路スタック逆にたどると、ルートノード210aに至る。そこで探索経路スタックのポインタを1つ進め、ノード211bの配列番号を得る。挿入キー“111000”はノード211bのリンク先に挿入される。
【0093】
また、探索経路スタック逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【0094】
次に、ステップS524以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップS524では探索経路スタックからスタックポインタの指す配列番号を取り出す。
ステップS525において、ステップS514で得た配列番号の指す配列要素のノード種別に“1”(リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップS526に進み、配列からステップS524で得た配列番号の配列要素を読み出す。
【0095】
次にステップS527において、ステップS515で得た配列番号の配列要素にステップS526で読み出した内容を書き込む。
最後にステップS528において、ステップS524で得た配列番号の指す配列要素のノード種別に“0”(ブランチノード)を、弁別ビット位置にステップS517で得たビット位置を、代表ノード番号にステップS512で得た配列番号を書き込み、処理を終了する。
【0096】
上述の図2のカップルドノードツリーに“111000”を挿入する例では、取得された空ノード対のノード[0]にノード211bの内容を書き込み(ステップS527)、ノード[1]を挿入キー“111000”を保持するリーフノードとする(ステップS525)。そして、ノード211bの弁別ビット位置にビット列比較により異なるビット値となる最上位のビット位置1を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号が格納される(ステップS528)。
【0097】
図6は、ルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。図6に示すフロー自体は、先の出願である上記特願2006−187827で提案されたノード挿入処理全体を説明する処理フローと同様である。
【0098】
ステップS601において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図5A〜図5Cを用いて説明した通常の挿入処理が行われる。
【0099】
ステップS601での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップS602において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS603において、ステップS602で得た配列番号に0を加えた配列番号を求める。(実際には、ステップS602で取得した配列番号に等しい。)。さらにステップS604において、ステップS603で得た配列番号の配列要素に、挿入するルートノードのノード種別に1(リーフノード)とインデックスキーに挿入キーを書き込み、ステップS605で、ステップS602で取得したルートノードの配列番号を登録して処理を終了する。
【0100】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図6及び図5A〜図5Cの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【0101】
次に図7A、図7Bを参照して、カップルドノードツリーに係るインデックスキーの集合から、特定のインデックスキーを削除する処理フローを説明する。図7A、図7Bに示すフロー自体は、本出願人による出願である上記特願2006−187827で提案された削除処理のフローと同様である。
【0102】
図7Aは、削除処理の前段である検索処理の処理フローを示す図であり、基本的には図4Aに示した検索処理において削除キーを検索キーとしたものに相当するが、図4AのステップS406aの探索経路スタックに弁別ビット位置を格納する処理は、省略されている。もし、削除処理の前段である検索処理の履歴における弁別ビット位置を頻繁に利用するような処理を引き続いて行うのであれば、探索経路スタックに弁別ビット位置を格納する処理を追加すればよい。
【0103】
ステップS701は図4AのステップS401で検索開始ノードをルートノードとしたものに相当し、ステップS702〜ステップS710の処理は図4AのステップS402〜ステップS410に上述の点を除いて完全に対応するので説明は省略する。
【0104】
図7AのステップS711において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図7BのステップS712以下の処理に進む。
【0105】
図7Bは、削除処理の後段の処理フローを説明する図である。
まず、ステップS712で探索経路スタックに2つ以上の配列番号が格納されているか判定する。2つ以上の配列番号が格納されていないということは、言い換えれば1つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップS718に移行し、ステップS701で得たルートノードの配列番号に係るノード対を削除する。次にステップS719に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【0106】
ステップS712において探索経路スタックに2つ以上の配列番号が格納されていると判定されたときはステップS713に進み、ステップS708で得た代表ノード番号にステップS707で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【0107】
次にステップS714において、ステップS713で得た配列番号の配列要素の内容を読み出し、ステップS715において探索経路スタックのスタックポインタを1つ戻して配列番号を取り出す。
【0108】
次にステップS716に進み、ステップS714で読み出した配列要素の内容をステップS715で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
【0109】
最後にステップS717においてステップS708で得た代表ノード番号に係るノード対を削除して処理を終了する。
【0110】
図8は、本発明による、カップルドノードツリー(部分木を含む)に格納されたインデックスキーの最小値を求める処理を示したフローチャートである。図8に示すフローチャートは、本出願人による出願である上記特願2006−293619で提案されたインデックスキーの最小値を求めるフローチャートにおいて、ノードから弁別ビット位置を取り出す処理と探索経路スタックにノードから取り出した弁別ビット位置を格納する処理を追加したものである。インデックスキーの最小値を求める処理は、先に述べたようなインデックスキーのツリー上の配置から、検索開始ノードからノード[0]をリーフノードに至るまでツリー上でたどることに相当する。
【0111】
まず、ステップS801の検索開始ノードの配列番号の取得からステップS805のノード種別の判定までは、それぞれ上述の図4AのステップS401からステップS405の処理と同様である。
【0112】
ステップS805のノード種別の判定においてノード種別がブランチノードと判定されると、ステップS806に進み、ノードから配列の代表ノード番号を取り出す。
次にステップS806aに進み、ノードから弁別ビット位置を取り出し、ステップS806bで、その取り出した弁別ビット位置を探索経路スタックに格納する。
【0113】
次にステップS807で、ステップS806において取り出した代表ノード番号に値“0”を加算してその結果を新たな配列番号とし、ステップS802に戻る。以降、ステップS805においてそのノードがリーフノードと判定されるまでステップS802からステップS807までの処理を繰り返し、ステップS808で、リーフノードからインデックスキーを取り出し、処理を終了する。
【0114】
上記の図8に示す処理においては、ノード[0]をたどるため、代表ノード番号に一律に“0”を加算している。すなわち、図8の処理によれば、リンク先のノードは、ノード対のうち必ずノード[0]とし、より小さい値のインデックスキーが格納されているノードのほうに分岐している。これにより、ツリー構造が先に述べたように順列構成であるカップルドノードツリーの最小のインデックスキーを取り出すことができる。
【0115】
図9は、図8のフローチャートにより示したインデックスキーの最小値を求める処理を、図2に例示したカップルドノードツリーにより説明する図である。図9は、配列番号220のノード210aを検索開始ノードとする場合のリンク経路及び探索経路スタック310の状態を示す。
【0116】
検索開始ノードはノード210aであるから、その配列番号220と弁別ビット位置230aのビット値“0”が探索経路スタック310にプッシュされ、次に代表ノード番号220aにより表されるノード対201bのうちノード[0]であるノード210bにリンクしていき、その代表ノード番号220aと弁別ビット位置230bのビット値“1”が探索経路スタック310に格納され、さらにリーフノード210cに至る。リーフノード210cのインデックスキー“000111”を取り出すと、処理を終了する。
【0117】
以上説明したように、探索経路スタック310には、ノード対のうち、ノード[0]の配列番号とブランチノードの弁別ビット位置が順次格納されていく。
【0118】
図10は、カップルドノードツリー(部分木を含む)に格納されたインデックスキーの最大値を求める処理を示したフローチャートである。図10に示すフローチャートは、本出願人による出願である上記特願2006−293619で提案されたインデックスキーの最大値を求めるフローチャートにおいて、ノードから弁別ビット位置を取り出す処理と探索経路スタックにノードから取り出した弁別ビット位置を格納する処理を追加したものである。
【0119】
インデックスキーの最大値を求める処理は、ツリー上のノードのうちノード[1]について、リーフノードに至るまで順次たどっていくことに相当する。以下、任意の部分木の最大のインデックスキーを求める処理について、上記最小のインデックスキーを求める処理と比較しながら、異なる点を中心に説明する。
【0120】
図10に示す一連の処理のうち、ステップS1001からステップS1006b及びステップS1008については、図8のステップS801からステップS806b及びステップS808にそれぞれ対応しており、同様の処理が実行される。図8の最小値を求める処理と異なる点は、ステップS1007において、代表ノード番号に、値“1”を加算する点である。これにより、代表ノード番号が表すノード対のうち、ノード[1]に常にリンクすることとなり、リーフノードに至るまで順次ステップS1002からステップS1007の処理を繰り返すことにより、インデックスキーの最大値を得ることができる。
【0121】
図11は、図10のフローチャートにより示したインデックスキーの最大値を求める処理を、図2に例示したカップルドノードツリーにより説明する図である。図11に示すように、検索開始ノードを図9の例と同様に配列番号220のノード210aとしている。
【0122】
したがって、検索開始ノードの配列番号は配列番号220であり、探索経路スタック310には配列番号220がスタックされ、配列番号220の配列要素に格納されたノード210aが読み出される。ノード210aのノード種別260aは“0”でありブランチノードであるから、代表ノード番号220aと弁別ビット位置230aを取り出し、探索経路スタック310に弁別ビット位置230aの値“0”を格納する。
【0123】
次に、最大値検索においては常にノード[1]にリンクしていくことから、代表ノード番号220aに値“1”を加算した値をリンク先の配列番号としてノード211bにリンクする。そして配列番号220a+1を探索経路スタック310に格納するとともに、ノード211bを読み出す。
【0124】
ノード211bのノード種別261bは“0” でありブランチノードであるから、代表ノード番号221bと弁別ビット位置231bを取り出し、探索経路スタック310に弁別ビット位置231bの値“2”を格納する。
【0125】
次に、代表ノード番号221bに値“1”を加算した値をリンク先の配列番号としてノード211fにリンクする。そして配列番号221b+1を探索経路スタック310に格納するとともに、ノード211fを読み出す。
【0126】
ノード211fのノード種別261fは“0” でありブランチノードであるから、代表ノード番号221fと弁別ビット位置231fを取り出し、探索経路スタック310に弁別ビット位置231fの値“3”を格納する。
【0127】
次に、代表ノード番号221fに値“1”を加算した値をリンク先の配列番号としてノード211hにリンクする。そして配列番号221f+1を探索経路スタック310に格納するとともに、ノード211hを読み出す。
【0128】
ノード211hのノード種別261hは“1” でありリーフノードであるから、ノード211hからインデックスキー251hの値“101100”を最大値として取り出し、処理を終了する。
【0129】
図4Aから図11に示すように、検索キーと一致するインデックスキーを検索する基本動作やインデックスキーの最小値/最大値の検索処理を実行する際には、探索経路スタック310に参照した配列の配列番号とブランチノードの弁別ビット位置が順次格納されていく。
【0130】
なお、上述の図8及び図10を参照したインデックスキーの最小値/最大値の検索処理では、カップルドノードツリーは配列に記憶されたものとして説明したが、カップルドノードツリーが配列に記憶されることは必須ではなく、ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることによりインデックスキーの最小値/最大値の検索が可能であることは明らかである。
【0131】
次に、カップルドノードツリーの分割/結合方法について説明をする。
本発明でいうカップルドノードツリーの分割とは、あるビット列からなる分割キーを指定したとき、カップルドノードツリーに含まれるインデックスキーをその分割キーとの大小関係により2グループに分け、それぞれのグループに属するインデックスキーからなる2つのカップルドノードツリーを生成することである。
【0132】
大小関係による分割について、以下の説明では、分割キーより大きいグループと分割キー以下のグループに分割するとするが、分割キー以上のグループと分割キーより小さいグループに分割する場合でも、同様に分割/結合が可能であることは、以下の説明から容易に理解されるであろう。
【0133】
要するに、分割キーはカップルドノードツリーをどこで分割するかを決定するために用いられるキーである。
また、カップルドノードツリーの結合とは、2つのインデックスキーの集合に対応する2つカップルドノードツリーから2つのインデックスキーの集合の和集合に対応するカップルドノードツリーを生成することである。本発明では、2つのインデックスキーの集合の積集合は空であることを前提にしている。なお、以下の説明において、カップルドノードツリーを単にツリーということがある。
【0134】
図12は、本発明のカップルドノードツリーの第1の分割処理フローを説明する図である。図12に示すフローのステップ構成は、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例1のフローと同じであるが、ステップの内容については異なるものが存在する。
【0135】
第1の分割処理では、分割対象である処理元のツリー(以下、単に処理元ということがある。)のインデックスキーの最小値を取り出し、取り出したインデックスキーの最小値を、処理元の分割により生成される処理先のツリー(以下、単に処理先ということがある。)に挿入し、処理元のツリーからインデックスキーの最小値を削除する処理を、最小値が分割キー以下である間繰り返すことにより、分割対象である処理元のツリーから処理先のツリーを分割する。
【0136】
最初のステップS1201で指定された分割キーを処理元の分割キーとして設定する。分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。
【0137】
次にステップS1202で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップS1203に進む。
ステップS1203では、処理元のツリーが登録済みか判定する。この判定結果が登録済みではないというのは処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものであり、その場合には処理を終了する。
【0138】
処理元のツリーが登録済みであればステップS1204に移行し、ステップS1202で検索開始ノードとして設定したルートノードより、図8に示す処理を実行してインデックスキーの最小値を得る。このとき、先に説明したように、探索経路スタックには配列番号とともに弁別ビット位置が格納される。
【0139】
次にステップS1205に進み、ステップS1204で得た最小値が分割キーより大きいか判定する。最小値が分割キーより大きければ、ツリーの分割が完成しているのであるから処理を終了し、大きくなければ、以下で説明するステップS1206〜ステップS1209の処理先のツリーの生成と処理元のツリーからのノードの削除処理を実行し、ステップS1203へ戻る。
【0140】
ステップS1206では、ステップS1204で得られた最小値を処理先の挿入キーに設定する。
次にステップS1207で、図5A〜図5C、図6に示すツリーの生成、挿入処理により、挿入キーによる処理先のツリーの生成を実行する。
【0141】
本発明のカップルドノードツリーの第1の分割処理における生成、挿入処理は、先の最小値検索処理において探索経路スタックに格納された弁別ビット位置を参照することができるので、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例1よりも処理を速くすることができる。
【0142】
続いてステップS1208で、ステップS1207における挿入キーを処理元の削除キーに設定し、ステップS1209において、図7A、図7Bに示す削除処理により、処理元のツリーから削除キーを含むリーフノードを削除する。
【0143】
上記分割処理の説明では、処理元のインデックスキーの最小値から順に削除を行うようにしたが、同様にインデックスキーの最大値から順に削除を行うことができることは、当業者に明らかである。その場合、ステップS1205はインデックスキーの最大値を求める処理になり、ステップS1205は最大値と分割キーの大小関係の判定処理となり、ステップS1206では最大値を処理先の挿入キーに設定することになる。
【0144】
以上、分割処理について説明したが、結合処理も図12に示す処理フローにより実行できる。
結合処理は、結合しようとする2つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上とすれば、先に述べた例外的な処理に該当し、処理元のツリーは削除され、処理先のツリーに結合される。なお、処理元のツリーのインデックスキーの最大値が未知の場合には、前もって図10に示す最大値検索処理により分割キーを求めることになる。
【0145】
そして、処理元の分割キーを処理元のツリーのインデックスキーの最大値以上とするのであるから、ステップS1205の大小比較では、分割キーが最小値より常に大きくステップS1206へ分岐するのでステップS1205を省略することができる。そうであれば、分割キーを設定する意味もないことから、結局ステップS1202も不要になり、ただ単に最小値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができる。
【0146】
また、分割処理について述べたように、最大値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができることも明らかである。
【0147】
図13は、本発明のカップルドノードツリーの第2の分割処理フローを説明する図である。図13に示すフローのステップ構成は、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例2のフローと同じであるが、ステップの内容については異なるものが存在する。
【0148】
第2の分割処理は、インデックスキー単位で挿入削除を行う点では第1の分割処理と同様であるが、挿入削除すべきインデックスキーの探索に探索経路スタックを活用し、挿入処理及び削除処理の実行時の処理ステップ数を小さくしたものである。
【0149】
図13のステップS1301からステップS1306までの処理は、図12に示す第1の分割処理のステップS1201からステップS1206までの処理とまったく同じであるから、説明を省略する。なお、ステップS1304の最小値検索処理において、探索経路スタックには配列番号とともに弁別ビット位置が格納されることも、ステップS1204における最小値検索と同様である。
【0150】
ステップS1307において、挿入キーにより、処理先にノードを挿入する。この処理は、図12に示すステップS1207の挿入処理とは異なる第2の分割処理特有のものであり、後に図14、図15A、図15Bを参照して詳細に説明する。
【0151】
次にステップS1308においてステップS1304で得た最小値を含むノードを、処理元の削除ノードとして設定し、ステップS1309において処理元から削除ノードを削除し、削除ノードと対をなすノードの内容が複写される処理元の親ノードを得る。
続いてステップS1310で、ステップS1309で得られた処理元の親ノードを、処理元の検索開始ノードに設定し、ステップS1303に戻る。
【0152】
後に説明するように、処理元の親ノードは削除ノードの直近上位のブランチノードである。削除ノードは処理元のインデックスキーの最小値を含むものであり、先に述べたインデックスキーの順序性から、次に検索する最小値は処理元の親ノードの下位にある。
したがって、2回目以降のステップS1304での最小値検索の検索開始ノードはルートノードとしないで処理元の親ノードとすることにより、処理ステップ数を低減することができる。
ステップS1308〜ステップS1309及び処理元の親ノードについては、後に図16を参照して詳細に説明する。
【0153】
図14は、図13に示すステップS1306とステップS1307に対応するノードの挿入処理フローを説明する図である。
【0154】
最初のステップS1401における挿入キーを処理先の挿入キーとして設定するステップは、図13に示すステップS1306に対応する処理であり、図13に示すステップS1304で得られた最小値を処理先の挿入キー設定エリアに設定する
【0155】
。
次にステップS1402において、処理先が登録済みか判定する。
登録済みでなければステップS1403に移行し、ステップS1403において、挿入キーを含むノード対を処理先のルートノードに設定し、処理先のルートノードとして登録する。続いてステップS1404に進み、処理先のルートノードを挿入済みノードとして設定して処理を終了する。
【0156】
上記ステップS1402での判定結果が登録済みであれば、ステップS1405に移行する。ステップS1405では、挿入済みノードが設定済みであるか判定する。この判定処理は、後に説明するツリーの結合処理で必要になるものである。ツリーの分割処理では、最初の挿入処理においてステップS1404でルートノードを挿入済みノードとして設定することから、ステップS1406の判定は常に「はい」である。したがって、分割処理だけのためであれば、ステップS1405とステップS1407は必須ではない。
【0157】
ステップS1405での判定結果が「はい」であればステップS1406に進み、挿入済みノードとして設定されているノードを処理先の検索開始ノードとして設定し、ステップS1408に進む。
ステップS1405での判定結果が「いいえ」であればステップS1407に進み、ルートノードを処理先の検索開始ノードとして設定し、ステップS1408に進む。
【0158】
ステップS1408では、図10に示す最大値検索処理により、ステップS1406あるいはステップS1407で設定された検索開始ノードから処理先のインデックスキーの最大値を求める。このとき、先に説明したように、探索経路スタックには配列番号とともに弁別ビット位置が格納される。
【0159】
次にステップS1409において、ステップS1401で設定された挿入キーとステップS1407で得られた最大値により、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する。
【0160】
続いてステップS1410に進み、ステップS1409において挿入キーを含むノード対を挿入された処理先の親ノードを挿入済みノードとして設定し、処理を終了する。
次に、上述のステップS1403とステップS1409について詳細に説明する。
【0161】
図15Aは、図14に示すステップS1403のルートノード設定処理を説明するフロー図である。
【0162】
まず、ステップS1501で配列からノード対が空の代表ノード番号を取得する。
次にステップS1502において、ステップS1501で取得した代表ノード番号に値“0”を加えて得た配列番号を、挿入ノードの配列番号として設定しておく。
【0163】
ステップS1503に進み、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップS1502で設定した配列番号の配列要素に格納する。
次にステップS1504において、挿入ノードの配列番号をルートノードの配列番号として登録して処理を終了する。
【0164】
なお、上記ステップS1501〜ステップS1504の処理は、図6を参照して説明したカップルドノードツリーの生成処理において、ルートノードの配列番号が登録済みでない場合の、ステップS602〜ステップS605に対応するものである。
【0165】
図15Bは、図14に示すステップS1409の、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する処理を説明するフロー図である。図15Bに示すフローは、先に図5Cを参照して示した挿入処理の応用であり、ステップS1505の、挿入キーと最大値をビット列として比較して上位0ビット目から見た最初の不一致ビットの位置を求め、それを、差分ビット位置を格納するエリアに設定する処理は、図5Cに示すステップS516とステップS517の処理に対応する。
【0166】
ステップS1505に続いてステップS1506aに進む。なお、ステップS1506a〜ステップS1512の処理ブロックは図5Cに示すステップS519a〜ステップS523からなる処理ブロックに相当し、ステップS1513〜ステップS1518の処理は図5Cに示すステップS524〜ステップS528に相当する。
【0167】
ステップS1506aにおいて、先の図14に示すステップS1408の最大値検索処理における処理先の探索経路スタックのスタックポインタを1つ戻して、弁別ビット位置を取り出す。
【0168】
次に、ステップS1509において、ステップS1505で設定した差分ビット位置とステップS1506aで取り出した弁別ビット位置を比較し、弁別ビット位置が差分ビット位置より上位の位置関係か判定する。
【0169】
その判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係であれば、ステップS1512に進み、処理先の探索経路スタックのスタックポインタを1つ戻して配列番号を取り出し、それを親ノードの配列番号エリアに設定してステップS1513に移行する。
【0170】
ステップS1509での判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係でなければ、ステップS1510に進む。
ステップS1510では、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。
【0171】
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合には、ステップS1506に戻る。
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指している場合には、ステップS1511において処理先の探索経路スタックからスタックポインタの指す配列番号を取り出し、処理先の親ノードの配列番号を格納するエリアに設定してステップS1513に移行する。
【0172】
以上説明したステップS1506a〜ステップS1512の処理においては、先の最大値検索処理において探索経路スタックに格納された弁別ビット位置を参照することができるので、本出願人による先の出願である特願2006−319407で提案された分割処理の実施例2よりも処理を速くすることができる。
【0173】
ステップS1513においては、配列からノード対が空きの代表ノード番号を取得する。
次にステップS1514において、代表ノード番号に1を加えて得た配列番号を挿入ノードの配列番号を格納するエリアに設定する。
【0174】
次にステップS1515において、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップS1514で設定した配列番号の配列要素に格納する。
【0175】
次にステップS1516において、代表ノード番号に0を加えて得た配列番号を、挿入ノードと対をなす対ノードの配列番号を格納するエリアに設定する。
次にステップS1517において、ステップS1511あるいはステップS1512で設定した処理先の親ノードの配列番号の指す配列要素の内容を読み出し、ステップS1516で設定した対ノードの配列番号の指す配列要素に格納する。
【0176】
次にステップS1518において、ブランチノードを形成するため、ノード種別にブランチを、弁別ビット位置にステップS1505で設定した差分ビット位置を、代表ノード番号にステップS1516で設定した対ノードの配列番号を設定し、ステップS1511あるいはステップS1512で設定した処理先の親ノードの配列番号の指す配列要素に格納して処理を終了する。
【0177】
図16は、図13に示す処理フローにおける削除処理について説明する処理フロー例を示す図である。
最初のステップであるステップS1601は、図13に示すステップS1308に相当するものである。削除ノードに含まれる削除キーは図13に示すステップS1304において最小値検索により求められたものであるから、処理元の探索経路スタックには削除キーの格納された配列要素の配列番号がスタックされているので、その配列番号により削除ノードを読み出して削除ノードを格納するエリアに設定する。
【0178】
次のステップS1602では、処理元の探索経路スタックに2つ以上の配列番号が格納されているか判定される。このステップS1602以降、ステップS1608に至る処理は、図7Bに示す削除処理の後段の処理に対応するものである。
【0179】
処理元の探索経路スタックに2つ以上の配列番号が格納されていなければ、ステップS1607に移行し、ステップS1601で設定した削除ノードの配列番号の指すノード対を削除し、ステップS1608に進み、ルートノードの配列番号を削除して処理を終了する。
【0180】
処理元の探索経路スタックに2つ以上の配列番号が格納されていれば、ステップS1603に進み、削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号を格納するエリアに設定する。
【0181】
次にステップS1604において、処理先の探索経路スタックのスタックポインタを1つ戻して配列番号を取り出し、削除ノードの直近上位のブランチノードである処理元の親ノードの配列番号格納エリアに設定する。
【0182】
次にステップS1605において、ステップS1603で設定した対ノードの配列番号の指す配列要素の内容を読出し、ステップS1604で設定した処理元の親ノードの配列番号の指す配列要素に格納する。
次にステップS1606において、削除ノードの代表ノード番号の指すノード対を削除して処理を終了する。
【0183】
以上、第2の分割処理について説明したが、第2の分割処理においても、第1の分割処理の場合と同様にインデックスキーの最大値から順に削除を行うことができる。
また、第1の分割処理の場合と同様に分割処理の処理フローをツリーの結合処理に用いることが可能である。結合しようとする2つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上あるいは最小値以下として処理元のツリーの削除処理を行い、削除されたノードを処理先のツリーに挿入する処理を行えばよい。
【符号の説明】
【0184】
10、20、30 配列番号
100 配列
101 ノード
102 ノード種別
103 弁別ビット位置
104 代表ノード番号
111 ノード対
112 ノード[0]、代表ノード
113 ノード[1]、代表ノードと対をなすノード
118 インデックスキー
301 データ処理装置
302 中央処理装置
303 キャッシュメモリ
304 バス
305 主記憶装置
306 外部記憶装置
307 通信装置
308 データ格納装置
309 配列
310 探索経路スタック
【特許請求の範囲】
【請求項1】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成されたカップルドノードツリーをコンピュータが分割する、カップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割するインデックスキーを決定する分割キーを取得するステップと、
前記処理元カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードが配置された記憶領域のアドレス情報と該ブランチノードの弁別ビット位置をスタックに順次格納する、処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理元最小値あるいは最大値取得ステップと、
前記分割キーと前記最小値あるいは最大値との大小を比較し、該最小値が前記分割キーより大きければあるいは該最大値が前記分割キーより小ければ処理を終了する比較ステップと、
前記比較の結果、該最小値が前記分割キーより大きくなければあるいは該最大値が前記分割キーより小さくなければ、
該最小値あるいは該最大値をインデックスキーとして挿入する処理先カップルドノードツリーが存在していない場合は、該最小値あるいは該最大値をインデックスキーとして含むリーフノードをルートノードとする処理先カップルドノードツリーを生成し、前記処理先カップルドノードツリーが存在している場合は、該処理先カップルドノードツリーに該最小値あるいは該最大値のインデックスキーを挿入して新たな処理先カップルドノードツリーを生成する生成ステップと、
前記処理元カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記比較ステップ、前記生成ステップ及び前記削除ステップを前記処理元最小値あるいは最大値取得ステップで取得された最小値あるいは最大値が前記分割キーより大きくなるまであるいは小さくなるまで繰り返すことを特徴とするカップルドノードツリーの分割方法。
【請求項2】
請求項1に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの格納された配列要素の配列番号であり、
前記生成ステップは、
前記処理先カップルドノードツリーが存在している場合は、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値を前記処理先カップルドノードツリーの挿入キーとして設定して前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である処理先親ノードを決定し、
該処理先親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの分割方法。
【請求項3】
請求項2に記載のカップルドノードツリーの分割方法において、
前記生成ステップは、さらに前記処理先親ノードを、挿入キーを含むリーフノードを挿入した挿入済みノードとして設定するステップを含み、
前記処理先最大値あるいは最小値取得ステップは、前記挿入済みノードを検索開始ノードとして前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得するものであることを特徴とするカップルドノードツリーの分割方法。
【請求項4】
請求項3に記載のカップルドノードツリーの分割方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの分割方法。
【請求項5】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された2つのカップルドノードツリーをコンピュータが結合する、カップルドノードツリーの結合方法において、
前記処理元カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードが配置された記憶領域のアドレス情報と該ブランチノードの弁別ビット位置をスタックに順次格納する、前記2つのカップルドノードツリーの一方の処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理元最小値あるいは最大値取得ステップと、
前記2つのカップルドノードツリーの他方の処理先カップルドノードツリーに前記最小値あるいは最大値のインデックスキーを挿入する挿入ステップと、
前記処理先カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記挿入ステップ及び前記削除ステップを前記処理元カップルドノードツリーがすべて削除されるまで繰り返すことを特徴とするカップルドノードツリーの結合方法。
【請求項6】
請求項5に記載のカップルドノードツリーの結合方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応する代表ノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの格納された配列要素の配列番号であり、
前記挿入ステップは、
前記最小値あるいは前記最大値を前記処理先カップルドノードツリーの挿入キーとして設定して前記前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である親ノードを決定し、
該親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの結合方法。
【請求項7】
請求項6に記載のカップルドノードツリーの結合方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの結合方法。
【請求項8】
請求項1〜7のいずれか1項に記載のカップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるためのプログラム。
【請求項9】
請求項1〜7のいずれか1項に記載のカップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項1】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成されたカップルドノードツリーをコンピュータが分割する、カップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割するインデックスキーを決定する分割キーを取得するステップと、
前記処理元カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードが配置された記憶領域のアドレス情報と該ブランチノードの弁別ビット位置をスタックに順次格納する、処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理元最小値あるいは最大値取得ステップと、
前記分割キーと前記最小値あるいは最大値との大小を比較し、該最小値が前記分割キーより大きければあるいは該最大値が前記分割キーより小ければ処理を終了する比較ステップと、
前記比較の結果、該最小値が前記分割キーより大きくなければあるいは該最大値が前記分割キーより小さくなければ、
該最小値あるいは該最大値をインデックスキーとして挿入する処理先カップルドノードツリーが存在していない場合は、該最小値あるいは該最大値をインデックスキーとして含むリーフノードをルートノードとする処理先カップルドノードツリーを生成し、前記処理先カップルドノードツリーが存在している場合は、該処理先カップルドノードツリーに該最小値あるいは該最大値のインデックスキーを挿入して新たな処理先カップルドノードツリーを生成する生成ステップと、
前記処理元カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記比較ステップ、前記生成ステップ及び前記削除ステップを前記処理元最小値あるいは最大値取得ステップで取得された最小値あるいは最大値が前記分割キーより大きくなるまであるいは小さくなるまで繰り返すことを特徴とするカップルドノードツリーの分割方法。
【請求項2】
請求項1に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの格納された配列要素の配列番号であり、
前記生成ステップは、
前記処理先カップルドノードツリーが存在している場合は、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値を前記処理先カップルドノードツリーの挿入キーとして設定して前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である処理先親ノードを決定し、
該処理先親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの分割方法。
【請求項3】
請求項2に記載のカップルドノードツリーの分割方法において、
前記生成ステップは、さらに前記処理先親ノードを、挿入キーを含むリーフノードを挿入した挿入済みノードとして設定するステップを含み、
前記処理先最大値あるいは最小値取得ステップは、前記挿入済みノードを検索開始ノードとして前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得するものであることを特徴とするカップルドノードツリーの分割方法。
【請求項4】
請求項3に記載のカップルドノードツリーの分割方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの分割方法。
【請求項5】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された2つのカップルドノードツリーをコンピュータが結合する、カップルドノードツリーの結合方法において、
前記処理元カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードが配置された記憶領域のアドレス情報と該ブランチノードの弁別ビット位置をスタックに順次格納する、前記2つのカップルドノードツリーの一方の処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理元最小値あるいは最大値取得ステップと、
前記2つのカップルドノードツリーの他方の処理先カップルドノードツリーに前記最小値あるいは最大値のインデックスキーを挿入する挿入ステップと、
前記処理先カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記挿入ステップ及び前記削除ステップを前記処理元カップルドノードツリーがすべて削除されるまで繰り返すことを特徴とするカップルドノードツリーの結合方法。
【請求項6】
請求項5に記載のカップルドノードツリーの結合方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応する代表ノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの格納された配列要素の配列番号であり、
前記挿入ステップは、
前記最小値あるいは前記最大値を前記処理先カップルドノードツリーの挿入キーとして設定して前記前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である親ノードを決定し、
該親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの結合方法。
【請求項7】
請求項6に記載のカップルドノードツリーの結合方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの結合方法。
【請求項8】
請求項1〜7のいずれか1項に記載のカップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるためのプログラム。
【請求項9】
請求項1〜7のいずれか1項に記載のカップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるためのプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【図1】
【図2】
【図3】
【図4A】
【図4B】
【図5A】
【図5B】
【図5C】
【図6】
【図7A】
【図7B】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15A】
【図15B】
【図16】
【図17】
【図2】
【図3】
【図4A】
【図4B】
【図5A】
【図5B】
【図5C】
【図6】
【図7A】
【図7B】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15A】
【図15B】
【図16】
【図17】
【公開番号】特開2009−301582(P2009−301582A)
【公開日】平成21年12月24日(2009.12.24)
【国際特許分類】
【出願番号】特願2009−221744(P2009−221744)
【出願日】平成21年9月28日(2009.9.28)
【分割の表示】特願2007−13211(P2007−13211)の分割
【原出願日】平成19年1月24日(2007.1.24)
【出願人】(506235616)株式会社エスグランツ (32)
【Fターム(参考)】
【公開日】平成21年12月24日(2009.12.24)
【国際特許分類】
【出願日】平成21年9月28日(2009.9.28)
【分割の表示】特願2007−13211(P2007−13211)の分割
【原出願日】平成19年1月24日(2007.1.24)
【出願人】(506235616)株式会社エスグランツ (32)
【Fターム(参考)】
[ Back to top ]