インデックス更新データ作成装置、作成方法及びプログラム
【課題】データベースのインデックスの差分更新を行うインデックス更新装置の処理負担を軽減する手法を提供する。
【解決手段】更新前のデータベースのインデックスキーを格納した差分ツリーを取得する手段と、更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する手段と、差分データに基づき差分ツリーを更新し、更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する手段を備えたインデックス更新データ作成装置。
【解決手段】更新前のデータベースのインデックスキーを格納した差分ツリーを取得する手段と、更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する手段と、差分データに基づき差分ツリーを更新し、更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する手段を備えたインデックス更新データ作成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースのインデックスの更新処理に関し、特に、インデックス更新に用いるインデックス更新データの作成処理とそのインデックス更新データによるインデックス更新処理に関する。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。また、カーナビゲーション用の地図データのように販売数の非常に大きなデータベースも存在する。
【０００３】
このようなデータベースシステムの機能として、データの更新機能は必須である。データベースに保管されるデータ量が増大するのに伴って、例えばバッチ処理により既存のデータベースに対して大量のデータの追加や削除を行おうとすると、その作業に要する時間が長くなるという不都合が生じている。
【０００４】
データベースのバッチ更新の態様としては、既存のデータベースに対する追加、変更あるいは削除データによりデータベースを更新する差分更新という態様と、既存のデータベースを新しいデータベースでそっくり置き換える態様が存在する。
【０００５】
後者のデータベース更新の態様は、例えばデータベースのデータの供給者が、データベースの更新が必要になったときにデータベースの更新データを供給するのではなく、データを更新済みの新しい版のデータベースを改めて供給する場合に採用される。しかし、このようなデータベースの更新の態様では、更新作業中はデータベースの利用ができないことから、この更新作業に長時間を要するのでは不便である。
【０００６】
また、データベースは、データベース本体のデータ部分とデータベース本体からデータを検索するためのインデックスから構成されるのが通例である。そこで、データベースの更新の態様には、インデックス部分を更新する態様があり、この部分の更新においても、更新後のインデックス全体が供給され、更新前のインデックスとそっくり入れ替える場合がある。
【０００７】
例えばカーナビゲーションシステムの地図データのインデックスを更新する場合には、地図データの販売業者から購入した新しい地図データのインデックスデータを、カーナビゲーションシステムの販売業者あるいは車のディーラーのセンターから、カーナビゲーションシステムを搭載した各車に配布し、搭載されたカーナビゲーションシステムごとに、インデックスデータを更新する。このように、新しいインデックスデータ全体を配布するため、配布するデータ量が多く、また各カーナビゲーションシステムにおける地図データの更新時間も長いものとなる。
【０００８】
そこで、インデックデータの追加、変更あるいは削除データの供給を受けるか、あるいはインデックスデータの新旧データから差分データを抽出して差分更新により、データベースを更新することが行われている。
下記特許文献１には、ナビゲーション端末で用いられる地図データの差分更新について記載されている。
【０００９】
上述のデータベースの差分更新を行うためには、データベースから更新対象のレコードの検索を行う必要がある。データベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
【００１０】
ビット列の検索処理手法については、種々のものが知られている。それらのなかでも、ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが行われている。このようなものの一つとして、下記特許文献２、３に記載された、カップルドノードツリーというデータ構造を用いた検索手法がある。
【００１１】
カップルドノードツリーは、ツリーの始点であるルートノードと、隣接した記憶領域に配置される２つのノードで構成されるツリーの構成要素としてのノード対を有する。ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、ブランチノードは、ノード種別に加えて、検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードである代表ノードの位置を示す情報を格納する領域を含むが、検索対象のビット列からなるインデックスキーを格納する領域を含まないものである。リーフノードは、ノード種別に加えて、検索対象のビット列からなるインデックスキーを格納する領域を含むが、検索キーの弁別ビット位置を格納する領域とリンク先の代表ノードの位置を示す情報を格納する領域を含まないものである。
【００１２】
上記カップルドノードツリーの任意のノードを検索開始ノードとして、各ブランチノードの弁別ビット位置に位置する検索キーのビット値に応じてリンク先を選択し、リーフノードに至ることにより、リーフノードに格納されたインデックスキーを検索キーによる検索結果キーとして取得する。
以下において、カップルドノードツリーとそれを用いた検索処理について、さらに説明する。その説明では、カップルドノードツリーは配列に格納されたものとする。ブランチノードが保持する代表ノードの位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【００１３】
図１は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図１を参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【００１４】
配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
【００１５】
なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。
【００１６】
ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【００１７】
図２は、カップルドノードツリーのツリー構造を概念的に示す図である。
符号２１０ａで示すのがルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。
ツリー構造としては、ルートノード２１０ａの下にノート対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。
各ノードの前に付された０あるいは１の符号は、図１において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００１８】
図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
【００１９】
ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。
【００２０】
ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
【００２１】
ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。
ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。
【００２２】
ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。
ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの格納された配列要素の配列番号２２１ｆが格納されている。
【００２３】
ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。
また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００“が格納されている。
【００２４】
以下、上述のツリーからインデックスキー“１０００１０”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
【００２５】
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを読み出して検索キーと比較すると両方とも“１０００１０”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【００２６】
次に、図２を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図２Ｂの例で、ルートノード２１０ａの弁別ビット位置が０であるのは、図２Ｂに例示されたインデックスキーに０ビット目が０のものと１のものがあるからである。０ビット目が０のインデックスキーのグループはノード２１０ｂの下に分類され、０ビット目が１のインデックスキーのグループはノード２１１ｂの下に分類されている。
【００２７】
ノード２１１ｂの弁別ビット位置が２であるのは、ノード２１１ｈ、２１０ｈ、２１１ｇ、２１０ｇに格納された０ビット目が１のインデックスキーの１ビット目がすべて０で等しく、２ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
以下０ビット目の場合と同様に、２ビット目が１であるものはノード２１１ｆ側に分類され、２ビット目が０であるものはノード２１０ｆ側に分類される。
そして２ビット目が１であるインデックスキーは３ビット目の異なるものがあるのでノード２１１ｆの弁別ビット位置には３が格納され、２ビット目が０であるインデックスキーでは３ビット目も４ビット目も等しく５ビット目で異なるのでノード２１０ｆの弁別ビット位置には５が格納される。
【００２８】
ノード２１１ｆのリンク先においては、３ビット目が１のものと０のものがそれぞれ１つしかないことから、ノード２１０ｈ、２１１ｈはリーフノードとなり、それぞれインデックスキー２５０ｈと２５１ｈに“１０１０１１”と“１０１１００”が格納されている。
仮にインデックスキーの集合に“１０１１００”の代わりに“１０１１０１”か“１０１１１０”が含まれていたとしても、３ビット目までは“１０１１００”と等しいので、ノード２１１ｈに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“１０１１００”に加えて“１０１１０１”が含まれていると、ノード２１１ｈはブランチノードとなり、その弁別ビット位置は５になる。追加されるインデックスキーが“１０１１１０”であれば、弁別ビット位置は４となる。
【００２９】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“１”のノードとビット値が“０”のノードとに分岐していることから、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード２１１ｈのインデックスキー２５１ｈの“１０１１００”、ノード２１０ｈのインデックスキー２５０ｈの“１０１０１１”、・・・、ノード２１０ｃのインデックスキー２５０ｃの“０００１１１”となり降順にソートされている。
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
【００３０】
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“１０１１００”であればノード２１１ｈに到達することができる。また、上記説明からも想像がつくように、“１０１１０１”か“１０１１１０”を検索キーとした場合でもノード２１１ｈにたどり着く。インデックスキー２５１ｈと比較することにより検索が失敗したとすることもできるし、インデックスキー２５１ｈである“１０１１００”を検索結果キーとすることもできる。
【００３１】
また、例えば“１００１００”で検索した場合でも、ノード２１０ａ、２１１ｂ、２１０ｆのリンク経路では検索キーの３ビット目と４ビット目は使われることがなく、“１００１００”の５ビット目が０なので、“１０００１０”で検索した場合と同様にノード２１０ｇに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【００３２】
次に、上述のカップルドノードツリーを用いた検索処理、及びカップルドノードツリーの挿入削除処理について説明する。以下の説明においては、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる。また、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合があるし、データ自体の名前をそのデータを格納する一時記憶領域の名前として用いることもある。
【００３３】
図３は、下記特許文献３に開示されたビット列検索の基本動作を示したフローチャートである。
まず、ステップＳ３０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、オペレータからの入力によってもよいし、図３に例示する処理を利用するアプリケーションプログラムによるものでもよい。
取得された検索開始ノードの配列番号は、図示しない検索開始ノード設定エリアに設定されるが、この検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の一つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードの配列番号を得る。」、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。
【００３４】
次に、ステップＳ３０２で、探索経路スタック３１０に取得された配列番号を格納し、ステップＳ３０３で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップＳ３０４で、読み出したノードから、ノード種別を取り出し、ステップＳ３０５で、ノード種別がブランチノードであるか否かを判定する。
ステップＳ３０５の判定において、読み出したノードがブランチノードである場合は、ステップＳ３０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ３０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ３０８で、ノードから代表ノード番号を取り出して、ステップＳ３０９で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、ステップＳ３０２に戻る。
【００３５】
以降、ステップＳ３０５の判定においてリーフノードと判定されてステップＳ３１０に進むまで、ステップＳ３０２からステップＳ３０９までの処理を繰り返す。ステップＳ３１０で、リーフノードからインデックスキーを検索結果キーとして取り出して、処理を終了する。
上述の説明では、カップルドノードツリーは配列に格納されているものとしたため、探索経路スタック３１０には配列番号を格納するとしたが、カップルドノードツリーが配列に格納されていない場合は、配列番号に替えてリンク先のノードの位置を示す情報が探索経路スタック３１０に格納される。
【００３６】
次に、図４Ａ〜図４Ｃにより下記特許文献２に開示されたカップルドノードツリーにおけるノード挿入処理を説明する。
図４Ａは挿入処理の前段である検索処理の処理フローを示す図であり、図３に示した検索処理において、ルートノードを検索開始ノードとし、挿入キーを検索キーとしたものに相当する。
【００３７】
ステップＳ４０１において、検索開始ノードの配列番号を設定するエリアにルートノードの配列番号を設定し、ステップＳ４０２において、検索キーに挿入キーを設定する。
次にステップＳ４１０において、図３に示す検索処理を実行し検索結果のインデックスキーを得て、ステップＳ４１１に進む。
ステップＳ４１１において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図４ＢのステップＳ４１２以下の処理に進む。
【００３８】
図４Ｂは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップＳ４１２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
ステップＳ４１３に進み、挿入キーとステップＳ４１０で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１を小さいときは値０のブール値を得る。
ステップＳ４１４に進み、ステップＳ４１２で得た代表ノードの配列番号にステップＳ４１３で得たブール値を加算した配列番号を得る。
ステップＳ４１５に進み、ステップＳ４１２で得た代表ノードの配列番号にステップＳ４１３で得たブール値の論理否定値を加算した配列番号を得る。
ステップＳ４１４で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップＳ４１５で得た配列番号は、そのリーフノードと対を成すブランチノードあるいはリーフノードが格納される配列要素のものである。
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【００３９】
次に図４ＣのステップＳ４１６以下の処理に進む。
図４Ｃは図４Ｂで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
ステップＳ４１６〜ステップＳ４２３までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップＳ４２４以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【００４０】
ステップＳ４１６で、挿入キーとステップＳ４１０で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップＳ４１７に進み、ステップＳ４１６で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【００４１】
次にステップＳ４１８に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップＳ４２４に移行し、指していなければステップＳ４１９に進む。
【００４２】
ステップＳ４１９において、探索経路スタックのスタックポインタを１つ戻してそこにスタックされている配列番号を取り出す。
ステップＳ４２０に進み、ステップＳ４１９で取り出した配列番号の配列要素を配列からノードとして読み出す。
ステップＳ４２１に進み、ステップＳ４２０で読み出したノードから、弁別ビット位置を取り出す。
次にステップＳ４２２に進み、ステップＳ４２１で取り出した弁別ビット位置がステップＳ４１７で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【００４３】
ステップＳ４２２の判定結果が否定であれば、ステップＳ４１８に戻り、ステップＳ４１８での判定が肯定になるかステップＳ４２２での判定が肯定になるまで繰り返す。ステップＳ４２２での判定が肯定になると、ステップＳ４２３で経路探索スタックのスタックポインタを1つ進め、ステップＳ４２４以下の処理に移行する。
【００４４】
上記ステップＳ４１６〜ステップＳ４２３で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の（最上位の）ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。
また、経路探索スタック逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【００４５】
次に、ステップＳ４２４以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップＳ４２４では探索経路スタックからスタックポインタの指す配列番号を取り出す。
ステップＳ４２５において、ステップＳ４１４で得た配列番号の指す配列要素のノード種別に１（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップＳ４２６に進み、配列からステップＳ４２４で得た配列番号の配列要素を読み出す。
次にステップＳ４２７において、ステップＳ４１５で得た配列番号の配列要素にステップＳ４２６で読み出した内容を書き込む。
最後にステップＳ４２８において、ステップＳ４２４で得た配列番号の指す配列要素のノード種別に０(ブランチノード）を、弁別ビット位置にステップＳ４１７で得たビット位置を、代表ノード番号にステップＳ４１２で得た配列番号を書き込み、処理を終了する。
【００４６】
図５は、下記特許文献２に開示されたカップルドノードツリーを生成する処理フロー例である。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成される。
ステップＳ５０１において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図４Ａ〜図４Ｃを用いて説明した通常の挿入処理が行われる。
【００４７】
ステップＳ５０１での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップＳ５０２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップＳ５０３において、ステップＳ５０２で得た配列番号に０を加えた配列番号を求める。（実際には、ステップＳ５０２で取得した配列番号に等しい。)。さらにステップＳ５０４において、ステップＳ５０３で得た配列番号の配列要素に、挿入するルートノードのノード種別に１（リーフノード)とインデックスキーに挿入キーを書き込み、ステップＳ５０５で、ステップＳ５０２で取得したルートノードの配列番号を登録して処理を終了する。
【００４８】
インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図５及び図４Ａ〜図４Ｃの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができる。
【００４９】
次に図６Ａ、図６Ｂを参照して、下記特許文献２に開示されたカップルドノードツリーから、特定のインデックスキーを格納したリーフノードを削除する処理フローを説明する。
図６Ａは、削除処理の前段である検索処理の処理フロー例を示す図であり、図３に示した検索処理において、ルートノードを検索開始ノードとし、挿入キーを検索キーとしたものに相当する。
【００５０】
ステップＳ６０１において、検索開始ノードの配列番号を設定するエリアにルートノードの配列番号を設定し、ステップＳ６０２において、検索キーに削除キーを設定する。
次にステップＳ６１０において、図４に示す検索処理を実行し検索結果のインデックスキーを得て、ステップＳ６１１に進む。
図６ＡのステップＳ６１１において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図６ＢのステップＳ６１２以下の処理に進む。
【００５１】
図６Ｂは、削除処理の後段の処理フローを説明する図である。
まず、ステップＳ６１２で探索経路スタックに２つ以上の配列番号が格納されているか判定する。２つ以上の配列番号が格納されていないということは、言い換えれば１つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップＳ６１８に移行し、ステップＳ６０１で得たルートノードの配列番号に係るノード対を削除する。次にステップＳ６１９に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【００５２】
ステップＳ６１２において探索経路スタックに２つ以上の配列番号が格納されていると判定されたときはステップＳ６１３に進み、ステップＳ６１０で参照するする図３に示す処理フローのステップＳ３０８で得た代表ノード番号にステップＳ３０７で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【００５３】
次にステップＳ６１４において、ステップＳ６１３で得た配列番号の配列要素の内容を読み出し、ステップＳ６１５において探索経路スタックのスタックポインタを１つ戻して配列番号を取り出す。
次にステップＳ６１６に進み、ステップＳ６１４で読み出した配列要素の内容をステップＳ６１５で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
最後にステップＳ６１７において、ステップＳ６１０で参照するする図３に示す処理フローのステップＳ３０８で得た代表ノード番号に係るノード対を削除して処理を終了する。
【先行技術文献】
【特許文献】
【００５４】
【特許文献１】特開２００７−２４０４９２号公報
【特許文献２】特開２００８−０１５８７２号公報
【特許文献３】特開２００８−１１２２４０号公報
【発明の概要】
【発明が解決しようとする課題】
【００５５】
本発明が解決しようとする課題は、データベースのインデックスの更新を行うインデックス更新装置の処理負担を軽減する手法を提供することである。
【課題を解決するための手段】
【００５６】
本発明のインデックス更新データ作成装置は、更新前のデータベースのインデックスキーを格納したカップルドノードツリーである差分ツリーを取得する差分ツリー取得手段と、更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する差分データ取得手段と、差分データに基づき差分ツリーを更新し、該更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する更新データ作成手段と、を備える。
また、本発明のインデックス更新装置は、更新前のデータベースのインデックスキーを格納したカップルドノードツリーである更新ツリーを取得する更新ツリー取得手段と、インデックス更新データ作成装置から更新すべき更新ツリーのノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを取得する更新データ取得手段と、更新データの更新位置のノードの内容を更新ノードで書き換えることにより更新ツリーを更新する更新ツリー更新手段と、を備える。
【発明の効果】
【００５７】
本発明によれば、インデックス更新データ作成装置が、差分データに基づいてインデックス更新装置が更新すべきデータの位置とその内容を作成するので、インデックス更新装置の処理負担は大幅に削減される。
【図面の簡単な説明】
【００５８】
【図１】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２】カップルドノードツリーのツリー構造を概念的に示す図である。
【図３】ビット列検索の基本動作例を示すフローチャートである。
【図４Ａ】挿入処理の前段である検索処理の処理フロー例を示す図である。
【図４Ｂ】挿入するノード対の配列要素を準備する処理フロー例を示す図である。
【図４Ｃ】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フロー例を示す図である。
【図５】カップルドノードツリーを生成する処理フロー例を示す図である。
【図６Ａ】削除処理の前段である検索処理の処理フロー例を示す図である。
【図６Ｂ】削除処理の後段の処理フロー例を示す図である。
【図７】本発明の原理を説明する図である。
【図８Ａ】インデックス更新データ作成装置の機能ブロック構成例を説明する図である。
【図８Ｂ】インデックス更新装置の機能ブロック構成例を説明する図である。
【図９】本発明を実施するためのハードウェア構成例を説明する図である。
【図１０】差分データによる更新データ作成処理の概要を説明する図である。
【図１１】差分データによる更新データ作成の処理フロー例を示す図である。
【図１２Ａ】差分ツリーに更新種別が挿入である差分データのインデックスキーを挿入して更新データを作成する処理フロー例を示す図である。
【図１２Ｂ】差分ツリーから更新種別が削除である差分データのインデックスキーを削除して更新データを作成する処理フロー例を示す図である。
【図１３Ａ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｂ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｃ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｄ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｅ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１４】更新データによるインデックス更新処理の概要を説明する図である。
【図１５】更新データによるインデックス更新の処理フロー例を示す図である。
【図１６Ａ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｂ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｃ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｄ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｅ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【発明を実施するための形態】
【００５９】
図７を参照して、本発明の原理を説明する。本発明に係る差分更新システムは、インデックス更新データ作成装置３００と任意の数のインデックス更新装置４００ａ、４００ｂから構成される。なお、どのインデックス更新装置についての説明は同じであるので、以下の説明では、インデックス更新装置４００のように表記する場合がある。インデックス更新装置の構成要素についても同様に表記する場合がある。
インデックス更新データ作成装置３００は、インデックスを格納する配列３０９、差分データ格納領域３２０、及び更新データ格納領域３２２を含む。差分データ格納領域３２０には、差分データとして、挿入データである挿入キーと削除データである削除キーが取得され、格納される。差分データの取得方法は、データベースの供給元から提供を受けるものであってもよいし、データベース供給元から新インデックスを受領し、旧インデックスとの差分を抽出するものであってもよい。
【００６０】
インデックス更新データ作成装置３００は、旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧差分ツリー）３０９０に対して、差分データ格納領域３２０に格納された挿入キーと削除キーによる挿入処理と削除処理を実行し、新インデックスに対応した新差分ツリー３０９１を得る。図７の例では、差分ツリーは配列に配置されているが、先にも述べたとおり、配列に配置することは必須ではない。
【００６１】
上記挿入処理時及び削除処理時に得られる情報を基に、インデックス更新データ作成装置３００は、インデックス更新装置４００においてインデックスの更新に用いられる更新データ３８０を作成して更新データ格納領域３２２に格納する。更新データ３８０は、更新対象のノードの位置を示す更新位置３８３と更新内容である更新ノード３８４を含む。
【００６２】
更新データ格納領域３２２に格納された更新データ３８０は、この更新データを用いてデータベースのインデックスを更新するインデックス更新装置４００に送信される。更新データ３８０の送信は、無線、有線あるいはそれらを組み合わせた通信回線を用いたもの、記憶媒体を用いたもの、通信回線と記憶媒体を組み合わせたものなどで実現される。
【００６３】
インデックス更新装置４００に送信された更新データ３８０は、更新データ格納領域４２０に格納される。インデックス更新装置４００は、旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧更新ツリー）４０９０のノード、すなわち旧更新ツリーの配置された配列４０９ａの配列要素の内容に対して、更新データ格納領域４２０に格納された更新データ３８０による書換処理を実行し、新インデックスに対応した新更新ツリー４０９１を得る。
【００６４】
インデックス更新装置４００における更新ツリーに格納されたインデックスキーの更新は、カップルドノードツリーの挿入処理や削除処理によるのではなく、更新ツリーの配置された配列の配列要素の内容を書き換えることにより実現されるので、インデックス更新装置４００における処理負担を軽減させることができる。
【００６５】
図８Ａは、インデックス更新データ作成装置の機能ブロック構成例を説明する図である。
インデックス更新データ作成装置３００は、差分ツリー取得手段３３０、差分データ取得手段３４０、及び更新データ作成手段３５０を含んで構成される。
【００６６】
差分ツリー取得手段３３０は、図７に示す旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧差分ツリー）３０９０を取得するものである。旧インデックスであるインデックスキーが既にカップルドノードツリーに格納されていれば、それを旧差分ツリー３０９０とする。そうでなければ、インデックスキーを取り出して図５に示すカップルドノードツリーの生成処理を実行して生成したカップルドノードツリーを旧差分ツリーとする。
【００６７】
差分データ取得手段は、差分データとして、挿入データである挿入キーと削除データである削除キーを取得し、差分データ格納領域３２０に格納する。差分データの取得方法は、先に述べたように、データベースの供給元から提供を受けるものであってもよいし、データベース供給元から新インデックスを受領し、旧インデックスとの差分を抽出するものであってもよい。
【００６８】
更新データ作成手段３５０は、差分データ取得手段３４０で取得された差分データに基づき差分ツリー取得手段３３０で取得された差分ツリーを更新し、インデックス更新装置４００において用いるインデックスの更新データを作成する。更新データ作成手段３５０は、挿入データ作成手段３５２、削除データ作成手段３５４及び更新種別判定手段３５６を含む。更新種別判定手段３５６は、差分データが挿入データであるか削除データであるか判定する。挿入データ作成手段３５２は、挿入データに基づいて更新データを作成し、削除データ作成手段３５４は、削除データに基づいて更新データを作成する。
それぞれの手段の詳細な動作は、後に図１０〜図１３Ｅを参照して説明する。
【００６９】
図８Ｂは、インデックス更新装置の機能ブロック構成例を説明する図である。
インデックス更新装置４００は、更新ツリー取得手段４３０、更新データ取得手段４４０、及び更新ツリー更新手段３５０を含んで構成される。
【００７０】
更新ツリー取得手段４３０は、図７に示す旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧更新ツリー）４０９０を取得するものである。旧インデックスであるインデックスキーが既にカップルドノードツリーに格納されていれば、それを旧更新ツリー４０９０とする。そうでなければ、インデックスキーを取り出して図５に示すカップルドノードツリーの生成処理を実行して生成したカップルドノードツリーを旧更新ツリーとする。
【００７１】
更新データ取得手段４４０は、インデックス更新データ作成装置３００から送信された更新データを受信して更新データ格納装置４２０に格納する。更新データの送信方法は、先に述べたとおりのものである。
【００７２】
更新ツリー更新手段４５０は、旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧更新ツリー）４０９０のノード、すなわち旧更新ツリーの配置された配列４０９の配列要素の内容に対して、更新データ取得手段４４０において取得され、更新データ格納領域４２０に格納された更新データによる書換処理を実行し、新インデックスに対応した新更新ツリー４０９１を得る。
【００７３】
図９は、本発明を実施するためのハードウェア構成例を説明する図である。図に示すように、本発明を実施するためのハードウェアは、インデックス更新データ作成装置３００とインデックス更新装置４００ａ〜４００ｘで構成される。インデックス更新装置４００ａ〜４００ｘの数は任意である。
【００７４】
本発明のインデックス更新データ作成装置３００による更新データ作成は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０、差分データを格納する差分データ格納領域３２０及び作成済みの更新データを格納する更新データ格納領域３２２を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００７５】
図９の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、更新データ格納領域３２２及び差分データ格納領域３２０は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。
【００７６】
インデックス更新データ作成装置３００において作成された更新データは、インデックス更新装置４００ａ〜４００ｘに送られ、それぞれの差分データ格納領域４２０ａ〜４２０ｘに格納され、それぞれのインデックス格納領域である配列４０９ａ〜４０９ｘに格納された旧データを新データに更新するために用いられる。特に図示はしていないが、インデックス更新装置４００ａ〜４００ｘにおいても、データ処理装置や、差分データ格納領域、インデックス格納領域及びその他の記憶領域を有するデータ格納装置が備えられている。
なお、以下においては、上述の例えば差分データ格納領域３２０に格納された差分データを差分データ３２０と表記するように、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合がある。
【００７７】
図１０は、本発明の一実施形態における差分データにより更新データを作成する処理の概要を説明する図である。
図１０に示す例では、差分データ格納領域３２０には、差分データ３９０ａ、３９０ｂ、３９０ｃ、３９０ｄが格納されている。各差分データは更新種別３９１と差分キー３９２で構成されている。
差分データ３９０ａの更新種別は削除を意味する“ｄ”、差分キーはキー３２１ｄ“１０１０１１”である。差分データ３９０ｂの更新種別は“ｄ”、差分キーはキー３２１ｂ“０１００１１”である。差分データ３９０ｃの更新種別は挿入を意味する“ｉ”、差分キーはキー３２２ｃ“１０００１１”である。差分データ３９０ｄの更新種別は“ｉ”、差分キーはキー３２２ｂ“０１０１１０”である。
【００７８】
更新処理の開始前の差分ツリー３０９０には、インデックスキーとして“１０１１００”、“１０１０１１”、“１０００１１”、“０１００１１”、“０１００１０”が格納されている。矢印３３１ｄ及び矢印３３１ｂで示すように、更新種別が“ｄ”である差分データのキー３２１ｄとキー３２１ｂにより差分ツリー３０９０の削除処理が行われ、矢印３３３で示すように、キー３２１ｄによる更新データ３８０ａとキー３２１ｂによる更新データ３８０ｂが作成され、更新データ格納領域３２２に格納される。
【００７９】
また、矢印３３２ｃ及び矢印３３２ｂで示すように、更新種別が“ｉ”である差分データのキー３２２ｃとキー３２２ｂにより挿入処理が行われ、更新後の差分ツリー３０９１にインデックスキーとして挿入される。そして、矢印３３４で示すように、キー３２２ｃによる更新データ３８０ｃとキー３２２ｂによる更新データ３８０ｄが作成され、更新データ格納領域３２２に格納される。
【００８０】
上述の削除処理と挿入処理により、更新前の差分ツリー３０９０から符号３２１ｄで示すインデックスキー“１０１０１１”と符号３２１ｂで示すインデックスキー“１０００１１”が削除され、点線の矢印で示すように、インデックスキー３２１ｅ“１０１１００”、３２１ｃ“１０００１１”、３２１ａ“０１００１０”が更新後の差分ツリー３０９１に残る。また、差分ツリー３０９１にはインデックスキー３２２ｃ、３２２ｂが挿入されている。
【００８１】
次に、図１１を参照して、差分データによる更新データ作成の処理フロー例を説明する。
図１１に示すように、ステップＳ１１０１において差分ツリーを設定し、ステップＳ１１０２において差分データを設定する。差分ツリーの設定は、図８Ａに示す差分ツリー取得手段３３０による差分ツリーの取得、すなわち差分ツリーのルートノードの配列番号を取得し設定することにより行われる。差分データの設定は、差分データ取得手段３４０により差分データを取得して差分データ格納領域３２０に格納することにより行われる。
【００８２】
ステップＳ１１０３に進み、すべての差分データは処理済みか判定する。すべての差分データが処理済みであれば処理を終了し、すべての差分データが処理済みでなければ、ステップＳ１１０４に進む。
【００８３】
ステップＳ１１０４では、差分データ格納領域から差分データを読み出し、読み出した差分データの差分キーを取り出し、ステップＳ１１０５において、差分データの更新種別を取り出す。
【００８４】
次にステップＳ１１０６において、ステップＳ１１０５で取り出した更新種別を判定し、更新種別が削除であればステップＳ１１０７に進み、削除でなければステップＳ１１０８に進む。
【００８５】
ステップＳ１１０７では、ステップＳ１１０４で取り出した差分キーを削除キーとして、差分ツリーより削除するとともに、更新データを作成し、ステップＳ１１０３に戻る。ステップＳ１１０７の処理の詳細は、後に図１２Ｂを参照して説明する。
【００８６】
ステップＳ１１０８では、ステップＳ１１０４で取り出したキーを挿入キーとして、差分ツリーに挿入するとともに、更新データを作成し、ステップＳ１１０３に戻る。ステップＳ１１０８の処理の詳細は、次に図１２Ａを参照して説明する。
上記ステップＳ１１０３〜ステップＳ１１０７、ステップＳ１１０８のループ処理を、ステップＳ１１０３において全ての差分データを処理済みと判定するまで繰り返し、全ての差分データを処理済みと判定すると処理を終了する。
全ての差分データの処理済みを判定するには、差分データ格納領域に格納された差分データ数をカウントしておき、１つ差分データを処理する毎に差分データ数をデクリメントする等、種々の手法を採用可能である。
【００８７】
図１２Ａは、差分ツリーに更新種別が挿入である差分データの差分キーを挿入して更新データを作成する処理フロー例を示す図であり、図１１に示すステップＳ１１０８の処理の詳細を説明するものである。
【００８８】
まずステップ１２０１で、差分キーを挿入キーとして、差分ツリーに挿入する。ステップＳ１２０１の処理の詳細は、図４Ａ〜図４Ｃを参照して説明したものである。
【００８９】
次にステップＳ１２０２において、挿入したキーを含むリーフノードの配列番号とリーフノードの内容により第１の更新データを作成する。
挿入したキーを含むリーフノードの配列番号は、ステップＳ１２０１において図４Ｂに示すステップＳ４１４で得た配列番号であり、リーフノードの内容は、図４ＣのステップＳ４２５で書き込まれたものである。
【００９０】
次にステップＳ１２０３において、挿入したキーを含むリーフノードと対をなす対ノードの配列番号と対ノードの内容により第２の更新データを作成する。
対ノードの配列番号は、ステップＳ１２０１において図４Ｂに示すステップＳ４１５で得た配列番号であり、対ノードの内容は、図４ＣのステップＳ４２７で書き込まれたものである。
【００９１】
次にステップＳ１２０４において、挿入したキーを含むリーフノードの直近上位のブランチノードの配列番号とブランチノードの内容により第３の更新データを作成して処理を終了する。
ブランチノードの配列番号は、ステップＳ１２０１において図４Ｃに示すステップＳ４２４で探索経路スタックから取り出した配列番号であり、ブランチノードの内容は、図４ＣのステップＳ４２８で書き込まれたものである。
【００９２】
図１２Ｂは、差分ツリーから更新種別が削除である差分データの差分キーを削除して更新データを作成する処理フロー例を示す図であり、図１１に示すステップＳ１１０７の処理の詳細を説明するものである。
【００９３】
まずステップ１２１１で、差分キーを削除キーとして、差分ツリーより削除する。ステップＳ１２１１の処理の詳細は、図６Ａ、図６Ｂを参照して説明したものである。
次にステップＳ１２１２において、削除したキーを格納していたリーフノードの直近上位のブランチノードの配列番号とリーフノードと対をなしていたノードの内容により更新データを作成して処理を終了する。
ブランチノードの配列番号は、ステップＳ１２１１において、図６Ｂに示すステップＳ６１５で探索経路スタックから取り出した配列番号であり、リーフノードと対をなしていたノードの内容は、図６Ｂに示すステップＳ６１６で書き込まれたものである。
【００９４】
次に図１３Ａ〜図１３Ｅを参照して、本発明の一実施の形態における、差分データによる更新データの作成処理の流れを差分データ３９０ａ〜３９０ｄ毎に説明する。例に挙げる差分データと差分ツリーは、図１０で例示したものと同一である。しかし、差分ツリーについては、ツリー構造を明記している。
【００９５】
図１３Ａには、差分データ３９０ａによる更新前の差分ツリー３０９０が記載されている。差分ツリー３０９０は、図２に例示したカップルドノードツリーからノード２１０ｇ、２１１ｄ、２１０ｃを除いたものに相当する。したがって、差分ツリー３０９０のノード２１０ｆには、図２に示すツリーのノード２１１ｇの内容が書き込まれており、また、差分ツリー３０９０のノード２１０ｂには、図２に示すツリーのノード２１０ｄの内容が書き込まれている。
そして、図１３Ａの矢印３３１ａで示すように、差分データ３９０ａの差分キー３２１ｄを削除キーとして削除処理を実行すると、ノード２１０ｈが削除の対象となる。
【００９６】
図１３Ｂには、差分データ３９０ａによる更新後、差分データ３９０ｂによる更新前の差分ツリー３０９２が記載されている。
矢印３３３ａで示すように、差分データ３９０ａによる更新の結果、ノード２１１ｆの内容が、削除キーを含むリーフノード２１０ｈと対をなすノード２１１ｈの内容に変更されたので、差分データ３９０ａによる更新前の差分ツリー３０９０のノード２１１ｈの内容を更新ノード３８４とし、リーフノード２１０ｈの直近上位のブランチノード２１１ｇの配列番号２２１ｂ＋１を更新位置とする更新データ３８０ａが作成され、更新データ格納領域３２２に格納される。
そして、矢印３３１ｂで示すように、差分データ３９０ｂの差分キー３２１ｂを削除キーとして削除処理を実行すると、ノード２１１ｃが削除の対象となる。
【００９７】
図１３Ｃには、差分データ３９０ｂによる更新後、差分データ３９０ｃによる更新前の差分ツリー３０９３が記載されている。
矢印３３３ｂで示すように、差分データ３９０ｂによる更新の結果、ノード２１０ｂの内容が、削除キーを含むリーフノード２１０ｃと対をなすノード２１１ｃの内容に変更されたので、差分データ３９０ｂによる更新前の差分ツリー３０９２のノード２１１ｃの内容を更新ノード３８４とし、リーフノード２１０ｃの直近上位のブランチノード２１０ｂの配列番号２２０ａを更新位置とする更新データ３８０ｂが作成され、更新データ格納領域３２２に格納される。
そして、矢印３３２ｃで示すように、差分データ３９０ｃの差分キー３２２ｃを挿入キーとして挿入処理を実行すると、ノード２１０ｆが検索結果キーを格納するリーフノードとして得られる。
【００９８】
図１３Ｄには、差分データ３９０ｃによる更新後、差分データ３９０ｄによる更新前の差分ツリー３０９４が記載されている。差分ツリー３０９４には、ノード対２０１ｇがノード２１０ｆの下に挿入され、挿入キーを含むリーフノードはノード２１０ｇである。
矢印３４１ｃ、３４２ｃ、３４３ｃは、差分データ３９０ｃによる更新により作成される３つの更新データ３８０ｃを示している。
矢印３４１ｃで示すように、挿入されたノード対２０１ｇのうち挿入キー３２２ｃを含むリーフノード２１０ｇの内容を第１の更新ノードとし、リーフノード２１０ｇの配列番号２２０ｆを第１の更新位置とする第１の更新データが作成され、更新データ格納領域３２２に格納される。
また、矢印３４２ｃで示すように、挿入キー３２２ｃを含むリーフノード２１０ｇと対をなすノード２１１ｇの内容を第２の更新ノードとし、ノード２１１ｇの配列番号２２０ｆ＋１を第２の更新位置とする第２の更新データが作成され、更新データ格納領域３２２に格納される。
さらに、矢印３４３ｃで示すように、リーフノード２１０ｇの直近上位のブランチノード２１０ｆの内容を第３の更新ノードとし、ブランチノード２１０ｆの配列番号２２１ｂを第３の更新位置とする第３の更新データが作成され、更新データ格納領域３２２に格納される。
そして、矢印３３２ｄで示すように、差分データ３９０ｄの差分キー３２２ｂを挿入キーとして挿入処理を実行すると、ノード２１０ｂが検索結果キーを格納するリーフノードとして得られる。
【００９９】
図１３Ｅには、差分データ３９０ｄによる更新後、すなわち全差分データによる更新後の差分ツリー３０９１が記載されている。差分ツリー３０９１には、ノード対２０１ｅがノード２１０ｂの下に挿入され、挿入キーを含むリーフノードはノード２１１ｅである。
矢印３４１ｄ、３４２ｄ、３４３ｄは、差分データ３９０ｄによる更新により作成される３つの更新データ３８０ｄを示している。
矢印３４１ｄで示すように、挿入されたノード対２０１ｅのうち挿入キー３２２ｄを含むリーフノード２１１ｅの内容を第１の更新ノードとし、リーフノード２１１ｅの配列番号２２０ｂ＋１を第１の更新位置とする第１の更新データが作成され、更新データ格納領域３２２に格納される。
また、矢印３４２ｄで示すように、挿入キー３２２ｄを含むリーフノード２１１ｅと対をなすノード２１０ｅの内容を第２の更新ノードとし、ノード２１０ｅの配列番号２２０ｂを第２の更新位置とする第２の更新データが作成され、更新データ格納領域３２２に格納される。
さらに、矢印３４３ｄで示すように、リーフノード２１１ｅの直近上位のブランチノード２１０ｂの内容を第３の更新ノードとし、ブランチノード２１０ｂの配列番号２２０ａを第３の更新位置とする第３の更新データが作成され、更新データ格納領域３２２に格納される。
【０１００】
図１４は、インデックス更新装置で実行される更新データによるインデックス更新処理の概要を説明する図である。
更新データ格納領域４２０には、インデックス更新データ作成装置３００から送信され、更新データ取得手段４４０で受信され格納された更新データ３８０ａ〜３８ｄ０ｄが設定されている。
更新データ３８０ａ、３８０ｂは、それぞれ差分データ３９０ａのキー３２１ｄ及び差分データ３９０ｂのキー３２１ｂを削除キーとした差分ツリーの削除処理により作成されたものである。
また、更新データ３８０ｃ、３８０ｄは、それぞれ差分データ３９０ｃのキー３２２ｃ及び差分データ３９０ｄのキー３２２ｂを挿入キーとした差分ツリーの挿入処理により作成されたものである。
【０１０１】
更新処理の開始前の更新ツリー４０９０にはインデックス更新データ作成装置３００の更新処理前の差分ツリー３０９０（図１０に示す）と同一のインデックスキーが格納されている。それだけではなく、配列の同一の配列番号の配列要素には差分ツリー３０９０と更新ツリー４０９０の同一のノードが配置されている。
【０１０２】
キー３２１ｄに基づく更新データ３８０ａ及びキー３２１ｂに基づく更新データ３８０ｂにより、更新ツリー４０９０からキー３２１ｄ、３２１ｂが削除され、キー３２２ｃに基づく更新データ３８０ｃ及びキー３２２ｂに基づく更新データ３８０ｄにより、更新ツリー４０９０にキー３２２ｃ、３２２ｂが挿入されて更新後の差分ツリー４０９１が得られる。
【０１０３】
図１５は、更新データによるインデックス更新の処理フロー例を示す図である。
図１５に示すように、ステップＳ１５０１において更新ツリーを設定し、ステップＳ１５０２において更新データを設定する。更新ツリーの設定は、図８Ｂに示す更新ツリー取得手段４３０による差分ツリーの取得、すなわち更新ツリーのルートノードの配列番号を取得し設定することにより行われる。更新データの設定は、更新データ取得手段４４０により、インデックス更新データ作成装置から受信した更新データを更新データ格納領域４２０に格納することにより行われる。
【０１０４】
ステップＳ１５０３に進み、全ての更新データは処理済みか判定する。すべての更新データが処理済みであれば処理を終了し、すべての更新データが処理済みでなければ、ステップＳ１５０４に進む。
【０１０５】
ステップＳ１５０４では、更新データ格納領域から更新データを読み出し、読み出した更新データから、更新位置と更新ノードを取り出し、ステップＳ１５０５において、更新位置の指す更新ツリーの配列要素に、更新ノードを書き込み、ステップＳ１５０３に戻る。
上記ステップＳ１５０３〜ステップＳ１５０５のループ処理を、ステップＳ１５０３において全ての更新データを処理済みと判定するまで繰り返し、全ての更新データを処理済みと判定すると処理を終了する。
【０１０６】
本発明に係るインデックス更新装置は、上述のステップＳ１５０５の処理にあるように、更新データの更新位置の指す配列番号の配列要素を更新データの更新ノードで書き換えることにより、インデックスの更新を実行する。したがって、インデックス更新の処理負担は、更新ツリーの削除処理と挿入処理を行う場合と比べて軽くなる。
【０１０７】
次に図１６Ａ〜図１６Ｅを参照して、本発明の一実施の形態における、更新データに基づく更新ツリーの書換処理の流れを更新データ３８０ａ〜３８０ｄ毎に説明する。更新データは、インデックスデータ作成装置から送信されたものであるから、図１３Ａ〜図１３Ｅで例示した更新データと同一である。また、図１６Ａ〜図１６Ｅに示す更新ツリーの構造と各ノードの内容も、図１３Ａ〜図１３Ｅで例示した差分ツリーとそれぞれ対応し、同一のものとなる。
【０１０８】
図１６Ａには、更新データ３８０ａによる更新前の更新ツリー４０９０が記載されている。
図１６Ａの矢印３６０ａで示すように、更新データ３８０ａの更新位置３８３は２２１ｂ＋１であるので、ノード２１１ｆが書き換え対象となる。
【０１０９】
図１６Ｂには、更新データ３８０ａによる書き換え後、更新データ３８０ｂによる書き換え前の更新ツリー４０９２が記載されている。
ノード２１１ｆは、差分キー３２１ｄを格納していた更新ツリー４０９０のノード２１０ｈと対をなすノード２１１ｈに書き換えられている。
そして、図１６Ｂの矢印３６０ｂで示すように、更新データ３８０ｂの更新位置３８３は２２０ａであるので、ノード２１０ｂが書き換え対象となる。
【０１１０】
図１６Ｃには、更新データ３８０ｂによる書き換え後、更新データ３８０ｃによる書き換え前の更新ツリー４０９３が記載されている。
ノード２１０ｂは、差分キー３２１ｂを格納していた更新ツリー４０９０のノード２１１ｃと対をなすノード２１０ｃに書き換えられている。
そして、矢印３６０１ｃ、３６０２ｃで示すように、代表ノードの配列番号が２２０ｆである空ノード対２０１ｇが書き換え対象となる。また、矢印３６０３ｃで示すように、更新データ３８０ｃのうち第３の更新ノードの格納される配列要素の配列番号は２２１ｂなので、ノード２１０ｆが書き換え対象となる。
【０１１１】
図１６Ｄには、更新データ３８０ｃによる書き換え後、更新データ３８０ｄによる書き換え前の更新ツリー４０９４が記載されている。
ノード２１０ｆは、更新データ３８０ｃの第３の更新ノードに書き換えられている。また、ノード２１０ｇには更新データ３８０ｃのうち第１の更新ノードが、ノード２１１ｇには第２の更新ノードが格納されている。
そして、矢印３６０１ｄ、３６０２ｄで示すように、代表ノードの配列番号が２２０ｂである空ノード対２０１ｅが書き換え対象となる。また、矢印３６０３ｄで示すように、更新データ３８０ｄのうち第３の更新ノードの格納される配列要素の配列番号は２２０ａなので、ノード２１０ｂが書き換え対象となる。
【０１１２】
図１６Ｅには、更新データ３８０ｄによる書き換え後、すなわち全更新データによる書きかえ後の更新ツリー４０９１が記載されている。更新ツリー４０９１には、ノード対２０１ｅがノード２１０ｂの下に挿入され、挿入キーを含むリーフノードはノード２１１ｅである。
更新ツリー４０９１は差分ツリー３０９１と全く同一であり、このようにして、インデックス更新データ作成装置とインデックス更新装置の間のインデックスの同期をとることができる。
つまり、インデックス更新データ作成装置で作成される更新データは、差分データによる挿入処理や削除処理に関わらず、更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードであり、インデックス更新装置において、更新データの更新位置のノードの内容を更新ノードで書き換えることにより更新ツリーを更新して、差分ツリーと更新ツリーを容易に同期させることができる。
【０１１３】
以上詳細に説明したところから明らかなとおり、本発明によればカップルドノードツリーを活用した、データベースのインデックスを旧データのものから新データに効率よく更新するためのインデックス更新データを提供することができ、また、本発明のインデックス更新データにより、インデックス更新装置の処理負担を軽減することができる。
また、本発明の実施の形態は上記に限ることなく種々の変形が可能であることは当業者に明らかである。さらに、本発明のインデックス更新データ作成装置及び作成方法、さらにはインデックス更新装置及び更新方法を、コンピュータに実行させるプログラムによりコンピュータ上で実現可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。
【符号の説明】
【０１１４】
３００ インデックス更新データ作成装置
３０１ データ処理装置
３０２ 中央処理装置
３０３ キャッシュメモリ
３０４ バス
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ 通信装置
３０８ データ格納装置
３０９ 配列
３１０ 探索経路スタック
３２０ 差分データ格納領域
３２２ 更新データ格納領域
３３０ 差分ツリー取得手段
３４０ 差分データ取得手段
３５０ 更新データ作成手段
３５２ 挿入データ作成手段
３５４ 削除データ作成手段
３５６ 更新種別判定手段
３８０ 更新データ
３８３ 更新位置
３８４ 更新ノード
３９０ 差分データ
３９１ 更新種別
３９２ 差分キー
４００ インデックス更新装置
４０９ 配列
４２０ 更新データ格納領域
４３０ 更新ツリー取得手段
４４０ 更新データ取得手段
４５０ 更新ツリー更新手段
【技術分野】
【０００１】
本発明は、データベースのインデックスの更新処理に関し、特に、インデックス更新に用いるインデックス更新データの作成処理とそのインデックス更新データによるインデックス更新処理に関する。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。また、カーナビゲーション用の地図データのように販売数の非常に大きなデータベースも存在する。
【０００３】
このようなデータベースシステムの機能として、データの更新機能は必須である。データベースに保管されるデータ量が増大するのに伴って、例えばバッチ処理により既存のデータベースに対して大量のデータの追加や削除を行おうとすると、その作業に要する時間が長くなるという不都合が生じている。
【０００４】
データベースのバッチ更新の態様としては、既存のデータベースに対する追加、変更あるいは削除データによりデータベースを更新する差分更新という態様と、既存のデータベースを新しいデータベースでそっくり置き換える態様が存在する。
【０００５】
後者のデータベース更新の態様は、例えばデータベースのデータの供給者が、データベースの更新が必要になったときにデータベースの更新データを供給するのではなく、データを更新済みの新しい版のデータベースを改めて供給する場合に採用される。しかし、このようなデータベースの更新の態様では、更新作業中はデータベースの利用ができないことから、この更新作業に長時間を要するのでは不便である。
【０００６】
また、データベースは、データベース本体のデータ部分とデータベース本体からデータを検索するためのインデックスから構成されるのが通例である。そこで、データベースの更新の態様には、インデックス部分を更新する態様があり、この部分の更新においても、更新後のインデックス全体が供給され、更新前のインデックスとそっくり入れ替える場合がある。
【０００７】
例えばカーナビゲーションシステムの地図データのインデックスを更新する場合には、地図データの販売業者から購入した新しい地図データのインデックスデータを、カーナビゲーションシステムの販売業者あるいは車のディーラーのセンターから、カーナビゲーションシステムを搭載した各車に配布し、搭載されたカーナビゲーションシステムごとに、インデックスデータを更新する。このように、新しいインデックスデータ全体を配布するため、配布するデータ量が多く、また各カーナビゲーションシステムにおける地図データの更新時間も長いものとなる。
【０００８】
そこで、インデックデータの追加、変更あるいは削除データの供給を受けるか、あるいはインデックスデータの新旧データから差分データを抽出して差分更新により、データベースを更新することが行われている。
下記特許文献１には、ナビゲーション端末で用いられる地図データの差分更新について記載されている。
【０００９】
上述のデータベースの差分更新を行うためには、データベースから更新対象のレコードの検索を行う必要がある。データベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
【００１０】
ビット列の検索処理手法については、種々のものが知られている。それらのなかでも、ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが行われている。このようなものの一つとして、下記特許文献２、３に記載された、カップルドノードツリーというデータ構造を用いた検索手法がある。
【００１１】
カップルドノードツリーは、ツリーの始点であるルートノードと、隣接した記憶領域に配置される２つのノードで構成されるツリーの構成要素としてのノード対を有する。ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、ブランチノードは、ノード種別に加えて、検索キーの弁別ビット位置を格納する領域とリンク先のノード対の一方のノードである代表ノードの位置を示す情報を格納する領域を含むが、検索対象のビット列からなるインデックスキーを格納する領域を含まないものである。リーフノードは、ノード種別に加えて、検索対象のビット列からなるインデックスキーを格納する領域を含むが、検索キーの弁別ビット位置を格納する領域とリンク先の代表ノードの位置を示す情報を格納する領域を含まないものである。
【００１２】
上記カップルドノードツリーの任意のノードを検索開始ノードとして、各ブランチノードの弁別ビット位置に位置する検索キーのビット値に応じてリンク先を選択し、リーフノードに至ることにより、リーフノードに格納されたインデックスキーを検索キーによる検索結果キーとして取得する。
以下において、カップルドノードツリーとそれを用いた検索処理について、さらに説明する。その説明では、カップルドノードツリーは配列に格納されたものとする。ブランチノードが保持する代表ノードの位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【００１３】
図１は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図１を参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【００１４】
配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
【００１５】
なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。
【００１６】
ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【００１７】
図２は、カップルドノードツリーのツリー構造を概念的に示す図である。
符号２１０ａで示すのがルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。
ツリー構造としては、ルートノード２１０ａの下にノート対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。
各ノードの前に付された０あるいは１の符号は、図１において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００１８】
図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
【００１９】
ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。
【００２０】
ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
【００２１】
ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。
ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。
【００２２】
ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。
ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの格納された配列要素の配列番号２２１ｆが格納されている。
【００２３】
ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。
また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００“が格納されている。
【００２４】
以下、上述のツリーからインデックスキー“１０００１０”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
【００２５】
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを読み出して検索キーと比較すると両方とも“１０００１０”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【００２６】
次に、図２を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図２Ｂの例で、ルートノード２１０ａの弁別ビット位置が０であるのは、図２Ｂに例示されたインデックスキーに０ビット目が０のものと１のものがあるからである。０ビット目が０のインデックスキーのグループはノード２１０ｂの下に分類され、０ビット目が１のインデックスキーのグループはノード２１１ｂの下に分類されている。
【００２７】
ノード２１１ｂの弁別ビット位置が２であるのは、ノード２１１ｈ、２１０ｈ、２１１ｇ、２１０ｇに格納された０ビット目が１のインデックスキーの１ビット目がすべて０で等しく、２ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
以下０ビット目の場合と同様に、２ビット目が１であるものはノード２１１ｆ側に分類され、２ビット目が０であるものはノード２１０ｆ側に分類される。
そして２ビット目が１であるインデックスキーは３ビット目の異なるものがあるのでノード２１１ｆの弁別ビット位置には３が格納され、２ビット目が０であるインデックスキーでは３ビット目も４ビット目も等しく５ビット目で異なるのでノード２１０ｆの弁別ビット位置には５が格納される。
【００２８】
ノード２１１ｆのリンク先においては、３ビット目が１のものと０のものがそれぞれ１つしかないことから、ノード２１０ｈ、２１１ｈはリーフノードとなり、それぞれインデックスキー２５０ｈと２５１ｈに“１０１０１１”と“１０１１００”が格納されている。
仮にインデックスキーの集合に“１０１１００”の代わりに“１０１１０１”か“１０１１１０”が含まれていたとしても、３ビット目までは“１０１１００”と等しいので、ノード２１１ｈに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“１０１１００”に加えて“１０１１０１”が含まれていると、ノード２１１ｈはブランチノードとなり、その弁別ビット位置は５になる。追加されるインデックスキーが“１０１１１０”であれば、弁別ビット位置は４となる。
【００２９】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“１”のノードとビット値が“０”のノードとに分岐していることから、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード２１１ｈのインデックスキー２５１ｈの“１０１１００”、ノード２１０ｈのインデックスキー２５０ｈの“１０１０１１”、・・・、ノード２１０ｃのインデックスキー２５０ｃの“０００１１１”となり降順にソートされている。
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
【００３０】
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“１０１１００”であればノード２１１ｈに到達することができる。また、上記説明からも想像がつくように、“１０１１０１”か“１０１１１０”を検索キーとした場合でもノード２１１ｈにたどり着く。インデックスキー２５１ｈと比較することにより検索が失敗したとすることもできるし、インデックスキー２５１ｈである“１０１１００”を検索結果キーとすることもできる。
【００３１】
また、例えば“１００１００”で検索した場合でも、ノード２１０ａ、２１１ｂ、２１０ｆのリンク経路では検索キーの３ビット目と４ビット目は使われることがなく、“１００１００”の５ビット目が０なので、“１０００１０”で検索した場合と同様にノード２１０ｇに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【００３２】
次に、上述のカップルドノードツリーを用いた検索処理、及びカップルドノードツリーの挿入削除処理について説明する。以下の説明においては、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる。また、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合があるし、データ自体の名前をそのデータを格納する一時記憶領域の名前として用いることもある。
【００３３】
図３は、下記特許文献３に開示されたビット列検索の基本動作を示したフローチャートである。
まず、ステップＳ３０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、オペレータからの入力によってもよいし、図３に例示する処理を利用するアプリケーションプログラムによるものでもよい。
取得された検索開始ノードの配列番号は、図示しない検索開始ノード設定エリアに設定されるが、この検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の一つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードの配列番号を得る。」、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。
【００３４】
次に、ステップＳ３０２で、探索経路スタック３１０に取得された配列番号を格納し、ステップＳ３０３で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップＳ３０４で、読み出したノードから、ノード種別を取り出し、ステップＳ３０５で、ノード種別がブランチノードであるか否かを判定する。
ステップＳ３０５の判定において、読み出したノードがブランチノードである場合は、ステップＳ３０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ３０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ３０８で、ノードから代表ノード番号を取り出して、ステップＳ３０９で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、ステップＳ３０２に戻る。
【００３５】
以降、ステップＳ３０５の判定においてリーフノードと判定されてステップＳ３１０に進むまで、ステップＳ３０２からステップＳ３０９までの処理を繰り返す。ステップＳ３１０で、リーフノードからインデックスキーを検索結果キーとして取り出して、処理を終了する。
上述の説明では、カップルドノードツリーは配列に格納されているものとしたため、探索経路スタック３１０には配列番号を格納するとしたが、カップルドノードツリーが配列に格納されていない場合は、配列番号に替えてリンク先のノードの位置を示す情報が探索経路スタック３１０に格納される。
【００３６】
次に、図４Ａ〜図４Ｃにより下記特許文献２に開示されたカップルドノードツリーにおけるノード挿入処理を説明する。
図４Ａは挿入処理の前段である検索処理の処理フローを示す図であり、図３に示した検索処理において、ルートノードを検索開始ノードとし、挿入キーを検索キーとしたものに相当する。
【００３７】
ステップＳ４０１において、検索開始ノードの配列番号を設定するエリアにルートノードの配列番号を設定し、ステップＳ４０２において、検索キーに挿入キーを設定する。
次にステップＳ４１０において、図３に示す検索処理を実行し検索結果のインデックスキーを得て、ステップＳ４１１に進む。
ステップＳ４１１において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、図４ＢのステップＳ４１２以下の処理に進む。
【００３８】
図４Ｂは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップＳ４１２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
ステップＳ４１３に進み、挿入キーとステップＳ４１０で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１を小さいときは値０のブール値を得る。
ステップＳ４１４に進み、ステップＳ４１２で得た代表ノードの配列番号にステップＳ４１３で得たブール値を加算した配列番号を得る。
ステップＳ４１５に進み、ステップＳ４１２で得た代表ノードの配列番号にステップＳ４１３で得たブール値の論理否定値を加算した配列番号を得る。
ステップＳ４１４で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップＳ４１５で得た配列番号は、そのリーフノードと対を成すブランチノードあるいはリーフノードが格納される配列要素のものである。
つまり、前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが決定される。
【００３９】
次に図４ＣのステップＳ４１６以下の処理に進む。
図４Ｃは図４Ｂで準備された配列にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
ステップＳ４１６〜ステップＳ４２３までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップＳ４２４以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【００４０】
ステップＳ４１６で、挿入キーとステップＳ４１０で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップＳ４１７に進み、ステップＳ４１６で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【００４１】
次にステップＳ４１８に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップＳ４２４に移行し、指していなければステップＳ４１９に進む。
【００４２】
ステップＳ４１９において、探索経路スタックのスタックポインタを１つ戻してそこにスタックされている配列番号を取り出す。
ステップＳ４２０に進み、ステップＳ４１９で取り出した配列番号の配列要素を配列からノードとして読み出す。
ステップＳ４２１に進み、ステップＳ４２０で読み出したノードから、弁別ビット位置を取り出す。
次にステップＳ４２２に進み、ステップＳ４２１で取り出した弁別ビット位置がステップＳ４１７で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【００４３】
ステップＳ４２２の判定結果が否定であれば、ステップＳ４１８に戻り、ステップＳ４１８での判定が肯定になるかステップＳ４２２での判定が肯定になるまで繰り返す。ステップＳ４２２での判定が肯定になると、ステップＳ４２３で経路探索スタックのスタックポインタを1つ進め、ステップＳ４２４以下の処理に移行する。
【００４４】
上記ステップＳ４１６〜ステップＳ４２３で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入するインデックスキーと検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の（最上位の）ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。
また、経路探索スタック逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【００４５】
次に、ステップＳ４２４以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップＳ４２４では探索経路スタックからスタックポインタの指す配列番号を取り出す。
ステップＳ４２５において、ステップＳ４１４で得た配列番号の指す配列要素のノード種別に１（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップＳ４２６に進み、配列からステップＳ４２４で得た配列番号の配列要素を読み出す。
次にステップＳ４２７において、ステップＳ４１５で得た配列番号の配列要素にステップＳ４２６で読み出した内容を書き込む。
最後にステップＳ４２８において、ステップＳ４２４で得た配列番号の指す配列要素のノード種別に０(ブランチノード）を、弁別ビット位置にステップＳ４１７で得たビット位置を、代表ノード番号にステップＳ４１２で得た配列番号を書き込み、処理を終了する。
【００４６】
図５は、下記特許文献２に開示されたカップルドノードツリーを生成する処理フロー例である。ルートノードの挿入処理と通常の挿入処理により、カップルドノードツリーが生成される。
ステップＳ５０１において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか判定される。登録済みであれば、図４Ａ〜図４Ｃを用いて説明した通常の挿入処理が行われる。
【００４７】
ステップＳ５０１での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
まず、ステップＳ５０２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。次にステップＳ５０３において、ステップＳ５０２で得た配列番号に０を加えた配列番号を求める。（実際には、ステップＳ５０２で取得した配列番号に等しい。)。さらにステップＳ５０４において、ステップＳ５０３で得た配列番号の配列要素に、挿入するルートノードのノード種別に１（リーフノード)とインデックスキーに挿入キーを書き込み、ステップＳ５０５で、ステップＳ５０２で取得したルートノードの配列番号を登録して処理を終了する。
【００４８】
インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図５及び図４Ａ〜図４Ｃの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができる。
【００４９】
次に図６Ａ、図６Ｂを参照して、下記特許文献２に開示されたカップルドノードツリーから、特定のインデックスキーを格納したリーフノードを削除する処理フローを説明する。
図６Ａは、削除処理の前段である検索処理の処理フロー例を示す図であり、図３に示した検索処理において、ルートノードを検索開始ノードとし、挿入キーを検索キーとしたものに相当する。
【００５０】
ステップＳ６０１において、検索開始ノードの配列番号を設定するエリアにルートノードの配列番号を設定し、ステップＳ６０２において、検索キーに削除キーを設定する。
次にステップＳ６１０において、図４に示す検索処理を実行し検索結果のインデックスキーを得て、ステップＳ６１１に進む。
図６ＡのステップＳ６１１において削除キーとインデックスキーを比較し、等しくなければければ削除するインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、図６ＢのステップＳ６１２以下の処理に進む。
【００５１】
図６Ｂは、削除処理の後段の処理フローを説明する図である。
まず、ステップＳ６１２で探索経路スタックに２つ以上の配列番号が格納されているか判定する。２つ以上の配列番号が格納されていないということは、言い換えれば１つだけで、その配列番号はルートノードの格納された配列要素のものである。その場合はステップＳ６１８に移行し、ステップＳ６０１で得たルートノードの配列番号に係るノード対を削除する。次にステップＳ６１９に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【００５２】
ステップＳ６１２において探索経路スタックに２つ以上の配列番号が格納されていると判定されたときはステップＳ６１３に進み、ステップＳ６１０で参照するする図３に示す処理フローのステップＳ３０８で得た代表ノード番号にステップＳ３０７で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【００５３】
次にステップＳ６１４において、ステップＳ６１３で得た配列番号の配列要素の内容を読み出し、ステップＳ６１５において探索経路スタックのスタックポインタを１つ戻して配列番号を取り出す。
次にステップＳ６１６に進み、ステップＳ６１４で読み出した配列要素の内容をステップＳ６１５で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
最後にステップＳ６１７において、ステップＳ６１０で参照するする図３に示す処理フローのステップＳ３０８で得た代表ノード番号に係るノード対を削除して処理を終了する。
【先行技術文献】
【特許文献】
【００５４】
【特許文献１】特開２００７−２４０４９２号公報
【特許文献２】特開２００８−０１５８７２号公報
【特許文献３】特開２００８−１１２２４０号公報
【発明の概要】
【発明が解決しようとする課題】
【００５５】
本発明が解決しようとする課題は、データベースのインデックスの更新を行うインデックス更新装置の処理負担を軽減する手法を提供することである。
【課題を解決するための手段】
【００５６】
本発明のインデックス更新データ作成装置は、更新前のデータベースのインデックスキーを格納したカップルドノードツリーである差分ツリーを取得する差分ツリー取得手段と、更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する差分データ取得手段と、差分データに基づき差分ツリーを更新し、該更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する更新データ作成手段と、を備える。
また、本発明のインデックス更新装置は、更新前のデータベースのインデックスキーを格納したカップルドノードツリーである更新ツリーを取得する更新ツリー取得手段と、インデックス更新データ作成装置から更新すべき更新ツリーのノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを取得する更新データ取得手段と、更新データの更新位置のノードの内容を更新ノードで書き換えることにより更新ツリーを更新する更新ツリー更新手段と、を備える。
【発明の効果】
【００５７】
本発明によれば、インデックス更新データ作成装置が、差分データに基づいてインデックス更新装置が更新すべきデータの位置とその内容を作成するので、インデックス更新装置の処理負担は大幅に削減される。
【図面の簡単な説明】
【００５８】
【図１】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２】カップルドノードツリーのツリー構造を概念的に示す図である。
【図３】ビット列検索の基本動作例を示すフローチャートである。
【図４Ａ】挿入処理の前段である検索処理の処理フロー例を示す図である。
【図４Ｂ】挿入するノード対の配列要素を準備する処理フロー例を示す図である。
【図４Ｃ】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させる処理フロー例を示す図である。
【図５】カップルドノードツリーを生成する処理フロー例を示す図である。
【図６Ａ】削除処理の前段である検索処理の処理フロー例を示す図である。
【図６Ｂ】削除処理の後段の処理フロー例を示す図である。
【図７】本発明の原理を説明する図である。
【図８Ａ】インデックス更新データ作成装置の機能ブロック構成例を説明する図である。
【図８Ｂ】インデックス更新装置の機能ブロック構成例を説明する図である。
【図９】本発明を実施するためのハードウェア構成例を説明する図である。
【図１０】差分データによる更新データ作成処理の概要を説明する図である。
【図１１】差分データによる更新データ作成の処理フロー例を示す図である。
【図１２Ａ】差分ツリーに更新種別が挿入である差分データのインデックスキーを挿入して更新データを作成する処理フロー例を示す図である。
【図１２Ｂ】差分ツリーから更新種別が削除である差分データのインデックスキーを削除して更新データを作成する処理フロー例を示す図である。
【図１３Ａ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｂ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｃ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｄ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１３Ｅ】本発明の一実施の形態における差分データに基づく更新データ作成処理の流れを説明する図である。
【図１４】更新データによるインデックス更新処理の概要を説明する図である。
【図１５】更新データによるインデックス更新の処理フロー例を示す図である。
【図１６Ａ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｂ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｃ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｄ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【図１６Ｅ】本発明の一実施の形態における更新データに基づく更新ツリーの更新処理の流れを説明する図である。
【発明を実施するための形態】
【００５９】
図７を参照して、本発明の原理を説明する。本発明に係る差分更新システムは、インデックス更新データ作成装置３００と任意の数のインデックス更新装置４００ａ、４００ｂから構成される。なお、どのインデックス更新装置についての説明は同じであるので、以下の説明では、インデックス更新装置４００のように表記する場合がある。インデックス更新装置の構成要素についても同様に表記する場合がある。
インデックス更新データ作成装置３００は、インデックスを格納する配列３０９、差分データ格納領域３２０、及び更新データ格納領域３２２を含む。差分データ格納領域３２０には、差分データとして、挿入データである挿入キーと削除データである削除キーが取得され、格納される。差分データの取得方法は、データベースの供給元から提供を受けるものであってもよいし、データベース供給元から新インデックスを受領し、旧インデックスとの差分を抽出するものであってもよい。
【００６０】
インデックス更新データ作成装置３００は、旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧差分ツリー）３０９０に対して、差分データ格納領域３２０に格納された挿入キーと削除キーによる挿入処理と削除処理を実行し、新インデックスに対応した新差分ツリー３０９１を得る。図７の例では、差分ツリーは配列に配置されているが、先にも述べたとおり、配列に配置することは必須ではない。
【００６１】
上記挿入処理時及び削除処理時に得られる情報を基に、インデックス更新データ作成装置３００は、インデックス更新装置４００においてインデックスの更新に用いられる更新データ３８０を作成して更新データ格納領域３２２に格納する。更新データ３８０は、更新対象のノードの位置を示す更新位置３８３と更新内容である更新ノード３８４を含む。
【００６２】
更新データ格納領域３２２に格納された更新データ３８０は、この更新データを用いてデータベースのインデックスを更新するインデックス更新装置４００に送信される。更新データ３８０の送信は、無線、有線あるいはそれらを組み合わせた通信回線を用いたもの、記憶媒体を用いたもの、通信回線と記憶媒体を組み合わせたものなどで実現される。
【００６３】
インデックス更新装置４００に送信された更新データ３８０は、更新データ格納領域４２０に格納される。インデックス更新装置４００は、旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧更新ツリー）４０９０のノード、すなわち旧更新ツリーの配置された配列４０９ａの配列要素の内容に対して、更新データ格納領域４２０に格納された更新データ３８０による書換処理を実行し、新インデックスに対応した新更新ツリー４０９１を得る。
【００６４】
インデックス更新装置４００における更新ツリーに格納されたインデックスキーの更新は、カップルドノードツリーの挿入処理や削除処理によるのではなく、更新ツリーの配置された配列の配列要素の内容を書き換えることにより実現されるので、インデックス更新装置４００における処理負担を軽減させることができる。
【００６５】
図８Ａは、インデックス更新データ作成装置の機能ブロック構成例を説明する図である。
インデックス更新データ作成装置３００は、差分ツリー取得手段３３０、差分データ取得手段３４０、及び更新データ作成手段３５０を含んで構成される。
【００６６】
差分ツリー取得手段３３０は、図７に示す旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧差分ツリー）３０９０を取得するものである。旧インデックスであるインデックスキーが既にカップルドノードツリーに格納されていれば、それを旧差分ツリー３０９０とする。そうでなければ、インデックスキーを取り出して図５に示すカップルドノードツリーの生成処理を実行して生成したカップルドノードツリーを旧差分ツリーとする。
【００６７】
差分データ取得手段は、差分データとして、挿入データである挿入キーと削除データである削除キーを取得し、差分データ格納領域３２０に格納する。差分データの取得方法は、先に述べたように、データベースの供給元から提供を受けるものであってもよいし、データベース供給元から新インデックスを受領し、旧インデックスとの差分を抽出するものであってもよい。
【００６８】
更新データ作成手段３５０は、差分データ取得手段３４０で取得された差分データに基づき差分ツリー取得手段３３０で取得された差分ツリーを更新し、インデックス更新装置４００において用いるインデックスの更新データを作成する。更新データ作成手段３５０は、挿入データ作成手段３５２、削除データ作成手段３５４及び更新種別判定手段３５６を含む。更新種別判定手段３５６は、差分データが挿入データであるか削除データであるか判定する。挿入データ作成手段３５２は、挿入データに基づいて更新データを作成し、削除データ作成手段３５４は、削除データに基づいて更新データを作成する。
それぞれの手段の詳細な動作は、後に図１０〜図１３Ｅを参照して説明する。
【００６９】
図８Ｂは、インデックス更新装置の機能ブロック構成例を説明する図である。
インデックス更新装置４００は、更新ツリー取得手段４３０、更新データ取得手段４４０、及び更新ツリー更新手段３５０を含んで構成される。
【００７０】
更新ツリー取得手段４３０は、図７に示す旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧更新ツリー）４０９０を取得するものである。旧インデックスであるインデックスキーが既にカップルドノードツリーに格納されていれば、それを旧更新ツリー４０９０とする。そうでなければ、インデックスキーを取り出して図５に示すカップルドノードツリーの生成処理を実行して生成したカップルドノードツリーを旧更新ツリーとする。
【００７１】
更新データ取得手段４４０は、インデックス更新データ作成装置３００から送信された更新データを受信して更新データ格納装置４２０に格納する。更新データの送信方法は、先に述べたとおりのものである。
【００７２】
更新ツリー更新手段４５０は、旧インデックスであるインデックスキーを格納したカップルドノードツリー（旧更新ツリー）４０９０のノード、すなわち旧更新ツリーの配置された配列４０９の配列要素の内容に対して、更新データ取得手段４４０において取得され、更新データ格納領域４２０に格納された更新データによる書換処理を実行し、新インデックスに対応した新更新ツリー４０９１を得る。
【００７３】
図９は、本発明を実施するためのハードウェア構成例を説明する図である。図に示すように、本発明を実施するためのハードウェアは、インデックス更新データ作成装置３００とインデックス更新装置４００ａ〜４００ｘで構成される。インデックス更新装置４００ａ〜４００ｘの数は任意である。
【００７４】
本発明のインデックス更新データ作成装置３００による更新データ作成は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０、差分データを格納する差分データ格納領域３２０及び作成済みの更新データを格納する更新データ格納領域３２２を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
【００７５】
図９の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、更新データ格納領域３２２及び差分データ格納領域３２０は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられることは当然である。
【００７６】
インデックス更新データ作成装置３００において作成された更新データは、インデックス更新装置４００ａ〜４００ｘに送られ、それぞれの差分データ格納領域４２０ａ〜４２０ｘに格納され、それぞれのインデックス格納領域である配列４０９ａ〜４０９ｘに格納された旧データを新データに更新するために用いられる。特に図示はしていないが、インデックス更新装置４００ａ〜４００ｘにおいても、データ処理装置や、差分データ格納領域、インデックス格納領域及びその他の記憶領域を有するデータ格納装置が備えられている。
なお、以下においては、上述の例えば差分データ格納領域３２０に格納された差分データを差分データ３２０と表記するように、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合がある。
【００７７】
図１０は、本発明の一実施形態における差分データにより更新データを作成する処理の概要を説明する図である。
図１０に示す例では、差分データ格納領域３２０には、差分データ３９０ａ、３９０ｂ、３９０ｃ、３９０ｄが格納されている。各差分データは更新種別３９１と差分キー３９２で構成されている。
差分データ３９０ａの更新種別は削除を意味する“ｄ”、差分キーはキー３２１ｄ“１０１０１１”である。差分データ３９０ｂの更新種別は“ｄ”、差分キーはキー３２１ｂ“０１００１１”である。差分データ３９０ｃの更新種別は挿入を意味する“ｉ”、差分キーはキー３２２ｃ“１０００１１”である。差分データ３９０ｄの更新種別は“ｉ”、差分キーはキー３２２ｂ“０１０１１０”である。
【００７８】
更新処理の開始前の差分ツリー３０９０には、インデックスキーとして“１０１１００”、“１０１０１１”、“１０００１１”、“０１００１１”、“０１００１０”が格納されている。矢印３３１ｄ及び矢印３３１ｂで示すように、更新種別が“ｄ”である差分データのキー３２１ｄとキー３２１ｂにより差分ツリー３０９０の削除処理が行われ、矢印３３３で示すように、キー３２１ｄによる更新データ３８０ａとキー３２１ｂによる更新データ３８０ｂが作成され、更新データ格納領域３２２に格納される。
【００７９】
また、矢印３３２ｃ及び矢印３３２ｂで示すように、更新種別が“ｉ”である差分データのキー３２２ｃとキー３２２ｂにより挿入処理が行われ、更新後の差分ツリー３０９１にインデックスキーとして挿入される。そして、矢印３３４で示すように、キー３２２ｃによる更新データ３８０ｃとキー３２２ｂによる更新データ３８０ｄが作成され、更新データ格納領域３２２に格納される。
【００８０】
上述の削除処理と挿入処理により、更新前の差分ツリー３０９０から符号３２１ｄで示すインデックスキー“１０１０１１”と符号３２１ｂで示すインデックスキー“１０００１１”が削除され、点線の矢印で示すように、インデックスキー３２１ｅ“１０１１００”、３２１ｃ“１０００１１”、３２１ａ“０１００１０”が更新後の差分ツリー３０９１に残る。また、差分ツリー３０９１にはインデックスキー３２２ｃ、３２２ｂが挿入されている。
【００８１】
次に、図１１を参照して、差分データによる更新データ作成の処理フロー例を説明する。
図１１に示すように、ステップＳ１１０１において差分ツリーを設定し、ステップＳ１１０２において差分データを設定する。差分ツリーの設定は、図８Ａに示す差分ツリー取得手段３３０による差分ツリーの取得、すなわち差分ツリーのルートノードの配列番号を取得し設定することにより行われる。差分データの設定は、差分データ取得手段３４０により差分データを取得して差分データ格納領域３２０に格納することにより行われる。
【００８２】
ステップＳ１１０３に進み、すべての差分データは処理済みか判定する。すべての差分データが処理済みであれば処理を終了し、すべての差分データが処理済みでなければ、ステップＳ１１０４に進む。
【００８３】
ステップＳ１１０４では、差分データ格納領域から差分データを読み出し、読み出した差分データの差分キーを取り出し、ステップＳ１１０５において、差分データの更新種別を取り出す。
【００８４】
次にステップＳ１１０６において、ステップＳ１１０５で取り出した更新種別を判定し、更新種別が削除であればステップＳ１１０７に進み、削除でなければステップＳ１１０８に進む。
【００８５】
ステップＳ１１０７では、ステップＳ１１０４で取り出した差分キーを削除キーとして、差分ツリーより削除するとともに、更新データを作成し、ステップＳ１１０３に戻る。ステップＳ１１０７の処理の詳細は、後に図１２Ｂを参照して説明する。
【００８６】
ステップＳ１１０８では、ステップＳ１１０４で取り出したキーを挿入キーとして、差分ツリーに挿入するとともに、更新データを作成し、ステップＳ１１０３に戻る。ステップＳ１１０８の処理の詳細は、次に図１２Ａを参照して説明する。
上記ステップＳ１１０３〜ステップＳ１１０７、ステップＳ１１０８のループ処理を、ステップＳ１１０３において全ての差分データを処理済みと判定するまで繰り返し、全ての差分データを処理済みと判定すると処理を終了する。
全ての差分データの処理済みを判定するには、差分データ格納領域に格納された差分データ数をカウントしておき、１つ差分データを処理する毎に差分データ数をデクリメントする等、種々の手法を採用可能である。
【００８７】
図１２Ａは、差分ツリーに更新種別が挿入である差分データの差分キーを挿入して更新データを作成する処理フロー例を示す図であり、図１１に示すステップＳ１１０８の処理の詳細を説明するものである。
【００８８】
まずステップ１２０１で、差分キーを挿入キーとして、差分ツリーに挿入する。ステップＳ１２０１の処理の詳細は、図４Ａ〜図４Ｃを参照して説明したものである。
【００８９】
次にステップＳ１２０２において、挿入したキーを含むリーフノードの配列番号とリーフノードの内容により第１の更新データを作成する。
挿入したキーを含むリーフノードの配列番号は、ステップＳ１２０１において図４Ｂに示すステップＳ４１４で得た配列番号であり、リーフノードの内容は、図４ＣのステップＳ４２５で書き込まれたものである。
【００９０】
次にステップＳ１２０３において、挿入したキーを含むリーフノードと対をなす対ノードの配列番号と対ノードの内容により第２の更新データを作成する。
対ノードの配列番号は、ステップＳ１２０１において図４Ｂに示すステップＳ４１５で得た配列番号であり、対ノードの内容は、図４ＣのステップＳ４２７で書き込まれたものである。
【００９１】
次にステップＳ１２０４において、挿入したキーを含むリーフノードの直近上位のブランチノードの配列番号とブランチノードの内容により第３の更新データを作成して処理を終了する。
ブランチノードの配列番号は、ステップＳ１２０１において図４Ｃに示すステップＳ４２４で探索経路スタックから取り出した配列番号であり、ブランチノードの内容は、図４ＣのステップＳ４２８で書き込まれたものである。
【００９２】
図１２Ｂは、差分ツリーから更新種別が削除である差分データの差分キーを削除して更新データを作成する処理フロー例を示す図であり、図１１に示すステップＳ１１０７の処理の詳細を説明するものである。
【００９３】
まずステップ１２１１で、差分キーを削除キーとして、差分ツリーより削除する。ステップＳ１２１１の処理の詳細は、図６Ａ、図６Ｂを参照して説明したものである。
次にステップＳ１２１２において、削除したキーを格納していたリーフノードの直近上位のブランチノードの配列番号とリーフノードと対をなしていたノードの内容により更新データを作成して処理を終了する。
ブランチノードの配列番号は、ステップＳ１２１１において、図６Ｂに示すステップＳ６１５で探索経路スタックから取り出した配列番号であり、リーフノードと対をなしていたノードの内容は、図６Ｂに示すステップＳ６１６で書き込まれたものである。
【００９４】
次に図１３Ａ〜図１３Ｅを参照して、本発明の一実施の形態における、差分データによる更新データの作成処理の流れを差分データ３９０ａ〜３９０ｄ毎に説明する。例に挙げる差分データと差分ツリーは、図１０で例示したものと同一である。しかし、差分ツリーについては、ツリー構造を明記している。
【００９５】
図１３Ａには、差分データ３９０ａによる更新前の差分ツリー３０９０が記載されている。差分ツリー３０９０は、図２に例示したカップルドノードツリーからノード２１０ｇ、２１１ｄ、２１０ｃを除いたものに相当する。したがって、差分ツリー３０９０のノード２１０ｆには、図２に示すツリーのノード２１１ｇの内容が書き込まれており、また、差分ツリー３０９０のノード２１０ｂには、図２に示すツリーのノード２１０ｄの内容が書き込まれている。
そして、図１３Ａの矢印３３１ａで示すように、差分データ３９０ａの差分キー３２１ｄを削除キーとして削除処理を実行すると、ノード２１０ｈが削除の対象となる。
【００９６】
図１３Ｂには、差分データ３９０ａによる更新後、差分データ３９０ｂによる更新前の差分ツリー３０９２が記載されている。
矢印３３３ａで示すように、差分データ３９０ａによる更新の結果、ノード２１１ｆの内容が、削除キーを含むリーフノード２１０ｈと対をなすノード２１１ｈの内容に変更されたので、差分データ３９０ａによる更新前の差分ツリー３０９０のノード２１１ｈの内容を更新ノード３８４とし、リーフノード２１０ｈの直近上位のブランチノード２１１ｇの配列番号２２１ｂ＋１を更新位置とする更新データ３８０ａが作成され、更新データ格納領域３２２に格納される。
そして、矢印３３１ｂで示すように、差分データ３９０ｂの差分キー３２１ｂを削除キーとして削除処理を実行すると、ノード２１１ｃが削除の対象となる。
【００９７】
図１３Ｃには、差分データ３９０ｂによる更新後、差分データ３９０ｃによる更新前の差分ツリー３０９３が記載されている。
矢印３３３ｂで示すように、差分データ３９０ｂによる更新の結果、ノード２１０ｂの内容が、削除キーを含むリーフノード２１０ｃと対をなすノード２１１ｃの内容に変更されたので、差分データ３９０ｂによる更新前の差分ツリー３０９２のノード２１１ｃの内容を更新ノード３８４とし、リーフノード２１０ｃの直近上位のブランチノード２１０ｂの配列番号２２０ａを更新位置とする更新データ３８０ｂが作成され、更新データ格納領域３２２に格納される。
そして、矢印３３２ｃで示すように、差分データ３９０ｃの差分キー３２２ｃを挿入キーとして挿入処理を実行すると、ノード２１０ｆが検索結果キーを格納するリーフノードとして得られる。
【００９８】
図１３Ｄには、差分データ３９０ｃによる更新後、差分データ３９０ｄによる更新前の差分ツリー３０９４が記載されている。差分ツリー３０９４には、ノード対２０１ｇがノード２１０ｆの下に挿入され、挿入キーを含むリーフノードはノード２１０ｇである。
矢印３４１ｃ、３４２ｃ、３４３ｃは、差分データ３９０ｃによる更新により作成される３つの更新データ３８０ｃを示している。
矢印３４１ｃで示すように、挿入されたノード対２０１ｇのうち挿入キー３２２ｃを含むリーフノード２１０ｇの内容を第１の更新ノードとし、リーフノード２１０ｇの配列番号２２０ｆを第１の更新位置とする第１の更新データが作成され、更新データ格納領域３２２に格納される。
また、矢印３４２ｃで示すように、挿入キー３２２ｃを含むリーフノード２１０ｇと対をなすノード２１１ｇの内容を第２の更新ノードとし、ノード２１１ｇの配列番号２２０ｆ＋１を第２の更新位置とする第２の更新データが作成され、更新データ格納領域３２２に格納される。
さらに、矢印３４３ｃで示すように、リーフノード２１０ｇの直近上位のブランチノード２１０ｆの内容を第３の更新ノードとし、ブランチノード２１０ｆの配列番号２２１ｂを第３の更新位置とする第３の更新データが作成され、更新データ格納領域３２２に格納される。
そして、矢印３３２ｄで示すように、差分データ３９０ｄの差分キー３２２ｂを挿入キーとして挿入処理を実行すると、ノード２１０ｂが検索結果キーを格納するリーフノードとして得られる。
【００９９】
図１３Ｅには、差分データ３９０ｄによる更新後、すなわち全差分データによる更新後の差分ツリー３０９１が記載されている。差分ツリー３０９１には、ノード対２０１ｅがノード２１０ｂの下に挿入され、挿入キーを含むリーフノードはノード２１１ｅである。
矢印３４１ｄ、３４２ｄ、３４３ｄは、差分データ３９０ｄによる更新により作成される３つの更新データ３８０ｄを示している。
矢印３４１ｄで示すように、挿入されたノード対２０１ｅのうち挿入キー３２２ｄを含むリーフノード２１１ｅの内容を第１の更新ノードとし、リーフノード２１１ｅの配列番号２２０ｂ＋１を第１の更新位置とする第１の更新データが作成され、更新データ格納領域３２２に格納される。
また、矢印３４２ｄで示すように、挿入キー３２２ｄを含むリーフノード２１１ｅと対をなすノード２１０ｅの内容を第２の更新ノードとし、ノード２１０ｅの配列番号２２０ｂを第２の更新位置とする第２の更新データが作成され、更新データ格納領域３２２に格納される。
さらに、矢印３４３ｄで示すように、リーフノード２１１ｅの直近上位のブランチノード２１０ｂの内容を第３の更新ノードとし、ブランチノード２１０ｂの配列番号２２０ａを第３の更新位置とする第３の更新データが作成され、更新データ格納領域３２２に格納される。
【０１００】
図１４は、インデックス更新装置で実行される更新データによるインデックス更新処理の概要を説明する図である。
更新データ格納領域４２０には、インデックス更新データ作成装置３００から送信され、更新データ取得手段４４０で受信され格納された更新データ３８０ａ〜３８ｄ０ｄが設定されている。
更新データ３８０ａ、３８０ｂは、それぞれ差分データ３９０ａのキー３２１ｄ及び差分データ３９０ｂのキー３２１ｂを削除キーとした差分ツリーの削除処理により作成されたものである。
また、更新データ３８０ｃ、３８０ｄは、それぞれ差分データ３９０ｃのキー３２２ｃ及び差分データ３９０ｄのキー３２２ｂを挿入キーとした差分ツリーの挿入処理により作成されたものである。
【０１０１】
更新処理の開始前の更新ツリー４０９０にはインデックス更新データ作成装置３００の更新処理前の差分ツリー３０９０（図１０に示す）と同一のインデックスキーが格納されている。それだけではなく、配列の同一の配列番号の配列要素には差分ツリー３０９０と更新ツリー４０９０の同一のノードが配置されている。
【０１０２】
キー３２１ｄに基づく更新データ３８０ａ及びキー３２１ｂに基づく更新データ３８０ｂにより、更新ツリー４０９０からキー３２１ｄ、３２１ｂが削除され、キー３２２ｃに基づく更新データ３８０ｃ及びキー３２２ｂに基づく更新データ３８０ｄにより、更新ツリー４０９０にキー３２２ｃ、３２２ｂが挿入されて更新後の差分ツリー４０９１が得られる。
【０１０３】
図１５は、更新データによるインデックス更新の処理フロー例を示す図である。
図１５に示すように、ステップＳ１５０１において更新ツリーを設定し、ステップＳ１５０２において更新データを設定する。更新ツリーの設定は、図８Ｂに示す更新ツリー取得手段４３０による差分ツリーの取得、すなわち更新ツリーのルートノードの配列番号を取得し設定することにより行われる。更新データの設定は、更新データ取得手段４４０により、インデックス更新データ作成装置から受信した更新データを更新データ格納領域４２０に格納することにより行われる。
【０１０４】
ステップＳ１５０３に進み、全ての更新データは処理済みか判定する。すべての更新データが処理済みであれば処理を終了し、すべての更新データが処理済みでなければ、ステップＳ１５０４に進む。
【０１０５】
ステップＳ１５０４では、更新データ格納領域から更新データを読み出し、読み出した更新データから、更新位置と更新ノードを取り出し、ステップＳ１５０５において、更新位置の指す更新ツリーの配列要素に、更新ノードを書き込み、ステップＳ１５０３に戻る。
上記ステップＳ１５０３〜ステップＳ１５０５のループ処理を、ステップＳ１５０３において全ての更新データを処理済みと判定するまで繰り返し、全ての更新データを処理済みと判定すると処理を終了する。
【０１０６】
本発明に係るインデックス更新装置は、上述のステップＳ１５０５の処理にあるように、更新データの更新位置の指す配列番号の配列要素を更新データの更新ノードで書き換えることにより、インデックスの更新を実行する。したがって、インデックス更新の処理負担は、更新ツリーの削除処理と挿入処理を行う場合と比べて軽くなる。
【０１０７】
次に図１６Ａ〜図１６Ｅを参照して、本発明の一実施の形態における、更新データに基づく更新ツリーの書換処理の流れを更新データ３８０ａ〜３８０ｄ毎に説明する。更新データは、インデックスデータ作成装置から送信されたものであるから、図１３Ａ〜図１３Ｅで例示した更新データと同一である。また、図１６Ａ〜図１６Ｅに示す更新ツリーの構造と各ノードの内容も、図１３Ａ〜図１３Ｅで例示した差分ツリーとそれぞれ対応し、同一のものとなる。
【０１０８】
図１６Ａには、更新データ３８０ａによる更新前の更新ツリー４０９０が記載されている。
図１６Ａの矢印３６０ａで示すように、更新データ３８０ａの更新位置３８３は２２１ｂ＋１であるので、ノード２１１ｆが書き換え対象となる。
【０１０９】
図１６Ｂには、更新データ３８０ａによる書き換え後、更新データ３８０ｂによる書き換え前の更新ツリー４０９２が記載されている。
ノード２１１ｆは、差分キー３２１ｄを格納していた更新ツリー４０９０のノード２１０ｈと対をなすノード２１１ｈに書き換えられている。
そして、図１６Ｂの矢印３６０ｂで示すように、更新データ３８０ｂの更新位置３８３は２２０ａであるので、ノード２１０ｂが書き換え対象となる。
【０１１０】
図１６Ｃには、更新データ３８０ｂによる書き換え後、更新データ３８０ｃによる書き換え前の更新ツリー４０９３が記載されている。
ノード２１０ｂは、差分キー３２１ｂを格納していた更新ツリー４０９０のノード２１１ｃと対をなすノード２１０ｃに書き換えられている。
そして、矢印３６０１ｃ、３６０２ｃで示すように、代表ノードの配列番号が２２０ｆである空ノード対２０１ｇが書き換え対象となる。また、矢印３６０３ｃで示すように、更新データ３８０ｃのうち第３の更新ノードの格納される配列要素の配列番号は２２１ｂなので、ノード２１０ｆが書き換え対象となる。
【０１１１】
図１６Ｄには、更新データ３８０ｃによる書き換え後、更新データ３８０ｄによる書き換え前の更新ツリー４０９４が記載されている。
ノード２１０ｆは、更新データ３８０ｃの第３の更新ノードに書き換えられている。また、ノード２１０ｇには更新データ３８０ｃのうち第１の更新ノードが、ノード２１１ｇには第２の更新ノードが格納されている。
そして、矢印３６０１ｄ、３６０２ｄで示すように、代表ノードの配列番号が２２０ｂである空ノード対２０１ｅが書き換え対象となる。また、矢印３６０３ｄで示すように、更新データ３８０ｄのうち第３の更新ノードの格納される配列要素の配列番号は２２０ａなので、ノード２１０ｂが書き換え対象となる。
【０１１２】
図１６Ｅには、更新データ３８０ｄによる書き換え後、すなわち全更新データによる書きかえ後の更新ツリー４０９１が記載されている。更新ツリー４０９１には、ノード対２０１ｅがノード２１０ｂの下に挿入され、挿入キーを含むリーフノードはノード２１１ｅである。
更新ツリー４０９１は差分ツリー３０９１と全く同一であり、このようにして、インデックス更新データ作成装置とインデックス更新装置の間のインデックスの同期をとることができる。
つまり、インデックス更新データ作成装置で作成される更新データは、差分データによる挿入処理や削除処理に関わらず、更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードであり、インデックス更新装置において、更新データの更新位置のノードの内容を更新ノードで書き換えることにより更新ツリーを更新して、差分ツリーと更新ツリーを容易に同期させることができる。
【０１１３】
以上詳細に説明したところから明らかなとおり、本発明によればカップルドノードツリーを活用した、データベースのインデックスを旧データのものから新データに効率よく更新するためのインデックス更新データを提供することができ、また、本発明のインデックス更新データにより、インデックス更新装置の処理負担を軽減することができる。
また、本発明の実施の形態は上記に限ることなく種々の変形が可能であることは当業者に明らかである。さらに、本発明のインデックス更新データ作成装置及び作成方法、さらにはインデックス更新装置及び更新方法を、コンピュータに実行させるプログラムによりコンピュータ上で実現可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。
【符号の説明】
【０１１４】
３００ インデックス更新データ作成装置
３０１ データ処理装置
３０２ 中央処理装置
３０３ キャッシュメモリ
３０４ バス
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ 通信装置
３０８ データ格納装置
３０９ 配列
３１０ 探索経路スタック
３２０ 差分データ格納領域
３２２ 更新データ格納領域
３３０ 差分ツリー取得手段
３４０ 差分データ取得手段
３５０ 更新データ作成手段
３５２ 挿入データ作成手段
３５４ 削除データ作成手段
３５６ 更新種別判定手段
３８０ 更新データ
３８３ 更新位置
３８４ 更新ノード
３９０ 差分データ
３９１ 更新種別
３９２ 差分キー
４００ インデックス更新装置
４０９ 配列
４２０ 更新データ格納領域
４３０ 更新ツリー取得手段
４４０ 更新データ取得手段
４５０ 更新ツリー更新手段
【特許請求の範囲】
【請求項１】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新データ作成装置において、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである差分ツリーを取得する差分ツリー取得手段と、
更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する差分データ取得手段と、
前記差分データに基づき前記差分ツリーを更新し、該更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する更新データ作成手段と、
を備えることを特徴とするインデックス更新データ作成装置。
【請求項２】
請求項１に記載のインデックス更新データ作成装置において、
前記差分データは、更新対象であるインデックスキーと該インデックスキーが挿入されるものであるか削除されるものであるかを示す更新種別を含み、
前記更新データ作成手段は、前記更新種別を判定する更新種別判定手段と、該更新種別が挿入であると判定されたときに前記更新データを作成する挿入データ作成手段と、該更新種別が削除であると判定されたときに前記更新データを作成する削除データ作成手段とを含む、
ことを特徴とするインデックス更新データ作成装置。
【請求項３】
請求項２に記載のインデックス更新データ作成装置において、
前記挿入データ作成手段は、更新種別が挿入を示すものである前記差分データのインデックスキーを挿入キーとして、前記差分ツリーに該挿入キーを格納するリーフノードを挿入し、該リーフノードの内容を第１の更新ノードとし該リーフノードの位置情報を第１の更新位置とする第１の更新データと、該リーフノードと対をなす対ノードの内容を第２の更新ノードとし該対ノードの位置情報を第２の更新位置とする第２の更新データを作成するとともに、更新後の差分ツリーにおける前記リーフノードの直近上位のブランチノードの内容を第３の更新ノードとし該ブランチノードの位置情報を第３の更新位置とする第３の更新データを作成し、
前記削除データ作成手段は、更新種別が削除を示すものである前記差分データのインデックスキーを削除キーとして、前記差分ツリーから該削除キーと同一のインデックスキーを格納するリーフノードを削除し、該リーフノードと同一のノード対を構成するノードの内容を前記更新ノードとし更新前の差分ツリーにおける前記リーフノードの直近上位のノードの位置情報を前記更新位置として更新データを作成する、
ことを特徴とするインデックス更新データ作成装置。
【請求項４】
請求項１〜請求項３のいずれか１項に記載されたインデックス更新データ作成装置において、
前記差分ツリーは配列に記憶され、前記ノードの位置情報は、該ノードの配置された配列要素の配列番号であることを特徴とするインデックス更新データ作成装置。
【請求項５】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新データ作成装置がインデックスの更新データを作成するインデックス更新データ作成方法において、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである差分ツリーを取得する差分ツリー取得ステップと、
更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する差分データ取得ステップと、
前記差分データに基づき前記差分ツリーを更新し、該更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する更新データ作成ステップと、
を備えることを特徴とするインデックス更新データ作成方法。
【請求項６】
請求項５に記載のインデックス更新データ作成方法において、
前記差分データは、更新対象であるインデックスキーと該インデックスキーが挿入されるものであるか削除されるものであるかを示す更新種別を含み、
前記更新データ作成ステップは、前記更新種別を判定する更新種別判定ステップと、該更新種別が挿入であると判定されたときに前記更新データを作成する挿入データ作成ステップと、該更新種別が削除であると判定されたときに前記更新データを作成する削除データ作成ステップとを含む、
ことを特徴とするインデックス更新データ作成方法。
【請求項７】
請求項６に記載のインデックス更新データ作成方法において、
前記挿入データ作成ステップは、更新種別が挿入を示すものである前記差分データのインデックスキーを挿入キーとして、前記差分ツリーに該挿入キーを格納するリーフノードを挿入するステップと、該リーフノードの内容を第１の更新ノードとし該リーフノードの位置情報を第１の更新位置とする第１の更新データと、該リーフノードと対をなす対ノードの内容を第２の更新ノードとし該対ノードの位置情報を第２の更新位置とする第２の更新データを作成するステップと、更新後の差分ツリーにおける前記リーフノードの直近上位のブランチノードの内容を第３の更新ノードとし該ブランチノードの位置情報を第３の更新位置とする第３の更新データを作成するステップを含み、
前記削除データ作成ステップは、更新種別が削除を示すものである前記差分データのインデックスキーを削除キーとして、前記差分ツリーから該削除キーと同一のインデックスキーを格納するリーフノードを削除するステップと、該リーフノードと同一のノード対を構成するノードの内容を前記更新ノードとし更新前の差分ツリーにおける前記リーフノードの直近上位のノードの位置情報を前記更新位置として更新データを作成するステップを含む、
ことを特徴とするインデックス更新データ作成方法。
【請求項８】
請求項５〜請求項７のいずれか１項に記載されたインデックス更新データ作成方法において、
前記差分ツリーは配列に記憶され、前記ノードの位置情報は、該ノードの配置された配列要素の配列番号であることを特徴とするインデックス更新データ作成方法。
【請求項９】
請求項５〜請求項８のいずれか以降に記載のインデックス更新データ作成方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１０】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新装置において、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである前記更新ツリーを取得する更新ツリー取得手段と、
前記インデックス更新データ作成装置から更新すべき前記更新ツリーのノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを取得する更新データ取得手段と、
前記更新データの更新位置のノードの内容を更新ノードで書き換えることにより前記更新ツリーを更新する更新ツリー更新手段と、
を備えることを特徴とするインデックス更新装置。
【請求項１１】
請求項１０に記載のインデックス更新装置において、
前記更新ツリーは配列に記憶され、前記更新位置は、前記更新すべきノードが配置された配列要素の配列番号であることを特徴とするインデックス更新装置。
【請求項１２】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新装置がインデックスを更新するインデックス更新方法おいて、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである前記更新ツリーを取得する更新ツリー取得ステップと、
前記インデックス更新データ作成装置から更新すべき前記更新ツリーのノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを取得する更新データ取得ステップと、
前記更新データの更新位置のノードの内容を更新ノードで書き換えることにより前記更新ツリーを更新する更新ツリー更新ステップと、
を備えることを特徴とするインデックス更新方法。
【請求項１３】
請求項１２に記載のインデックス更新方法において、
前記更新ツリーは配列に記憶され、前記更新位置は、前記更新すべきノードが配置された配列要素の配列番号であることを特徴とするインデックス更新方法。
【請求項１４】
請求項１２又は請求項１３に記載のインデックス更新方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１５】
請求項９又は請求項１４に記載のプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新データ作成装置において、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである差分ツリーを取得する差分ツリー取得手段と、
更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する差分データ取得手段と、
前記差分データに基づき前記差分ツリーを更新し、該更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する更新データ作成手段と、
を備えることを特徴とするインデックス更新データ作成装置。
【請求項２】
請求項１に記載のインデックス更新データ作成装置において、
前記差分データは、更新対象であるインデックスキーと該インデックスキーが挿入されるものであるか削除されるものであるかを示す更新種別を含み、
前記更新データ作成手段は、前記更新種別を判定する更新種別判定手段と、該更新種別が挿入であると判定されたときに前記更新データを作成する挿入データ作成手段と、該更新種別が削除であると判定されたときに前記更新データを作成する削除データ作成手段とを含む、
ことを特徴とするインデックス更新データ作成装置。
【請求項３】
請求項２に記載のインデックス更新データ作成装置において、
前記挿入データ作成手段は、更新種別が挿入を示すものである前記差分データのインデックスキーを挿入キーとして、前記差分ツリーに該挿入キーを格納するリーフノードを挿入し、該リーフノードの内容を第１の更新ノードとし該リーフノードの位置情報を第１の更新位置とする第１の更新データと、該リーフノードと対をなす対ノードの内容を第２の更新ノードとし該対ノードの位置情報を第２の更新位置とする第２の更新データを作成するとともに、更新後の差分ツリーにおける前記リーフノードの直近上位のブランチノードの内容を第３の更新ノードとし該ブランチノードの位置情報を第３の更新位置とする第３の更新データを作成し、
前記削除データ作成手段は、更新種別が削除を示すものである前記差分データのインデックスキーを削除キーとして、前記差分ツリーから該削除キーと同一のインデックスキーを格納するリーフノードを削除し、該リーフノードと同一のノード対を構成するノードの内容を前記更新ノードとし更新前の差分ツリーにおける前記リーフノードの直近上位のノードの位置情報を前記更新位置として更新データを作成する、
ことを特徴とするインデックス更新データ作成装置。
【請求項４】
請求項１〜請求項３のいずれか１項に記載されたインデックス更新データ作成装置において、
前記差分ツリーは配列に記憶され、前記ノードの位置情報は、該ノードの配置された配列要素の配列番号であることを特徴とするインデックス更新データ作成装置。
【請求項５】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新データ作成装置がインデックスの更新データを作成するインデックス更新データ作成方法において、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである差分ツリーを取得する差分ツリー取得ステップと、
更新前のデータベースのインデックスと更新後のデータベースのインデックスの差分データを取得する差分データ取得ステップと、
前記差分データに基づき前記差分ツリーを更新し、該更新された差分ツリーのうち更新されたノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを作成する更新データ作成ステップと、
を備えることを特徴とするインデックス更新データ作成方法。
【請求項６】
請求項５に記載のインデックス更新データ作成方法において、
前記差分データは、更新対象であるインデックスキーと該インデックスキーが挿入されるものであるか削除されるものであるかを示す更新種別を含み、
前記更新データ作成ステップは、前記更新種別を判定する更新種別判定ステップと、該更新種別が挿入であると判定されたときに前記更新データを作成する挿入データ作成ステップと、該更新種別が削除であると判定されたときに前記更新データを作成する削除データ作成ステップとを含む、
ことを特徴とするインデックス更新データ作成方法。
【請求項７】
請求項６に記載のインデックス更新データ作成方法において、
前記挿入データ作成ステップは、更新種別が挿入を示すものである前記差分データのインデックスキーを挿入キーとして、前記差分ツリーに該挿入キーを格納するリーフノードを挿入するステップと、該リーフノードの内容を第１の更新ノードとし該リーフノードの位置情報を第１の更新位置とする第１の更新データと、該リーフノードと対をなす対ノードの内容を第２の更新ノードとし該対ノードの位置情報を第２の更新位置とする第２の更新データを作成するステップと、更新後の差分ツリーにおける前記リーフノードの直近上位のブランチノードの内容を第３の更新ノードとし該ブランチノードの位置情報を第３の更新位置とする第３の更新データを作成するステップを含み、
前記削除データ作成ステップは、更新種別が削除を示すものである前記差分データのインデックスキーを削除キーとして、前記差分ツリーから該削除キーと同一のインデックスキーを格納するリーフノードを削除するステップと、該リーフノードと同一のノード対を構成するノードの内容を前記更新ノードとし更新前の差分ツリーにおける前記リーフノードの直近上位のノードの位置情報を前記更新位置として更新データを作成するステップを含む、
ことを特徴とするインデックス更新データ作成方法。
【請求項８】
請求項５〜請求項７のいずれか１項に記載されたインデックス更新データ作成方法において、
前記差分ツリーは配列に記憶され、前記ノードの位置情報は、該ノードの配置された配列要素の配列番号であることを特徴とするインデックス更新データ作成方法。
【請求項９】
請求項５〜請求項８のいずれか以降に記載のインデックス更新データ作成方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１０】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新装置において、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである前記更新ツリーを取得する更新ツリー取得手段と、
前記インデックス更新データ作成装置から更新すべき前記更新ツリーのノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを取得する更新データ取得手段と、
前記更新データの更新位置のノードの内容を更新ノードで書き換えることにより前記更新ツリーを更新する更新ツリー更新手段と、
を備えることを特徴とするインデックス更新装置。
【請求項１１】
請求項１０に記載のインデックス更新装置において、
前記更新ツリーは配列に記憶され、前記更新位置は、前記更新すべきノードが配置された配列要素の配列番号であることを特徴とするインデックス更新装置。
【請求項１２】
データベースのインデックスの更新データを作成するインデックス更新データ作成装置と該更新データにより自装置のデータベースのインデックスを更新するインデックス更新装置から構成されるシステムにおける前記インデックス更新装置がインデックスを更新するインデックス更新方法おいて、
更新前のデータベースのインデックスキーを格納したカップルドノードツリーである前記更新ツリーを取得する更新ツリー取得ステップと、
前記インデックス更新データ作成装置から更新すべき前記更新ツリーのノードの位置情報である更新位置とそのノードの内容である更新ノードからなるインデックスの更新データを取得する更新データ取得ステップと、
前記更新データの更新位置のノードの内容を更新ノードで書き換えることにより前記更新ツリーを更新する更新ツリー更新ステップと、
を備えることを特徴とするインデックス更新方法。
【請求項１３】
請求項１２に記載のインデックス更新方法において、
前記更新ツリーは配列に記憶され、前記更新位置は、前記更新すべきノードが配置された配列要素の配列番号であることを特徴とするインデックス更新方法。
【請求項１４】
請求項１２又は請求項１３に記載のインデックス更新方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１５】
請求項９又は請求項１４に記載のプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５】
【図６Ａ】
【図６Ｂ】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１３Ｅ】
【図１４】
【図１５】
【図１６Ａ】
【図１６Ｂ】
【図１６Ｃ】
【図１６Ｄ】
【図１６Ｅ】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５】
【図６Ａ】
【図６Ｂ】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１３Ｅ】
【図１４】
【図１５】
【図１６Ａ】
【図１６Ｂ】
【図１６Ｃ】
【図１６Ｄ】
【図１６Ｅ】
【公開番号】特開２０１０−２５７４２７（Ｐ２０１０−２５７４２７Ａ）
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願番号】特願２００９−１１００８０（Ｐ２００９−１１００８０）
【出願日】平成２１年４月２８日（２００９．４．２８）
【出願人】（５０６２３５６１６）株式会社エスグランツ (32)
【Ｆターム（参考）】
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願日】平成２１年４月２８日（２００９．４．２８）
【出願人】（５０６２３５６１６）株式会社エスグランツ (32)
【Ｆターム（参考）】
[ Back to top ]