説明

カップルドノードツリーの分割/結合方法及びプログラム

【課題】カップルドノードツリーを2つに分割し、また2つのカップルドノードツリーを結合する手法を提供する。
【解決手段】処理元のカップルドノードツリーのインデックスキーの最小値あるいは最大値を求めてそれらインデックスキーを順次分割点となるインデックスキーまで削除し、削除したインデックスキーを処理先のカップルドノードツリーに挿入することによりカップルドノードツリーを分割する。一方のカップルドノードツリーを上記分割方法の処理元として削除処理を行い、他方を処理先として挿入処理を行ってカップルドノードツリーを結合する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する検索方法に関するものであり、特に本出願人が特願2006−187827において提案したカップルドノードツリーの分割/結合方法及びそのプログラムに関するものである。
【背景技術】
【0002】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【0003】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【0004】
図32は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【0005】
図32の例では、インデックスキー“100010”を保持するノード1750aがルートノードとなっており、その検査ビット位置は0である。ノード1750aの左リンク1740aにはノード1750bが接続され、右リンク1741aにはノード1750fが接続されている。
【0006】
ノード1750bの保持するインデックスキーは“010011”であり、検査ビット位置2030bは1である。ノード1750bの左リンク1740bにはノード1750cが、右リンク1741bにはノード1750dが接続されている。ノード1750cが保持するインデックスキーは“000111”、検査ビット位置は3である。ノード1750dが保持するインデックスキーは“011010”、検査ビット位置は2である。
【0007】
ノード1750cから実線で接続された部分はノード1750cの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ1740cは、その欄が空欄であることを示している。点線の接続された右ポインタ1741cの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード1750cを右ポインタが指定していることを表している。
【0008】
ノード1750dの右ポインタ1741dはノード1750d自身を指しており、左リンク1740dにはノード1750eが接続されている。ノード1750eの保持するインデックスキーは“010010”、検査ビット位置は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】
図32の例では、ルートノード1750aからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が1であるか0であるか判定を行い、1であれば右リンクをたどり、0であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば(図32において点線で示されたこの逆戻りのリンクをバックリンクという)、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【0013】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は1回ですむことなどのメリットがあるが、各ノードからの2つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【0014】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献1に開示された技術がある。下記特許文献1に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【0015】
しかしながら、下記特許文献1に開示されたものにおいても、1つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを1つとしたため、例えば図32に示したパトリシアツリーの最下段の部分である左ポインタ1740c、右ポインタ1741h等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【0016】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願2006−187827において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが1つのときはリーフノード、ツリーのノードが2つ以上のとき
は前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を提案した。
【0017】
上記出願においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。
【0018】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願2006−293619において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの最大値/最小値を求める手法等を提案した。
【0019】
ところで近年において、情報処理技術の進展とともに情報サービスへの要求がさらに拡大し、より厳しいものになってきている。情報サービスを提供する上で基本となるのはデータベースの構築とそのデータベースからの情報の取出しであるが、データベースに蓄積されるデータ量はますます増大し、極めて巨大なものとなりつつある。
【0020】
本出願人の先に提案した検索手法は、上記巨大化しつつあるデータベースの高速検索を可能とするものであるが、データベースが巨大化するとともにそれに対応するカップルドノードツリーも、従来のツリー構造のものより記憶容量が少なくてすむとはいえ、大きなものとなる。一方、各種記憶手段の記憶容量にはそれぞれ制限があり、経済的なシステムを構築するためには各種アクセス速度、記憶容量の記憶手段を組み合わせて利用する必要がある。
【0021】
また、データベース自体も物理的に分割し、分散設置されることもありうる。
したがって、1つのカップルドノードツリーを分割し、また再結合することが必要になる。
【特許文献1】特開2001−357070号公報
【発明の開示】
【発明が解決しようとする課題】
【0022】
そこで本発明の目的は、カップルドノードツリーを2つに分割し、また2つのカップルドノードツリーを結合する手法を提供することである。
【課題を解決するための手段】
【0023】
本発明の一つの態様によれば、分割点となるインデックスキーを決定する分割キーを指定し、処理元のカップルドノードツリーのインデックスキーの最小値あるいは最大値を求めてそれらインデックスキーを順次分割点となるインデックスキーまで削除し、削除したインデックスキーを処理先のカップルドノードツリーに挿入することによりカップルドノードツリーを分割するカップルドノードツリーの分割方法が提供される。
【0024】
また、本発明の別の態様によれば、上記分割方法において処理元のカップルドノードツリーのインデックスキーの最小値あるいは最大値を順次求める処理において、前回最小値あるいは最大値を求めたときの検索経路の履歴により、検索開始ノードを設定して行う。
【0025】
また、本発明のさらに別の態様によれば、2つのカップルドノードツリーの結合を、一方のカップルドノードツリーを上記分割方法における処理元として削除処理を行い、他方を処理先として挿入処理を行うカップルドノードツリーの結合方法が提供される。
【0026】
また、本発明のさらに別の態様によれば、分割点となるインデックスキーを決定する分割キーを指定し、処理元カップルドノードツリーの部分木であって分割キーをその最大値あるいは最小値とするもののうちで最大の部分木のルートノードである分割ノードを求め、前記分割ノードをルートノードとする部分木である分割ノードツリーを挿入することにより新たな処理先のカップルドノードツリーを生成し、前記分割ノードツリーを前記処理元カップルドノードツリーから削除するカップルドノードツリーの分割方法が提供される。
【0027】
また、本発明のさらに別の態様によれば、処理元のカップルドノードツリーのインデックスキーの最大値あるいは最小値と処理先のカップルドノードツリーのインデックスキーの最小値あるいは最大値との差分ビット位置に基づき処理元のカップルドノードツリーから分割して処理先に結合する部分木である分割結合ノードツリーを求め、該分割結合ノードツリーを差分ビット位置に基づいて処理先のカップルドノードツリーに結合する2つのカップルドノードツリーの結合方法を提供する。
【0028】
さらに本発明の別の態様によれば、上記カップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるプログラムが提供される。
【発明の効果】
【0029】
本発明によれば、簡単な処理で、効率よくカップルドノードツリーの分割/結合処理を実施することができ、カップルドノードツリーの大きさが大きくになったとしても、取り扱いを容易なものとすることができる。
【発明を実施するための最良の形態】
【0030】
最初に、本出願人により先の上記出願において提案された、本発明の前提となるカップルドノードツリーについて、カップルドノードツリーを配列に格納する例を説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【0031】
図1は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図1を参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード種別102、弁別ビット位置103及び代表ノード番号104で構成されている。ノード種別102は0であり、ノード101がブランチノードであることを示している。弁別ビット位置103には1が格納されている。代表ノード番号104にはリンク先のノード対の代表ノードの配列番号20が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【0032】
配列番号20の配列要素には、ノード対111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1)に代表ノードと対になるノード[1]113が格納されている。ノード[0]112のノード種別114には0が、弁別ビット位置115には3が、代表ノード番号116には30が格納されている。またノード[1]113のノード種別117には1が格納されており、ノード[1]113がリーフノードであることを示している。インデックスキー118には、“0001”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが
、表記は省略している。
【0033】
なお、代表ノードをノード[0]で表し、それと対になるノードをノード[1]で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
【0034】
配列番号30及び31の配列要素に格納されたノード122とノード123からなるノード対121の内容は省略されている。
ノード[0]112、ノード[1]113、ノード122、及びノード123の格納された配列要素にそれぞれ付された0あるいは1は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である0か1を代表ノード番号に加えた配列番号のノードにリンクする。
【0035】
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
【0036】
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
図2は、カップルドノードツリーのツリー構造を概念的に示す図である。図示の6ビットのインデックスキーは、図32に例示されたパトリシアツリーのものと同じである。
【0037】
符号210aで示すのがルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード対201aの代表ノードとしている。
ツリー構造としては、ルートノード210aの下にノート対201bが、その下層にノード対201cとノード対201fが配置され、ノード対201fの下層にはノード対201hとノード対201gが配置されている。ノード対201cの下にはノード対201dが、さらにその下にはノード対201eが配置されている。
【0038】
各ノードの前に付された0あるいは1の符号は、図1において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【0039】
図示された例では、ルートノード210aのノード種別260aは0でブランチノードであることを示し、弁別ビット位置230aは0を示している。代表ノード番号は220aであり、それはノード対201bの代表ノード210bの格納された配列要素の配列番号である。
【0040】
ノード対201bはノード210bと211bで構成され、それらのノード種別260b、261bはともに0であり、ブランチノードであることを示している。ノード210bの弁別ビット位置230bには1が格納され、リンク先の代表ノード番号にはノード対201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。
【0041】
ノード210cのノード種別260cには1が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー250cには“000111”が格納されている。一方ノード211cのノード種別261cは0、弁別ビット位置231cは2であり、代表ノード番号にはノード対201dの代表ノ
ード210dの格納された配列要素の配列番号221cが格納されている。
【0042】
ノード210dのノード種別260dは0、弁別ビット位置230dは5であり、代表ノード番号にはノード対201eの代表ノード210eの格納された配列要素の配列番号220dが格納されている。ノード210dと対になるノード211dのノード種別261dは1であり、インデックスキー251dには“011010”が格納されている。
【0043】
ノード対201eのノード210e、211eのノード種別260e、261eはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250e、251eにはインデックスキーとして“010010”と“010011”が格納されている。
【0044】
ノード対201bのもう一方のノードであるノード211bの弁別ビット位置231bには2が格納され、リンク先の代表ノード番号にはノード対201fの代表ノード210fの格納された配列要素の配列番号221bが格納されている。
【0045】
ノード対201fのノード210f、211fのノード種別260f、261fはともに0であり双方ともブランチノードである。それぞれの弁別ビット位置230f、231fには5、3が格納されている。ノード210fの代表ノード番号にはノード対201gの代表ノード210gの格納された配列要素の配列番号220fが格納され、ノード211fの代表ノード番号にはノード対201hの代表ノードであるノード[0]210hの格納された配列要素の配列番号221fが格納されている。
【0046】
ノード対201gのノード210g、211gのノード種別260g、261gはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250g、251gには“100010”と“100011”が格納されている。
【0047】
また同じくノード対201hの代表ノードであるノード[0]210hとそれと対をなすノード[1]211hのノード種別260h、261hはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250h、251hには“101011”と“101100“が格納されている。
【0048】
以下、上述のツリーからインデックスキー“100010”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から0、1、2、・・・とする。
まず、ビット列“100010”を検索キーとしてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは0であるので、検索キー“100010”の弁別ビット位置が0のビット値をみると1である。そこで代表ノード番号の格納された配列番号220aに1を加えた配列番号の配列要素に格納されたノード211bにリンクする。ノード211bの弁別ビット位置231bには2が格納されているので、検索キー“100010”の弁別ビット位置が2のビット値をみると0であるから、代表ノード番号の格納された配列番号221bの配列要素に格納されたノード210fにリンクする。
【0049】
ノード210fの弁別ビット位置230fには5が格納されているので、検索キー“100010”の弁別ビット位置が5のビット値をみると0であるから、代表ノード番号の格納された配列番号220fの配列要素に格納されたノード210gにリンクする。
【0050】
ノード210gのノード種別260gは1でありリーフノードであることを示しているので、インデックスキー250gを読み出して検索キーと比較すると両方とも“100010”であって一致している。このようにしてカップルドノードツリーを用いた検索が行
われる。
【0051】
次に、図2を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図2の例で、ルートノード210aの弁別ビット位置が0であるのは、図2に例示されたインデックスキーに0ビット目が0のものと1のものがあるからである。0ビット目が0のインデックスキーのグループはノード210bの下に分類され、0ビット目が1のインデックスキーのグループはノード211bの下に分類されている。
【0052】
ノード211bの弁別ビット位置が2であるのは、ノード211h、210h、211g、210gに格納された0ビット目が1のインデックスキーの1ビット目がすべて0で等しく、2ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
【0053】
以下0ビット目の場合と同様に、2ビット目が1であるものはノード211f側に分類され、2ビット目が0であるものはノード210f側に分類される。
そして2ビット目が1であるインデックスキーは3ビット目の異なるものがあるのでノード211fの弁別ビット位置には3が格納され、2ビット目が0であるインデックスキーでは3ビット目も4ビット目も等しく5ビット目で異なるのでノード210fの弁別ビット位置には5が格納される。
【0054】
ノード211fのリンク先においては、3ビット目が1のものと0のものがそれぞれ1つしかないことから、ノード210h、211hはリーフノードとなり、それぞれインデックスキー250hと251hに“101011”と“101100”が格納されている。
【0055】
仮にインデックスキーの集合に“101100”の代わりに“101101”か“101110”が含まれていたとしても、3ビット目までは“101100”と等しいので、ノード211hに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“101100”に加えて“101101”が含まれていると、ノード211hはブランチノードとなり、その弁別ビット位置は5になる。追加されるインデックスキーが“101110”であれば、弁別ビット位置は4となる。
【0056】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“1”のノードとビット値が“0”のノードとに分岐していることから、ノード[1]側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード211hのインデックスキー251hの“101100”、ノード210hのインデックスキー250hの“101011”、・・・、ノード210cのインデックスキー250cの“000111”となり降順にソートされている。
【0057】
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“101100”であればノード211hに到達することができる。また、上記説明からも想像がつくように、“101101”か“101110”を検索キーとした場合でもノード211hにたどり着き、インデックスキー251hと比較することにより検索が失敗したことが分かる。
【0058】
また、例えば“100100”で検索した場合でも、ノード210a、211b、210fのリンク経路では検索キーの3ビット目と4ビット目は使われることがなく、“100100”の5ビット目が0なので、“100010”で検索した場合と同様にノード210gに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【0059】
図3は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施される。カップルドノードツリーが配置される配列309と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック310を有するデータ格納装置308は、主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。
【0060】
図3の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできるし、探索経路スタック310を中央処理装置302内のハードウェアとして実現することも可能である。あるいは、配列309は外部記憶装置306に、探索経路スタック310を主記憶装置305に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【0061】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
次に、上述の出願において、本出願人により提案されたカップルドノードツリーを用いた基本的な検索処理、カップルドノードツリーにおける挿入削除処理、及びカップルドノードツリーに含まれるインデックスキーの最大値/最小値を求める処理等の応用処理の一部について、図4〜図11Bを参照することにより、本発明を理解するために必要な範囲で紹介する。
【0062】
図4は、本出願人による出願である上記特願2006−293619で提案されたビット列検索の基本動作を示したフローチャートである。
まず、ステップS401で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後に説明する各種応用検索において行われる。
【0063】
次に、ステップS402で、探索経路スタック310に取得された配列番号を格納し、ステップS403で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップS404で、読み出したノードから、ノード種別を取り出し、ステップS405で、ノード種別がブランチノードであるか否かを判定する。
【0064】
ステップS405の判定において、読み出したノードがブランチノードである場合は、ステップS406に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップS407で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップS408で、ノードから代表ノード番号を取り出して、ステップS409で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、ステップS402に戻る。
【0065】
以降、ステップS405の判定においてリーフノードと判定されてステップS410に
進むまで、ステップS402からステップS409までの処理を繰り返す。ステップS410で、リーフノードからインデックスキーを取り出して、処理を終了する。
【0066】
図5は、本出願人による出願である上記特願2006−293619で提案されたカップルドノードツリー(部分木を含む)に格納されたインデックスキーの最小値を求める処理を示したフローチャートである。先に述べたようなインデックスキーのツリー上の配置から、インデックスキーの最小値を求める処理は検索開始ノードからノード[0]をリーフノードに至るまでツリー上でたどることに相当する。
【0067】
まず、ステップS501の検索開始ノードの配列番号の取得からステップS505のノード種別の判定までは、それぞれ上述の図4のステップS401からステップS405の処理と同様である。
【0068】
ステップS505のノード種別の判定においてノード種別がブランチノードと判定されると、ステップS506に進み、ノードから配列の代表ノード番号を取り出し、ステップS507で、取り出した代表ノード番号に値「0」を加算してその結果を新たな配列番号とし、ステップS502に戻る。以降、ステップS505においてそのノードがリーフノードと判定されるまでステップS502からステップS507までの処理を繰り返し、ステップS508で、リーフノードからインデックスキーを取り出し、処理を終了する。
【0069】
上記の図5に示す処理においては、ノード[0]をたどるため、代表ノード番号に一律「0」を加算している。すなわち、図5の処理によれば、リンク先のノードは、ノード対のうち必ずノード[0]とし、より小さい値のインデックスキーが格納されているノードのほうに分岐している。これにより、ツリー構造が先に述べたように順列構成であるカップルドノードツリーの最小のインデックスキーを取り出すことができる。
【0070】
図6は、本出願人による出願である上記特願2006−293619で提案されたカップルドノードツリー(部分木を含む)に格納されたインデックスキーの最大値を求める処理を示したフローチャートである。
【0071】
インデックスキーの最大値を求める処理は、ツリー上のノードのうちノード[1]について、リーフノードに至るまで順次たどっていくことに相当する。以下、任意の部分木の最大のインデックスキーを求める処理について、上記最小のインデックスキーを求める処理と比較しながら、異なる点を中心に説明する。
【0072】
図6に示す一連の処理のうち、ステップS601からステップS606及びステップS608については、図5のステップ501からステップS506及びステップS508にそれぞれ対応しており、同様の処理が実行される。図5の最小値を求める処理と異なる点は、ステップS607において、代表ノード番号に、値「1」を加算する点である。これにより、代表ノード番号が表すノード対のうち、ノード[1]に常にリンクすることとなり、リーフノードに至るまで順次ステップS602からステップS607の処理を繰り返すことにより、インデックスキーの最大値を得ることができる。
【0073】
図4から図6に示すように、検索キーと一致するインデックスキーを検索する基本動作やインデックスキーの最小値/最大値の検索処理を実行する際には、探索経路スタック310に参照した配列の配列番号が順次格納されていく。
【0074】
なお、上述の図5及び図6を参照したインデックスキーの最小値/最大値の検索処理では、カップルドノードツリーは配列に記憶されたものとして説明したが、カップルドノードツリーが配列に記憶されることは必須ではなく、ノード対を構成する2つのノードのう
ちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることによりインデックスキーの最小値/最大値の検索が可能であることは明らかである。
【0075】
図7A及び図7Bは、本出願人による出願である上記特願2006−293619で提案されたカップルドノードツリーに格納されたインデックスキーの下限値を求める処理を示したフローチャートである。ここで下限値とは、指定された下限キー以上のインデックスキーの最小値である。図7A及び図7Bに示す下限値を求める処理は、ユーザ等が指定する検索範囲について検索を行う際に、実際にはインデックスキーが取り得ない範囲については対象外とし、実際にインデックスキーが含まれる範囲について検索を行う処理に応用される。なお、図7A及び図7Bでは、指定された下限キー及び上限キーの取得処理は省略されている。以降の各種応用検索においても同様である。
【0076】
まず、ステップS701で、検索開始ノードの配列番号に、ルートノードの配列番号を設定し、ステップS702で最小値検索処理を行いインデックスキーの最小値を求める。そして、ステップS703で、下限キーと、ステップS702で求めた最小値との比較をし、下限キーが最小値より大きいか否かを判定する。下限キーが最小値以下の値をとる場合、ステップS704に進み、ステップS702で求めた最小値を下限値として設定し、処理を終了する。
【0077】
ステップS703において、下限キーはステップS702で求めた最小値よりも大きいと判定された場合は、ステップS705に進み、下限キーを検索キーとして設定する。そして、ステップS706で、検索開始ノードの配列番号にルートノードの配列番号を設定して、ステップS707で、図4及び図5により説明したビット列検索方法によりインデックスキーを検索する。そして、ステップS708で、検索キーとステップS707の検索の結果得られたインデックスキーとを比較して値が一致するか否かを判定する。検索キーとインデックスキーとが等しいと判定された場合は、ステップS709に進み、検索により得られたインデックスキーを上記下限値として設定し、処理を終了する。検索キーとインデックスキーとは等しくないと判定された場合は、図7BのステップS710に進む。
【0078】
ステップS710で、検索キーとインデックスキーの大小関係を判定する。ここで、検索キーがインデックスキーよりも大きい場合は、そのインデックスキーは検索キーすなわち下限キーよりも小さく、ユーザ等により指定された検索範囲に含まれないことを意味する。一方、検索キーがインデックスキーよりも小さい場合は、そのインデックスキーは指定された検索範囲に含まれることを意味する。そこで、検索キーがインデックスキーよりも小さいと判定されると、ステップS718に進み、そのインデックスキーを下限値に設定して、処理を終了する。
【0079】
ステップS710において、検索キーがインデックスキーよりも大きいと判定されると、ステップS711に進む。ステップS711からステップS717までの処理は、昇順にインデックスキーを取り出す処理であり、ステップS711からステップS717の処理により、カップルドノードツリーに格納されているインデックスキーが順に取り出されていき、検索キーすなわち下限キーよりも大きい値をとるインデックスキーが得られると、そのインデックスキーが下限値として設定される。
【0080】
図8A及び図8Bは、本出願人による出願である上記特願2006−293619で提案されたカップルドノードツリーに格納されたインデックスキーの上限値を求める処理を示したフローチャートである。ここで上限値とは、指定された上限キー以下のインデックスキーの最大値である。図8A及び図8Bに示す上限値を求める処理は、上記下限値を求
める処理と同様に、ユーザ等が指定する検索範囲について検索を行う際に、実際にはインデックスキーが取り得ない範囲については対象外とし、実際にインデックスキーが含まれる範囲について検索を行う処理等に応用される。
【0081】
まず、ステップS801でルートノードを検索開始ノードとして検索する処理についてはインデックスキーの下限値を求める処理と同様であり、また、ステップS802以降の処理については、上記ステップS702以降の処理とそれぞれ対応している。
【0082】
すなわち、図7A及び図7Bを用いて説明した下限値を求める処理においては、ステップS702以降の処理により、ユーザ等により指定された下限キーと、カップルドノードツリーに含まれるインデックスキーのうち下限キー以上で、且つ最も下限キーに近い値をとるインデックスキーを検索している。これに対し、図8A及び図8Bに示す上限値を求める処理においては、ステップS802以降の処理により、検索範囲の上限としてユーザ等により指定された上限キー以下の値をとり、且つ上限キーに最も上限キーに近い値をとるインデックスキーを検索している。
【0083】
図7A及び図7Bに示す処理と比較すると、指定されたキー(下限キー/上限キー)とインデックスキーとを比較する際の大小関係(ステップS703とステップS710、及びステップS803とステップS810)や、指定されたキーを検索キーとしてカップルドノードツリーを検索する際にインデックスキーの最小値/最大値をそれぞれ求める(ステップS707及びステップS807)点、及びインデックスキーを求める順序がそれぞれ昇順/降順である(ステップS711及びステップS811以降の処理)点については逆であるが、下限値及び上限値を求めるまでの手順は基本的に上記と同様である。
【0084】
ステップS802以降の処理について具体的に説明する。
ステップS802でカップルドノードツリーに含まれるインデックスキーの最大値を求めると、ステップS803で、ステップS802で求めた最大値と上限キーとを比較し、上限キーが最大値より大きいか否かを判定する。上限キーがインデックスキーの最大値以上であるときは、ステップS804に進み、ステップS802で求めた最大値を上限値として設定し、処理を終了する。
【0085】
上限キーが最大値よりも小さい場合は、ステップS805に進み、上限キーを検索キーに設定する。そして、ステップS806で、検索開始ノードの配列番号としてルートノードの配列番号を設定し、ステップS807で、検索キーについての検索処理を行い、ステップS808に進む。
【0086】
ステップS808で、検索キーとステップS807で取得したインデックスキーとが等しいか否かを判定する。ステップS808でこれらの値が等しいと判定された場合は、ステップS809に進み、ステップS807の処理で得られたインデックスキーを上記上限値に設定し、処理を終了する。ステップS808で等しくないと判定された場合は、図8BのステップS810に進む。
【0087】
ステップS810で、検索キーとインデックスキーとの大小関係を判定する。ここで、検索キーがインデックスキーよりも小さい場合は、そのインデックスキーは検索キーすなわち上限キーよりも小さく、ユーザ等により指定された検索範囲に含まれないことを意味する。一方、検索キーがインデックスキーよりも大きい場合は、そのインデックスキーは指定された検索範囲に含まれることを意味する。そこで、検索キーがインデックスキーよりも大きいと判定されると、ステップS818に進み、そのインデックスキーを上限値に設定して、処理を終了する。
【0088】
ステップS810において、検索キーがインデックスキーよりも小さいと判定されると、ステップS811に進む。ステップS811以降の処理は、降順にインデックスキーを取り出す処理であり、検索キーがインデックスキーよりも大きいと判定されるまで、ステップS810からステップS817までの処理を繰り返す。
【0089】
次に、図9A〜図9C、図10により本出願人による出願である上記特願2006−187827で提案されたカップルドノードツリーにおけるノード挿入処理を説明する。図9A〜図9Cが通常の挿入処理を説明するものであり、図10はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【0090】
図9Aは挿入処理の前段である検索処理の処理フローを示す図であり、図4に示した検索処理において挿入キーを検索キーとしたものに相当する。ステップS901は図4のステップS401で検索開始ノードをルートノードとしたものに相当し、ステップS902〜ステップS910の処理は図4のステップS402〜ステップS410に完全に対応するので説明は省略する。
【0091】
図9AのステップS911において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図9BのステップS912以下の処理に進む。
【0092】
図9Bは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップS912において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【0093】
ステップS913に進み、挿入キーとステップS910で得たインデックスキーの大小を比較し、挿入キーが大きいときは値1を小さいときは値0のブール値を得る。
ステップS914に進み、ステップS912で得た代表ノードの配列番号にステップS913で得たブール値を加算した配列番号を得る。
【0094】
ステップS915に進み、ステップS912で得た代表ノードの配列番号にステップS913で得たブール値の論理否定値を加算した配列番号を得る。
ステップS914で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップS915で得た配列番号は、そのリーフノードと対を成すブランチノードが格納される配列要素のものである。
【0095】
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【0096】
例えば図2のカップルドノードツリーに“011011”を挿入する場合、検索結果のインデックスキーはノード211dに格納された“011010”になる。挿入キー“011011”とノード211dに格納されたインデックスキー“011010”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値1が得られ、挿入されるノード対の代表ノード番号に1を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー“011010”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。
【0097】
その際、インデックスキー“011010”と挿入キー“011011”とは5ビット目で異なることから、ノード211dは、弁別ビット位置を5とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【0098】
また図2のカップルドノードツリーに“011001”を挿入しようとする場合も、検索結果のインデックスキーはノード211dに格納された“011010”になる。この場合には挿入キーが小さいのでブール値0が得られ、挿入されるノード対の代表ノード番号に0を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー“011010”と挿入キー“011001”とは4ビット目で異なることから、ノード211dは、弁別ビット位置を4とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。次に図9CのステップS916以下の処理に進む。
【0099】
図9Cは図9Bで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
ステップS916〜ステップS923までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップS924以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【0100】
ステップS916で、挿入キーとステップS910で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップS917に進み、ステップS916で得た差分ビット列から、上位0ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するCPUではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【0101】
次にステップS918に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップS924に移行し、指していなければステップS919に進む。
【0102】
ステップS919において、探索経路スタックのスタックポインタを1つ戻してそこにスタックされている配列番号を取り出す。
ステップS920に進み、ステップS919で取り出した配列番号の配列要素を配列からノードとして読み出す。
【0103】
ステップS921に進み、ステップS920で読み出したノードから、弁別ビット位置を取り出す。
次にステップS922に進み、ステップS921で取り出した弁別ビット位置がステップS917で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【0104】
ステップS922の判定結果が否定であれば、ステップS918に戻り、ステップS918での判定が肯定になるかステップS922での判定が肯定になるまで繰り返す。ステップS922での判定が肯定になると、ステップS923で経路探索スタックのスタックポインタを1つ進め、ステップS924以下の処理に移行する。
【0105】
上記ステップS916〜ステップS923で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の(最上位の
)ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。
【0106】
例えば図2のカップルドノードツリーに“111000”を挿入するとき、検索結果のインデックスキーはノード210hに格納された“101011”になる。挿入キー“111000”とノード210hに格納されたインデックスキー“101011”のビット列比較により異なるビット値となる最上位のビット位置1が得られる。得られたビット位置1と経路探索スタックに積まれた配列番号の配列要素に格納されたブランチノードの弁別ビット位置との位置関係を弁別ビット位置が上位になるまでを順次経路探索スタック逆にたどると、ルートノード210aに至る。そこで探索経路スタックのポインタを1つ進め、ノード211bの配列番号を得る。挿入キー“111000”はノード211bのリンク先に挿入される。
【0107】
また、経路探索スタック逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【0108】
次に、ステップS924以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップS924では探索経路スタックからスタックポインタの指す配列番号を取り出す。
【0109】
ステップS925において、ステップS914で得た配列番号の指す配列要素のノード種別に1(リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップS926に進み、配列からステップS924で得た配列番号の配列要素を読み出す。
【0110】
次にステップS927において、ステップS915で得た配列番号の配列要素にステップS926で読み出した内容を書き込む。
最後にステップS928において、ステップS924で得た配列番号の指す配列要素のノード種別に0(ブランチノード)を、弁別ビット位置にステップS917で得たビット位置を、代表ノード番号にステップS912で得た配列番号を書き込み、処理を終了する。
【0111】
上述の図2のカップルドノードツリーに“111000”を挿入する例では、取得された空ノード対のノード[0]にノード211bの内容を書き込み(ステップS927)、ノード[1]を挿入キー“111000”を保持するリーフノードとする(ステップS925)。そして、ノード211bの弁別ビット位置にビット列比較により異なるビット値となる最上位のビット位置1を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号が格納される(ステップS928)。
【0112】
図10は、本出願人による出願である上記特願2006−187827で提案されたルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【0113】
ステップS101において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図9A〜図9Cを用いて説明した通常の挿入処理が行われる。
【0114】
ステップS101での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップS102において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS103において、ステップS102で得た配列番号に0を加えた配列番号を求める。(実際には、ステップS102で取得した配列番号に等しい。)。さらにステップS104において、ステップS103で得た配列番号の配列要素に、挿入するルートノードのノード種別に1(リーフノード)とインデックスキーに挿入キーを書き込み、ステップS105で、ステップS102で取得したルートノードの配列番号を登録して処理を終了する。
【0115】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図10及び図9A〜図9Cの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【0116】
次に図11A、図11Bを参照して、本出願人による出願である上記特願2006−187827で提案されたカップルドノードツリーに係るインデックスキーの集合から、特定のインデックスキーを削除する処理フローを説明する。
【0117】
図11Aは、削除処理の前段である検索処理の処理フローを示す図であり、図4に示した検索処理において削除キーを検索キーとしたものに相当する。ステップS1101は図4のステップS401で検索開始ノードをルートノードとしたものに相当し、ステップS1102〜ステップS1110の処理は図4のステップS402〜ステップS410に完全に対応するので説明は省略する。
【0118】
図11AのステップS1111において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図11BのステップS1112以下の処理に進む。
【0119】
図11Bは、削除処理の後段の処理フローを説明する図である。
まず、ステップS1112で探索経路スタックに2つ以上の配列番号が格納されているか判定する。2つ以上の配列番号が格納されていないということは、言い換えれば1つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップS1118に移行し、ステップS1101で得たルートノードの配列番号に係るノード対を削除する。次にステップS1119に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【0120】
ステップS1112において探索経路スタックに2つ以上の配列番号が格納されていると判定されたときはステップS1113に進み、ステップS1108で得た代表ノード番号にステップS1107で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【0121】
次にステップS1114において、ステップS1113で得た配列番号の配列要素の内
容を読み出し、ステップS1115において探索経路スタックのスタックポインタを1つ戻して配列番号を取り出す。
【0122】
次にステップS1116に進み、ステップS1114で読み出した配列要素の内容をステップS1115で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
【0123】
最後にステップS1117においてステップS1108で得た代表ノード番号に係るノード対を削除して処理を終了する。
以上、カップルドノードツリーの分割/結合に関する本発明の前提となる技術を説明したが、必要とあれば、上述の特許出願の明細書及び図面の記載を参照されたい。
【0124】
次に、本発明のカップルドノードツリーの分割/結合方法について説明をする。
ここでカップルドノードツリーの分割とは、あるビット列からなる分割キーを指定したとき、カップルドノードツリーに含まれるインデックスキーをその分割キーとの大小関係により2グループに分け、それぞれのグループに属するインデックスキーからなる2つのカップルドノードツリーを生成することである。
【0125】
大小関係による分割について、以下の説明では、分割キーより大きいグループと分割キー以下のグループに分割するとするが、分割キー以上のグループと分割キーより小さいグループに分割する場合でも、同様に分割/結合が可能であることは、以下の説明から容易に理解されるであろう。
【0126】
要するに、分割キーはカップルドノードツリーをどこで分割するかを決定するために用いられるキーである。
また、カップルドノードツリーの結合とは、2つのインデックスキーの集合に対応する2つカップルドノードツリーから2つのインデックスキーの集合の和集合に対応するカップルドノードツリーを生成することである。本発明では、2つのインデックスキーの集合の積集合は空であることを前提にしている。
【0127】
以下、本発明の3つの実施例について説明をするが、その説明において、カップルドノードツリーを単にツリーということがある。以下説明する実施例1、2及び3では、指定された分割キーと等しいインデックスキーが分割処理対象のツリーに含まれる必要はないが、指定された分割キーに対応するインデックスキーを分割キーとする場合には、指定された分割キーを上限キーあるいは下限キーとして、図7A、図7B、図8A、図8Bを参照して説明した検索方法により上限値あるいは下限値を求め、それを指定された分割キーに対応する新たな分割キーとすることができる。
【実施例1】
【0128】
本実施例1は、分割対象である処理元のツリー(以下、単に処理元ということがある。)のインデックスキーの最小値を取り出し、取り出したインデックスキーの最小値を、処理元の分割により生成される処理先のツリー(以下、単に処理先ということがある。)に挿入し、処理元のツリーからインデックスキーの最小値を削除する処理を、最小値が分割キー以下である間繰り返すことにより、分割対象である処理元のツリーから処理先のツリーを分割するものである。
【0129】
図12は、本発明の実施例1におけるカップルドノードツリーの分割処理フローを説明する図である。
最初のステップS1201で指定された分割キーを処理元の分割キーとして設定する。
分割キーの指定は、操作者による外部入力の場合もあり得るし、あるコンピュータプログラムの処理結果による場合、遠方からコマンドによる場合等があり得る。指定された分割キーは、処理元の分割キーを保持するメモリ上のエリアに設定される。
【0130】
次にステップS1202で、処理元のルートノードを、処理元の検索開始ノードに設定し、ステップS1203に進む。
ステップS1203では、処理元のツリーが登録済みか判定する。この判定結果が登録済みではないというのは処理元のツリーが全て削除済みであることを意味するから、分割キーが処理元のツリーのインデックスキーの最大値以上である例外的なものであり、その場合には処理を終了する。
【0131】
処理元のツリーが登録済みであればステップS1204に移行し、ステップS1202で検索開始ノードとして設定したルートノードより、図5に示す処理を実行してインデックスキーの最小値を得る。
【0132】
次にステップS1205に進み、ステップS1204で得た最小値が分割キーより大きいか判定する。最小値が分割キーより大きければ、ツリーの分割が完成しているのであるから処理を終了し、大きくなければ、以下で説明するステップS1206〜ステップS1209の処理先のツリーの生成と処理元のツリーからのノードの削除処理を実行し、ステップS1203へ戻る。
【0133】
ステップS1206では、ステップS1204で得られた最小値を処理先の挿入キーに設定する。
次にステップS1207で、図9A〜図9C、図10に示すツリーの生成、挿入処理により、挿入キーによる処理先のツリーの生成を実行する。
【0134】
続いてステップS1208で、ステップS1207における挿入キーを処理元の削除キーに設定し、ステップS1209において、図11A、図11Bに示す削除処理により、処理元のツリーから削除キーを含むリーフノードを削除する。
【0135】
上記分割処理の説明では、処理元のインデックスキーの最小値から順に削除を行うようにしたが、同様にインデックスキーの最大値から順に削除を行うことができることは、当業者に明らかである。その場合、ステップS1204はインデックスキーの最大値を求める処理になり、ステップS1205は最大値と分割キーの大小関係の判定処理となり、ステップS1206では最大値を処理先の挿入キーに設定することになる。
【0136】
以上、分割処理について説明したが、結合処理も図12に示す処理フローにより実行できる。
結合処理は、結合しようとする2つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上とすれば、先に述べた例外的な処理に該当し、処理元のツリーは削除され、処理先のツリーに結合される。なお、処理元のツリーのインデックスキーの最大値が未知の場合には、前もって図6に示す最大値検索処理により分割キーを求めることになる。
【0137】
そして、処理元の分割キーを処理元のツリーのインデックスキーの最大値以上とするのであるから、ステップS1205の大小比較では、分割キーが最小値より常に大きくステップS1206へ分岐するのでステップS1205を省略することができる。そうであれば、分割キーを設定する意味もないことから、結局ステップS1201も不要になり、ただ単に最小値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができる。
【0138】
また、分割処理について述べたように、最大値検索と挿入処理と削除処理の繰り返しにより結合処理を行うことができることも明らかである。
本実施例1は処理のロジックは簡易なものであるが、処理元のルートノードを検索開始ノードとする最小値検索を繰り返し、インデックスキー単位で挿入削除を行うため、実行時の処理ステップ数は大きくなる。
【実施例2】
【0139】
本実施例2は、インデックスキー単位で挿入削除を行う点では実施例1と同様であるが、挿入削除すべきインデックスキーの探索に探索経路スタックを活用し、挿入処理及び削除処理の実行時の処理ステップ数を小さくしたものである。
【0140】
図13は、本発明の実施例2におけるカップルドノードツリーの分割処理フローを説明する図である。
ステップS1301からステップS1306までの処理は、図12に示す実施例1のステップS1201からステップS1206までの処理とまったく同じであるから、説明を省略する。
【0141】
ステップS1307において、挿入キーにより、処理先にノードを挿入する。この処理は、図12に示すステップS1207の挿入処理とは異なる本実施例特有のものであり、後に図14、図15A、図15Bを参照して詳細に説明する。
【0142】
次にステップS1308においてステップS1304で得た最小値を含むノードを、処理元の削除ノードとして設定し、ステップS1309において処理元から削除ノードを削除し、削除ノードと対をなすノードの内容が複写される処理元の親ノードを得る。
【0143】
続いてステップS1310で、ステップS1309で得られた処理元の親ノードを、処理元の検索開始ノードに設定し、ステップS1303に戻る。
後に説明するように、処理元の親ノードは削除ノードの直近上位のブランチノードである。削除ノードは処理元のインデックスキーの最小値を含むものであり、先に述べたインデックスキーの順序性から、次に検索する最小値は処理元の親ノードの下位にある。
【0144】
したがって、2回目以降のステップS1304での最小値検索の検索開始ノードはルートノードとしないで処理元の親ノードとすることにより、処理ステップ数を低減することができる。
【0145】
ステップS1308〜ステップS1309及び処理元の親ノードについては、後に図16を参照して詳細に説明する。
図14は、図13に示すステップS1306とステップS1307に対応するノードの挿入処理フローを説明する図である。
【0146】
最初のステップS1401における挿入キーを処理先の挿入キーとして設定するステップは、図13に示すステップS1306に対応する処理であり、図13に示すステップS1304で得られた最小値を処理先の挿入キー設定エリアに設定する。
【0147】
次にステップS1402において、処理先が登録済みか判定する。
登録済みでなければステップS1403に移行し、ステップS1403において、挿入キーを含むノード対を処理先のルートノードに設定し、処理先のルートノードとして登録する。続いてステップS1404に進み、処理先のルートノードを挿入済みノードとして設定して処理を終了する。
【0148】
上記ステップS1402での判定結果が登録済みであれば、ステップS1405に移行する。ステップS1405では、挿入済みノードが設定済みであるか判定する。この判定処理は、後に説明するツリーの結合処理で必要になるものである。ツリーの分割処理では、最初の挿入処理においてステップS1404でルートノードを挿入済みノードとして設定することから、ステップS1406の判定は常に「はい」である。したがって、分割処理だけのためであれば、ステップS1405とステップS1407は必須ではない。
【0149】
ステップS1405での判定結果が「はい」であればステップS1406に進み、挿入済みノードとして設定されているノードを処理先の検索開始ノードとして設定し、ステップS1408に進む。
【0150】
ステップS1405での判定結果が「いいえ」であればステップS1407に進み、ルートノードを処理先の検索開始ノードとして設定し、ステップS1408に進む。
ステップS1408では、図6に示す最大値検索処理により、ステップS1406あるいはステップS1407で設定された検索開始ノードから処理先のインデックスキーの最大値を求める。
【0151】
次にステップS1409において、ステップS1401で設定された挿入キーとステップS1407で得られた最大値により、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する。
【0152】
続いてステップS1410に進み、ステップS1409において挿入キーを含むノード対を挿入された処理先の親ノードを挿入済みノードとして設定し、処理を終了する。
次に、上述のステップS1403とステップS1409について詳細に説明する。
【0153】
図15Aは、図14に示すステップS1403のルートノード設定処理を説明するフロー図である。
まず、ステップS1501で配列からノード対が空の代表ノード番号を取得する。
【0154】
次にステップS1502において、ステップS1501で取得した代表ノード番号に値“0”を加えて得た配列番号を、挿入ノードの配列番号として設定しておく。
ステップS1503に進み、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップS1502で設定した配列番号の配列要素に格納する。
【0155】
次にステップS1504において、挿入ノードの配列番号をルートノードの配列番号として登録して処理を終了する。
なお、上記ステップS1501〜ステップS1504の処理は、図10を参照して説明したカップルドノードツリーの生成処理において、ルートノードの配列番号が登録済みでない場合の、ステップS102〜ステップS105に対応するものである。
【0156】
図15Bは、図14に示すステップS1409の、挿入するノード対の処理先の親ノードを求め、該親ノードに前記挿入キーを含むノード対を挿入する処理を説明するフロー図である。図15Bに示すフローは、本出願人による先の出願である特願2006−187827で提案された挿入処理の応用であり、ステップS1505の、挿入キーと最大値をビット列として比較して上位0ビット目から見た最初の不一致ビットの位置を求め、それを差分ビット位置を格納するエリアに設定する処理は、図9Cに示すステップS916とステップS917の処理に対応する。
【0157】
ステップS1505に続いてステップS1506に進む。なお、ステップS1506〜
ステップS1512の処理は図9Cに示すステップS918〜ステップS923に相当し、ステップS1513〜ステップS1518の処理は図9Cに示すステップS924〜ステップS928に相当する。
【0158】
ステップS1506において、処理先の探索経路スタックのスタックポインタを1つ戻して、配列番号を取り出す。
次にステップS1507において、配列から、配列番号の指す配列要素の内容をノードとして取り出す。
【0159】
次にステップS1508において、ステップS1507で取り出したノードから、弁別ビット位置を取り出す。
続いてステップS1509において、ステップS1505で設定した差分ビット位置とステップS1508で取り出した差分ビット位置を比較し、弁別ビット位置が差分ビット位置より上位の位置関係か判定する。
【0160】
その判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係であれば、ステップS1512に進み、処理先の探索経路スタックのスタックポインタを1つ戻して配列番号を取り出し、それを親ノードの配列番号エリアに設定してステップS1513に移行する。
【0161】
ステップS1509での判定の結果、弁別ビット位置が差分ビット位置より上位の位置関係でなければ、ステップS1510に進む。
ステップS1510では、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。
【0162】
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合には、ステップS1506に戻る。
判定の結果、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指している場合には、ステップS1511において処理先の探索経路スタックからスタックポインタの指す配列番号を取り出し、処理先の親ノードの配列番号を格納するエリアに設定してステップS1513に移行する。
【0163】
ステップS1513においては、配列からノード対が空きの代表ノード番号を取得する。
次にステップS1514において、代表ノード番号に1を加えて得た配列番号を挿入ノードの配列番号を格納するエリアに設定する。
【0164】
次にステップS1515において、リーフノードを形成するために、ノード種別にリーフを、インデックスキーに挿入キーを設定し、ステップS1514で設定した配列番号の配列要素に格納する。
【0165】
次にステップS1516において、代表ノード番号に0を加えて得た配列番号を、挿入ノードと対をなす対ノードの配列番号を格納するエリアに設定する。
次にステップS1517において、ステップS1511あるいはステップS1512で設定した処理先の親ノードの配列番号の指す配列要素の内容を読み出し、ステップS1516で設定した対ノードの配列番号の指す配列要素に格納する。
【0166】
次にステップS1518において、ブランチノードを形成するため、ノード種別にブランチを、弁別ビット位置にステップS1505で設定した差分ビット位置を、代表ノード番号にステップS1516で設定した対ノードの配列番号を設定し、ステップS1511
あるいはステップS1512で設定した処理先の親ノードの配列番号の指す配列要素に格納して処理を終了する。
【0167】
図16は、図13に示す処理フローにおける削除処理について説明する処理フロー例を示す図である。
最初のステップであるステップS1601は、図13に示すステップS1308に相当するものである。削除ノードに含まれる削除キーは図13に示すステップS1304において最小値検索により求められたものであるから、処理元の探索経路スタックには削除キーの格納された配列要素の配列番号がスタックされているので、その配列番号を読み出して削除ノードを格納するエリアに設定する。
【0168】
次のステップS1602では、処理元の探索経路スタックに2つ以上の配列番号が格納されているか判定される。このステップS1602以降、ステップS1608に至る処理は、図11Bに示す、本出願人による先の出願である特願2006−187827で提案された削除処理の後段の処理に対応するものである。
【0169】
処理元の探索経路スタックに2つ以上の配列番号が格納されていなければ、ステップS1607に移行し、ステップS1601で設定した削除ノードの配列番号の指すノード対を削除し、ステップS1608に進み、ルートノードの配列番号を削除(登録を抹消)して処理を終了する。
【0170】
処理元の探索経路スタックに2つ以上の配列番号が格納されていれば、ステップS1603に進み、ステップS1601で設定した削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号を格納するエリアに設定する。
【0171】
次にステップS1604において、処理元の探索経路スタックのスタックポインタを1つ戻して配列番号を取り出し、削除ノードの直近上位のブランチノードである処理元の親ノードの配列番号格納エリアに設定する。
【0172】
次にステップS1605において、ステップS1603で設定した対ノードの配列番号の指す配列要素の内容を読出し、ステップS1604で設定した処理元の親ノードの配列番号の指す配列要素に格納する。
【0173】
次にステップS1606において、削除ノードの配列番号の指すノード対を削除して処理を終了する。
以上、実施例2のツリー分離処理について説明したが、実施例2においても、実施例1の場合と同様にインデックスキーの最大値から順に削除を行うことができる。
【0174】
また、実施例1の場合と同様に分離処理の処理フローをツリーの結合処理に用いることが可能である。結合しようとする2つのツリーのうちどちらかを処理元のツリーとし、分割キーを処理元のツリーのインデックスキーの最大値以上あるいは最小値以下として処理元のツリーの削除処理を行い、削除されたノードを処理先のツリーに挿入する処理を行えばよい。
【実施例3】
【0175】
上述の実施例1と実施例2の分割結合方法は、インデックスキー単位で挿入削除を行うものであるが、次に実施例3として、カップルドノードツリーの順序性に着目した、カップルドノードツリーのより大きい、所定の条件を満たす、部分木を単位として挿入削除を行う分割結合方法を説明する。
【0176】
図17は、実施例3におけるカップルドノードツリーの分割処理フローを説明する図である。また、図30A〜図30Cは、上記分割処理を実例により説明する図であり、図2に例示したカップルドノードツリーと類似したツリーを例示している。図30Aは分割前のツリー構造例を示し、図30Bは最初の分割後のツリー構造例を示し、図30Cは次の分割後のツリー構造例を示している。
【0177】
まず図17に示すように、ステップS001で分割キーを取得して分割キーを格納するエリアに設定する。図30Aの例示では、分割キーはノード211gのインデックスキー251gの“100011”と等しい。なお、先に述べたように、取得する分割キーは処理元に含まれる必要はないが、後に説明するように、本実施例においては取得された分割キーにより上限値あるいは下限値を求めて処理元に含まれるインデックスキーを新たな分割キーとする必要がある。したがって、以下の説明では分割キーは処理元に含まれるものとして説明する。
【0178】
次にステップS002で分割キーにより処理元の分割ノードを求める。分割ノードは、分割キーを最大値として含む部分木のうち最大のもの(以下、分割ノードツリーという。)のルートノードである。図30Aの例示では、ノード210fが分割ノードであり、点線で囲まれた部分木が分割ノードツリー291である。分割ノードを求める処理の詳細は後に図18と図19を参照して説明する。
【0179】
次にステップS003に進み、処理先は登録済みか判定する。登録済みでなければステップS004に進み、ステップS002で求めた分割ノードを処理先のルートノードに設定して処理先のルートノードとして登録し、さらにステップS007に移行して分割ノードツリーの削除処理を実行する。なお、ステップS004の処理の詳細な説明は後に図20を参照して行う。
【0180】
図30Aの例示では、分割処理が開始されたばかりであり、図30Aの(b)に示すように処理先は存在せず登録されていないから、ステップS004に進み、分割ノード210fの内容を処理先として新たに取得されたノード対201iの代表ノード210iに格納して処理先のルートノードに設定し、処理先のルートノードとして登録する。その結果として、図30Bの(b)に示すように、挿入された分割ノードツリー291からなる処理先のツリーが生成される。
【0181】
一方、図30Bの(a)には、処理元からノード211gを分割ノードとする分割ノードツリー291が削除されたツリー構造が示されており、分割ノード210bをルートノードとする次の分割ノードツリー292が点線で囲まれて示されている。
【0182】
ステップS003での判定結果が登録済みであればステップS005に移行する。ステップS005では、後記ステップS010で設定された次の分割ノードツリーの最大値である分割キーと処理先の最小値の差分ビット位置を求める。差分ビット位置を求める処理の詳細は後に図21を参照して説明する。
【0183】
図30Bの例示では、次の分割ノードツリー292の最大値はインデックスキー251c“011010”であり、処理先の最小値はインデックスキー250g“100010”であるから、差分ビット位置は“0”である。
【0184】
次にステップS006に進み、処理先のルートノードを挿入位置として処理先に分割ノードツリーを挿入し、ステップS007に進む。
ステップS007では、処理元から分割ノードツリーを削除する。そして、ステップS008に進み、次の分割ノードを求める。
【0185】
図30Cの(b)の例示では、ルートノード210iを挿入位置とし、新たに取得されたノード対201jを介して次の分割ノードツリー292が処理先に挿入されたツリー構造が示されている。また、図30Cの(a)には、図30Bの(a)に示されたツリー構造から次の分割ノードツリー292が削除された構造が示されている。
【0186】
ステップS006における分割ノードツリーの挿入処理、ステップS007における削除処理、及びステップS008における次の分割ノードを求める処理の詳細は、後にそれぞれ図22、図23、図24を参照して説明する。
【0187】
ステップS008に続いてステップS009において、ステップS008で分割ノードが求まったか判定される。分割ノードが求まらなければ分割処理は終了となる。
分割ノードが求まれば、ステップS010において、その分割ノードをルートノードとする部分木である分割ノードツリーの最大値を求めて次の分割キーとし、ステップS005に戻って次の分割ノードツリーの挿入、削除処理及び更なる次の分割ノードを求める処理を繰り返す。
【0188】
ステップS010における分割ノードの最大値を求めて次の分割キーとする処理の詳細は、後に図25を参照して説明する。
本実施例では上述のように分割ノードツリー単位で削除挿入処理が行われるため、処理ステップ数が削減される。
【0189】
次に、図18と図19を参照して図17に示すステップS002における分割ノードを求める処理を詳細に説明する。
図18は、最初の分割ノードを求める処理フローの前段を説明する図である。
【0190】
図18に示すように、ステップS1801で分割キーを検索キーとして設定し、ステップS1802で処理元のルートノードの格納された配列要素の配列番号を検索開始ノードの配列番号として設定する。
【0191】
次にステップS1803に進み、図4に示す検索処理を実行し、検索結果として分割キーと等しいインデックスキーを得て前段の処理を終了し、図19に示す後段の処理に進む。
【0192】
後段の処理は図19を参照して説明するが、その前に、図30Aを再び参照して、本実施例においては分割キーを処理元に含まれるインデックスキーとしておく必要性について説明する。
【0193】
いま、図30Aに示す処理元を分割キー“100001”で分割するとする。この分割キーで図18に示すステップS1803の検索処理を実行すると、検索結果として得られるインデックスキーはインデックスキー251gの“100011”である。ところが、分割点とすべきインデックスキーは、リーフノード211cに格納された、“100001”を上限とする上限値“011010”あるいはリーフノード211gに格納された、“100001”を下限とする下限値“100010”であり、いずれの場合も分割キー“100001”で検索した結果と一致しないからである。
【0194】
したがって、分割ノードを求める前に、分割キーをその定義に応じて処理元に含まれるインデックスキーとして求めておく必要がある。
図19は、最初の分割ノードを求める処理フローの後段を説明する図である。後段の処理は、処理元の探索経路スタックを遡り、最初のノード〔0〕の配列番号を求めて分割ノ
ードの配列番号として設定するものである。
【0195】
図19に示すように、ステップS1901で探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。探索経路スタックのスタックポインタがルートノードの配列番号を指していれば、ステップS1906に進み、ルートノードの配列番号を分割ノードの配列番号として設定して処理を終了する。
【0196】
探索経路スタックのスタックポインタがルートノードの配列番号を指していなければ、ステップS1902へ進み、探索経路スタックから配列番号を取り出し、スタックポインタを1つ減らす。
【0197】
次にステップS1903において、ステップS1902で取り出した配列番号からこの配列番号の配列要素に配置されたノードが当該ノード対のどちら側の位置であるかを得る。
【0198】
そして、ステップS1904において、ステップS1903で得たノード位置がノード〔1〕側か判定する。
判定の結果がノード〔1〕側であればステップS1901の処理に戻り、ノード〔0〕側であればステップS1905に移行してステップS1902で取り出した配列番号を分割ノードの配列番号として設定して処理を終了する。
【0199】
図30Aに示す例では、ルートノード210aの配列番号220を検索開始キーに設定して分割キー“100011”により検索処理を実行すると検索結果としてのインデックスキー251gが得られ、経路探索スタックには配列番号220、220a+1、221b、220f+1が順次スタックされる。
【0200】
したがって、図19に示すステップS1901の最初の処理時には探索経路スタックのスタックポインタは配列番号220f+1を指しており、次にステップS1904の判定処理の結果ステップS1901に戻り、次のステップS1904では1つ遡って配列番号221bのノード210fのノード位置が判定され、ステップS1905に移行してノード210fの配列番号221bが分割ノードの配列番号として設定される。
【0201】
ここで、さらに分割処理について説明する前に、分割キーは分割ノードツリーの最大値であり、分割ノードツリーは分割キーを最大値とする処理元の部分木のうち最大の部分木、別の表現をすればそのルートノードの弁別ビット位置が最上位である部分木であることを説明する。
【0202】
今までの説明から明らかなとおり、分割ノードは、分割キーで検索を行ったときの分割キーに至るまでの経路を遡って初めてのノード〔0〕である。
分割キーをインデックスキーとして含むリーフノードがノード〔0〕であれば、そのリーフノードが分割ノード自体であり、分割ノードツリーは1つのリーフノードだけから構成される。このリーフノードと対をなすノード〔1〕側に存在するリーフノードのインデックスキーは、カップルドノードツリーの順序性によって全て分割キーより大きい。したがって、今のケースの場合、分割キーより上位のブランチノードをルートノードとする部分木においては分割キーは最大値とはなりえないから、分割キーは分割ノードツリーの最大値であり、分割ノードツリーは分割キーを最大値とする処理元の部分木のうち最大のものである。
【0203】
分割キーをインデックスキーとして含むリーフノードがノード〔1〕であれば、ツリーをノード〔1〕側をたどって遡っている限りは、カップルドノードツリーの順序性により
、どのノード〔1〕をルートノードとする部分木においても上記分割キーはこれらの部分木の最大値である。そして、ノード〔0〕にまで遡ったとき、それ以上上位のノードの下位には当該ノード〔0〕と対をなすノード〔1〕以下のノードが存在し、これらのノードには上記分割キーより大きいインデックスキーを含むリーフノードが存在する。
【0204】
したがって、上記ノード〔0〕すなわち分割ノードをルートノードとする部分木が、上記分割キーを最大値として含む最大の部分木である。
以下引き続き、分割処理の説明を、図20以下を参照して行う。
【0205】
図20は、図17に示すステップS004における処理先のルートノードの挿入処理の処理フローを説明する図である。
ステップS2001において、図17に示す処理フローのステップS002で求められた分割ノードの格納された配列要素の配列番号を挿入ノードの配列番号として設定する。
【0206】
次にステップS2003で、配列から、空のノード対の代表ノード番号を取得する。
次にステップS2004で、ステップS2003で取得した代表ノード番号をノード[0]の配列番号として設定する。
【0207】
次にステップS2005において、ステップS2001で設定された挿入ノードの配列番号の指す配列要素の内容を読み出して、ステップS2004で設定されたノード[0]の配列番号の指す配列要素に格納する。
【0208】
最後にステップS2009で、ノード[0]の配列番号を処理先のルートノードの配列番号として登録して、ルートノードの挿入処理を終了する。
図30A及び図30Bの(b)の例示では、分割ノード210fの格納された配列要素の配列番号221bが挿入ノードの配列番号に設定され、取得された空のノード対201iの代表ノード番号220’ がノード[0]の配列番号として設定される。
【0209】
そして、配列番号221bが指す配列要素の内容、すなわち分割ノード210fの内容が配列番号220’の指す配列要素すなわちノード210iに格納され、配列番号220’が処理先のルートノードの配列番号として登録される。
【0210】
図21は、図17に示すステップS005における分割キーと処理先の最小値により差分ビット位置を求める処理フローを説明する図である。
図21に示すように、ステップS2101で、処理先のルートノードの配列番号を、検索開始ノードの配列番号として設定する。
【0211】
次にステップS2102において、図5に示す最小値検索を実行し、処理先のインデックスキーの最小値を得る。
次にステップS2103において、図17に示すステップS010で設定された分割キーとステップS2103で得られた最小値をビット列比較して上位0ビット目から見た最初の不一致ビット位置を求め、差分ビット位置として設定する。
【0212】
なお、上記ステップS2101においては、処理先のルートノードの配列番号を、検索開始ノードの配列番号として設定するものとしたが、最後に処理先に挿入された分割ノードツリーに処理先の最小値が含まれていることは明らかであるから、最後に挿入された分割ノード、例えば図30Bの(b)に例示した処理先においては、ノード210jの配列番号220jを検索開始ノードの配列番号として設定することにより、最小値検索の処理を軽減することができる。
【0213】
図22は、図17に示すステップS006におけるルートノード以外の処理先への挿入処理の処理フローを説明する図である。
最初にステップS2201で、図17に示す処理フローのステップS008で求められた分割ノードの格納された配列要素の配列番号を、挿入ノードの配列番号として設定する。このステップS2201は図20に示すステップS2001とは、分割ノードが求められた処理ステップがステップS008である点で異なるだけである。
【0214】
次にステップS2202において、処理先の挿入位置として、ルートノードの配列番号を設定する。
次のステップS2203〜ステップS2205は、図20に示すルートノードの挿入処理のステップS2003〜ステップS2005と同様である。
【0215】
ステップS2203で、配列から、空のノード対の代表ノード番号を取得し、次にステップS2204で、ステップS2203で取得した代表ノード番号をノード[0]の配列番号として設定し、次にステップS2205において、ステップS2201で設定された挿入ノードの配列番号の指す配列要素の内容を読み出して、ステップS2204で設定されたノード[0]の配列番号の指す配列要素に格納する。
【0216】
次にステップS2206に進み、ステップS2203で取得した代表ノード番号に値1を加えた値を、ノード[1]の配列番号として設定する。
次にステップS2207において、ステップS2202で設定した処理先の挿入位置の配列番号の指す配列要素の内容を読み出し、ステップS2206で設定したノード[1]の配列番号の指す配列要素に格納する。
【0217】
最後にステップS2208において、ノード種別にブランチを、弁別ビット位置に図17に示すステップS005で求めた弁別ビット位置を、代表ノード番号にステップS2204で設定したノード[0]の配列番号を設定してブランチノードを形成し、ステップS2202で設定した処理先の挿入位置の配列番号の指す配列要素に格納して処理を終了する。
【0218】
図30B及び図30Cの例示では、分割ノード210bの格納された配列要素の配列番号220aが挿入ノードの配列番号に設定され、処理先の挿入位置としてルートノード210iの配列番号220’が設定される。また、取得された空のノード対201jの代表ノード番号220jがノード[0]の配列番号として設定される。
【0219】
そして、挿入ノードの配列番号220aが指す配列要素の内容、すなわち分割ノード210bの内容をノード[0]の配列番号220jの指す配列要素すなわちノード210jに格納される。
【0220】
一方、代表ノード番号220jに1を加えて得た値である配列番号220j+1の指す配列要素すなわちノード211jに、処理先の挿入位置の配列番号220’の指す配列要素すなわち図30Bの(b)に示すルートノード210iの内容を格納している。
【0221】
そして図30Cの(b)に示すルートノード210iの弁別ビット位置230iには、先に図17のステップS005に関する例示で説明した分割ノードツリー292の最大値であるインデックスキー251c“011010”と処理先の最小値であるインデックスキー250g“100010”の差分ビット位置 “0”が格納されている。また、代表ノード番号には、ノード[0]の配列番号220jが格納されている。
【0222】
上記説明から理解されるように、挿入先が生成された後の挿入処理は、挿入先のルート
ノードの直下にブランチノード同士からなるノード対を挿入し、そのノード対のノード〔1〕以下に既存の処理先のルートノード以下の部分木を接続し、ノード〔0〕に分割ノードツリーを接続するものである。この処理により、分割ノードツリーを挿入後の挿入先の順序性が保たれることは明らかである。
【0223】
図23は、図17に示すステップS007における分割ノードツリーの削除処理の処理フローを説明する図である。同じ削除処理で類似している点もあるが、図16に示す削除処理は削除キーの格納されたリーフノードである削除ノードの削除であるのに対して、図23に示すものは基本的にはブランチノードである分割ノードの削除であり、処理元からは該分割ノードをルートノードとする分割ブランチノードツリーが削除される。
【0224】
まずステップS2301において、図17に示すステップS002もしくはステップS008で求めた分割ノードの配列番号を処理元の削除ノードの配列番号として設定する。
次にステップS2301で設定された削除ノードの配列番号が、処理元のルートノードの配列番号と一致するか判定する。削除ノードの配列番号が、処理元のルートノードの配列番号と一致するときは、ステップS2303に進み、処理元のルートノードの代表ノード番号の指すノード対を削除し、次にステップS2304で処理元のルートノードの配列番号の登録を抹消して処理を終了する。
【0225】
ステップS2302の判定処理の結果、削除ノードの配列番号が処理元のルートノードの配列番号と一致しないときは、ステップS2305に進み、ステップS2301で設定された削除ノードと対をなすノードの配列番号を求め、対ノードの配列番号として設定する。
【0226】
次にステップS2306において、処理元の探索経路スタックから配列番号を取り出し、その取り出した配列番号をステップS2307において親ノードの配列番号として設定するとともに、親ノードの代表ノード番号を退避する。なお、処理元の探索経路スタックには、図19に示すステップS1902あるいは後に説明する図24に示すステップS2402の処理により、分割ノードの直近上位である親ノードの配列番号が格納されている。
【0227】
次にステップS2308において、ステップS2305で設定した対ノードの配列番号の指す配列要素の内容を読み出し、ステップS2307で設定した親ノードの配列番号の指す配列要素に格納する。
【0228】
最後にステップS2309において、ステップS2307で退避した親ノードの代表ノード番号の指すノード対を削除し、処理を終了する。
図24は、図17に示すステップS008における次の分割ノードを求める処理の処理フローを説明する図である。
【0229】
ステップS2401において、処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指していれば「分割ノードなし」を返す。
【0230】
処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指していなければステップS2402に進み、探索経路スタックから配列番号を取り出し、探索経路スタックのスタックポインタを1つ減らす。
【0231】
次にステップS2403に進み、ステップS2402で取り出された配列番号から、その配列番号が指す配列要素に格納されたノードのノード位置を得る。
次にステップS2404において、ステップS2403で得たノード位置がノード〔0〕側であるか判定する。ノード〔0〕側であればステップS2401に戻り、ノード〔1〕側であればステップS2406に移行してS2402で取り出した配列番号から値1を減じて得たノード〔0〕の配列番号を、分割ノードの配列番号として設定して「分割ノードあり」を返す。
【0232】
図30A及び図30Bの例示では、次の分割ノードを求める段階では処理元の経路探索スタックのスタックポインタは分割ノード210fの親ノードの配列番号である220a+1を指しており、ノード位置がノード〔1〕側となることから、それと対を成すノード〔0〕側に位置するノード210bが次の分割ノードとなり、それの格納されている配列要素の配列番号である220aが分割ノードの配列番号として設定される。
【0233】
また、図30B及び図30Cの例示では、さらに次の分割ノードを求める段階では処理元の経路探索スタックのスタックポインタはノード210bの親ノードであるルートノード210aの配列番号220を指しているから、上記ステップS2401の判定処理の結果分割ノードなしを返す。すなわち、分割ノードの親ノードがルートノードになると次の分割ノードは存在しない。これは、カップルドノードツリーの順序性から見て当然である。
【0234】
図25は、図17に示すステップS008で求めた分割ノードをルートノードとする分割ノードツリーの最大値を求め次の分割キーとするステップS010の処理フローを説明する図である。
【0235】
始めにステップS2501において、処理元の探索経路スタックのスタックポインタの値を退避する。その理由は、図19に示すステップS1902あるいは図24に示すステップS2402の処理によって分割ノードの親ノードの配列番号を指している処理元のスタックポインタの値が、後記ステップS2503の最大値検索によって変動し、図23に示すステップS2306で用いることができなくなるからである。
【0236】
次にステップS2502において、図24のステップS2406で設定された分割ノードの配列番号を検索開始ノードの配列番号として設定する。
そしてステップS2503において、図6に示す最大値検索を実行し、インデックスキーの最大値を求める。
【0237】
次にステップS2504に進み、ステップS2502で得た最大値を分割キーとして設定する。
最後にステップS2505において、ステップS2501で退避した値を処理元の探索経路スタックのスタックポインタの値として復元して処理を終了する。
【0238】
以上、図24および図25を参照して詳細に説明したところから理解されるように、図17のステップS008で求めた次の分割ノードとステップS010で求めた次の分割キーの関係は、先に説明したステップS001で設定された分割キーとステップS002で求めた分割ノード、あるいは分割ノードツリーの関係と同様である。
【0239】
上記ステップS010で求めた次の分割キーがステップS008で求めた次の分割ノードをルートノードとする分割ノードツリーの最大値であることは自明である。また、ステップS008で求めた次の分割ノードはノード〔0〕であるから、それより上位のノードをルートノードとする部分木は、ステップS010で求めた次の分割キーより大きいインデックスキーを格納したリーフノードを含むことも、カップルドノードツリーの順序性により明らかである。
【0240】
以上により、実施例3によるカップルドノードツリーの分割処理について詳細に説明しが、実施例3によれば、分割ノードツリー単位で分割処理が行われる。すなわち、分割ノードを処理元から分離し、分割ノードの対ノードを親ノードに複写することにより分割ノードツリーが処理元から削除され、分割ノードを処理先に挿入することにより分割ノードツリーの挿入が完成する。
【0241】
したがって、同じ配列を用いている限りは、分割ノード以外のノードについての処理は不要であり、実施例2の場合よりも処理の実行ステップ数がさらに少なくてすむ。
次に分割処理と同様に部分木単位で処理を行う実施例3によるカップルドノードツリーの結合処理を説明する。本実施例の結合処理は、実施例1及び実施例2の結合処理と大きく異なり、実施例1及び実施例2の結合処理がインデックスキー単位、言い換えればノード単位で結合処理を行うものであるのに対して、所定の条件を満たす部分木単位で処理元から分割して処理先に結合するものである。実施例1及び実施例2の結合処理では分割キーを選択することにより分割処理をそのまま適用できたのに対して、本実施例のように部分木単位で結合処理を行おうとすると、単純に分割処理を適用することができない。
【0242】
それは、処理元及び処理先はそれぞれの内部に格納されたインデックスキーの差分ビット位置に応じた構造を有しており、処理元自体を分割ノードツリーとしてそのまま処理先に挿入することができるとは限らないからである。
【0243】
図26は、実施例3におけるカップルドノードツリーの結合処理フローを説明する図である。以下の説明では、処理先のインデックスキーは処理元のインデックスキーより大きいとするが、その逆でも同様に処理が可能であることは、下記の説明から容易に理解されるものである。
【0244】
図31A〜図31Cは、上記結合処理を実例により説明する図であり、図2に例示したカップルドノードツリーの部分木と類似したツリーが例示されている。
図31Aは結合処理開始前の処理元と処理先のツリーの構造例を示す図である。図31Aの(a)には処理元が例示され、その配列番号の符号220a+1が付された分割結合ノードとそれをルートノードとする部分木であり、結合処理の単位となる部分木である分割結合ノードツリー293が示されている。以後、ノードを示す符号を、そのノードを検索処理でたどったときに経路探索スタックにスタックされるそのノードが配置された配列要素の配列番号で表すことがある。
【0245】
図31Aの(b)には処理先が例示され、結合位置となるノードがその配列番号の符号221fを付して示されている。また、図31Aには、処理元の最大値がインデックスキー251gの“101001”であること、処理先の最小値がインデックスキー250hの“101011”であることも示されている。
【0246】
図31Bは、図31Aに示す分割結合ノードツリー293を処理先に挿入し、処理元から削除したツリー構造を示す図である。図31Bの(a)には処理元の次の分割結合ノードツリー294が点線で囲われて示され、最大値がインデックスキー251dの“011010”であることが示されている。図31Bの(b)には、処理先の結合された分割ノードツリー293、結合処理により追加されたノード対201kとノード221fのリンク関係がそれぞれ点線で囲われて示され、次の結合位置がノード221であることが示されている。
【0247】
図31Cは、図31Bに示す分割結合ノードツリー294を処理先に挿入し、処理元から削除したツリー構造を示す図である。図31Bの(a)に示す処理元の次ぎ分割結合ノ
ード220がルートノードであるため、処理元のルートノードは削除され、図31Cの(a)には何も表示されていない。図31Cの(b)には、処理先の結合された分割ノードツリー294、結合処理により追加されたノード対201mとノード221のリンク関係がそれぞれ点線で囲われて示されている。
【0248】
以下、図26及び図31A〜図31Cを参照して本実施例の結合処理の概要を説明する。
図26のステップS2601において、処理元の最大値と処理先の最小値の差分ビット位置を求める。図31Aの例示では、処理元の最大値“101001”と処理先の最小値“101011”の差分ビット位置4が求められる。差分ビット位置を求める処理の詳細は、後に図27を参照して説明する。なお、以下の説明では、このステップS2601で求めた差分ビット位置を単に差分ビット位置ということがある。
【0249】
次にステップS2602で、ステップS2601で求めた差分ビット位置により、処理元の分割結合ノードを求める。図31Aの例示では、分割結合ノード220a+1が求められている。この処理の詳細は、後に図28を参照して説明する。
【0250】
次にステップS2603に進み、ステップS2601で求めた差分ビット位置により、ステップS2602で求めた分割結合ノードを挿入するための処理先の結合位置を求める。図31Aの例示では、結合位置221fが求められている。この処理の詳細は、後に図29を参照して説明する。
【0251】
次にステップS2604において、ステップS2603で求めた結合位置にステップS2602で求めた分割結合ノードを挿入する。この処理は、図22を参照して説明をした挿入処理において、ステップS2201の挿入ノードの配列番号としてステップS2602で求めた分割結合ノードの配列番号を設定し、ステップS2202の処理先の挿入位置にステップSS2603で求めた結合位置の配列番号を設定して該挿入処理を実行することにより実現される。
【0252】
図31A及び図31Bの例示では、図22のステップS2201において分割結合ノード220a+1の配列番号220a+1が挿入ノード設定エリアに設定され、ステップS2202において挿入位置設定エリアに結合位置221fの配列番号221fが設定される。次にステップS2203において、空きのノード対201kが取得され、その代表ノード番号220kがステップS2204においてノード〔0〕の配列番号として設定される。
【0253】
そして、ステップS2205において、挿入ノード設定エリアに設定された配列番号220a+1が指す配列要素の内容、すなわち分割結合ノード221bの内容を読み出して、ノード〔0〕の配列番号として設定されている配列番号220kの指す配列要素、すなわちノード210kに格納する。
【0254】
さらにステップS2206において、代表ノード番号220kに1を加えた値である220k+1をノード〔1〕の配列番号として設定する。そしてステップS2207で挿入位置として設定されている配列番号221fの指す配列要素、すなわちノード210hの内容を読み出し、ノード〔1〕の配列番号として設定された配列番号220k+1の指す配列要素、すなわちノード211kに格納する。
【0255】
最後にステップS2208において、挿入位置として設定されている配列番号221fの指す配列要素、すなわちノード210hの位置に、ノード種別に0、弁別ビット位置に図26のステップS2601で求めた差分ビット位置4、代表ノード番号にノード〔0〕
の配列番号として設定されている配列番号220kを設定して新たなブランチノードを生成し、図31Bの(b)に示す結合後の処理先の構造が得られている。
【0256】
次に図26によるツリー結合処理の説明に戻ると、ステップS2605において、処理元より分割結合ノードを削除する。この処理は、図23を参照して説明した削除処理において、分割ノードを分割結合ノードと読み替えて実行することにより実現される。
【0257】
次にステップS2606に進み、処理元が登録されているか判定する。登録されていればステップS2601に戻って処理を繰り返し、登録されていなければ結合処理は完了したので処理を終了する。
【0258】
次に、本実施例の結合処理を図27〜図29を参照して詳細に説明する。
図27は、図26に示すステップS2601の差分ビット位置を求める処理の詳細な処理フローを説明する図である。まず、ステップS2701において、処理元のルートノードの配列番号を検索開始ノードの配列番号に設定する。次にステップS2702において、図6に示す検索処理により、処理元のインデックスキーの最大値を求める。
【0259】
次にステップS2703に進み、処理先のルートノードの配列番号を、検索開始ノードの配列番号に設定する。次にステップS2704において、図5に示す検索処理により、処理先のインデックスキーの最小値を求める。
【0260】
次にステップS2705において、ステップS2702で求めた最大値とステップS2704で求めた最小値のビット列比較を行い、上位0ビット目から見た最初の不一致ビットの位置を求め、差分ビット位置に設定して処理を終了する。
【0261】
先に述べたように、図31Aの例示では、処理元の最大値“101001”と処理先の最小値“101011”の差分ビット位置4が求められる。そして、処理元にも処理先にも、弁別ビット位置がこの差分ビット位置と等しいブランチノードは存在しない。
【0262】
なぜならば、処理元の最大値より処理先の最小値が大きいことから処理元の最大値の差分ビット位置のビット値は0であり、もし、処理元のブランチノードに弁別ビット位置が差分ビット位置と等しいものがあるとすると処理元の最大値がノード〔0〕となり、最大値であることと矛盾するからである。処理先についても同様である。
【0263】
次に、処理元の分割結合ノードを求める処理を説明する。分割結合ノードは、処理元がルートノードだけであるという例外を除けば、最大値検索でたどったブランチノードのうち、弁別ビット位置が図26に示すステップS2601で求めた差分ビット位置より下位であるもののうち最上位であるブランチノードである。
【0264】
分割結合ノードをルートノードとする処理元の部分木を分割結合ノードツリーということにすると、本実施例の結合処理は、分割結合ノードツリー単位で結合処理を行うものである。
【0265】
図28は、図26に示すステップS2602の処理元の分割結合ノードを求める処理フローを説明する図である。なお、分割結合ノードを求める処理の開始時には、処理元の探索経路スタックのスタックポインタは図26に示すステップS2601における最大値検索の結果、インデックスキーの最大値を格納したリーフノードの配列番号を指している。
【0266】
ステップS2801において、処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。処理元の探索経路スタックのスタックポイン
タがルートノードの配列番号を指している場合にはステップS2810に進み、処理元の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合にはステップS2802に進む。
【0267】
ステップS2802では探索経路スタックのスタックポインタを1つ戻してそのスタックポインタが指す配列番号を取り出してステップS2803に進む。
ステップS2803ではステップS2802で取り出した配列番号の指す配列要素の内容をノードとして取り出し、ステップS2304において取り出したノードの弁別ビット位置を取得する。
【0268】
次にステップS2805において、ステップS2804で取得した弁別ビット位置が差分ビット位置より上位の位置関係か判定する。下位であればステップS2801に戻り、上位であればステップS2809に進む。先に述べたように、上述の弁別ビット位置と差分ビット位置が等しいことはない。
【0269】
ステップS2809においては、処理元の探索経路スタックのスタックポインタを1つ進め、ステップS2810に移行する。
ステップS2810においては、処理元の経路探索スタックから、スタックポインタの指す配列番号を取り出し、処理元の分割結合ノードの配列番号として設定して処理を終了する。なお、以下の説明において、ここで設定された配列番号を単に分割結合ノードの配列番号ということがある。
【0270】
上記処理を図31A及び図31Bを参照して説明すると以下のとおりである。
図31Aの例示においては、キーの最大値を格納したノード211gから探索経路を遡ると、始めはスタックポインタがノード211gの配列番号221bを指しているのでステップS2801の判定は「いいえ」となって、ステップS2801からの処理を繰り返し、差分ビット位置が4であることからステップS2802の処理でルートノード210aまで至り、ルートノード210aの弁別ビット位置が0であって差分ビット位置より上位であるからステップS2805の判定処理でステップS2809に分岐し、ステップS2809の処理により探索経路を1つ進めて分割結合ノード220a+1が求められる。
【0271】
図31Bの例示においては、キーの最大値を格納したノード211dから探索経路を遡ると、差分ビット位置が0であることからステップS2802の処理でルートノード210aまで至り、ルートノード210aの弁別ビット位置が1であって差分ビット位置より下位であるからステップS2805の判定処理でステップS2801に分岐し、ステップS2801の判定処理でルートノードと判定されてステップS2810に分岐し、ルートノード210aが次の分割結合ノードとして求められる。
【0272】
次に、処理先の結合位置を求める処理を説明する。結合処理後の処理先には処理元のインデックスキーの最大値を格納したリーフノードが挿入されることから、差分ビット位置と等しい値の弁別ビット位置を持つブランチノードが新しく存在する。すなわち、差分ビット位置と等しい値の弁別ビット位置を持つブランチノードを最小値検索でたどった経路中に挿入することになるが、この挿入位置を処理先の結合位置とする。
【0273】
カップルドノードツリーにおいては、下位のブランチノードの弁別ビット位置は上位のブランチノードの弁別ビット位置より下位であることから、差分ビット位置より直近上位の弁別ビット位置を持つブランチノードの子ノードの位置かあるいは例外的に上位の弁別ビット位置を持つブランチノードがなければルートノードが結合位置となる。
【0274】
結合位置に挿入されたブランチノードの子ノード対のノード〔1〕側には結合前の処理
先のインデックスキーの最小値を格納したリーフノードが存在し、ノード〔0〕は分割結合ノードである。
【0275】
図29は、上記処理先の結合位置を求める処理フローを説明する図である。図29に示すように、処理先の結合位置を求める処理フローは、図28に示す処理元の分割結合ノードを求める処理フローと同じ構造である。図29の処理フローは処理先についてのものであり、求めるものは結合位置であることで異なるだけである。なお、処理先の結合位置を求める処理の開始時には、処理先の探索経路スタックのスタックポインタは図26に示すステップS2601における最小値検索の結果、インデックスキーの最小値を格納したリーフノードの配列番号を指している。
【0276】
ステップS2901において、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指している場合にはステップS2910に進み、処理先の探索経路スタックのスタックポインタがルートノードの配列番号を指していない場合にはステップS2902に進む。
【0277】
ステップS2902では探索経路スタックのスタックポインタを1つ戻して配列番号を取り出してステップS2903に進む。
ステップS2903ではステップS2902で取り出した配列番号の指す配列要素の内容をノードとして取り出し、ステップS2904において、取り出したノードの弁別ビット位置を取得する。
【0278】
次にステップS2905において、ステップS2904で取得した弁別ビット位置が差分ビット位置より上位の位置関係か判定する。下位であればステップS2901に戻り、上位であればステップS2909に進む。先に述べたように、上述の弁別ビット位置と差分ビット位置が等しいことはない。
【0279】
ステップS2909においては、処理元の探索経路スタックのスタックポインタを1つ進め、ステップS2910に移行する。
ステップS2910においては、処理先の経路探索スタックから、スタックポインタの指す配列番号を取り出し、処理先の結合位置の配列番号として設定して処理を終了する。なお、以下の説明において、ここで設定された配列番号を単に結合位置の配列番号ということがある。
【0280】
上記処理を図31A及び図31Bを参照して説明すると以下のとおりである。
図31Aの例示においては、キーの最小値を格納したノード210hから探索経路を遡ると、差分ビット位置が4でありステップS2904で取り出すルートノード210fの弁別ビット位置が3であることからステップS2905からステップS2909に分岐し、ステップS2909の処理により探索経路を1つ進めて結合位置の配列番号221fが求められる。
【0281】
図31Bの例示において、キーの最小値を格納したノード210gから探索経路を遡ると、差分ビット位置が0であることからルートノード210fまで至り、ステップS2901において、ルートノードであると判定されてステップS2910に分岐し、ルートノード210fの配列番号221が次の結合位置の配列番号として求められる。
【0282】
以上により、実施例3によるカップルドノードツリーの結合処理について詳細に説明しが、実施例3によれば、分割結合ノードツリー単位で結合処理が行われる。すなわち、分割結合ノードを処理元から分離し、分割結合ノードの対ノードを親ノードに複写すること
により分割結合ノードツリーが処理元から削除され、分割結合ノードを処理先に結合することにより分割結合ノードツリーの結合が完成する。
【0283】
したがって、同じ配列を用いている限りは、分割結合ノード以外のノードについての処理は不要であり、実施例2の場合よりも処理の実行ステップ数がさらに少なくてすむ。
以上本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
【0284】
以上に説明した本発明の実施の形態によるカップルドノードツリーの分割結合処理及びその均等物をコンピュータに実行させるプログラムにより、本発明のカップルドノードツリーの分割方法及び結合方法が実現可能であることも明らかである。
【0285】
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。
【図面の簡単な説明】
【0286】
【図1】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図2】カップルドノードツリーのツリー構造を概念的に示す図である。
【図3】本発明を実施するためのハードウェア構成例を説明する図である。
【図4】ビット列検索の基本動作を示したフローチャートである。
【図5】カップルドノードツリーに格納されたインデックスキーの最小値を求める処理を示したフローチャートである。
【図6】カップルドノードツリーに格納されたインデックスキーの最大値を求める処理を示したフローチャートである。
【図7A】インデックスキーの下限値を求める処理の前段を示したフローチャートである。
【図7B】インデックスキーの下限値を求める処理の後段を示したフローチャートである。
【図8A】インデックスキーの上限値を求める処理の前段を示したフローチャートである。
【図8B】インデックスキーの上限値を求める処理の後段を示したフローチャートである。
【図9A】挿入処理の前段である検索処理の処理フローを示す図である。
【図9B】挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
【図9C】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フローを示す図である。
【図10】ルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー図である。
【図11A】削除処理の前段である検索処理の処理フローを示す図である。
【図11B】削除処理の後段の処理フローを説明する図である。
【図12】実施例1におけるカップルドノードツリーの分割処理フローを説明する図である。
【図13】実施例2におけるカップルドノードツリーの分割処理フローを説明する図である。
【図14】実施例2におけるノードの挿入処理フローを説明する図である。
【図15A】実施例2におけるルートノード設定処理を説明するフロー図である。
【図15B】実施例2における親ノードに挿入キーを含むノード対を挿入する処理フローを説明する図である。
【図16】実施例2における削除処理を説明するフロー図である。
【図17】実施例3におけるカップルドノードツリーの分割処理フローを説明する図である。
【図18】最初の分割ノードを求める処理フローの前段を説明する図である。
【図19】最初の分割ノードを求める処理フローの後段を説明する図である
【図20】処理先のルートノードの挿入処理の処理フローを説明する図である。
【図21】分割処理での差分ビット位置を求める処理フローを説明する図である。
【図22】ルートノード以外の挿入処理の処理フローを説明する図である。
【図23】実施例3における削除処理の処理フローを説明する図である。
【図24】次の分割ノードを求める処理の処理フローを説明する図である。
【図25】分割ノードツリーの最大値を求め次の分割キーとする処理の処理フローを説明する図である。
【図26】実施例3におけるカップルドノードツリーの結合処理フローの概要を説明する図である。
【図27】結合処理での差分ビット位置を求める処理フローを説明する図である。
【図28】処理元の分割結合ノードを求める処理フローを説明する図である。
【図29】処理先の結合位置を求める処理フローを説明する図である。
【図30A】分割前のツリー構造例を説明する図である。
【図30B】最初の分割後のツリー構造例を説明する図である。
【図30C】次の分割後のツリー構造例を説明する図である。
【図31A】最初の結合処理前のツリー構造例を説明する図である。
【図31B】最初の結合しょり後のツリー構造例を説明する図である。
【図31C】次の結合処理後のツリー構造例を説明する図である。
【図32】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【符号の説明】
【0287】
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】
請求項1に記載のカップルドノードツリーの分割方法において、
前記最小値あるいは最大値取得ステップは、前記処理元カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるステップであることを特徴とするカップルドノードツリーの分割方法。
【請求項3】
請求項1又は請求項2に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次スタックに保持されていくものであり、
前記生成ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値を前記処理先カップルドノードツリーの挿入キーとして設定し、
前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている配列番号のブランチノードの弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である処理先親ノードを決定し、
該処理先親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの分割方法。
【請求項4】
請求項3に記載のカップルドノードツリーの分割方法において、
前記生成ステップは、さらに前記処理先親ノードを、挿入キーを含むリーフノードを挿入した挿入済みノードとして設定するステップを含み、
前記処理先最大値あるいは最小値取得ステップは、前記挿入済みノードを検索開始ノードとして前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得するものであることを特徴とするカップルドノードツリーの分割方法。
【請求項5】
請求項4に記載のカップルドノードツリーの分割方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの分割方法。
【請求項6】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された2つのカッ
プルドノードツリーの結合方法において、
前記2つのカップルドノードツリーの一方の処理元カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理元最小値あるいは最大値取得ステップと、
前記2つのカップルドノードツリーの他方の処理先カップルドノードツリーに前記最小値あるいは最大値のインデックスキーを挿入する挿入ステップと、
前記処理元カップルドノードツリーから前記最小値あるいは前記最大値のインデックスキーを削除する削除ステップと、
を備え、
前記最小値あるいは前記最大値のインデックスキーを削除した前記処理元カップルドノードツリーを新たな処理元カップルドノードツリーとした前記処理元最小値あるいは最大値取得ステップ、前記挿入ステップ及び前記削除ステップを前記処理元カップルドノードツリーがすべて削除されるまで繰り返すことを特徴とするカップルドノードツリーの結合方法。
【請求項7】
請求項6に記載のカップルドノードツリーの結合方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次スタックに保持されていくものであり、
前記挿入ステップは、
前記最小値あるいは前記最大値を前記処理先カップルドノードツリーの挿入キーとして設定し、
前記処理先カップルドノードツリーのインデックスキーの最大値あるいは最小値を取得する処理先最大値あるいは最小値取得ステップを実行し、
前記挿入キーと前記インデックスキーの最大値あるいは最小値との間でビット列比較を行って異なるビット値となる先頭のビット位置を求め、
該ビット位置と前記スタックに格納されている配列番号のブランチノードの弁別ビット位置との相対的位置関係により、前記挿入キーを保持するリーフノードを含むノード対の挿入位置である親ノードを決定し、
該親ノードの前記位置情報を、前記挿入キーを保持するリーフノードを含むノード対の代表ノードが格納されている配列要素の配列番号とする、
ステップを含むものであること、
を特徴とするカップルドノードツリーの結合方法。
【請求項8】
請求項7に記載のカップルドノードツリーの結合方法において、
前記削除ステップは、
前記処理元最小値あるいは最大値取得ステップで求めた最小値あるいは最大値をインデックスキーとして含むリーフノードを前記処理元カップルドノードツリーの削除ノードとして設定し、
前記削除ノートと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ステップを含むものであることを特徴とするカップルドノードツリーの結合方法。
【請求項9】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり

前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された、カップルドノードツリーの分割方法において、
分割対象である処理元カップルドノードツリーを分割する分割キーを取得するステップと、
前記処理元カップルドノードツリーの部分木であって前記分割キーをその最大値あるいは最小値とするもののうちで最大の部分木のルートノードである分割ノードを求める分割ノード取得ステップと、
前記分割ノードをルートノードとする部分木である分割ノードツリーを挿入することにより新たな処理先のカップルドノードツリーを生成するする生成ステップと、
前記分割ノードツリーを前記処理元カップルドノードツリーから削除する削除ステップ
を含むことを特徴とするカップルドノードツリーの分割方法。
【請求項10】
請求項9に記載のカップルドノードツリーの分割方法において、
前記分割ノード取得ステップは、前記処理元のルートノードを前記検索開始ノードとし、前記分割キーを前記検索キーとして検索を行い、前記ルートノードから前記分割キーに至る検索におけるリンク経路上のブランチノードであって該ブランチノードからの全てのリンク先のノードに前記分割キーより大きいあるいは小さいインデックスキーを含むリーフノードが存在せず、かつカップルドノードツリー上で最も上位にあるブランチノードを前記分割ノードとして取得することを特徴とするカップルドノードツリーの分割方法。
【請求項11】
請求項10に記載のカップルドノードツリーの分割方法において、
前記ルートノードから前記分割ノードに至る前記リンク経路のブランチノードと前記ノード対をなすノードであって、該ノードよりカップルドノードツリー上で下位の全てのリーフノードが前記分割キーより大きいあるいは小さいインデックスキーを含まず、かつカップルドノードツリー上で最も上位にあるノードを次の分割ノードとして取得する次分割ノード取得ステップを備え、
前記分割ノードを前記次の分割ノードとして前記生成ステップと前記削除ステップを実行することを特徴とするカップルドノードツリーの分割方法。
【請求項12】
請求項10又は請求項11に記載のカップルドノードツリーの分割方法において、
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次スタックに保持されていくことを特徴とするカップルドノードツリーの分割方法。
【請求項13】
請求項12に記載のカップルドノードツリーの分割方法において、
前記分割ノード取得ステップは、前記スタックに格納された配列番号を、前記代表ノードの格納された配列要素の配列番号となるまで、あるいは前記代表ノードと対をなすノードの格納された配列要素の配列番号となるまで順次読み出し、該読み出した前記代表ノードの格納された配列要素の配列番号あるいは前記代表ノードと対をなすノードの格納され
た配列要素の配列番号の配列要素に格納されたノードを前記分割ノードとして取得することを特徴とするカップルドノードツリーの分割方法。
【請求項14】
請求項13に記載のカップルドノードツリーの分割方法において、
前記次分割ノード取得ステップは、前記スタックに格納された、前記分割ノードの格納された配列要素の配列番号より前に格納された配列番号を、前記代表ノードと対をなすノードの格納された配列要素の配列番号となるまで、あるいは前記代表ノードの格納された配列要素の配列番号となるまで順次読み出し、該読み出した前記代表ノードと対をなすノードの格納された配列要素の配列番号あるいは前記代表ノードの格納された配列要素の配列番号の配列要素に格納されたノードと対をなすノードを前記次の分割ノードとして取得することを特徴とするカップルドノードツリーの分割方法。
【請求項15】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが1つのときは前記リーフノード、ツリーのノードが2つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索結果である検索結果キーとするように構成された2つのカップルドノードツリーの結合方法において、
前記2つのカップルドノードツリーの一方の処理元カップルドノードツリーのインデックスキーの最大値あるいは最小値を求める処理元最大値あるいは最小値取得ステップと、
前記2つのカップルドノードツリーの他方の処理先カップルドノードツリーのインデックスキーの最小値あるいは最大値を求める処理先最小値あるいは最大値取得ステップと、
前記処理元最大値あるいは最小値取得ステップで求めた処理元カップルドノードツリーのインデックスキーの最大値あるいは最小値と前記処理先最小値あるいは最大値取得ステップで求めた処理先カップルドノードツリーのインデックスキーの最小値あるいは最大値の差分ビット位置を求める差分ビット位置取得ステップと、
前記差分ビット位置取得ステップで求めた差分ビット位置に基づき前記処理元から分割して処理先に結合する部分木のルートノードである分割結合ノードを求める分割結合ノード取得ステップと、
前記差分ビット位置取得ステップで求めた差分ビット位置に基づき分割結合ノード取得ステップで求めた分割結合ノードを結合する処理先の結合位置を求める結合位置取得ステップと、
前記分割結合ノード取得ステップで求めた分割結合ノードを前記結合位置取得ステップで求めた処理先の結合位置に挿入する挿入ステップと、
前記分割結合ノード取得ステップで求めた分割結合ノードを前記処理元カップルドノードツリーから削除する削除ステップと、
を含むことを特徴とするカップルドノードツリーの結合方法。
【請求項16】
請求項15に記載のカップルドノードツリーの結合方法において、
前記処理元最大値あるいは最小値取得ステップは、前記処理元カップルドノードツリー
のルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理元カップルドノードツリーのインデックスキーの最大値あるいは最小値を求めるステップであり、
前記処理先最小値あるいは最大値取得ステップは、前記処理先カップルドノードツリーのルートノードを検索開始ノードとして前記ノード対のうち、該ノード対を構成する2つのノードのうちの代表ノードのみあるいは代表ノードと隣接した記憶領域に配置されたノードのみをリンクしてリーフノードに至ることにより、前記処理先カップルドノードツリーのインデックスキーの最小値あるいは最大値を求めるステップであることを特徴とするカップルドノードツリーの結合方法。
【請求項17】
請求項16に記載のカップルドノードツリーの結合方法において、
前記処理元カップルドノードツリー及び処理先カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応するノードが格納された前記配列の配列要素の配列番号であり、
前記処理元最大値あるいは最小値取得ステップ及び前記処理先最小値あるいは最大値取得ステップにおける前記検索開始ノードの格納された配列要素の配列番号及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの格納された配列要素の配列番号は、順次それぞれ処理元のスタック及び処理先のスタックに保持されていくことを特徴とするカップルドノードツリーの結合方法。
【請求項18】
請求項17に記載のカップルドノードツリーの結合方法において、
前記分割結合ノード取得ステップは、前記処理元のスタックに格納された配列番号の1つ前に格納された配列番号から、該配列番号の配列要素に格納されたブランチノードの弁別ビット位置が前記差分ビット位置より上位になるまで読み出し、該読み出した配列要素の次に前記処理元のスタックに格納された配列番号の配列要素に格納されたノードを分割結合ノードとして求め、
前記結合位置取得ステップは、前記処理先のスタックに格納された配列番号の1つ前に格納された配列番号から、該配列番号の配列要素に格納されたブランチノードの弁別ビット位置が前記差分ビット位置より上位になるまで読み出し、該読み出した配列要素の次に前記処理先のスタックに格納された配列番号の配列要素に格納されたノードを結合位置として求めることを特徴とするカップルドノードツリーの結合方法。
【請求項19】
請求項1〜18のいずれか1つに記載のカップルドノードツリーの分割方法あるいはカップルドノードツリーの結合方法をコンピュータに実行させるためのプログラム。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7A】
image rotate

【図7B】
image rotate

【図8A】
image rotate

【図8B】
image rotate

【図9A】
image rotate

【図9B】
image rotate

【図9C】
image rotate

【図10】
image rotate

【図11A】
image rotate

【図11B】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15A】
image rotate

【図15B】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30A】
image rotate

【図30B】
image rotate

【図30C】
image rotate

【図31A】
image rotate

【図31B】
image rotate

【図31C】
image rotate

【図32】
image rotate


【公開番号】特開2008−159025(P2008−159025A)
【公開日】平成20年7月10日(2008.7.10)
【国際特許分類】
【出願番号】特願2007−169459(P2007−169459)
【出願日】平成19年6月27日(2007.6.27)
【出願人】(506235616)株式会社エスグランツ (32)
【Fターム(参考)】