カップルドノードツリーのインデックスキー挿入／削除方法
【課題】探索経路スタックを用いないカップルドノードツリーのインデックスキー挿入／削除方法を提供する。
【解決手段】ノード対の挿入位置を決定するに際して、挿入するインデックスキーによる検索を再度開始するとともに、各リンク先ノードであるブランチノードの弁別ビット位置が検索結果キーとのビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、ブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定するとそのブランチノードをノード対の挿入位置とする。削除処理においては、リンク元の配列番号の退避領域を利用する。
【解決手段】ノード対の挿入位置を決定するに際して、挿入するインデックスキーによる検索を再度開始するとともに、各リンク先ノードであるブランチノードの弁別ビット位置が検索結果キーとのビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、ブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定するとそのブランチノードをノード対の挿入位置とする。削除処理においては、リンク元の配列番号の退避領域を利用する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビット列からなるインデックスキーの集合から所望のインデックスキーを検索するために用いられるカップルドノードツリーのインデックスキーの挿入及び削除に関するものである。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【０００３】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【０００４】
図１は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【０００５】
図１の例では、インデックスキー”100010”を保持するノード1750aがルートノードとなっており、その検査ビット位置は０である。ノード1750aの左リンク1740aにはノード1750bが接続され、右リンク1741aにはノード1750fが接続されている。
【０００６】
ノード1750bの保持するインデックスキーは”010011”であり、検査ビット位置1730bは１である。ノード1750bの左リンク1740bにはノード1750cが、右リンク1741bにはノード1750dが接続されている。ノード1750cが保持するインデックスキーは”000111”、検査ビット位置は３である。ノード1750dが保持するインデックスキーは”011010”、検査ビット位置は２である。
【０００７】
ノード1750cから実線で接続された部分はノード1750cの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ1740cは、その欄が空欄であることを示している。点線の接続された右ポインタ1741cの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード1750cを右ポインタが指定していることを表している。
【０００８】
ノード1750dの右ポインタ1741dはノード1750d自身を指しており、左リンク1740dにはノード1750eが接続されている。1750eの保持するインデックスキーは”010010”、検査ビット位置は５である。ノード1750eの左ポインタ1740eはノード1750bを、右ポインタ1741eはノード1750eを指している。
【０００９】
また、ノード1750fの保持するインデックスキーは”101011”であり、検査ビット位置1730fは２である。ノード1750fの左リンク1740fにはノード1750gが、右リンク1741fにはノード1750hが接続されている。
【００１０】
ノード1750gの保持するインデックスキーは”100011”であり、検査ビット位置1730gは５である。ノード1750gの左ポインタ1740gはノード1750aを、右ポインタ1741gはノード1750gを指している。
【００１１】
ノード1750hの保持するインデックスキーは”101100”であり、検査ビット位置1730hは３である。ノード1750hの左ポインタ1740hはノード1750fを、右ポインタ1741hはノード1750hを指している。
図１の例では、ルートノード1750aからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
【００１２】
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が１であるか０であるか判定を行い、１であれば右リンクをたどり、０であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば（図１において点線で示されたこの逆戻りのリンクをバックリンクという。)、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【００１３】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は１回ですむことなどのメリットがあるが、各ノードからの２つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【００１４】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献１に開示された技術がある。下記特許文献１に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【００１５】
また、下記特許文献２には、必要とする記憶容量が小さく、検索速度が高速であり、データメンテナンスの容易なデータ構造であるカップルドノードツリーが開示されている。
以下、特許文献２に記載されたカップルドノードツリーを配列に格納する例について説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【００１６】
図２Ａは、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図２Ａを参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード種別102、弁別ビット位置103及び代表ノード番号104で構成されている。ノード種別102は０であり、ノード101がブランチノードであることを示している。弁別ビット位置103には１が格納されている。代表ノード番号104にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【００１７】
配列番号２０の配列要素には、ノード対111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1）に代表ノードと対になるノード[1]113が格納されている。ノード[0]112のノード種別114には０が、弁別ビット位置115には３が、代表ノード番号116には３０が格納されている。またノード[1]113のノード種別117には１が格納されており、ノード[1]113がリーフノードであることを示している。インデックスキー118には、”0001”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
なお、代表ノードをノード[0]で表し、それと対になるノードをノード[1]で表すことがある。
配列番号30及び31の配列要素に格納されたノード122とノード123からなるノード対121の内容は省略されている。
【００１８】
ノード[0]112、ノード[1]113、ノード122、及びノード123の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【００１９】
図２Ｂは、カップルドノードツリーのツリー構造を概念的に示す図である。図示の６ビットのインデックスキーは、図１に例示されたパトリシアツリーのものと同じである。
符号210aで示すのがルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード対201ａの代表ノードとしている。
【００２０】
ツリー構造としては、ルートノード210ａの下にノート対201bが、その下層にノード対201cとノード対201fが配置され、ノード対201fの下層にはノード対201hとノード対201gが配置されている。ノード対201cの下にはノード対201dが、さらにその下にはノード対201eが配置されている。
【００２１】
各ノードの前に付された０あるいは１の符号は、図２Ａにおいて説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００２２】
図示された例では、ルートノード210aのノード種別260aは０でブランチノードであることを示し、弁別ビット位置230aは０を示している。代表ノード番号は220aであり、それはノード対201bの代表ノード210bの格納された配列要素の配列番号である。
【００２３】
ノード対201bはノード210bと211bで構成され、それらのノード種別260b、261bはともに０であり、ブランチノードであることを示している。ノード210bの弁別ビット位置230bには１が格納され、リンク先の代表ノード番号にはノード対201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。
【００２４】
ノード210cのノード種別260cには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー250ｃには”000111”が格納されている。一方ノード211cのノード種別261cは０、弁別ビット位置231cは２であり、代表ノード番号にはノード対201dの代表ノード210dの格納された配列要素の配列番号221cが格納されている。
【００２５】
ノード210dのノード種別260dは０、弁別ビット位置230dは５であり、代表ノード番号にはノード対201ｅの代表ノード210ｅの格納された配列要素の配列番号220dが格納されている。ノード210dと対になるノード211dのノード種別261dは１であり、インデックスキー251dには”011010”が格納されている。
【００２６】
ノード対201eのノード210e、211eのノード種別260e、261eはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー250e、251eにはインデックスキーとして”010010”と”010011”が格納されている。
【００２７】
ノード対201bのもう一方のノードであるノード211bの弁別ビット位置231bには２が格納され、リンク先の代表ノード番号にはノード対201fの代表ノード210fの格納された配列要素の配列番号221bが格納されている。
【００２８】
ノード対201fのノード210f、211fのノード種別260f、261fはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置230f、231fには５、３が格納されている。ノード210fの代表ノード番号にはノード対201gの代表ノード210gの格納された配列要素の配列番号220fが格納され、ノード211fの代表ノード番号にはノード対201hの代表ノードであるノード[0]210hの格納された配列要素の配列番号221fが格納されている。
【００２９】
ノード対201gのノード210g、211gのノード種別260g、261gはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー250g、251gには”100010”と”100011”が格納されている。
【００３０】
また同じくノード対201hの代表ノードであるノード[0]210hとそれと対をなすノード[1]211hのノード種別260h、261hはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー250h、251hには”101011”と”101100”が格納されている。
【００３１】
以下、上述のツリーからインデックスキー”100010”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列”100010”を検索キーとしてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは０であるので、検索キー”100010”の弁別ビット位置０のビット値をみると１である。そこで代表ノード番号の格納された配列番号220aに１を加えた配列番号の配列要素に格納されたノード211bにリンクする。ノード211bの弁別ビット位置231bには２が格納されているので、検索キー”100010”の弁別ビット位置２のビット値をみると０であるから、代表ノード番号の格納された配列番号221bの配列要素に格納されたノード210fにリンクする。
【００３２】
ノード210fの弁別ビット位置230fには５が格納されているので、検索キー”100010”の弁別ビット位置５のビット値をみると０であるから、代表ノード番号の格納された配列番号220fの配列要素に格納されたノード210gにリンクする。
ノード210gのノード種別260gは１でありリーフノードであることを示しているので、インデックスキー250gを読み出して検索キーと比較すると両方とも”100010”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【００３３】
上記カップルドノードツリーを用いた検索の一つの態様は、ルートノードのノード種別を読み出し、読みだしたノード種別を判定し、ノード種別がリーフノードを示すものであれば、リーフノードからインデックスキーを読み出し、ノード種別がブランチノードを示すものであれば、リンク先ノードを読み出し、読み出したリンク先ノードのノード種別を判定することをノード種別がリーフノードを示すものとなるまで繰り返し、リーフノードからインデックスキーを読み出すとともに、リーフノードに至るまでたどったリンク経路のブランチノード及びリーフノードが格納された配列要素の配列番号を探索経路スタックに順次格納する。
【００３４】
そして、上記カップルドノードツリーにインデックスキーを挿入、すなわちそのインデックスキーを含むリーフノードを挿入するときには、そのインデックスキーを検索キーとしてカップルドノードツリーから検索結果キーを取得し、インデックスキーと検索キーの間で大小比較とビット列比較を行い、配列からノード対を格納する空配列要素の組を取得し、その一方の配列要素の配列番号を取得し、大小比較により検索キーを含むリーフノードを取得した空配列要素の組のどちらの空配列要素に格納するかを決定し、ビット列比較で異なるビット値となる先頭のビット位置と、探索経路スタックに格納されている配列番号の配列要素に記憶されたブランチノードの弁別ビット位置との相対的位置関係により、探索経路スタックに格納されている配列番号を読み出し、配列番号の配列要素に格納されるノードを、取得した空配列要素の組に格納されるノード対のリンク元としてノード対の挿入位置を決定し、決定した空配列要素に配置するリーフノードの、ノード種別を格納する領域にリーフノードであることを示すノード種別を、インデックスキーを格納する領域に検索キーを書き込み、もう一方の空配列要素に、探索経路スタックから読み出した配列番号の配列要素に格納されるノードの内容を読み出して書き込むことで挿入ノード対を生成し、探索経路スタックから読み出した配列番号の配列要素に格納されるノードをブランチノードとし、そのノード種別を格納する領域にブランチノードであることを示すノード種別を、弁別ビット位置を格納する領域にビット列比較で異なるビット値となる先頭のビット位置を、リンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域に取得した配列番号を、それぞれ書き込むことを実行する。
【００３５】
また、上記カップルドノードツリーからインデックスキーを削除、すなわちそのインデックスキーを含むリーフノードを削除するときには、そのインデックスキーを検索キーとしてカップルドノードツリーから検索結果キーを取得し、検索結果キーを保持するリーフノードと同一ノード対を構成するノードが格納された配列要素の内容を読み出し、リーフノードが格納された配列要素の配列番号の１つ前に探索経路スタックに格納された配列番号を探索経路スタックから読み出し、その配列番号の配列要素に先に読み出した配列要素の内容を書き込み、上記ノード対の記憶されていた配列要素の組を解放することを実行する。
【先行技術文献】
【特許文献】
【００３６】
【特許文献１】特開２００１−３５７０７０号公報
【特許文献２】特開２００８−０１５８７２号公報
【発明の概要】
【発明が解決しようとする課題】
【００３７】
上記特許文献２に記載されたカップルドノードツリーにおけるインデックスキーの挿入処理では、探索経路スタックを用いることにより、一般的にはインデックスキーの挿入位置を探索する処理を高速化することができる。また、インデックスキーの削除処理においても、削除するインデックスキーの保持されているリーフノードの直近上位のブランチノードの配列番号を探索経路スタックから得ることができる。
【００３８】
しかしながら、キャッシュサイズに収まる程度の大きさのカップルドノードツリーにおいては、カップルドノードツリーをキャッシュ内に配置し、探索経路スタックは使用しないことにより、カップルドノードツリーの検索、挿入及び削除処理をより高速に実行することができる。
【００３９】
そこで本発明の解決しようとする課題は、探索経路スタックを用いないカップルドノードツリーのインデックスキー挿入／削除方法を提供することである。
【課題を解決するための手段】
【００４０】
本発明のカップルドノードツリーのインデックスキー挿入方法によれば、ノード対の挿入位置を決定するに際して、挿入するインデックスキーによる検索を再度開始するとともに、各リンク先ノードであるブランチノードの弁別ビット位置が検索結果キーとのビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、リーフノードが読み出される前にリンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定するとそのブランチノードを、リンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定する前にリーフノードが読み出されるとそのリーフノードを、配列から取得した空配列要素の組に格納されるノード対のリンク元ノードとして該ノード対の挿入位置を決定する。
【００４１】
また、本発明のカップルドノードツリーのインデックスキー削除方法によれば、検索結果キーを求めるに際して、リンク先ノードのノード種別がブランチノードと判定される毎にそのブランチノードが格納された配列要素の配列番号を親ノードの配列番号として退避しておき、検索結果キーであるインデックスキーを保持するリーフノードと同一ノード対を構成するノードが格納された配列要素の内容を読み出して、退避された親ノードの配列番号の配列要素にその配列要素の内容を書き込む。
【発明の効果】
【００４２】
本発明によれば、カップルドノードツリーのインデックスキーの挿入及び削除を、探索経路スタックを用いないで実現することができる。
したがって、キャッシュサイズに収まる程度の大きさのカップルドノードツリーにおいては、カップルドノードツリーをキャッシュ内に配置し、探索経路スタックは使用しないことにより、カップルドノードツリーの検索、挿入及び削除処理をより高速に実行することができる。
【図面の簡単な説明】
【００４３】
【図１】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【図２Ａ】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２Ｂ】カップルドノードツリーのツリー構造を説明する図である。
【図３】本発明を実施するためのハードウェア構成例を説明する図である。
【図４】本発明の一実施形態における検索処理を示すフローチャート例である。
【図５】本発明の一実施形態における挿入処理の前段である検索処理の処理フロー例を示す図である。
【図６】本発明の一実施形態における挿入処理における挿入するノード対のための配列要素を準備する処理フロー例を示す図である。
【図７Ａ】ノード対を挿入する位置を求める処理フロー例を示す図である。
【図７Ｂ】ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フロー例を示す図である。
【図８】本発明の一実施の形態におけるルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー例を示す図である。
【図９】本発明の一実施形態における削除処理の前段である検索処理の処理フロー例を示す図である。
【図１０】本発明の一実施形態における削除処理の後段の処理フロー例を示す図である。
【図１１Ａ】削除キー”011010”による削除処理前のカップルドノードツリー例を説明する図である。
【図１１Ｂ】削除処理後のカップルドノードツリー例を説明する図である。
【図１２Ａ】挿入キー”0011”による挿入処理前のカップルドノードツリー例を説明する図である。
【図１２Ｂ】挿入処理後のカップルドノードツリー例を説明する図である。
【発明を実施するための形態】
【００４４】
以下、本発明を実施するための形態を説明する。
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
【００４５】
本発明による検索処理及び挿入／削除のデータメンテナンス処理は中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施される。カップルドノードツリーが配置される配列309を有するデータ格納装置308は、主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。
【００４６】
図３の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできる。あるいは、配列309はキャッシュメモリ303に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【００４７】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるために、それぞれの処理に応じた一時記憶領域が用いられることは当然である。
【００４８】
図４は、本発明の一実施形態における検索処理を示すフローチャート例である。適宜図２Ｂを参照しながら、検索処理のアルゴリズムを説明する。
【００４９】
図４に示すように、ステップS401において、検索対象であるカップルドノードツリーの検索開始ノードの配列番号を取得して一時記憶領域である配列番号に設定する。検索開始ノードの配列番号の取得は、各種応用プログラムから検索開始ノードの配列番号を受け取ることなどにより行われる。また、検索開始ノードがルートノードである場合には、カップルドノードツリーの管理手段に登録されたルートノードの配列番号を取得する。
【００５０】
上記一時記憶領域である配列番号は、先に述べた、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域のひとつである。以下の説明において、これらの一時記憶領域の名前に、そこに記憶されるデータの名前を用いることがある。また、一時記憶領域の名前を、その一時記憶領域に記憶されるデータの名前とすることもある。
【００５１】
なお、図示の検索処理がコンピュータ上のプログラムにより実現可能であることは明らかであるが、先に述べたカップルドノードツリーの管理手段は、例えば検索処理をコンピュータに実行させるプログラム上の記憶エリアとすることができる。
また、１つのコンピュータシステムに複数のカップルドノードツリーを用いた検索システムが搭載されている場合は、個々の検索プログラムの外部に持つようにすることもできる。
【００５２】
なお、ルートノードを含む検索開始ノードの配列番号の取得は、上記の方法に限らず、キーボード等から直接配列番号を入力するようにしてもよいし、固定値として予めプログラム上に設定しておいてもよい。
【００５３】
次にステップS403において、配列番号の指す配列要素をリンク先のノードとして配列から読み出す。ステップS404において、ステップS403で読み出したノードからノード種別を取り出す。
【００５４】
次にステップS405においてノード種別の判定を行う。ステップS405での判定がブランチノードであれば、ステップS406に移行する。ステップS406ではノードから弁別ビット位置を取り出す。次にステップS407において検索キーからステップS406で取り出した弁別ビット位置のビット値を取得する。
【００５５】
次にステップS408に進み、ノードから、リンク先のノード対の代表ノードの配列番号を取得する。続いてステップS409に進み、ステップS408で取得した配列番号にステップS407で取得したビット値を加算して配列番号に設定し、ステップS403に戻る。
【００５６】
以上のステップS403からS409のループ処理をステップS405での判定がリーフノードとなるまで繰り返す。
ステップS405でノード種別がリーフノードと判定されるとステップS410に移行し、ノードからインデックスキーを取り出し、処理を終了する。
【００５７】
次に、図５〜図８によりカップルドノードツリーにおけるノード挿入処理を説明する。図５〜図７Ｂが通常の挿入処理を説明するものであり、図８はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【００５８】
図５は本発明の一実施形態における挿入処理の前段である検索処理の処理フロー例を示す図である。
図５に示すように、ステップS501で、検索開始ノードの配列番号に、ルートノードの配列番号を設定し、ステップS502で、検索キーに挿入するインデックスキーである挿入キーを設定する。
【００５９】
そしてステップS510において、図４に示す検索処理を実行する。
次にステップS511において、挿入キーとステップS510で検索結果として得られたインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図６のステップS512以下の処理に進む。
【００６０】
図６は、本発明の一実施形態における挿入するノード対のための配列要素を準備する処理フロー例を示す図である。
【００６１】
ステップS512において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【００６２】
ステップS513に進み、挿入キーとステップS510で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１の、小さいときは値０のブール値を得る。
【００６３】
ステップS514に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値を加算した配列番号を得る。
【００６４】
ステップS515に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値の論理否定値を加算した配列番号を得る。
【００６５】
ステップS514で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップS515で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。
【００６６】
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【００６７】
例えば図２Ｂのカップルドノードツリーに”011011”を挿入する場合、検索結果のインデックスキーはノード211dに格納された”011010”になる。挿入キー”011011”とノード211dに格納されたインデックスキー”011010”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値１が得られ、挿入されるノード対の代表ノード番号に１を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー”011010”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。
その際、インデックスキー”011010”と挿入キー”011011”とは５ビット目で異なることから、ノード211dは、弁別ビット位置を５とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【００６８】
また図２Ｂのカップルドノードツリーに”011001”を挿入しようとする場合も、検索結果のインデックスキーはノード211dに格納された”011010”になる。この場合には挿入キーが小さいのでブール値０が得られ、挿入されるノード対の代表ノード番号に０を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー”011010”と挿入キー”011001”とは４ビット目で異なることから、ノード211dは、弁別ビット位置を４とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
次に図７ＡのステップS516以下の処理に進む。
【００６９】
図７Ａは図６で準備された配列に格納されるノード対の挿入位置を求める処理フロー例を示す図である。
【００７０】
ステップS516で、挿入キーとステップS510で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップS517に進み、ステップS516で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【００７１】
次にステップS519aに進み、配列番号に、検索開始ノードの配列番号を設定する。ここで検索開始ノードの配列番号には、図５に示すステップS501において、ルートノードの配列番号が設定されている。したがって、一時記憶領域である配列番号にはルートノードの配列番号が設定される。
ステップS520aに進み、配列からステップS519aで設定した配列番号の指す配列要素をノードとして読み出す。
ステップS520bに進み、ステップS520aで読み出したノードから、ノード種別を取り出す。
【００７２】
次にステップS520cに進み、ステップS520bで取り出したノード種別はブランチか判定し、ブランチであればステップS521に進み、ブランチでなければ、図７ＢのステップS524に進む。ステップS521では、ステップS520aで読み出したノードから、弁別ビット位置を取り出す。
次にステップS522に進み、ステップS521で取り出した弁別ビット位置がステップS517で得たビット位置より下位の位置関係か判定する。ここで下位の位置関係とは、ビット列のより右側の位置、すなわちビット位置の値が大きい位置であることとする。
ステップS522の判定結果が否定であれば、ステップS523a〜ステップS523cの処理を介して、ステップS520aの処理に戻る。ステップS522での判定が肯定になると、図７ＢのステップS524以下の処理に移行する。
ステップS523aでは、検索キーから、弁別ビット位置の指すビット値を取り出し、ステップS523bでは、ノードから、代表ノードを取り出し、ステップS523cでは、その代表ノード番号にステップS523aで取り出したビット値を加えて配列番号に設定する。
【００７３】
上記ステップS516〜ステップS523cで説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーによる検索を再度開始するとともに、各リンク先ノードであるブランチノードの弁別ビット位置がステップS510で得たインデックスキーとのビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、リーフノードが読み出される前にリンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定するとそのブランチノードを、リンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定する前にリーフノードが読み出されるとそのリーフノードを、配列から取得した空配列要素の組に格納されるノード対のリンク元ノードとして該ノード対の挿入位置を決定するものである。
【００７４】
ステップS520cでノード種別がブランチではないと判定されたときは挿入位置のリンク元ノードとなるのがリーフノードの場合である。このリーフノードは挿入処理後には挿入されたノード対のリンク元のブランチノードになる。
【００７５】
また、ステップS522での判定が肯定的なものとなる場合の挿入位置のノードはブランチノードである。この場合には、後に説明するように、そのブランチノードの弁別ビット位置はステップS517で得たビット位置に変更される。
【００７６】
図７Ｂは、ノード対の各ノードの内容を書き込むとともに、既存のノードの内容を変更して挿入処理を完成させる処理フロー例を示す図である。
図に示すように、ステップS524では、挿入位置の配列番号に、配列番号を設定する。ここで挿入位置の配列番号に設定されるのは、挿入位置のノードの格納された配列要素の配列番号である。
【００７７】
ステップS525において、ステップS514で得た配列番号の指す配列要素のノード種別に１（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップS526に進み、配列からステップS524で設定した挿入位置の配列番号の配列要素を読み出す。
次にステップS527において、ステップS515で得た配列番号の配列要素にステップS526で読み出した内容を書き込む。
上述のステップS525とステップS527の処理は挿入されるノード対の各ノードの内容を書き込むものである。
【００７８】
最後にステップS528において、ステップS524で設定した挿入位置の配列番号の指す配列要素のノード種別に０(ブランチノード）を、弁別ビット位置にステップS517で得たビット位置を、代表ノード番号にステップS512で得た、空のノード対のうち代表ノードとなるべき配列要素の配列番号を書き込み、処理を終了する。この最後の処理は、既存のノードの内容を変更する処理である。
【００７９】
図８は、本発明の一実施の形態におけるルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー例を示す図である。
ステップS551において、カップルドノードツリーのルートノードの配列番号が登録済みであるか判定する。登録済みであれば、図５〜図７Ｂを用いて説明した通常の挿入処理が行われる。
【００８０】
ステップS551での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップS552において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS553において、ステップS552で得た配列番号に０を加えた配列番号を求める（実際には、ステップS552で取得した配列番号に等しい。)。さらにステップS554において、ステップS553で得た配列番号の配列要素に、挿入するルートノードのノード種別に１（リーフノード)とインデックスキーに挿入キーを書き込み、ステップS556で、ステップS552で取得したルートノードの配列番号を登録して処理を終了する。
【００８１】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図８及び図５〜図７Ｂの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【００８２】
次に図９、図１０を参照して、本発明の一実施の形態におけるカップルドノードツリーから、特定のインデックスキー（削除キー）、すなわち削除キーを保持するリーフノードを削除する処理フローを説明する。
【００８３】
図９は、本発明の一実施の形態における削除処理の前段である検索処理の処理フロー例を示す図であり、図４に示した検索処理において削除キーを検索キーとするとともに、一時記憶領域である親ノードの配列番号に、リンク経路のブランチノードの配列番号を退避する処理を加えたものに相当する。
【００８４】
図９に示すように、ステップS901において、削除処理対象であるカップルドノードツリーのルートノードの配列番号を取得して一時記憶領域である配列番号に設定する。
次にステップS903において、配列番号の指す配列要素をリンク先のノードとして配列から読み出す。ステップS904において、ステップS903で読み出したノードからノード種別を取り出す。
【００８５】
次にステップS905においてノード種別の判定を行う。ステップS905での判定がブランチノードであれば、ステップS906aに移行する。ステップS906aでは一時記憶領域である親ノードの配列番号に、配列番号、すなわち、ステップS903で読み出したノードの格納されている配列要素の配列番号を設定し、ステップS906bに進み、ステップS903で読み出したノードから弁別ビット位置を取り出す。次にステップS907において削除キーからステップS906bで取り出した弁別ビット位置の指すビット値を取得する。
【００８６】
次にステップS908に進み、ノードから、リンク先のノード対の代表ノードの配列番号を取得する。続いてステップS909に進み、ステップS908で取り出した代表ノード番号にステップS907で取り出したビット値を加算した値を配列番号に設定し、ステップS903に戻る。
以上のステップS903〜S909のループ処理をステップS905での判定がリーフノードとなるまで繰り返す。
【００８７】
ステップS905での判定がリーフノードとなると、ステップS910に移行し、ノードからインデックスキーを取り出し、ステップS911に進む。
ステップS911においては、削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。削除キーとインデックスキーが等しければ次の処理、図１０のステップS912以下の処理に進む。
【００８８】
図１０は、本発明の一実施形態における削除処理の後段の処理フロー例を説明する図である。
まずステップS912で、配列番号に設定されているのは検索開始ノードの配列番号であるか判定する。ここで検索開始ノードの配列番号に設定されているのはルートノードの配列番号である。この場合はステップS918に移行し、ステップS901で得たルートノードの配列番号の指すノード対を削除する。次にステップS919に進み、ルートノードの配列番号の登録を抹消して処理を終了する。
【００８９】
ステップS912において配列番号に設定されているのは検索開始ノードの配列番号ではないと判定されたときはステップS913に進み、ステップS908で得た代表ノード番号にステップS907で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【００９０】
次にステップS914において、ステップS913で得た配列番号の配列要素の内容を読み出し、ステップS916において、ステップS914で読み出した配列要素の内容を親ノードの配列番号の指す配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
最後にステップS917においてステップS908で得た代表ノード番号の指すノード対を削除して処理を終了する。
【００９１】
図１１Ａ及び図１１Ｂは、図２Ｂに例示したカップルドノードツリーからインデックスキー”011010”を削除する処理を説明する図である。
図１１Ａに示したカップルドノードツリーは、ノード対201f以下のノードは記載を省略している。削除対象のインデックスキー”011010”は一時記憶エリアである削除キー270に格納されている。図中太枠で囲まれたノードが検索処理でたどられたノードであり、検索結果のインデックスキーは、リーフノード211dに格納されている。そして、図示しない親ノードの配列番号には、リーフノード211dの直近上位に位置する親ノードであるブランチノード211cの格納された配列要素の配列番号220b+1が退避されている。
【００９２】
削除キーによる検索処理においては、まず始めにルートノード210aの配列番号220を取得し、ルートノード210aを読み出す。ルートノード210aの弁別ビット位置230aが０であり、削除キーのビット位置０のビット値が０であるので、代表ノード番号220a+0=220aの指すノード210bが読み出される。
【００９３】
ノード210bの弁別ビット位置230bが１であり、削除キーのビット位置１のビット値が１であるので、代表ノード番号220b+1の配列番号が指すノード211cが読み出され、その弁別ビット位置231cが２であり、削除キーのビット位置２のビット値が１であるので、代表ノード番号221c+1の配列番号が指す配列要素に格納されたノード211dがさらに読み出される。そのノード種別261dは１であり、リーフノードであることを示しているのでインデックスキー251dを取り出すとその値は”011010”であり、削除キー270に格納された削除対象のインデックスキーと一致している。
【００９４】
図１１Ａに示した状態において、削除対象のインデックスキーを有するノード211dと対をなすノード210dの内容が読み出され、その内容が、親ノードの配列番号に退避されている配列番号220b+1の配列要素（ノード221c）に書き込まれる。その後ノード対201dを削除する。ノード対が削除された配列要素は空となり、再利用可能となる。
【００９５】
図１１Ｂに示したカップルドノードツリーは、削除処理の終了後のものである。ノード211cのノード種別261c、弁別ビット位置231c、代表ノード番号221cには、括弧書きで示すように、ノード210dに格納されていた値がそのまま格納されている。
【００９６】
次に、図１２Ａ、図１２Ｂにより、具体例を挙げて挿入処理を更に説明する。
図１２Ａに示すのは、ビット列”0100”、”0001”、”0000”をインデックスキーとして持つカップルドノードツリーとこれから挿入しようとする挿入キー”0011”を保持している一時記憶エリア1250である。図示のツリーはノード対1201a,1201b,1201cで構成されている。
【００９７】
ノード対1201aの代表ノードはルートノード1210aであり、弁別ビット位置には１が保持されている。ノード対1201aの下位のノード対1201bの代表ノード1210bはブランチノードであり、弁別ビット位置には３が保持され、代表ノード1210bと対になるノード1211bはリーフノードであり、インデックスキー”0100”が保持されている。ブランチノードであるノード1210bはノード対1201cにリンクしている。
ノード対1201cを構成するノード1210c,1211cはともにリーフノードであり、それぞれインデックスキー”0000”、 ”0001”を保持している。
【００９８】
挿入キー”0011”で検索を実行すると検索結果キーとしてインデックスキー”0001”が得られ、挿入キーと検索結果キーの大小比較でブール値１が、挿入キーと検索結果キーの最上位からのビット列比較により最初に異なるビット値となる位置として２が得られる。
ルートノード1210aから検索結果キーを保持するリーフノード1211cまでのリンク経路をたどり、挿入キーと検索結果キーの最上位からのビット列比較により最初に異なるビット値となる位置２とブランチノードの弁別ビット位置の相対的位置関係をみると、弁別ビット位置は上記位置２に対してブランチノード1210bにおいて下位の位置関係となることから、空ノード対の挿入位置はブランチノード1210bである。
【００９９】
図１２Ｂは、挿入キー”0011”を挿入したカップルドノードツリーを示す図である。新たなノード対1201dがブランチノード1210bの下位に挿入されている。挿入キーはノード対1201dのノード[1]側のリーフノード1211dに保持され、図１２Ａに示す挿入位置のノード1210bの内容は、ノード対1201dのノード[0]側のノード1210dに書き込まれている。図１２Ｂに示す挿入後のノード1210bの弁別ビット位置は挿入キーと検索結果キーの最上位からのビット列比較により最初に異なるビット値となる位置２に変化している。
【０１００】
以上本発明を実施するための形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明に係るビット列検索装置が、カップルドノードツリーを格納する記憶手段と図４に示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。さらに、本発明のカップルドノードツリーのインデックスキー挿入／削除方法が、図５〜図１０に示した処理をコンピュータ上に構築されたビット列検索装置に実行させるプログラムにより実現可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。
【符号の説明】
【０１０１】
10，20，30 配列番号
100 配列
101 ノード
102 ノード種別
103 弁別ビット位置
104 代表ノード番号
111 ノード対
112 ノード[0]、代表ノード
113 ノード[1]、代表ノードと対をなすノード
118 インデックスキー
301 データ処理装置
302 中央処理装置
303 キャッシュメモリ
304 バス
305 主記憶装置
306 外部記憶装置
307 通信装置
308 データ格納装置
309 配列
【技術分野】
【０００１】
本発明はビット列からなるインデックスキーの集合から所望のインデックスキーを検索するために用いられるカップルドノードツリーのインデックスキーの挿入及び削除に関するものである。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【０００３】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【０００４】
図１は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【０００５】
図１の例では、インデックスキー”100010”を保持するノード1750aがルートノードとなっており、その検査ビット位置は０である。ノード1750aの左リンク1740aにはノード1750bが接続され、右リンク1741aにはノード1750fが接続されている。
【０００６】
ノード1750bの保持するインデックスキーは”010011”であり、検査ビット位置1730bは１である。ノード1750bの左リンク1740bにはノード1750cが、右リンク1741bにはノード1750dが接続されている。ノード1750cが保持するインデックスキーは”000111”、検査ビット位置は３である。ノード1750dが保持するインデックスキーは”011010”、検査ビット位置は２である。
【０００７】
ノード1750cから実線で接続された部分はノード1750cの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ1740cは、その欄が空欄であることを示している。点線の接続された右ポインタ1741cの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード1750cを右ポインタが指定していることを表している。
【０００８】
ノード1750dの右ポインタ1741dはノード1750d自身を指しており、左リンク1740dにはノード1750eが接続されている。1750eの保持するインデックスキーは”010010”、検査ビット位置は５である。ノード1750eの左ポインタ1740eはノード1750bを、右ポインタ1741eはノード1750eを指している。
【０００９】
また、ノード1750fの保持するインデックスキーは”101011”であり、検査ビット位置1730fは２である。ノード1750fの左リンク1740fにはノード1750gが、右リンク1741fにはノード1750hが接続されている。
【００１０】
ノード1750gの保持するインデックスキーは”100011”であり、検査ビット位置1730gは５である。ノード1750gの左ポインタ1740gはノード1750aを、右ポインタ1741gはノード1750gを指している。
【００１１】
ノード1750hの保持するインデックスキーは”101100”であり、検査ビット位置1730hは３である。ノード1750hの左ポインタ1740hはノード1750fを、右ポインタ1741hはノード1750hを指している。
図１の例では、ルートノード1750aからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
【００１２】
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が１であるか０であるか判定を行い、１であれば右リンクをたどり、０であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば（図１において点線で示されたこの逆戻りのリンクをバックリンクという。)、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【００１３】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は１回ですむことなどのメリットがあるが、各ノードからの２つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【００１４】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献１に開示された技術がある。下記特許文献１に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【００１５】
また、下記特許文献２には、必要とする記憶容量が小さく、検索速度が高速であり、データメンテナンスの容易なデータ構造であるカップルドノードツリーが開示されている。
以下、特許文献２に記載されたカップルドノードツリーを配列に格納する例について説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【００１６】
図２Ａは、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図２Ａを参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード種別102、弁別ビット位置103及び代表ノード番号104で構成されている。ノード種別102は０であり、ノード101がブランチノードであることを示している。弁別ビット位置103には１が格納されている。代表ノード番号104にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【００１７】
配列番号２０の配列要素には、ノード対111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1）に代表ノードと対になるノード[1]113が格納されている。ノード[0]112のノード種別114には０が、弁別ビット位置115には３が、代表ノード番号116には３０が格納されている。またノード[1]113のノード種別117には１が格納されており、ノード[1]113がリーフノードであることを示している。インデックスキー118には、”0001”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
なお、代表ノードをノード[0]で表し、それと対になるノードをノード[1]で表すことがある。
配列番号30及び31の配列要素に格納されたノード122とノード123からなるノード対121の内容は省略されている。
【００１８】
ノード[0]112、ノード[1]113、ノード122、及びノード123の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【００１９】
図２Ｂは、カップルドノードツリーのツリー構造を概念的に示す図である。図示の６ビットのインデックスキーは、図１に例示されたパトリシアツリーのものと同じである。
符号210aで示すのがルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード対201ａの代表ノードとしている。
【００２０】
ツリー構造としては、ルートノード210ａの下にノート対201bが、その下層にノード対201cとノード対201fが配置され、ノード対201fの下層にはノード対201hとノード対201gが配置されている。ノード対201cの下にはノード対201dが、さらにその下にはノード対201eが配置されている。
【００２１】
各ノードの前に付された０あるいは１の符号は、図２Ａにおいて説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００２２】
図示された例では、ルートノード210aのノード種別260aは０でブランチノードであることを示し、弁別ビット位置230aは０を示している。代表ノード番号は220aであり、それはノード対201bの代表ノード210bの格納された配列要素の配列番号である。
【００２３】
ノード対201bはノード210bと211bで構成され、それらのノード種別260b、261bはともに０であり、ブランチノードであることを示している。ノード210bの弁別ビット位置230bには１が格納され、リンク先の代表ノード番号にはノード対201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。
【００２４】
ノード210cのノード種別260cには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー250ｃには”000111”が格納されている。一方ノード211cのノード種別261cは０、弁別ビット位置231cは２であり、代表ノード番号にはノード対201dの代表ノード210dの格納された配列要素の配列番号221cが格納されている。
【００２５】
ノード210dのノード種別260dは０、弁別ビット位置230dは５であり、代表ノード番号にはノード対201ｅの代表ノード210ｅの格納された配列要素の配列番号220dが格納されている。ノード210dと対になるノード211dのノード種別261dは１であり、インデックスキー251dには”011010”が格納されている。
【００２６】
ノード対201eのノード210e、211eのノード種別260e、261eはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー250e、251eにはインデックスキーとして”010010”と”010011”が格納されている。
【００２７】
ノード対201bのもう一方のノードであるノード211bの弁別ビット位置231bには２が格納され、リンク先の代表ノード番号にはノード対201fの代表ノード210fの格納された配列要素の配列番号221bが格納されている。
【００２８】
ノード対201fのノード210f、211fのノード種別260f、261fはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置230f、231fには５、３が格納されている。ノード210fの代表ノード番号にはノード対201gの代表ノード210gの格納された配列要素の配列番号220fが格納され、ノード211fの代表ノード番号にはノード対201hの代表ノードであるノード[0]210hの格納された配列要素の配列番号221fが格納されている。
【００２９】
ノード対201gのノード210g、211gのノード種別260g、261gはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー250g、251gには”100010”と”100011”が格納されている。
【００３０】
また同じくノード対201hの代表ノードであるノード[0]210hとそれと対をなすノード[1]211hのノード種別260h、261hはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー250h、251hには”101011”と”101100”が格納されている。
【００３１】
以下、上述のツリーからインデックスキー”100010”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列”100010”を検索キーとしてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは０であるので、検索キー”100010”の弁別ビット位置０のビット値をみると１である。そこで代表ノード番号の格納された配列番号220aに１を加えた配列番号の配列要素に格納されたノード211bにリンクする。ノード211bの弁別ビット位置231bには２が格納されているので、検索キー”100010”の弁別ビット位置２のビット値をみると０であるから、代表ノード番号の格納された配列番号221bの配列要素に格納されたノード210fにリンクする。
【００３２】
ノード210fの弁別ビット位置230fには５が格納されているので、検索キー”100010”の弁別ビット位置５のビット値をみると０であるから、代表ノード番号の格納された配列番号220fの配列要素に格納されたノード210gにリンクする。
ノード210gのノード種別260gは１でありリーフノードであることを示しているので、インデックスキー250gを読み出して検索キーと比較すると両方とも”100010”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【００３３】
上記カップルドノードツリーを用いた検索の一つの態様は、ルートノードのノード種別を読み出し、読みだしたノード種別を判定し、ノード種別がリーフノードを示すものであれば、リーフノードからインデックスキーを読み出し、ノード種別がブランチノードを示すものであれば、リンク先ノードを読み出し、読み出したリンク先ノードのノード種別を判定することをノード種別がリーフノードを示すものとなるまで繰り返し、リーフノードからインデックスキーを読み出すとともに、リーフノードに至るまでたどったリンク経路のブランチノード及びリーフノードが格納された配列要素の配列番号を探索経路スタックに順次格納する。
【００３４】
そして、上記カップルドノードツリーにインデックスキーを挿入、すなわちそのインデックスキーを含むリーフノードを挿入するときには、そのインデックスキーを検索キーとしてカップルドノードツリーから検索結果キーを取得し、インデックスキーと検索キーの間で大小比較とビット列比較を行い、配列からノード対を格納する空配列要素の組を取得し、その一方の配列要素の配列番号を取得し、大小比較により検索キーを含むリーフノードを取得した空配列要素の組のどちらの空配列要素に格納するかを決定し、ビット列比較で異なるビット値となる先頭のビット位置と、探索経路スタックに格納されている配列番号の配列要素に記憶されたブランチノードの弁別ビット位置との相対的位置関係により、探索経路スタックに格納されている配列番号を読み出し、配列番号の配列要素に格納されるノードを、取得した空配列要素の組に格納されるノード対のリンク元としてノード対の挿入位置を決定し、決定した空配列要素に配置するリーフノードの、ノード種別を格納する領域にリーフノードであることを示すノード種別を、インデックスキーを格納する領域に検索キーを書き込み、もう一方の空配列要素に、探索経路スタックから読み出した配列番号の配列要素に格納されるノードの内容を読み出して書き込むことで挿入ノード対を生成し、探索経路スタックから読み出した配列番号の配列要素に格納されるノードをブランチノードとし、そのノード種別を格納する領域にブランチノードであることを示すノード種別を、弁別ビット位置を格納する領域にビット列比較で異なるビット値となる先頭のビット位置を、リンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域に取得した配列番号を、それぞれ書き込むことを実行する。
【００３５】
また、上記カップルドノードツリーからインデックスキーを削除、すなわちそのインデックスキーを含むリーフノードを削除するときには、そのインデックスキーを検索キーとしてカップルドノードツリーから検索結果キーを取得し、検索結果キーを保持するリーフノードと同一ノード対を構成するノードが格納された配列要素の内容を読み出し、リーフノードが格納された配列要素の配列番号の１つ前に探索経路スタックに格納された配列番号を探索経路スタックから読み出し、その配列番号の配列要素に先に読み出した配列要素の内容を書き込み、上記ノード対の記憶されていた配列要素の組を解放することを実行する。
【先行技術文献】
【特許文献】
【００３６】
【特許文献１】特開２００１−３５７０７０号公報
【特許文献２】特開２００８−０１５８７２号公報
【発明の概要】
【発明が解決しようとする課題】
【００３７】
上記特許文献２に記載されたカップルドノードツリーにおけるインデックスキーの挿入処理では、探索経路スタックを用いることにより、一般的にはインデックスキーの挿入位置を探索する処理を高速化することができる。また、インデックスキーの削除処理においても、削除するインデックスキーの保持されているリーフノードの直近上位のブランチノードの配列番号を探索経路スタックから得ることができる。
【００３８】
しかしながら、キャッシュサイズに収まる程度の大きさのカップルドノードツリーにおいては、カップルドノードツリーをキャッシュ内に配置し、探索経路スタックは使用しないことにより、カップルドノードツリーの検索、挿入及び削除処理をより高速に実行することができる。
【００３９】
そこで本発明の解決しようとする課題は、探索経路スタックを用いないカップルドノードツリーのインデックスキー挿入／削除方法を提供することである。
【課題を解決するための手段】
【００４０】
本発明のカップルドノードツリーのインデックスキー挿入方法によれば、ノード対の挿入位置を決定するに際して、挿入するインデックスキーによる検索を再度開始するとともに、各リンク先ノードであるブランチノードの弁別ビット位置が検索結果キーとのビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、リーフノードが読み出される前にリンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定するとそのブランチノードを、リンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定する前にリーフノードが読み出されるとそのリーフノードを、配列から取得した空配列要素の組に格納されるノード対のリンク元ノードとして該ノード対の挿入位置を決定する。
【００４１】
また、本発明のカップルドノードツリーのインデックスキー削除方法によれば、検索結果キーを求めるに際して、リンク先ノードのノード種別がブランチノードと判定される毎にそのブランチノードが格納された配列要素の配列番号を親ノードの配列番号として退避しておき、検索結果キーであるインデックスキーを保持するリーフノードと同一ノード対を構成するノードが格納された配列要素の内容を読み出して、退避された親ノードの配列番号の配列要素にその配列要素の内容を書き込む。
【発明の効果】
【００４２】
本発明によれば、カップルドノードツリーのインデックスキーの挿入及び削除を、探索経路スタックを用いないで実現することができる。
したがって、キャッシュサイズに収まる程度の大きさのカップルドノードツリーにおいては、カップルドノードツリーをキャッシュ内に配置し、探索経路スタックは使用しないことにより、カップルドノードツリーの検索、挿入及び削除処理をより高速に実行することができる。
【図面の簡単な説明】
【００４３】
【図１】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【図２Ａ】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２Ｂ】カップルドノードツリーのツリー構造を説明する図である。
【図３】本発明を実施するためのハードウェア構成例を説明する図である。
【図４】本発明の一実施形態における検索処理を示すフローチャート例である。
【図５】本発明の一実施形態における挿入処理の前段である検索処理の処理フロー例を示す図である。
【図６】本発明の一実施形態における挿入処理における挿入するノード対のための配列要素を準備する処理フロー例を示す図である。
【図７Ａ】ノード対を挿入する位置を求める処理フロー例を示す図である。
【図７Ｂ】ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フロー例を示す図である。
【図８】本発明の一実施の形態におけるルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー例を示す図である。
【図９】本発明の一実施形態における削除処理の前段である検索処理の処理フロー例を示す図である。
【図１０】本発明の一実施形態における削除処理の後段の処理フロー例を示す図である。
【図１１Ａ】削除キー”011010”による削除処理前のカップルドノードツリー例を説明する図である。
【図１１Ｂ】削除処理後のカップルドノードツリー例を説明する図である。
【図１２Ａ】挿入キー”0011”による挿入処理前のカップルドノードツリー例を説明する図である。
【図１２Ｂ】挿入処理後のカップルドノードツリー例を説明する図である。
【発明を実施するための形態】
【００４４】
以下、本発明を実施するための形態を説明する。
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
【００４５】
本発明による検索処理及び挿入／削除のデータメンテナンス処理は中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施される。カップルドノードツリーが配置される配列309を有するデータ格納装置308は、主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。
【００４６】
図３の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできる。あるいは、配列309はキャッシュメモリ303に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【００４７】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるために、それぞれの処理に応じた一時記憶領域が用いられることは当然である。
【００４８】
図４は、本発明の一実施形態における検索処理を示すフローチャート例である。適宜図２Ｂを参照しながら、検索処理のアルゴリズムを説明する。
【００４９】
図４に示すように、ステップS401において、検索対象であるカップルドノードツリーの検索開始ノードの配列番号を取得して一時記憶領域である配列番号に設定する。検索開始ノードの配列番号の取得は、各種応用プログラムから検索開始ノードの配列番号を受け取ることなどにより行われる。また、検索開始ノードがルートノードである場合には、カップルドノードツリーの管理手段に登録されたルートノードの配列番号を取得する。
【００５０】
上記一時記憶領域である配列番号は、先に述べた、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域のひとつである。以下の説明において、これらの一時記憶領域の名前に、そこに記憶されるデータの名前を用いることがある。また、一時記憶領域の名前を、その一時記憶領域に記憶されるデータの名前とすることもある。
【００５１】
なお、図示の検索処理がコンピュータ上のプログラムにより実現可能であることは明らかであるが、先に述べたカップルドノードツリーの管理手段は、例えば検索処理をコンピュータに実行させるプログラム上の記憶エリアとすることができる。
また、１つのコンピュータシステムに複数のカップルドノードツリーを用いた検索システムが搭載されている場合は、個々の検索プログラムの外部に持つようにすることもできる。
【００５２】
なお、ルートノードを含む検索開始ノードの配列番号の取得は、上記の方法に限らず、キーボード等から直接配列番号を入力するようにしてもよいし、固定値として予めプログラム上に設定しておいてもよい。
【００５３】
次にステップS403において、配列番号の指す配列要素をリンク先のノードとして配列から読み出す。ステップS404において、ステップS403で読み出したノードからノード種別を取り出す。
【００５４】
次にステップS405においてノード種別の判定を行う。ステップS405での判定がブランチノードであれば、ステップS406に移行する。ステップS406ではノードから弁別ビット位置を取り出す。次にステップS407において検索キーからステップS406で取り出した弁別ビット位置のビット値を取得する。
【００５５】
次にステップS408に進み、ノードから、リンク先のノード対の代表ノードの配列番号を取得する。続いてステップS409に進み、ステップS408で取得した配列番号にステップS407で取得したビット値を加算して配列番号に設定し、ステップS403に戻る。
【００５６】
以上のステップS403からS409のループ処理をステップS405での判定がリーフノードとなるまで繰り返す。
ステップS405でノード種別がリーフノードと判定されるとステップS410に移行し、ノードからインデックスキーを取り出し、処理を終了する。
【００５７】
次に、図５〜図８によりカップルドノードツリーにおけるノード挿入処理を説明する。図５〜図７Ｂが通常の挿入処理を説明するものであり、図８はルートノードの挿入処理を説明するものである。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成されることから、ノード挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【００５８】
図５は本発明の一実施形態における挿入処理の前段である検索処理の処理フロー例を示す図である。
図５に示すように、ステップS501で、検索開始ノードの配列番号に、ルートノードの配列番号を設定し、ステップS502で、検索キーに挿入するインデックスキーである挿入キーを設定する。
【００５９】
そしてステップS510において、図４に示す検索処理を実行する。
次にステップS511において、挿入キーとステップS510で検索結果として得られたインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図６のステップS512以下の処理に進む。
【００６０】
図６は、本発明の一実施形態における挿入するノード対のための配列要素を準備する処理フロー例を示す図である。
【００６１】
ステップS512において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【００６２】
ステップS513に進み、挿入キーとステップS510で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１の、小さいときは値０のブール値を得る。
【００６３】
ステップS514に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値を加算した配列番号を得る。
【００６４】
ステップS515に進み、ステップS512で得た代表ノードの配列番号にステップS513で得たブール値の論理否定値を加算した配列番号を得る。
【００６５】
ステップS514で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップS515で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。
【００６６】
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【００６７】
例えば図２Ｂのカップルドノードツリーに”011011”を挿入する場合、検索結果のインデックスキーはノード211dに格納された”011010”になる。挿入キー”011011”とノード211dに格納されたインデックスキー”011010”の大小比較によりブール値が求められ、今の例では挿入キーが大きいのでブール値１が得られ、挿入されるノード対の代表ノード番号に１を加えた配列要素に挿入キーを保持するリーフノードが格納される。一方、インデックスキー”011010”は、大小比較で得られたブール値を論理反転した値を代表ノード番号に加算した配列番号の配列要素に格納される。
その際、インデックスキー”011010”と挿入キー”011011”とは５ビット目で異なることから、ノード211dは、弁別ビット位置を５とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
【００６８】
また図２Ｂのカップルドノードツリーに”011001”を挿入しようとする場合も、検索結果のインデックスキーはノード211dに格納された”011010”になる。この場合には挿入キーが小さいのでブール値０が得られ、挿入されるノード対の代表ノード番号に０を加えた配列要素に挿入キーを保持するリーフノードが格納される。そして、インデックスキー”011010”と挿入キー”011001”とは４ビット目で異なることから、ノード211dは、弁別ビット位置を４とし、代表ノード番号を挿入されたノード対の代表ノードの配列番号とするブランチノードとなる。
次に図７ＡのステップS516以下の処理に進む。
【００６９】
図７Ａは図６で準備された配列に格納されるノード対の挿入位置を求める処理フロー例を示す図である。
【００７０】
ステップS516で、挿入キーとステップS510で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップS517に進み、ステップS516で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【００７１】
次にステップS519aに進み、配列番号に、検索開始ノードの配列番号を設定する。ここで検索開始ノードの配列番号には、図５に示すステップS501において、ルートノードの配列番号が設定されている。したがって、一時記憶領域である配列番号にはルートノードの配列番号が設定される。
ステップS520aに進み、配列からステップS519aで設定した配列番号の指す配列要素をノードとして読み出す。
ステップS520bに進み、ステップS520aで読み出したノードから、ノード種別を取り出す。
【００７２】
次にステップS520cに進み、ステップS520bで取り出したノード種別はブランチか判定し、ブランチであればステップS521に進み、ブランチでなければ、図７ＢのステップS524に進む。ステップS521では、ステップS520aで読み出したノードから、弁別ビット位置を取り出す。
次にステップS522に進み、ステップS521で取り出した弁別ビット位置がステップS517で得たビット位置より下位の位置関係か判定する。ここで下位の位置関係とは、ビット列のより右側の位置、すなわちビット位置の値が大きい位置であることとする。
ステップS522の判定結果が否定であれば、ステップS523a〜ステップS523cの処理を介して、ステップS520aの処理に戻る。ステップS522での判定が肯定になると、図７ＢのステップS524以下の処理に移行する。
ステップS523aでは、検索キーから、弁別ビット位置の指すビット値を取り出し、ステップS523bでは、ノードから、代表ノードを取り出し、ステップS523cでは、その代表ノード番号にステップS523aで取り出したビット値を加えて配列番号に設定する。
【００７３】
上記ステップS516〜ステップS523cで説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーによる検索を再度開始するとともに、各リンク先ノードであるブランチノードの弁別ビット位置がステップS510で得たインデックスキーとのビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、リーフノードが読み出される前にリンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定するとそのブランチノードを、リンク先ノードであるブランチノードの弁別ビット位置がビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定する前にリーフノードが読み出されるとそのリーフノードを、配列から取得した空配列要素の組に格納されるノード対のリンク元ノードとして該ノード対の挿入位置を決定するものである。
【００７４】
ステップS520cでノード種別がブランチではないと判定されたときは挿入位置のリンク元ノードとなるのがリーフノードの場合である。このリーフノードは挿入処理後には挿入されたノード対のリンク元のブランチノードになる。
【００７５】
また、ステップS522での判定が肯定的なものとなる場合の挿入位置のノードはブランチノードである。この場合には、後に説明するように、そのブランチノードの弁別ビット位置はステップS517で得たビット位置に変更される。
【００７６】
図７Ｂは、ノード対の各ノードの内容を書き込むとともに、既存のノードの内容を変更して挿入処理を完成させる処理フロー例を示す図である。
図に示すように、ステップS524では、挿入位置の配列番号に、配列番号を設定する。ここで挿入位置の配列番号に設定されるのは、挿入位置のノードの格納された配列要素の配列番号である。
【００７７】
ステップS525において、ステップS514で得た配列番号の指す配列要素のノード種別に１（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップS526に進み、配列からステップS524で設定した挿入位置の配列番号の配列要素を読み出す。
次にステップS527において、ステップS515で得た配列番号の配列要素にステップS526で読み出した内容を書き込む。
上述のステップS525とステップS527の処理は挿入されるノード対の各ノードの内容を書き込むものである。
【００７８】
最後にステップS528において、ステップS524で設定した挿入位置の配列番号の指す配列要素のノード種別に０(ブランチノード）を、弁別ビット位置にステップS517で得たビット位置を、代表ノード番号にステップS512で得た、空のノード対のうち代表ノードとなるべき配列要素の配列番号を書き込み、処理を終了する。この最後の処理は、既存のノードの内容を変更する処理である。
【００７９】
図８は、本発明の一実施の形態におけるルートノードの挿入処理を含むインデックスキーを追加する場合のノード挿入処理全体を説明する処理フロー例を示す図である。
ステップS551において、カップルドノードツリーのルートノードの配列番号が登録済みであるか判定する。登録済みであれば、図５〜図７Ｂを用いて説明した通常の挿入処理が行われる。
【００８０】
ステップS551での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップS552において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップS553において、ステップS552で得た配列番号に０を加えた配列番号を求める（実際には、ステップS552で取得した配列番号に等しい。)。さらにステップS554において、ステップS553で得た配列番号の配列要素に、挿入するルートノードのノード種別に１（リーフノード)とインデックスキーに挿入キーを書き込み、ステップS556で、ステップS552で取得したルートノードの配列番号を登録して処理を終了する。
【００８１】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図８及び図５〜図７Ｂの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【００８２】
次に図９、図１０を参照して、本発明の一実施の形態におけるカップルドノードツリーから、特定のインデックスキー（削除キー）、すなわち削除キーを保持するリーフノードを削除する処理フローを説明する。
【００８３】
図９は、本発明の一実施の形態における削除処理の前段である検索処理の処理フロー例を示す図であり、図４に示した検索処理において削除キーを検索キーとするとともに、一時記憶領域である親ノードの配列番号に、リンク経路のブランチノードの配列番号を退避する処理を加えたものに相当する。
【００８４】
図９に示すように、ステップS901において、削除処理対象であるカップルドノードツリーのルートノードの配列番号を取得して一時記憶領域である配列番号に設定する。
次にステップS903において、配列番号の指す配列要素をリンク先のノードとして配列から読み出す。ステップS904において、ステップS903で読み出したノードからノード種別を取り出す。
【００８５】
次にステップS905においてノード種別の判定を行う。ステップS905での判定がブランチノードであれば、ステップS906aに移行する。ステップS906aでは一時記憶領域である親ノードの配列番号に、配列番号、すなわち、ステップS903で読み出したノードの格納されている配列要素の配列番号を設定し、ステップS906bに進み、ステップS903で読み出したノードから弁別ビット位置を取り出す。次にステップS907において削除キーからステップS906bで取り出した弁別ビット位置の指すビット値を取得する。
【００８６】
次にステップS908に進み、ノードから、リンク先のノード対の代表ノードの配列番号を取得する。続いてステップS909に進み、ステップS908で取り出した代表ノード番号にステップS907で取り出したビット値を加算した値を配列番号に設定し、ステップS903に戻る。
以上のステップS903〜S909のループ処理をステップS905での判定がリーフノードとなるまで繰り返す。
【００８７】
ステップS905での判定がリーフノードとなると、ステップS910に移行し、ノードからインデックスキーを取り出し、ステップS911に進む。
ステップS911においては、削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。削除キーとインデックスキーが等しければ次の処理、図１０のステップS912以下の処理に進む。
【００８８】
図１０は、本発明の一実施形態における削除処理の後段の処理フロー例を説明する図である。
まずステップS912で、配列番号に設定されているのは検索開始ノードの配列番号であるか判定する。ここで検索開始ノードの配列番号に設定されているのはルートノードの配列番号である。この場合はステップS918に移行し、ステップS901で得たルートノードの配列番号の指すノード対を削除する。次にステップS919に進み、ルートノードの配列番号の登録を抹消して処理を終了する。
【００８９】
ステップS912において配列番号に設定されているのは検索開始ノードの配列番号ではないと判定されたときはステップS913に進み、ステップS908で得た代表ノード番号にステップS907で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【００９０】
次にステップS914において、ステップS913で得た配列番号の配列要素の内容を読み出し、ステップS916において、ステップS914で読み出した配列要素の内容を親ノードの配列番号の指す配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
最後にステップS917においてステップS908で得た代表ノード番号の指すノード対を削除して処理を終了する。
【００９１】
図１１Ａ及び図１１Ｂは、図２Ｂに例示したカップルドノードツリーからインデックスキー”011010”を削除する処理を説明する図である。
図１１Ａに示したカップルドノードツリーは、ノード対201f以下のノードは記載を省略している。削除対象のインデックスキー”011010”は一時記憶エリアである削除キー270に格納されている。図中太枠で囲まれたノードが検索処理でたどられたノードであり、検索結果のインデックスキーは、リーフノード211dに格納されている。そして、図示しない親ノードの配列番号には、リーフノード211dの直近上位に位置する親ノードであるブランチノード211cの格納された配列要素の配列番号220b+1が退避されている。
【００９２】
削除キーによる検索処理においては、まず始めにルートノード210aの配列番号220を取得し、ルートノード210aを読み出す。ルートノード210aの弁別ビット位置230aが０であり、削除キーのビット位置０のビット値が０であるので、代表ノード番号220a+0=220aの指すノード210bが読み出される。
【００９３】
ノード210bの弁別ビット位置230bが１であり、削除キーのビット位置１のビット値が１であるので、代表ノード番号220b+1の配列番号が指すノード211cが読み出され、その弁別ビット位置231cが２であり、削除キーのビット位置２のビット値が１であるので、代表ノード番号221c+1の配列番号が指す配列要素に格納されたノード211dがさらに読み出される。そのノード種別261dは１であり、リーフノードであることを示しているのでインデックスキー251dを取り出すとその値は”011010”であり、削除キー270に格納された削除対象のインデックスキーと一致している。
【００９４】
図１１Ａに示した状態において、削除対象のインデックスキーを有するノード211dと対をなすノード210dの内容が読み出され、その内容が、親ノードの配列番号に退避されている配列番号220b+1の配列要素（ノード221c）に書き込まれる。その後ノード対201dを削除する。ノード対が削除された配列要素は空となり、再利用可能となる。
【００９５】
図１１Ｂに示したカップルドノードツリーは、削除処理の終了後のものである。ノード211cのノード種別261c、弁別ビット位置231c、代表ノード番号221cには、括弧書きで示すように、ノード210dに格納されていた値がそのまま格納されている。
【００９６】
次に、図１２Ａ、図１２Ｂにより、具体例を挙げて挿入処理を更に説明する。
図１２Ａに示すのは、ビット列”0100”、”0001”、”0000”をインデックスキーとして持つカップルドノードツリーとこれから挿入しようとする挿入キー”0011”を保持している一時記憶エリア1250である。図示のツリーはノード対1201a,1201b,1201cで構成されている。
【００９７】
ノード対1201aの代表ノードはルートノード1210aであり、弁別ビット位置には１が保持されている。ノード対1201aの下位のノード対1201bの代表ノード1210bはブランチノードであり、弁別ビット位置には３が保持され、代表ノード1210bと対になるノード1211bはリーフノードであり、インデックスキー”0100”が保持されている。ブランチノードであるノード1210bはノード対1201cにリンクしている。
ノード対1201cを構成するノード1210c,1211cはともにリーフノードであり、それぞれインデックスキー”0000”、 ”0001”を保持している。
【００９８】
挿入キー”0011”で検索を実行すると検索結果キーとしてインデックスキー”0001”が得られ、挿入キーと検索結果キーの大小比較でブール値１が、挿入キーと検索結果キーの最上位からのビット列比較により最初に異なるビット値となる位置として２が得られる。
ルートノード1210aから検索結果キーを保持するリーフノード1211cまでのリンク経路をたどり、挿入キーと検索結果キーの最上位からのビット列比較により最初に異なるビット値となる位置２とブランチノードの弁別ビット位置の相対的位置関係をみると、弁別ビット位置は上記位置２に対してブランチノード1210bにおいて下位の位置関係となることから、空ノード対の挿入位置はブランチノード1210bである。
【００９９】
図１２Ｂは、挿入キー”0011”を挿入したカップルドノードツリーを示す図である。新たなノード対1201dがブランチノード1210bの下位に挿入されている。挿入キーはノード対1201dのノード[1]側のリーフノード1211dに保持され、図１２Ａに示す挿入位置のノード1210bの内容は、ノード対1201dのノード[0]側のノード1210dに書き込まれている。図１２Ｂに示す挿入後のノード1210bの弁別ビット位置は挿入キーと検索結果キーの最上位からのビット列比較により最初に異なるビット値となる位置２に変化している。
【０１００】
以上本発明を実施するための形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明に係るビット列検索装置が、カップルドノードツリーを格納する記憶手段と図４に示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。さらに、本発明のカップルドノードツリーのインデックスキー挿入／削除方法が、図５〜図１０に示した処理をコンピュータ上に構築されたビット列検索装置に実行させるプログラムにより実現可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。
【符号の説明】
【０１０１】
10，20，30 配列番号
100 配列
101 ノード
102 ノード種別
103 弁別ビット位置
104 代表ノード番号
111 ノード対
112 ノード[0]、代表ノード
113 ノード[1]、代表ノードと対をなすノード
118 インデックスキー
301 データ処理装置
302 中央処理装置
303 キャッシュメモリ
304 バス
305 主記憶装置
306 外部記憶装置
307 通信装置
308 データ格納装置
309 配列
【特許請求の範囲】
【請求項１】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、前記ツリーに所望のビット列からなる挿入キーをインデックスキーとして格納するインデックスキー挿入方法において、
前記ツリーは配列に記憶されたツリーであって、該ツリーの始点であるルートノードと、前記配列の隣接した配列要素に配置される２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含まないものである、カップルドノードツリーであり、
前記ビット列検索装置は、
前記ルートノードが格納された前記配列の配列要素の配列番号を取得し、該取得した配列番号の配列要素からルートノードを読み出すルートノード読出手段と、
前記ノードのノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号との演算によりノードが格納された前記配列の配列要素の配列番号を求め、該求めた配列番号の配列要素に配置されたノードをリンク先ノードとして読み出すリンク手段と、
を備え、
前記挿入キーを前記検索キーとして、
前記ルートノード読出手段でルートノードを読み出し、該読み出したルートノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出す検索ステップと、
前記検索ステップで読み出したインデックスキーと前記挿入キーの間で大小比較とビット列比較を行う比較ステップと、
前記配列からノード対を格納する空配列要素の組を取得し、その一方の配列要素の配列番号を取得する空ノード対取得ステップと、
前記比較ステップにおける前記大小比較により挿入キーを含むリーフノードを前記空ノード対取得ステップで取得した空配列要素の組のどちらの空配列要素に格納するかを決定するリーフノード格納位置決定ステップと、
前記検索ステップを再度開始するとともに、前記リンク手段により読み出される各リンク先ノードであるブランチノードの弁別ビット位置が前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、前記リンク手段によりリーフノードが読み出される前に前記リンク先ノードであるブランチノードの弁別ビット位置が前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定すると該ブランチノードを、前記リンク先ノードであるブランチノードの弁別ビット位置が前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定する前に前記リンク手段がリーフノードを読み出すと該リーフノードを、前記空ノード対取得ステップで取得した空配列要素の組に格納されるノード対のリンク元ノードとして該ノード対の挿入位置を決定するノード対挿入位置決定ステップと、
前記リーフノード格納位置決定ステップで決定した空配列要素に配置するリーフノードの、ノード種別を格納する領域にリーフノードであることを示すノード種別を、インデックスキーを格納する領域に前記挿入キーを書き込み、もう一方の空配列要素に、前記ノード対挿入位置決定ステップで前記リンク元ノードとされたノードの内容を読み出して書き込むことで挿入ノード対を生成する挿入ノード対生成ステップと、
前記ノード対挿入位置決定ステップで前記リンク元ノードとされたノードをブランチノードとし、そのノード種別を格納する領域にブランチノードであることを示すノード種別を、弁別ビット位置を格納する領域に前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置を、リンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域に前記空ノード対取得ステップで取得した配列番号を、それぞれ書き込むブランチノード生成ステップと、
を備えたことを特徴とするインデックスキー挿入方法。
【請求項２】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、前記ツリーを生成するツリー生成方法において、
前記ツリーは請求項１に記載されたカップルドノードツリーであり、
前記ビット列検索装置は請求項１に記載されたものであって、
前記カップルドノードツリーに格納するインデックスキーの集合から１つのインデックスキーを取り出し、該インデックスキーを含むリーフノードをルートノードとするカップルドノードツリーを生成し、
前記インデックスキーの集合からさらに順次インデックスキーを取り出して該インデックスキーを、請求項１記載のインデックスキー挿入方法により前記カップルドノードツリーに挿入することによりカップルドノードツリーを生成することを特徴とするカップルドノードツリーの生成方法。
【請求項３】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、所望のビット列からなる削除キーと等しい前記ツリーに格納されたインデックスキーを削除するインデックスキー削除方法において、
前記ツリーは配列に記憶されたツリーであって、該ツリーの始点であるルートノードと、前記配列の隣接した配列要素に配置される２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含まないものである、カップルドノードツリーであり、
前記ビット列検索装置は、
前記ルートノードが格納された前記配列の配列要素の配列番号を取得し、該取得した配列番号の配列要素からルートノードを読み出すルートノード読出手段と、
前記ノードのノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号との演算によりノードが格納された前記配列の配列要素の配列番号を求め、該求めた配列番号の配列要素に配置されたノードをリンク先ノードとして読み出すリンク手段と、
を備え、
前記削除キーを前記検索キーとして、
前記ルートノード読出手段でルートノードを読み出し、該読み出したルートノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出すとともに、前記ノード種別判定手段でリンク先ノードのノード種別がブランチノードと判定する毎に該ブランチノードが格納された配列要素の配列番号を親ノードの配列番号として退避する検索ステップと、
前記検索ステップで読み出したインデックスキーと前記削除キーが等しいとき、
該インデックスキーを保持する前記リーフノードと同一ノード対を構成するノードが格納された配列要素の内容を読み出すノード読出ステップと、
前記検索ステップで退避された親ノードの配列番号の配列要素に前記ノード読出ステップで読み出した配列要素の内容を書き込む書込みステップと、
前記ノード対の記憶されていた配列要素の組を解放するノード対削除ステップと、
を実行することを特徴とするインデックスキー削除方法。
【請求項４】
請求項１記載のインデックスキー挿入方法をコンピュータに実行させるためのプログラム。
【請求項５】
請求項２記載のカップルドノードツリー生成方法をコンピュータに実行させるためのプログラム。
【請求項６】
請求項３記載のインデックスキー削除方法をコンピュータに実行させるためのプログラム。
【請求項７】
請求項４〜請求項６いずれか１項に記載のプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【請求項１】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、前記ツリーに所望のビット列からなる挿入キーをインデックスキーとして格納するインデックスキー挿入方法において、
前記ツリーは配列に記憶されたツリーであって、該ツリーの始点であるルートノードと、前記配列の隣接した配列要素に配置される２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含まないものである、カップルドノードツリーであり、
前記ビット列検索装置は、
前記ルートノードが格納された前記配列の配列要素の配列番号を取得し、該取得した配列番号の配列要素からルートノードを読み出すルートノード読出手段と、
前記ノードのノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号との演算によりノードが格納された前記配列の配列要素の配列番号を求め、該求めた配列番号の配列要素に配置されたノードをリンク先ノードとして読み出すリンク手段と、
を備え、
前記挿入キーを前記検索キーとして、
前記ルートノード読出手段でルートノードを読み出し、該読み出したルートノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出す検索ステップと、
前記検索ステップで読み出したインデックスキーと前記挿入キーの間で大小比較とビット列比較を行う比較ステップと、
前記配列からノード対を格納する空配列要素の組を取得し、その一方の配列要素の配列番号を取得する空ノード対取得ステップと、
前記比較ステップにおける前記大小比較により挿入キーを含むリーフノードを前記空ノード対取得ステップで取得した空配列要素の組のどちらの空配列要素に格納するかを決定するリーフノード格納位置決定ステップと、
前記検索ステップを再度開始するとともに、前記リンク手段により読み出される各リンク先ノードであるブランチノードの弁別ビット位置が前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあるか順次判定し、前記リンク手段によりリーフノードが読み出される前に前記リンク先ノードであるブランチノードの弁別ビット位置が前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定すると該ブランチノードを、前記リンク先ノードであるブランチノードの弁別ビット位置が前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置より下位の位置関係にあると判定する前に前記リンク手段がリーフノードを読み出すと該リーフノードを、前記空ノード対取得ステップで取得した空配列要素の組に格納されるノード対のリンク元ノードとして該ノード対の挿入位置を決定するノード対挿入位置決定ステップと、
前記リーフノード格納位置決定ステップで決定した空配列要素に配置するリーフノードの、ノード種別を格納する領域にリーフノードであることを示すノード種別を、インデックスキーを格納する領域に前記挿入キーを書き込み、もう一方の空配列要素に、前記ノード対挿入位置決定ステップで前記リンク元ノードとされたノードの内容を読み出して書き込むことで挿入ノード対を生成する挿入ノード対生成ステップと、
前記ノード対挿入位置決定ステップで前記リンク元ノードとされたノードをブランチノードとし、そのノード種別を格納する領域にブランチノードであることを示すノード種別を、弁別ビット位置を格納する領域に前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置を、リンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域に前記空ノード対取得ステップで取得した配列番号を、それぞれ書き込むブランチノード生成ステップと、
を備えたことを特徴とするインデックスキー挿入方法。
【請求項２】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、前記ツリーを生成するツリー生成方法において、
前記ツリーは請求項１に記載されたカップルドノードツリーであり、
前記ビット列検索装置は請求項１に記載されたものであって、
前記カップルドノードツリーに格納するインデックスキーの集合から１つのインデックスキーを取り出し、該インデックスキーを含むリーフノードをルートノードとするカップルドノードツリーを生成し、
前記インデックスキーの集合からさらに順次インデックスキーを取り出して該インデックスキーを、請求項１記載のインデックスキー挿入方法により前記カップルドノードツリーに挿入することによりカップルドノードツリーを生成することを特徴とするカップルドノードツリーの生成方法。
【請求項３】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、所望のビット列からなる削除キーと等しい前記ツリーに格納されたインデックスキーを削除するインデックスキー削除方法において、
前記ツリーは配列に記憶されたツリーであって、該ツリーの始点であるルートノードと、前記配列の隣接した配列要素に配置される２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域を含まないものである、カップルドノードツリーであり、
前記ビット列検索装置は、
前記ルートノードが格納された前記配列の配列要素の配列番号を取得し、該取得した配列番号の配列要素からルートノードを読み出すルートノード読出手段と、
前記ノードのノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号との演算によりノードが格納された前記配列の配列要素の配列番号を求め、該求めた配列番号の配列要素に配置されたノードをリンク先ノードとして読み出すリンク手段と、
を備え、
前記削除キーを前記検索キーとして、
前記ルートノード読出手段でルートノードを読み出し、該読み出したルートノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出すとともに、前記ノード種別判定手段でリンク先ノードのノード種別がブランチノードと判定する毎に該ブランチノードが格納された配列要素の配列番号を親ノードの配列番号として退避する検索ステップと、
前記検索ステップで読み出したインデックスキーと前記削除キーが等しいとき、
該インデックスキーを保持する前記リーフノードと同一ノード対を構成するノードが格納された配列要素の内容を読み出すノード読出ステップと、
前記検索ステップで退避された親ノードの配列番号の配列要素に前記ノード読出ステップで読み出した配列要素の内容を書き込む書込みステップと、
前記ノード対の記憶されていた配列要素の組を解放するノード対削除ステップと、
を実行することを特徴とするインデックスキー削除方法。
【請求項４】
請求項１記載のインデックスキー挿入方法をコンピュータに実行させるためのプログラム。
【請求項５】
請求項２記載のカップルドノードツリー生成方法をコンピュータに実行させるためのプログラム。
【請求項６】
請求項３記載のインデックスキー削除方法をコンピュータに実行させるためのプログラム。
【請求項７】
請求項４〜請求項６いずれか１項に記載のプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【公開番号】特開２０１１−１８２９６（Ｐ２０１１−１８２９６Ａ）
【公開日】平成２３年１月２７日（２０１１．１．２７）
【国際特許分類】
【出願番号】特願２００９−１６４３０５（Ｐ２００９−１６４３０５）
【出願日】平成２１年７月１１日（２００９．７．１１）
【出願人】（５０６２３５６１６）株式会社エスグランツ (32)
【Ｆターム（参考）】
【公開日】平成２３年１月２７日（２０１１．１．２７）
【国際特許分類】
【出願日】平成２１年７月１１日（２００９．７．１１）
【出願人】（５０６２３５６１６）株式会社エスグランツ (32)
【Ｆターム（参考）】
[ Back to top ]