(57)【要約】【課題】インデックスデータを管理する情報処理装置の追加ツリーデータと既存ツリーデータとのマージ処理の負荷を軽減する。【解決手段】複数のノードデータと複数のノードデータ間を結ぶ枝データとを含むツリー構造を有するインデックスデータにしたがってデータベースを有する情報処理装置の前処理装置において、データベースの既存インデックスデータを記憶した記憶部と、データベースに追加される入力データを受信する通信部と、既存インデックスデータと入力データが有する入力インデックスデータとを比較し、入力インデックスデータから既存インデックスデータに対する差分となる新規ノードデータを抽出し、新規ノードデータを連続で配置した新規ツリーデータを有する追加インデックスデータを作成し、かつ通信部を制御して情報処理装置へ追加インデックスデータを送信する制御部を備える。【選択図】図１５
2018045286.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードデータと前記複数のノードデータ間を結ぶ枝データとを含むツリー構造を有するインデックスデータにしたがってデータベースを有する情報処理装置の前処理装置において、
前記データベースの既存インデックスデータを記憶した記憶部と、
前記データベースに追加される入力データを受信する通信部と、
既存インデックスデータと前記入力データが有する入力インデックスデータとを比較し、前記入力インデックスデータから前記既存インデックスデータに対する差分となる新規ノードデータを抽出し、前記新規ノードデータを連続で配置した新規ツリーデータを有する追加インデックスデータを作成し、かつ前記通信部を制御して前記情報処理装置へ前記追加インデックスデータを送信する制御部を備える、情報処理装置の前処理装置。
【請求項２】
前記制御部は、前記比較の結果、前記入力データから、前記既存インデックスデータに記憶済みのノードデータを部分ツリーデータとして生成し、前記追加インデックスデータに前記部分ツリーデータを追加することを特徴とする請求項１記載の前処理装置。
【請求項３】
複数のノードデータと前記複数のノードデータ間を結ぶ枝データとを含むツリー構造を有するインデックスデータにしたがってデータベースを有する情報処理装置の前処理装置が、
前記データベースに追加される入力データを受信し、
記憶部に記憶された前記データベースの既存インデックスデータと、前記入力データが有する入力インデックスデータとを比較し、
前記入力インデックスデータから前記既存インデックスデータに対する差分となる新規ノードデータを抽出し、
前記新規ノードデータを連続で配置した新規ツリーデータを有する追加インデックスデータを作成し、
前記情報処理装置へ前記追加インデックスデータを送信する
ことを実行するインデックス追加ツリーデータ修正方法。
【請求項４】
複数のノードデータと前記複数のノードデータ間を結ぶ枝データとを含むツリー構造を有するインデックスデータにしたがってデータベースを管理する情報処理装置の前処理装置に、
前記データベースに追加される入力データを受信し、
記憶部に記憶された前記データベースの既存インデックスデータと、前記入力データが有する入力インデックスデータとを比較し、
前記入力インデックスデータから前記既存インデックスデータに対する差分となる新規ノードデータを抽出し、
前記新規ノードデータを連続で配置した新規ツリーデータを有する追加インデックスデータを作成し、
前記情報処理装置へ前記追加インデックスデータを送信する
ことを実行させるインデックス追加ツリーデータ修正プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、前処理装置、インデックス追加ツリーデータ修正方法及びインデックス追加ツリーデータ修正プログラムに関する。
【背景技術】
【０００２】
従来から、データベースを管理する情報処理装置では、インデックスを用いたデータ管理が行われている。インデックスにおいては、例えば、Ｂ−ｔｒｅｅといった木構造、ビットマップ構造等のデータ構造により、データベースに蓄積されたデータ集合が管理される。インデックスを用いることで、上記情報処理装置は、入力されたデータを処理しやすいように整理した状態でデータベースに格納可能になり、データベースへの検索要求やデータ抽出といった処理の実行速度を高めることが可能になる。
【０００３】
近年の、Information and Communication Technology（ＩＣＴ：情報通信技術）の発展に伴い、通信機能を有する様々な「物体」がインターネット等の通信ネットワークに接続するInternet of Things（ＩｏＴ）と呼ばれる技術がある。ＩｏＴにおいては、例えば、通信ネットワークに接続された様々な通信装置で観測された観測データがデータベースに継続的に追加されて蓄積される。データベースに蓄積されたデータは、例えば、通信ネットワークを介して接続されたスマートフォンや他の通信装置によって検索・抽出が行われ、所定の目的に沿ったデータ分析が行われる。データベースを管理する情報処理装置では、データベースへの入力データの追加・蓄積処理と共に、蓄積されたデータに対する検索・更新処理が発生するため、処理負荷が増大する傾向にあった。
【０００４】
なお、本明細書で説明する技術に関連する技術が記載されている先行技術文献としては、以下の特許文献が存在している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−３１１４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
木構造を用いたインデックスは、インデックスの各データ要素となるノードを親子関係や兄弟関係で結びつけられて階層化されたデータ構造を有する。上記関係によるノード間の結び付き（以下、枝とも称す）は、例えば、インデックス内の相対位置を示すポインタで表される。
【０００７】
データベースを有する情報処理装置には、木構造のインデックスを有する追加ツリーデータが入力される。追加ツリーデータと、データベースに蓄積された既存データのインデックス（以下、既存ツリーデータとも称す）とを結合するマージ処理が行われることになる。
【０００８】
追加ツリーデータには、既存ツリーデータと重複する重複ノード、既存ツリーデータに対しる新規ノードが含まれる。情報処理装置は、追加ツリーデータと既存ツリーデータとを走査して、新規ノードおよび重複ノードを特定し、既存ツリーデータに新規ノードを結合するマージ処理を行う。走査処理においては、各ツリーデータの木構造に沿って全てのノードが辿られるため、情報処理装置の処理負担となっていた。
【０００９】
また、マージ処理においては、既存ツリーデータに新規ノードが結合されるため、ノード間の結合後の相対位置が変化する。情報処理装置は、データ更新後の木構造に対応したノード間のポインタを書換えるため、新規ノードが結合された状態の既存ツリーデータを対象として再び走査処理を行っていた。
【００１０】
観測データが継続的に追加されてデータベースに蓄積される情報処理装置においては、入力データの追加の都度にマージ処理の処理負担が発生することになる。このため、情報処理装置では、データベースの更新処理が滞る虞があった。データベースを管理する情報処理装置においては、データ更新に係る処理速度の低下や、蓄積されたデータ集合への検索・抽出処理の効率が低下する虞があった。
【００１１】
１つの側面では、本発明は、インデックスデータを管理する情報処理装置の追加ツリーデータと既存ツリーデータとのマージ処理の負荷を軽減することを目的とする。
【課題を解決するための手段】
【００１２】
複数のノードデータと複数のノードデータ間を結ぶ枝データとを含むツリー構造を有するインデックスデータにしたがってデータベースを有する情報処理装置の前処理装置において、データベースの既存インデックスデータを記憶した記憶部と、データベースに追加される入力データを受信する通信部と、既存インデックスデータと入力データが有する入力インデックスデータとを比較し、入力インデックスデータから既存インデックスデータに対する差分となる新規ノードデータを抽出し、新規ノードデータを連続で配置した新規ツリーデータを有する追加インデックスデータを作成し、かつ通信部を制御して情報処理装置へ追加インデックスデータを送信する制御部を備える。
【発明の効果】
【００１３】
１つの側面では、インデックスデータを管理する情報処理装置の追加ツリーデータと既存ツリーデータとのマージ処理の負荷が軽減できる。
【図面の簡単な説明】
【００１４】
【図１】データベースを管理する情報処理装置を示す図である。
【図２】データベースサーバの処理負荷を軽減するための分散システムを示す図である。
【図３】インデックスにトライ木を用いたマージ処理を説明する図である。
【図４】幅優先探索によるマージ処理時のインデックスファイルの説明図である。
【図５】深さ優先探索によるマージ処理時のインデックスファイルの説明図である。
【図６】本実施形態に係る分散システム１の一例を示す図である。
【図７】前処理サーバのハードウェア構成の一例を示す図である。
【図８】ＤＢサーバのハードウェア構成の一例を示す図である。
【図９】トライ木構造のインデックスの実装についての説明図である。
【図１０】配列およびリスト形式によるトライ木構造の実装例を示す図である。
【図１１】既存インデックスの説明図である。
【図１２】入力データについてのインデックスの説明図である。
【図１３】更新後のインデックスの説明図である。
【図１４】追加インデックスのファイルの説明図である。
【図１５】追加データ作成処理の説明図である。
【図１６】前処理サーバの追加データ作成処理を例示するフローチャートである。
【図１７】追加データ作成処理時のノードの遷移を説明する図である。
【図１８】他の文字列について追加データ作成処理を継続した場合のノードの遷移を説明する図である。
【図１９】ＤＢサーバの追加データ統合処理を例示するフローチャートである。
【図２０】既存ノードと新規ノード間の枝の追加についての説明図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して、一実施形態に係る情報処理装置について説明する。以下の実施形態の構成は例示であり、本情報処理装置は、以下の実施形態の構成には限定されない。以下、図１から図２０の図面に基づいて、本実施形態の情報処理装置を説明する。
【００１６】
＜実施形態＞
（データベースサーバの負荷軽減の検討）
図１に、データベースを管理する情報処理装置の説明図を示す。情報処理装置３０は、図示しない通信ネットワークを介して入力されたデータを格納し、蓄積するためのデータベースを有する。データベースは、記録装置３１に保持される。情報処理装置３０は、例えば、デスクトップ型のパーソナルコンピュータやサーバである。また、記録装置３１は、例えば、ソリッドステートドライブ装置、ハードディスクドライブ、ＤＶＤドライブ装置である。なお、図示しない通信ネットワークは、例えば、インターネットといった公衆ネットワーク、Local Area Network（ＬＡＮ）といった有線ネットワーク、携帯電話網、無線ＬＡＮといった無線ネットワークを含む。情報処理装置３０は、記録装置３１が取扱い可能な記録媒体（例えば、シリコンディスク、ハードディスク、ＤＶＤ）の記憶領域にデータベースを保持する。なお、以下では、データベースを管理する情報処理装置３０をデータベースサーバ３０とも称する。
【００１７】
図示しない通信ネットワークを経由して、通信機能を有する様々な通信装置が接続される。データベースサーバ３０には、例えば、通信装置が観測したデータＤ１が入力される。データＤ１として、Comma-Separated Values（ＣＳＶ）、JavaScript（登録商標） Object Notation（ＪＳＯＮ）、Extensible Markup Language（ＸＭＬ）等で記述されたテキストデータが例示される。
【００１８】
データベースサーバ３０は、入力されたデータＤ１を受け付け、受け付けたデータＤ１をデータベースに格納するためのデータ生成処理を行う。データ生成処理では、受け付けたデータＤ１の要素がデータベースのテーブル形式に沿って再構築される。また、データ生成処理では、データＤ１の一部情報を用いてデータ管理を行うためのインデックスが作成される。なお、本実施形態では、データＤ１は、１以上の要素を含むものとしている。ここで、要素とは、データの部分であり、データベースに格納されるノードになる。
【００１９】
データ生成処理により生成されるインデックスのデータ構造として、Ｂ−ｔｒｅｅといった木構造が例示される。木構造では、インデックスのデータ要素（ノード）が、親子関係といった上下関係、兄弟関係といった並列関係で結び付けられて階層化されたデータ構造になる。上記関係によるノード間の結び付き（枝）は、インデックス内の相対位置を示すポインタで表される。
【００２０】
データベースサーバ３０は、データ生成処理により再構築されたレコードと共に生成されたインデックスをデータベースに格納する。データベースには、データＤ１から再構築されたレコードが、データＤ２として格納され、蓄積される。また、データベースには、データベースサーバ３０のマージ処理によって更新されたインデックスＤ３が保持される。
【００２１】
マージ処理においては、データＤ１から生成されたインデックスと、データベースに蓄積されたデータ集合についての既存のインデックスとが結合される。データベースサーバ３０では、入力データの受け付けが発生する都度にマージ処理が行われ、更新されたイン
デックスＤ３が保持される。データＤ１のインデックスには、既存のインデックスと重複するノード（重複ノード）、既存のインデックスに対して新規となるノード（新規ノード）が含まれる。
【００２２】
図２に、データベースサーバの処理負荷を軽減するための分散システムを例示する。図２において、分散システム１は、相互に接続されたデータ生成サーバ４０、データベースサーバ５０を含む。データ生成サーバ４０では、例えば、様々な通信装置から継続して入力されるデータＤ１を受け付け（データロードＲ１）、データ生成処理が行われる。また、データベースサーバ５０では、例えば、データベースに蓄積されたデータを使用する複数の情報処理装置（図示せず）からの問い合わせ対応処理が行われる（問い合わせＲ２）。
【００２３】
分散システム１では、図１のデータベースサーバ３０で行われるデータ入力時のデータ生成処理機能がデータ生成サーバ４０に分散される。このため、データベースサーバ５０の処理負荷が軽減される。データベースサーバ５０の処理負荷が軽減された分散システム１では、例えば、On-line Analytical Processing（ＯＬＡＰ）といった、データベース
に蓄積された大量のデータに対し複雑な集計、分析を行い、素早く結果を提示する処理が可能になる。また、上記分散システム１では、例えば、On-Line Transaction Processing（ＯＬＴＰ）といった、データベースに蓄積されたデータに対する複数の情報処理装置からの処理要求に対するデータ処理が可能になる。分散システム１では、データベースサーバ５０の処理負荷が軽減されるため、ＯＬＡＰとＯＬＴＰの両立が期待される。
【００２４】
なお、図２の分散システム１では、データ生成サーバ４０からデータ生成処理の結果がデータベースサーバ５０に出力される（データロードＲ３）。データベースサーバ５０では、データ生成サーバ４０で生成されたインデックスと、データベースに蓄積されたデータ集合についての既存のインデックスとのマージ処理が行われる。データベースサーバ５０では、データロードＲ３が行われる都度にマージ処理が発生し、データ更新後のデータベースについての木構造のインデックスが再構築されることになる。
【００２５】
図２の分散システム１では、データベースサーバ５０において、図１を用いて説明したマージ処理が行われる。
【００２６】
本実施形態では、インデックスの木構造として、例えば、Ｔｒｉｅ−ｔｒｅｅ（以下、トライ木とも称す）が採用する。トライ木をインデックスのデータ構造として用いる場合には、追加処理時間は、既存のインデックスのデータサイズではなく、追加するインデックスのデータサイズに影響を受ける傾向がある。
【００２７】
図３に、インデックスにトライ木構造を用いたマージ処理の説明図を例示する。図３において、破線の矩形枠で囲まれたＴＲ１、ＴＲ２、ＴＲ３は、トライ木構造のインデックスを表す。トライ木構造を用いることで、１以上のインデックスを含むインデックス集合を、各インデックスのデータ要素であるノード同士を枝関係で結び付けて１体の木構造に表すことができる。なお、一のインデックスのノードが、他のインデックスのノードに重複することがあり得る。インデックス間で重複するノードに対する枝関係は、トライ木構造の所定の規則に沿って枝関係が決定される。以下、トライ木構造で表されたインデックス集合の内の一のインデックスをインデックス要素とも称す。
【００２８】
図３において、ＴＲ１は、既存のインデックスを表し、ＴＲ２は、追加するインデックスを表し、ＴＲ３は、マージ処理で結合されたインデックスを表す。ＴＲ１、ＴＲ２、ＴＲ３の、丸囲みされた数字は、各インデックスに集合されたインデックス要素のノードを表す。Ｒ４−Ｒ１８は、ノード間の結び付き（関連）である枝を表す。なお、ＴＲ３にお
いて、斜め斜線でハッチングされた丸囲み数字“４”、“６”、“７”、“９”は、マージ処理によって追加されたノードを表す。
【００２９】
木構造においては、ノード間の上下関係は、所謂、親子関係を表し、同じ階層に並列するノード間の並列関係は兄弟関係を表す。兄弟関係にあるノードは同じ親ノードへの枝を持つ。なお、親ノードへの枝を持たないノードを根ノードともいう。例えば、図３のＴＲ１では、ノード“１”が根ノードであり、ノード“２”の親ノードである。また、ノード“１”は、ノード“３”の親ノードである。ノード“２”とノード“３”はノード“１”を親に持つ兄弟関係である。兄弟関係にあるノード同士は、木構造の中の同じ階層に並列する。
【００３０】
マージ処理は、既存のインデックスであるＴＲ１と、追加するインデックスであるＴＲ２とを走査処理しながら、ＴＲ１とは重複しないＴＲ２内の新規ノードを特定する。走査処理においては、例えば、木構造に沿って全てのノードを辿る処理が行われる。木構造の全てのノードを辿る処理は、ノード間を結び付ける枝に基づいて行われる。
【００３１】
なお、木構造の走査処理として、深さ優先探索、幅優先探索が例示される。深さ優先探索の処理は、例えば、対象のノードについて枝の存在を調査し、枝が存在する場合には、枝の辿り先にある子ノードを特定する。そして、深さ優先探索の処理は、特定した子ノードを探索対象として、上記の処理を繰り返して木構造を走査する。また、幅優先探索の処理は、階層レベルが同じノードを対象として、階層の上位側から下位側へ順に木構造を走査する。
【００３２】
ＴＲ１を探索例とすると、深さ優先探索の走査処理は、根ノード“１”を特定し、根ノード“１”の枝（Ｒ４、Ｒ５）を特定する。深さ優先探索の走査処理は、例えば、特定した左枝Ｒ４を辿り、ノード“２”特定し、特定したノード“２”を対象として上記処理を繰り返す。深さ優先探索の走査処理は、左枝Ｒ４についての処理後、右枝Ｒ５について上記処理を繰り返す。ＴＲ１においては、深さ優先探索の走査処理では、ノード“１”→枝Ｒ４→ノード“２”→枝Ｒ６→ノード“５”→枝Ｒ７→ノード“８”→枝Ｒ５→ノード“３”の順でノードが走査される。
【００３３】
幅優先探索の走査処理は、ＴＲ１では、ノード“１”を特定し、根ノード“１”の枝（Ｒ４、Ｒ５）から、同じ階層のノード“２”、“３”を特定する。そして、幅優先探索の走査処理は、下位階層の枝を持つノード“２”を対象として上記処理を繰り返す。ＴＲ１の幅優先探索の走査処理では、ノード“１”→枝Ｒ４→ノード“２”→枝Ｒ５→ノード“３”→枝Ｒ６→ノード“５”→枝Ｒ７→ノード“８”の順でノードが走査される。
【００３４】
マージ処理は、例えば、ＴＲ１、ＴＲ２に対して上記の走査処理をノード毎に交互に行い、ＴＲ２のＴＲ１には出現しない新規ノードを特定する。図３の例では、マージ処理は、ＴＲ２においてノード“２”から枝Ｒ１０を辿りノード“４”を参照した時点で、枝Ｒ１０で結び付けられたノード“４”および枝Ｒ１３で結び付けられたノード“７”を新規ノードとして特定する。ＴＲ１にはノード“４”は出現しないからである。なお、枝によって結びつけられたノードを部分木とも称す。
【００３５】
同様にして、マージ処理は、ＴＲ２においてノード“５”に枝Ｒ１４で結び付けられたノード“９”、ノード“３”に枝Ｒ１２で結び付けられたノード“６”を新規ノードとして特定する。マージ処理は、新規ノード“４”、“７”、“９”、“６”のそれぞれを参照した時点で、ＴＲ１のデータ要素として追加する。
【００３６】
マージ処理は、ＴＲ２に出現する新規ノードを追加後に、新規ノードが追加された状態
のＴＲ３に対し、再び走査処理を行う。新規ノードを追加した状態のＴＲ３として、各ノード間を結ぶ枝を再構築するためである。図３の例では、マージ処理は、根ノード“１”から枝Ｒ４を辿り、ノード“２”を参照する。そして、マージ処理は、ノード“２”とノード“４”とを結びつける枝関係（枝Ｒ１５）をＴＲ１に追加する。
【００３７】
同様にして、マージ処理は、ノード“２”から枝Ｒ６を辿り、ノード“５”を参照する。そして、マージ処理は、ノード“５”とノード“９”とを結びつける枝関係（枝Ｒ１８）をＴＲ１に追加する。また、マージ処理は、根ノード“１”から枝Ｒ５を辿り、ノード“３”を参照する。そして、マージ処理は、ノード“３”とノード“６”とを結びつける枝関係（枝Ｒ１６）をＴＲ１に追加する。また、マージ処理では、ＴＲ１には出現しない新規の部分木の、ノード“４”、“７”間の枝を枝Ｒ１７とする書換えが行われる。図３のＴＲ３では、ＴＲ１とＴＲ２とのマージ処理において、ＴＲ１に追加される枝は太線矢印により表されている。
【００３８】
図３を用いて説明したトライ木構造のインデックスは、該インデックスに集合されたインデックス要素についての各データ要素（ノード）が格納されたファイルである。ノード間を結び付ける枝は、ファイル内ではノードの格納位置に対するオフセット（offset）として表すことができる。例えば、親子関係で結び付けられるノード間の枝は、親ノードの格納位置に対する子ノードの格納位置への相対的なオフセットとして表される。次に、ファイルにおけるマージ処理を説明する。
【００３９】
図４に、幅優先探索によるマージ処理時のインデックスファイルの説明図を例示する。図４において、実線の矩形枠で囲まれたＦＴ１、ＦＴ２、ＦＴ３は、それぞれ、図３にトライ木構造のインデックスとして例示したＴＲ１、ＴＲ２、ＴＲ３に対応するファイルである。ＦＴ１、ＦＴ２、ＦＴ３において、数字が付された矩形枠は、各インデックスのデータ要素であるノードを表す。なお、ＦＴ２、ＦＴ３において、斜め斜線でハッチングされた数字“４”、“６”、“７”、“９”が付された矩形枠は、既存のインデックスであるＦＴ１に出現しない新規のノードを表す。なお、ファイルにおけるノードの並び順は、走査処理の探索法に沿って決定される。
【００４０】
図４において、Ｒ４−Ｒ１８は、図３と同様にノード間を結び付ける枝を表す。ファイルにおいては、ノード間を結び付ける枝Ｒ４−Ｒ１８は、結び付くノード間のオフセットとして表される。ノード間のオフセットについても、走査処理の探索法に沿って決定される。
【００４１】
図４のＦＴ１−ＦＴ３においては、各ノードは連続して格納されているとする。ＦＴ１においては、例えば、ノード“１”とノード“２”間の枝Ｒ４は、現在のノード“１”の格納位置から、現在のノード“２”の格納位置を指し示す相対的なオフセット値（ポインタ）として表される。例えば、ノード“１”とノード“２”の枝Ｒ４はオフセット値（＋１）として表される。同様にして、枝Ｒ５はオフセット値（＋２）、枝Ｒ６はオフセット値（＋２）、枝Ｒ７はオフセット値（＋１）として表される。
【００４２】
図３を用いて説明したように、幅優先探索においては、ＦＴ１に示すようにノード“１”→ノード“２”→ノード“３”→ノード“５”→ノード“８”の並び順でノードの走査が行われる。また、ＦＴ２に示すように、ノード“１”→ノード“２”→ノード“３”→ノード“４”→ノード“５”→ノード“６”→ノード“７”→ノード“９” の並び順で
ノードの走査が行われる。
【００４３】
マージ処理においては、既存のインデックス（ＦＴ１）に出現しないノード（新規ノード）が追加するインデックス（ＦＴ２）に出現した時点で、既存のインデックスに追加さ
れる。ファイルでの新規ノードは、ＦＴ１のノード“８”の格納位置以降に追加される。幅優先探索の走査処理においては、ノードは階層順に走査されるため、ノード“４”の既存のインデックスへの追加後に、ノード４と同じ階層のノード５、６が走査されることになる。ＦＴ３に示すように、ＦＴ２における新規ノードは、幅優先探索によって出現した順に追加される。
【００４４】
図３を用いて説明したように、新規ノードの追加後に、新規ノードへの枝を追加するために走査処理が行われる。図４の、ＦＴ３の太線矢印で示すように、走査処理により、ノード“２”と新規ノード“４”とを結びつける枝Ｒ１５のオフセット値が追加される。同様にして、ノード“３”と新規ノード“６”とを結びつける枝Ｒ１６のオフセット値、ノード“５”と新規ノード“９”とを結びつける枝Ｒ１８のオフセット値が追加される。
【００４５】
なお、幅優先探索の走査処理においては、部分木となるノード“４”とノード“７”との間の枝Ｒ１３のオフセット値が、太破線矢印で示す枝Ｒ１７のオフセット値に書き換えられる。ＴＦ２に示すように、枝Ｒ１３のオフセット値は、（＋３）である。ノード“４”とノード“７”とを結び付ける枝Ｒ１３は、部分木結合後の走査処理により、オフセット値（＋２）の枝Ｒ１７に書き換えられる。
【００４６】
図４において、ＦＴ２とＦＴ３における新規ノードの配置を比較すると、既存のインデックスに結合される新規ノード“４”、“６”、“７”、“９”は、ＦＴ２においては、分散していることがわかる。例えば、ＦＴ２における新規ノードが、結合後のＦＴ３に示すように、ノード群のブロックとして連続するのであれば、新規ノードが出現した時点で上記ブロックを纏めて既存のインデックスに追加することが可能になる。
【００４７】
つまり、図４に例示したマージ処理の、既存のインデックスと追加のインデックスとを対象にする走査処理においては、追加のインデックスに新規ノードが出現した時点で走査処理が終了できる。このため、マージ処理の、負担軽減が期待できる。次に、深さ優先探索の走査処理について検討する。
【００４８】
図５に、深さ優先探索によるマージ処理時のインデックスファイルの説明図を例示する。図５の、実線の矩形枠で囲まれたＦＴ４、ＦＴ５、ＦＴ６は、それぞれ、図３にトライ木構造のインデックスとして例示したＴＲ１、ＴＲ２、ＴＲ３に対応するファイルである。ＦＴ４、ＦＴ５、ＦＴ６において、数字が付された矩形枠は、各インデックスのデータ要素であるノードを表し、斜め斜線でハッチングされた数字“４”、“６”、“７”、“９”が付された矩形枠は、既存のインデックスであるＦＴ４に出現しない新規のノードを表す。また、Ｒ４−Ｒ１８は、ノード間を結び付ける枝を表す。
【００４９】
ＦＴ４、ＦＴ５、ＦＴ６の、それぞれにおけるノードの並び順は、走査処理の探索法に沿って決定される。深さ優先探索においては、既存のインデックスでは、ＦＴ４に示すようにノード“１”→ノード“２”→ノード“５”→ノード“８”→ノード“３”の並び順でノードの走査が行われる。また、追加のインデックスでは、ＦＴ５に示すようにノード“１”→ノード“２”→ノード“４”→ノード“７”→ノード“５”→ノード“９”→ノード“３”→ノード“６”の並び順でノードの走査が行われる。
【００５０】
深さ優先探索においても、ＦＴ５に示すように、新規ノードは分散することがわかる。深さ優先探索を用いたマージ処理では、ＦＴ６に示すように、ノード“３”以降に、部分木となるノード“４”、“７”が追加される。そして、ＦＴ５の他の新規ノード“９”、“６”は、出現時点でノード“７”以降に追加される。深さ優先探索においては、ＦＴ５の新規ノードは、“４”、“７”、“９”、“６”の順にＦＴ４と結合される。
【００５１】
深さ優先探索においても、新規ノードの追加後に、新規ノードへの枝を追加するために走査処理が行われる。図５の、ＦＴ６の太線矢印で示すように、走査処理によって、ノード“２”と新規ノード“４”とを結びつける枝Ｒ１５のオフセット値（＋４）が追加される。また、ノード“５”と新規ノード“９”とを結びつける枝Ｒ１８のオフセット値（＋５）、ノード“３”と新規ノード“６”とを結びつける枝Ｒ１６のオフセット値（＋４）が追加される。
【００５２】
なお、図３を用いて説明したように、深さ優先探索を用いた走査処理においては、部分木になる新規ノード“４”、“７”は、ＦＴ５の枝Ｒ１３で示すオフセット関係を保持した状態でＦＴ４に追加される。このため、前後に連続するノードとしてＦＴ４に結合された新規ノード間のオフセット値は、結合後においても維持されることになる（太破線矢印Ｒ１７）。つまり、部分木として追加された新規ノード間のオフセット値に対する書換えは発生しない。
【００５３】
深さ優先探索による走査処理においても、図４において検討したように、既存のインデックスに結合される新規ノード“４”、“７”、“９”、“６”は、分散することがわかる。このため、深さ優先探索においても、既存のインデックスに結合される新規ノードが、連続するノード群のブロックとして纏まるのであれば、新規ノードが出現した時点で上記ブロックを纏めて既存のインデックスに追加することが可能になる。
【００５４】
つまり、図５に例示した深さ優先探索のマージ処理においても、既存のインデックスと追加のインデックスとを対象にする走査処理においては、追加のインデックスに新規ノードが出現した時点で走査処理が終了できる。深さ優先探索においても、マージ処理の負担軽減が期待できる。
【００５５】
さらに、図５の部分木となるノード間のオフセットで説明したように、連続するノード群のブロック内のノード間のオフセット値は、結合後においても維持されることがわかる。つまり、既存のインデックスに結合される新規ノードが、連続するノード群のブロックとして纏まるのであれば、上記ブロックにおける新規ノード間のオフセット関係は保持される。上記ブロックの既存インデックスへの結合後においては、新規ノード間のフセット値の書換えは発生しない。
【００５６】
図６は、本実施形態に係る分散システム１の一例を示す。本実施形態に係る分散システム１は、相互に接続する前処理サーバ１０と、データベースサーバ２０とを含む。図６の分散システム１では、データベースサーバ２０は、自装置が備える記録装置にデータベース２１０を備える。データベース２１０には、図１を用いて説明したインデックスＤ３が保持される。図６の分散システム１では、図２を用いて説明したように、前処理サーバ１０では、例えば、通信機能を有する様々な通信装置から継続して入力される入力データＤ４を受け付ける。また、データベースサーバ２０では、例えば、データベース２１０に蓄積されたデータ集合を使用する複数の情報処理装置からの問い合わせ対応処理が行われる。
【００５７】
本実施形態に係る分散システム１においては、インデックスのデータ構造として、トライ木による木構造を用いる。トライ木構造を用いることで、分散システム１では、データベースサーバ２０に蓄積された既存のデータ量に依存しないインデックスの更新処理が可能になる。また、分散システム１では、インデックスのデータサイズ（ファイルサイズ）は、追加されるデータに依存して定まるサイズとなる。つまり、本実施形態では、インデックスのデータサイズは、図４に示すように、元の木のデータサイズには依存しない。インデックスのデータサイズを追加されるデータに依存して定まるサイズとすることで、更新処理時の処理時間の長大化が抑制可能になるためである。
【００５８】
また、本実施形態に係る分散システム１においては、図３、４、５を用いて検討したように、既存のインデックスに結合される新規ノードが、連続するノード群のブロックとして纏まるように、追加するインデックスを作成する。
【００５９】
具体的には、前処理サーバ１０は、データベースサーバ２０のデータベース２１０に蓄積されたデータ集合を自装置が備える補助記憶部にデータベース１１０として保持する。そして、前処理サーバ１０は、入力データＤ４を受け付けた際に、データベース１１０に蓄積されたデータ集合を用いて、上記の追加する追加インデックスを作成する。前処理サーバ１０で作成される追加インデックスには、入力データＤ４の、既存の既存インデックスに対して新規ノードが、連続するノード群のブロックとして纏められる。前処理サーバ１０は、作成した追加インデックスを追加データＤ５としてデータベースサーバ２０に送信する。
【００６０】
データベースサーバ２０は、追加データＤ５の上記ブロックを自装置が管理する既存インデックスに結合し、結合された新規ノードへの既存ノードからの枝の追加を行う。枝の書換えは、追加データＤ５における既存ノードと新規ノード間の枝関係に基づいて行われる。
【００６１】
データベースサーバ２０では、例えば、追加データＤ５の、既存インデックスとの差分となる新規ノードの上記ブロックを特定して結合し、結合された新規ノードへの既存ノードからの枝の追加を行うことで、インデックスの更新処理が完了する。このため、データベースサーバ２０では、マージ処理の負担が軽減する。
【００６２】
なお、前処理サーバ１０は、データベースサーバ２０のデータベース２１０に蓄積されたデータ集合を自装置が備える記録装置にデータベース１１０として保持することが好ましい。インデックスは、データベースに蓄積されるデータ種別に応じて複数に作成可能であるからである。但し、予めインデックスの作成対象となるデータ種別が定められているケースでは、例えば、既存インデックスに限定し、データベース１１０に保持するとしてもよい。
【００６３】
図７に、前処理サーバ１０のハードウェア構成の一例を示す。前処理サーバ１０は、接続バスＢ１によって相互に接続されたCentral Processing Unit（ＣＰＵ）１１、主記憶
部１２、補助記憶部１３、入力部１４、出力部１５、通信部１６を有する。主記憶部１２および補助記憶部１３は、前処理サーバ１０が読み取り可能な記録媒体である。なお、補助記憶部１３は、データベース１１０が保持される記録装置である。
【００６４】
前処理サーバ１０は、ＣＰＵ１１が補助記憶部１３に記憶されたプログラムを主記憶部１２の作業領域に実行可能に展開し、プログラムの実行を通じて周辺機器の制御を行う。これにより、前処理サーバ１０は、所定の目的に合致した処理を実行することができる。
【００６５】
ＣＰＵ１１は、前処理サーバ１０全体の制御を行う中央処理演算装置である。ＣＰＵ１１は、補助記憶部１３に格納されたプログラムにしたがって処理を行う。主記憶部１２は、ＣＰＵ１１がプログラムやデータをキャッシュしたり、作業領域を展開したりする記憶媒体である。主記憶部１２は、例えば、フラッシュメモリ、Random Access Memory（ＲＡＭ）やRead Only Memory（ＲＯＭ）を含む。
【００６６】
補助記憶部１３は、各種のプログラムおよび各種のデータを読み書き自在に記録媒体に格納する。補助記憶部１３は、外部記憶装置とも呼ばれる。補助記憶部１３には、例えば、Operating System（ＯＳ）、各種プログラム、各種テーブル等が格納される。ＯＳは、
例えば、通信部１６を介して接続される外部装置等とのデータの受け渡しを行う通信インターフェースプログラムを含む。外部装置等には、例えば、図示しない通信ネットワーク上のＰＣやサーバ、スマートフォンといった情報処理装置、外部記憶装置等が含まれる。
【００６７】
補助記憶部１３は、例えば、Erasable Programmable ROM（ＥＰＲＯＭ）、ソリッドス
テートドライブ装置、ハードディスクドライブ（ＨＤＤ、Hard Disk Drive）装置等であ
る。また、補助記憶部１３としては、例えば、ＣＤドライブ装置、ＤＶＤドライブ装置、ＢＤドライブ装置等が提示できる。記録媒体としては、例えば、不揮発性半導体メモリ（フラッシュメモリ）を含むシリコンディスク、ハードディスク、ＣＤ、ＤＶＤ、ＢＤ、Universal Serial Bus（ＵＳＢ）メモリ、Secure Digital（ＳＤ）メモリカード等がある。
【００６８】
入力部１４は、前処理サーバ１０の管理者等からの操作指示等を受け付ける。入力部１４は、例えば、入力ボタン、ポインティングデバイス、マイクロフォン等の入力デバイスである。入力部１４には、キーボード、ワイヤレスリモコンといった入力デバイスが含まれるとしてもよい。ポインティングデバイスには、例えば、タッチパネル、マウス、トラックボール、ジョイスティックが含まれる。
【００６９】
出力部１５は、ＣＰＵ１１で処理されるデータや情報、主記憶部１２、補助記憶部１３に記憶されるデータや情報を出力する。出力部１５には、例えば、Liquid Crystal Display（ＬＣＤ）、Plasma Display Panel（ＰＤＰ）、Electroluminescence（ＥＬ）パネル
、有機ＥＬパネル等の表示デバイスが含まれる。また、出力部１５は、プリンタ、スピーカ等の出力デバイスであってもよい。通信部１６は、例えば、分散システム１に接続する通信ネットワーク等とのインターフェースである。
【００７０】
前処理サーバ１０は、ＣＰＵ１１が補助記憶部１３に記憶されているＯＳ、各種プログラムや各種データを主記憶部１２に読み出して実行することで、対象プログラムの実行と共に追加データ作成処理部１０１を提供する。前処理サーバ１０は、追加データ作成処理部１０１が参照し、或いは、管理するデータの格納先として、例えば、データベース１１０を補助記憶部１３に備える。ここで、ＣＰＵ１１の対象プログラムの実行により提供される各処理部が受付部、処理部の一例である。また、補助記憶部１３、或いは、補助記憶部１３に備えるデータベース１１０が記憶部の一例である。
【００７１】
（ＤＢサーバ）
図８に、データベースサーバ２０のハードウェア構成の一例を例示する。図８に例示のデータベースサーバ２０は、接続バスＢ２によって相互に接続されたＣＰＵ２１、主記憶部２２、補助記憶部２３、入力部２４、出力部２５、通信部２６を有する。主記憶部２２および補助記憶部２３は、データベースサーバ２０が読み取り可能な記録媒体である。なお、補助記憶部２３は、データベース２１０が保持される記録装置である。
【００７２】
データベースサーバ２０は、ＣＰＵ２１が補助記憶部２３に記憶されたプログラムを主記憶部２２の作業領域に実行可能に展開し、プログラムの実行を通じて周辺機器の制御を行う。これにより、データベースサーバ２０は、所定の目的に合致した処理を実行することができる。
【００７３】
ＣＰＵ２１、主記憶部２２、補助記憶部２３、入力部２４、出力部２５、通信部２６は、それぞれ、前処理サーバ１０の有するＣＰＵ１１、主記憶部１２、補助記憶部１３、入力部１４、出力部１５、通信部１６と同様の機能を有する。このため、上記各部の説明を省略する。
【００７４】
データベースサーバ２０は、ＣＰＵ２１が補助記憶部２３に記憶されているＯＳ、各種
プログラムや各種データを主記憶部２２に読み出して実行することで、対象プログラムの実行と共に追加データ統合処理部２０１を提供する。データベースサーバ２０は、追加データ統合処理部２０１が参照し、或いは、管理するデータの格納先として、例えば、データベース２１０を補助記憶部２３に備える。
【００７５】
図６の説明図において、前処理サーバ１０は、入力データＤ４のインデックス作成対象となる一部情報を使用して、入力データＤ４についてのトライ木構造のインデックスを作成する。入力データＤ４についてのインデックスの作成は、主に前処理サーバ１０の追加データ作成処理部１０１で行われる。ここで、トライ木構造のインデックスはファイルであり、配列形式、或いは、リスト形式でノードおよびノード間を結び付ける枝（ポインタ）を実装する。
【００７６】
図９は、トライ木構造のインデックスの実装についての説明図である。図９において、ＴＲ４は、トライ木構造の一例である。インデックスのデータ要素であるノードは、“ａ”、“ｂ”、“ｃ”といった文字である。ＴＲ４において、空欄状態の根ノードは、枝Ｒ１９により子ノード“ａ”、枝Ｒ２０により子ノード“ｂ”、枝Ｒ２０により子ノード“ｃ”が結び付けられている。また、ＴＲ４の子ノード“ａ”は、さらに枝Ｒ２２で孫ノード“ａａ”に結び付けられている。
【００７７】
ＴＲ５は、ＴＲ４をリスト形式で実装する形態である。木構造ＴＲ４の左側の子ノード“ａ”について、親子関係を表す枝Ｒ１９が結び付けられる。そして、子ノード“ａ”には、兄弟関係を表す枝Ｒ２０が子ノード“ｂ”に対して結び付けられる。さらに、子ノード“ｂ”には、兄弟関係を表す枝Ｒ２１が子ノード“ｃ”に対して結び付けられる。また、子ノード“ａ”には、親子関係を表す枝Ｒ２２が孫ノード“ａａ”に対して結び付けられる。リスト形式では、兄弟関係にあるノードの中の一つのノードが親ノードと枝で結び付けられる。また、リスト形式では、子ノード間の枝より兄弟関係にあるノードが表される。図９のＴＲ５は、兄弟関係にあるノードの順序を枝によって示している。
【００７８】
また、ＴＲ４を配列形式で実装する形態では、ＴＲ６に示すように、根ノードのデータ要素の中に、兄弟関係にあるノード“ａ”、“ｂ”、“ｃ”へのポインタ（枝）が配置される。根ノードにおける兄弟関係の枝は、木構造ＴＲ４の左側から順に、枝Ｒ１９、枝Ｒ２０、枝Ｒ２１の並びで配置される。ＴＲ６は兄弟関係にあるノードの順序を配列上の一によって示している。同様にして、孫ノード“ａ”を結び付ける枝Ｒ２２は、子ノード“ａ”のデータ要素の中に配置される。
【００７９】
トライ木構造のインデックスにおいては、データ要素であるノードは、ファイル内の固定長領域として実装される。ファイルのサイズをｎバイト（ｎ：１−ｎの自然数）とした場合には、ノード領域はｋバイト目からｎバイトの領域となる。ノード領域は、自ノードが終端（子ノードを持たない）かどうかの終端フラグ、子ノードのデータ要素値、子ノードへの枝（子ノードの格納位置へのオフセット値）を含む。図９の説明例では、子ノードのデータ要素値は“ａ”、“ｂ”、“ｃ”といった文字である。
【００８０】
図１０は、配列およびリスト形式によるトライ木構造の実装例を示す。ＴＢ１は、図９に示すＴＲ４の配列形式による実装例である、ＴＢ２は、ＴＲ４のリスト形式による実装例である。なお、ＴＢ１、ＴＢ２の実装例は、子ノードのデータ要素値と、該子ノードへの枝を組合せた場合の実装例である。
【００８１】
ＴＢ１に示したように、レコードには、自ノードが終端を表すか否かの終端フラグを格納するカラムＣＬ１が含まれる。また、レコードには、子ノードのデータ要素値と該子ノードへの枝とを組合せた情報を格納するカラムＣＬ２−ＣＬ４が含まれる。ＴＢ１のレコ
ードにおいては、終端フラグを格納するカラムＣＬ１は、例えば、レコードの最先に配置される。子ノードのデータ要素値と該子ノードへの枝とを組合せた情報を格納するカラムは、カラムＣＬ１の後位置に継続して配置される。なお、以下では、ノードのデータ要素値と該ノードへの枝とを組合せた情報をノード情報とも称する。ＴＢ１のレコードにおいて、ノード情報が格納されるカラム数量は兄弟関係の子ノードの数量になる。
【００８２】
図１０の例では、カラムＣＬ１には、自ノードが終端を示す「ｙｅｓ」、自ノードが終端ではないことを示す「ｎｏ」といった２値情報が終端フラグとして格納される。また、カラムＣＬ２−ＣＬ４には、例えば、（子ノードのデータ要素値，子ノードへの枝）で表される配列データが、ノード情報として格納される。
【００８３】
ＴＢ１では、１段目のレコードは根ノードを表す。図９に示すＴＲ４では、３つの子ノードが存在するため、根ノードのレコードのカラムＣＬ１には、終端フラグ「ｎｏ」が格納される。上記レコードの、カラムＣＬ２には、子ノード“ａ”についてのノード情報が「ａ，１」として格納される。同様にして、上記レコードの、カラムＣＬ３には子ノード“ｂ”についてのノード情報が「ｂ，２」として、カラムＣＬ３には子ノード“ｃ”についてのノード情報が「ｃ，３」として格納される。
【００８４】
なお、図９に示すようにＴＲ４では、子ノード“ｂ”、“ｃ”は孫ノードを持たない。配列形式においては、上記子ノード（データ要素値を有し、且つ、終端するノード）を表すため、終端フラグ「ｙｅｓ」をカラムＣＬ１に格納したレコードへのオフセット値が、上記子ノードのデータ要素値と組合せて格納される。なお、終端フラグ「ｙｅｓ」をカラムＣＬ１に格納するレコードにおいては、他のカラムは空欄状態になる。
【００８５】
ＴＢ１の２段目のレコードは、子ノード“ａ”の孫ノード“ａａ”を表し、カラムＣＬ１には、終端フラグ「ｎｏ」が格納される。同レコードのカラムＣＬ２には、孫ノードのデータ要素値である“ａ”と、終端フラグ「ｙｅｓ」をカラムＣＬ１に格納するレコードへのオフセット値（枝）とが組み合わされて格納される。ＴＢ１の３段目以降には、終端フラグ「ｙｅｓ」をカラムＣＬ１に格納するレコードが連続して配置される。ＴＲ４では、終端するノードの数量は３つである。このため、配列形式のＴＢ１では、３段目以降に配置される、終端フラグ「ｙｅｓ」をカラムＣＬ１に格納するレコードの数量は「３」になる。
【００８６】
一方、リスト形式によるトライ木構造の実装は、ＴＢ２によって例示される。ＴＢ２に例示のように、リスト形式においても、トライ木構造のノードはレコードとして表される。レコードには、自ノードが終端を表すか否かの終端フラグを格納するカラムＣＬ５が含まれる。リスト形式のレコードにおいては、子ノードのノード情報を格納するカラムＣＬ６、兄弟関係にあるノードへの枝（オフセット値）を格納するカラムＣＬ７が含まれる。
【００８７】
リスト形式のレコードにおいて、カラムＣＬ５は、レコードの最先に配置され、同カラムに格納される終端フラグはカラムＣＬ１と同様である。また、カラムＣＬ６に格納される子ノードのノード情報は、ＴＢ１のカラムＣＬ２で説明したノード情報と同様である。カラムＣＬ７には、兄弟関係にあるノードへのオフセット値が枝として格納される。なお、カラムＣＬ６においては、データ要素値を有し、且つ、終端するノードを表すため、配列形式と同様に、終端フラグ「ｙｅｓ」をカラムＣＬ５に格納したレコードへのオフセット値がデータ要素値と組合せて格納される。終端フラグ「ｙｅｓ」をカラムＣＬ５に格納するレコードにおいては、他のカラムは空欄状態になる。
【００８８】
ＴＢ２においては、一段目のレコードから３段目のレコードが、ＴＲ４において兄弟関係となるノード“ａ”、“ｂ”、“ｃ”を表し、４段目のレコードが孫ノードを表す。配
列形式のＴＢ２では、５段目以降に、終端フラグ「ｙｅｓ」をカラムＣＬ１に格納する３つのレコードが配置される。
【００８９】
次に、図１１−図１５を参照し、前処理サーバ１０の追加データ作成処理を説明する。図１１に、既存インデックスの説明図を例示する。図１１において、Ｚ６は、例えば、データベースサーバ２０の備えるデータベース２１０に蓄積されたデータを表す。データベース２１０に蓄積されたデータはテーブル形式で表され、例えば、「ｉｄ」、「商品名」、「個数」といったカラムを有する商品名毎のレコードとして格納されている。入力データＤ４を受け付けた時点のデータベース２１０には、商品名“ｇｒｅｅｎ”、“ｇｏｌｄ”といった製品が格納されているものとする。
【００９０】
Ｚ６についての、商品名を対象としたインデックスの木構造は、ＴＲ７に示される。ＴＲ７に示すように、Ｚ６に示す商品名“ｇｒｅｅｎ”、“ｇｏｌｄ”の各文字が、枝Ｒ１９−Ｒ２６で結ばれた木構造として表される。ＴＲ７においては、例えば、根ノード→枝Ｒ２３→ノード“ｇ”→枝Ｒ２４→ノード“ｒ”→枝Ｒ２５→ノード“ｅ”→枝Ｒ２６→ノード“ｅ”→枝Ｒ２７→ノード“ｎ”の順に商品名“ｇｒｅｅｎ”のインデックスが表される。また、根ノード→枝Ｒ２３→ノード“ｇ”→枝Ｒ２８→ノード“ｏ”→枝Ｒ２９→ノード“ｌ”→枝Ｒ３０→ノード“ｄ”の順に商品名“ｇｏｌｄ”のインデックスが表される。前処理サーバ１０は、Ｚ６に示すデータをデータベース１１０に保持し、ＴＲ７に示す木構造のインデックスが既存インデックスとして保持しているものとする。
【００９１】
図１２は、入力データＤ４についてのインデックスの説明図を示す。入力データＤ４は、例えば、ＣＳＶで記述されたテキストデータである。入力データＤ４には、商品名“ｇｒａｙ”、“ｒｅｄ”といった製品のデータが含まれているものとする。入力データＤ４についての、商品名を対象としたインデックスの木構造は、ＴＲ８に示される。ＴＲ８においては、例えば、根ノード→枝Ｒ３１→ノード“ｇ”→枝Ｒ３２→ノード“ｒ”→枝Ｒ３３→ノード“ａ”→枝Ｒ３４→ノード“ｙ”の順に商品名“ｇｒａｙ”のインデックスが表される。また、根ノード→枝Ｒ３５→ノード“ｒ”→枝Ｒ３６→ノード“ｅ”→枝Ｒ３７→ノード“ｄ”の順に商品名“ｒｅｄ”のインデックスが表される。
【００９２】
図１３は、更新後のインデックスの説明図を示す。Ｚ７は、入力データＤ４がデータベース２１０に格納された状態のデータを表す。Ｚ７に示すように、データベース２１０においては、入力データＤ４の商品名に対応するレコードが追加されている。Ｚ７についての、商品名を対象としたインデックスの木構造は、ＴＲ９に示される。
【００９３】
ＴＲ９に示すように、更新後のインデックスにおいては、商品名“ｇｒａｙ”のノード“ａ”、“ｙ”は、商品名“ｇｒｅｅｎ”のノード“ｒ”に枝Ｒ３８によって結び付けられて、新規の部分木ＴＲ１０になる。同様にして、商品名“ｒｅｄ”は、枝Ｒ４０によって根ノードに結び付けられて、新規の部分木ＴＲ１１になる。
【００９４】
本実施形態の前処理サーバ１０は、ＴＲ９に示す部分木ＴＲ１０，ＴＲ１１を、既存インデックスＴＲ７と重複しない新規ノードのブロックとなるように、追加インデックスを作成する。ＴＲ１０、ＴＲ１１においては、新規ノードが連続するため追加インデックス作成時の枝が使用できる。更新後のインデックスＴＲ９においては、例えば、枝Ｒ３４を枝Ｒ３９とする書換えは生じない。また、ＴＲ１０においても、枝Ｒ３６を枝Ｒ４１，枝Ｒ３７を枝Ｒ４２とする書換えは生じない。
【００９５】
更新後のインデックスを作成するデータベースサーバ２０においては、既存インデックスと追加インデックスとを対象にする走査処理において、追加インデックスに新規ノードが出現した時点で走査処理が終了できる。このため、データベースサーバ２０においては
、走査処理の負担が軽減される。次に、本実施形態の前処理サーバ１０の追加データ作成処理において作成される追加インデックスのファイルを説明する。
【００９６】
図１４に、追加インデックスのファイルの説明図を例示する。図１４において、Ｄ６は、前処理サーバ１０で作成された追加インデックスのファイルを表す。ファイルＤ６のサイズＤ１１は、予め定められた一定のサイズである。Ｄ９はファイルＤ６の先端を表し、Ｄ１０はファイルＤ６の後端を表す。ファイルＤ６の後端に位置するノード領域には、追加インデックスの根ノードが配置される。
【００９７】
追加データ作成処理においては、インデックスの作成対象になるデータの既存インデックスに重複する既存ノードは、ファイルＤ６の後端側のノード領域から配置される。また、上記データの既存インデックスに重複しない新規ノードは、ファイルＤ６の先端側のノード領域から配置される。既存ノードおよび新規ノードは、例えば、インデックスの作成対象になるデータにおいて出現順に配置される。
【００９８】
追加データ作成処理においては、入力データＤ４について作成された追加インデックスのファイルＤ６が、追加データＤ５としてデータベースサーバ２０に送信される。なお、追加データＤ５は、新規ノードの配置されたブロックの領域サイズ（例えば、先端Ｄ９からのバイト数）Ｄ７を含む。また、追加データＤ５は、ファイルＤ６のサイズＤ１１を含む。次に、追加データ作成処理を説明する。
【００９９】
図１５に、追加データ作成処理の説明図を例示する。図１５において、ＴＲ７は、図１１を用いて説明した既存インデックスを表す。ＴＲ７には、文字列“ｇｒｅｅｎ”、“ｇｏｌｄ”となる各文字が既存ノードとして配置される。一方、前処理サーバ１０に入力される入力データＤ４には、インデックスの生成対象となる文字列“ｇｒａｙ”、“ｒｅｄ”が含まれる。
【０１００】
追加データ作成処理において、前処理サーバ１０は、既存インデックスの既存ノードと、入力データＤ４のインデックスの生成対象となる文字列を用いて、追加インデックスＴＦ７を作成する。
【０１０１】
前処理サーバ１０は、例えば、入力データＤ４から文字列“ｇｒａｙ”を追加データ作成処理の対象データとして取得する。前処理サーバ１０は、対象データの文字列の先頭文字と既存インデックスの根ノードの子ノードとを照合する。前処理サーバ１０は、照合の結果、上記先頭文字が、既存インデックスの根ノードの子ノードとして存在する場合には、上記先頭文字を追加インデックスＴＦ７の後端側のノード領域に配置する。既存インデックスの根ノードの子ノードはノード“ｇ”であり、対象データの先頭文字は“ｇ”である。このため、前処理サーバ１０は、対象データの先頭文字“ｇ”を追加インデックスＴＦ７の後端側のノード領域に配置し、根ノードとの間の枝を追加する。
【０１０２】
前処理サーバ１０は、対象データの文字列の２番目の文字“ｒ”と、既存インデックスの上記ノード“ｇ”を親に持つ子ノード“ｒ”とを対象として上記処理を行う。上記文字“ｒ”は上記ノード“ｇ”を親に持つ子ノード“ｒ”に照合する。このため、文字“ｒ”は、追加インデックスＴＦ７の先頭文字“ｇ”が配置されたノード領域から先端側の次のノード領域に配置され、先頭文字“ｇ”との間の枝が追加される。
【０１０３】
次に、前処理サーバ１０は、対象データの文字列の３番目の文字“ａ”と、既存インデックスの上記ノード“ｒ”を親に持つ子ノード“ｅ”とを対象として照合を行う。照合の結果、上記文字“ａ”は上記ノード“ｒ”を親に持つ子ノード“ｅ”に照合しない。前処理サーバ１０は、既存インデックスの上記ノード“ｒ”に照合しない文字“ａ”を、追加
インデックスＴＦ７の先端側のノード領域に配置する。また、前処理サーバ１０は、文字“ｒ”から文字“ａ”への枝Ｒ３３を追加する。
【０１０４】
なお、前処理サーバ１０は、既存インデックスには、対象データの文字列の３番目の文字“ａ”以降の文字“ｙ”に照合するノードが出現しないことがわかる。このため、前処理サーバ１０は、上記文字“ａ”が既存インデックスのノードに照合しないことを検知した時点で、対象データの文字“ａ”以降の文字列を追加インデックスＴＦ７のノード領域に配置する。追加インデックスＴＦ７においては、文字“ｙ”は、文字“ａ”が配置されたノード領域から後端側の次のノード領域に配置され、文字“ａ”との間の枝が追加される。
【０１０５】
前処理サーバ１０は、文字列“ｇｒａｙ”を対象データとする処理を終了する。前処理サーバ１０は、次に、入力データＤ４に存在する文字列“ｒｅｄ”を対象データとして取得し、追加データ作成処理を継続する。前処理サーバ１０では、入力データＤ４に存在する全ての文字列に対して追加データ作成処理が行われる。
【０１０６】
文字列“ｒｅｄ”を対象とする追加データ作成処理においては、前処理サーバ１０は、例えば、先頭文字“ｒ”と既存インデックスの根ノードの子ノード“ｇ”とを照合する。照合の結果、先頭文字“ｒ”は上記子ノード“ｇ”に照合しない。前処理サーバ１０は、先頭文字“ｒ”を、追加インデックスＴＦ７の文字“ｙ”が配置されたノード領域から後端側の次のノード領域に配置し、根ノードとの間の枝Ｒ３５を追加する。
【０１０７】
前処理サーバ１０は、既存インデックスには、対象データの文字列“ｒｅｄ”の“ｒ”以降の文字列“ｅｄ”に照合するノードが出現しないことがわかる。このため、前処理サーバ１０は、上記文字“ｒ”が既存インデックスのノードに照合しないことを検知した時点で、対象データの文字“ｒ”以降の文字列“ｅｄ”を追加インデックスＴＦ７のノード領域に配置する。追加インデックスＴＦ７においては、文字“ｅ”は、文字“ｒ”が配置されたノード領域から後端側の次のノード領域に配置され、文字“ａ”との間の枝が追加される。また、文字“ｄ”は、文字“ｅ”が配置されたノード領域から後端側の次のノード領域に配置され、文字“ｅ”との間の枝が追加される。前処理サーバ１０は、文字列“ｒｅｄ”を対象データとする処理を終了する。
【０１０８】
入力データＤ４についての追加データ作成処理は完了し、追加インデックスＴＦ７が作成される。追加インデックスＴＦ７においては、図１３のＴＲ１０、ＴＲ１１に示す部分木がファイルの先端側のノード領域から連続して配置される。また、追加インデックスＴＦ７においては、既存インデックスと重複する既存ノードがファイルの先端側のノード領域に配置される。
【０１０９】
前処理サーバ１０は、作成した入力データＤ４についての追加インデックスＴＦ７を追加データＤ５としてデータベースサーバ２０に送信する。また、前処理サーバ１０は、追加インデックスＴＦ７に配置された部分木ＴＲ１０、ＴＲ１１の領域サイズＤ７、追加インデックスＴＦ７の全体のサイズＤ１１を追加データＤ５に含めデータベースサーバ２０に送信する。
【０１１０】
次に、図１５を用いて、データベースサーバ２０における追加データ統合処理を説明する。追加データ統合処理は、主にデータベースサーバ２０の追加データ統合処理部２０１で行われる。追加データ統合処理においては、前処理サーバ１０から送信された追加インデックスＴＦ７の部分木ＴＲ１０、ＴＲ１１のデータが複写される。追加インデックスＴＦ７に配置された部分木ＴＲ１０、ＴＲ１１の領域は、追加データＤ５に含まれる領域サイズＤ７から特定される。複写された部分木ＴＲ１０、ＴＲ１１のデータは、図１５のＺ
８に示すように、既存インデックスＴＲ７に結合される。
【０１１１】
データベースサーバ２０は、部分木ＴＲ１０、ＴＲ１１のデータが結合された既存インデックスと追加インデックスＴＦ７とを走査し、既存ノードから部分木ＴＲ１０、ＴＲ１１への枝の書換えを行う。例えば、ＴＦ７の枝Ｒ３３は枝Ｒ３８に、ＴＦ７の枝Ｒ３５は枝Ｒ４０に書き換えられる。データベースサーバ２０は、既存ノードから部分木ＴＲ１０、ＴＲ１１への枝の書換えが行われた時点で、上記走査を終了する。新規ノードが連続して配置される部分木では、複写によって、新規ノード間の相対位置関係が変化しないため、新規ノード間を結び付ける枝には変更が生じない。こため、部分木ＴＲ１０、ＴＲ１１においては、追加インデックスＴＦ７の枝が使用できる。データベースサーバ２０では、追加データ統合処理により、既存インデックスＴＲ７に入力データＤ４のインデックスを統合した更新後のインデックスＴＲ９が保持される。
【０１１２】
図１６は、前処理サーバ１０で行われる追加データ作成処理を示すフローチャートである。
【０１１３】
入力データＤ４の受信時に、前処理サーバ１０は、図１６に開示されたフローチャートの処理を開始する。前処理サーバ１０は、受信した入力データＤ４を主記憶部１２の所定の領域に記憶する。また、前処理サーバ１０は、データベース１１０の既存インデックスのファイルを取得する。取得した上記ファイルは、補助記憶部１３にデータベース１１０に記憶する。なお、図１６の処理は、入力データＤ４に含まれる、インデックスの作成対象となる全ての文字列について行われる。
【０１１４】
Ｓ１の処理においては、前処理サーバ１０は、取得した文字列についての処理変数ｉに“０”を代入する。また、前処理サーバ１０は、作業ファイルに展開された既存インデックスの根ノードのアドレスを処理変数ｎに代入する。前処理サーバ１０は、追加インデックスの根ノードのアドレスを処理変数ｓに代入する。
【０１１５】
前処理サーバ１０は、処理変数ｉが入力データＤ４の追加データの対象となる文字列のサイズ（文字数）に等しいか否かを判定する（Ｓ２）。前処理サーバ１０は、処理変数ｉが上記文字列のサイズに等しい場合には（Ｓ２，ｙｅｓ）、図１６に例示の処理を終了する。一方、前処理サーバ１０は、処理変数ｉが上記文字列のサイズに等しくない場合には（Ｓ２，ｎｏ）、Ｓ３の処理に移行する。
【０１１６】
Ｓ３の処理においては、前処理サーバ１０は、入力データＤ４の追加データの対象となる文字列のｉ番目の文字が処理変数ｎが示す既存インデックスのノードの子にあるか否かを判定する。前処理サーバ１０は、上記ｉ番目の文字がノードの子にない場合には（Ｓ３，ｎｏ）、Ｓ４の処理に移行する。一方、前処理サーバ１０は、上記ｉ番目の文字がノードの子にある場合には（Ｓ３，ｙｅｓ）、Ｓ５の処理に移行する。
【０１１７】
Ｓ４の処理においては、上記ｉ番目の文字は、入力データＤ４において新規に追加されたノードである。したがって、前処理サーバ１０は、処理変数ｎが示す既存インデックスのノードに、上記ｉ番目の文字をノードの子として追加する。また、前処理サーバ１０は、処理変数ｓが示す追加インデックスに、上記ｉ番目の文字を追加インデックスファイルの新規ノード領域に追加する。新規ノードの追加の際には、親ノードとの間の相対位置によるオフセットが枝として追加される。
【０１１８】
例えば、既存インデックスは、“ｇｒｅｅｎ”の各文字を既存ノードとして配置する場合を想定する。文字列“ｇｒａｙ”が処理の対象の場合には、文字“ａ”、“ｙ”は、Ｓ３（ｎｏ）−Ｓ４の処理により、新規ノードとして既存インデックスに追加される。また
、Ｓ３（ｎｏ）−Ｓ４の処理により、図１５を用いて説明したように、追加インデックスの新規ノードノード領域に文字“ａ”、“ｙ”に対応するノードが連続して配置される。文字“ａ”には同ファイルに配置された既存ノード“ｒ”との間の枝３３が追加され、文字“ｙ”には文字“ａ”との間の枝３４（図示せず）が追加される。前処理サーバ１０は、Ｓ４の処理後、Ｓ７の処理に移行する。
【０１１９】
Ｓ５の処理においては、前処理サーバ１０は、追加データの対象となる文字列のｉ番目の文字が、処理変数ｓが示す追加インデックスのノードの子にあるか否かを判定する。前処理サーバ１０は、上記ｉ番目の文字がノードの子にない場合には（Ｓ５，ｎｏ）、Ｓ６の処理に移行する。一方、前処理サーバ１０は、上記ｉ番目の文字がノードの子にある場合には（Ｓ５，ｙｅｓ）、Ｓ７の処理に移行する。
【０１２０】
Ｓ６の処理においては、前処理サーバ１０は、処理変数ｓが示す追加インデックスのノードの子として、上記文字列のｉ番目の文字に対応するノードを、追加インデックスファイルの既存ノード領域に追加する。新規ノードの追加の際には、親ノードとの間の相対位置によるオフセットが枝として追加される。
【０１２１】
例えば、既存インデックスは、“ｇｒｅｅｎ”の各文字を既存ノードとして配置する場合を想定する。また、文字列“ｇｒａｙ”が追加インデックスとして入力される場合を想定する。文字列“ｇｒａｙ”の文字“ｇ”、“ｒ”は、Ｓ５（ｎｏ）−Ｓ６の処理により、図１５を用いて説明したように、追加インデックスファイルの既存ノードを配置するノード領域に文字“ｇ”、“ｒ”に対応するノードが連続して配置される。文字“ｇ”には根ノードとの間の枝が追加され、文字“ｒ”には文字“ｇ”との間の枝が追加される。前処理サーバ１０は、Ｓ６の処理後、Ｓ７の処理に移行する。
【０１２２】
Ｓ７においては、前処理サーバ１０は、処理変数ｎに、追加データの対象となる文字列のｉ番目の文字に対応する処理変数ｎの子ノードを代入する。また、前処理サーバ１０は、処理変数ｓに、追加データの対象となる文字列のｉ番目の文字に対応する処理変数ｓの子ノードを代入する。そして、処理変数ｉにｉ＋１を代入し、インクリメントする。
【０１２３】
Ｓ７の処理後、前処理サーバ１０は、Ｓ２の処理に移行する。
【０１２４】
図１７は、追加データ作成処理時のファイルに配置されるノード状態の遷移を説明する説明図である。図１７において、ＴＦ８は作業ファイルを表し、ＴＦ９は追加インデックスファイルを表す。既存インデックスには、文字列“ｇｒｅｅｎ”の各文字が既存ノードとして配置されているとする。また、入力データＤ４には、追加インデックスの作成対象となる文字列“ｇｒａｙ”、“ｒｅｄ”が含まれるとする。
【０１２５】
図１７において、追加データ作成処理の開始時の状態がＺ９で示される。すなわち、作業ファイルＴＦ８は、文字列“ｇｒｅｅｎ”の各文字が既存ノードとして配置されている。また、追加インデックスファイルＴＦ９は、ノードが配置されていない状態である。
【０１２６】
文字列“ｇｒａｙ”を対象として追加データ作成処理を進め、既存インデックスのノードと重複する文字に対応するノードを追加インデックスに配置した状態がＺ１０に示される。作業ファイルＴＦ８にはノードの追加は行われないが、追加インデックスファイルＴＦ９の後端側（根ノード側）には、既存ノード“ｇ”、“ｒ”が追加される。
【０１２７】
Ｚ１０の状態から追加データ作成処理を進め、文字列“ｇｒａｙ”についての処理終了時の状態がＺ１１に示される。追加インデックスファイルＴＦ９の先端側には、新規ノード“ａ”、“ｙ”が追加される。また、作業ファイルＴＦ８には、ノード“ｎ”の配置位
置以降に、新規ノード“ａ”、“ｙ”が追加される。なお、追加インデックスファイルＴＦ９では、既存ノード“ｒ”と新規ノード“ａ”との間に枝Ｒ３３が追加される。
【０１２８】
図１８は、他の文字列について追加データ作成処理を継続した場合の、ファイルに配置されるノード状態の遷移を説明する説明図である。図１８において、文字列“ｇｒａｙ”の処理終了後、文字列“ｒｅｄ”についての追加データ作成処理の開始時の状態がＺ１２に示される。Ｚ１２に示される状態は、Ｚ１１と同様である。
【０１２９】
文字列“ｒｅｄ”を対象として追加データ作成処理を進め、既存インデックスのノードと重複する文字に対応するノードを追加インデックスに配置した状態がＺ１３に示される。文字列“ｒｅｄ”には、既存インデックスのノードと重複する文字は出現しないため、Ｚ１３に示される状態は、Ｚ１２と同様である。
【０１３０】
Ｚ１３の状態から追加データ作成処理を進め、文字列“ｒｅｄ”についての処理終了時の状態がＺ１４に示される。追加インデックスファイルＴＦ９の先端側には、ノード“ｙ”の配置位置以降に、新規ノード“ｒ”、“ｅ”、“ｄ”が追加される。また、作業ファイルＴＦ８には、ノード“ｙ”の配置位置以降に、新規ノード“ｒ”、“ｅ”、“ｄ”が追加される。なお、追加インデックスファイルＴＦ９では、根ノードと新規ノード“ｒ”との間に枝Ｒ３５が追加される。
【０１３１】
前処理サーバ１０は、追加インデックスファイルＴＦ９の先端側（根ノードの対向側）に新規ノード、末尾側（根ノードの配置側）に既存ノードを配置した。追加インデックスファイルＴＦ９において、例えば、根ノードの配置側を先頭側とし、根ノードの対向側を末尾側とするとしてもよい。追加インデックスファイルＴＦ９において、新規ノードの配置領域と、根ノードを含む既存ノードの配置領域が区分けされればよい。新規ノードの配置領域と、根ノードを含む既存ノードの配置領域を区分けすることで、データベースサーバ２０における新規ノードの複写領域を簡易に特定できる。
【０１３２】
次に、図１９に示したフローチャートを参照し、本実施形態の追加データ統合処理を説明する。
【０１３３】
データベースサーバ２０は、ＣＰＵ２１が補助記憶部２３に記憶されている各種プログラムや各種データを主記憶部２２に読み出して実行することで、図１９の処理を行う。
【０１３４】
図１９に示したフローチャートにおいて、データベースサーバ２０の処理は、追加データＤ５の受信から開始される。データベースサーバ２０は、追加データＤ５を受信し、受信した追加データＤ５を主記憶部２２の所定の領域に一時的に記憶する。また、データベースサーバ２０は、データベース２１０を参照し、既存インデックスのファイルを取得する。取得した上記ファイルは、主記憶部２２の所定の領域に確保された作業ファイルに格納される。
【０１３５】
Ｓ１１の処理においては、データベースサーバ２０は、追加データＤ５内の追加インデックスのファイルの新規ノードが連続して配置される領域を特定する。上記領域は、追加データＤ５に含まれる領域サイズＤ７に基づいて特定される。データベースサーバ２０は、上記領域を複写し、複写した上記領域を既存インデックスのファイルに追加する。上記領域は、既存インデックスの後端に配置された既存ノードの配置位置以降に追加される。
【０１３６】
図１８のＺ１４に示す追加インデックスファイルＴＦ９では、新規ノード“ａ”、“ｙ”、“ｒ”、“ｅ”、“ｄ”がファイルの先端側から連続して配置される。データベースサーバ２０は、連続して配置された上記新規ノードを、既存インデックスのファイルに追
加する。図１７のＺ９に示す作業ファイルＴＦ８を、既存インデックスのファイルと想定する。データベースサーバ２０は、連続して配置された上記新規ノードを複写し、作業ファイルＴＦ８の既存ノード“ｎ”が配置された配置位置以降に追加する。
【０１３７】
Ｓ１２の処理においては、データベースサーバ２０は、Ｓ１１の処理で新規ノードが追加されたファイルと追加インデックスのファイルとの間に共通する子が出現しなくなるまでノードの探索を行う。そして、データベースサーバ２０は、上記ファイル間に共通する子が出現しなくなった時点でＳ１３の処理を行う。
【０１３８】
データベースサーバ２０は、Ｓ１２の処理の対象ノードが既存インデックスのファイルに出現する子ノードに結び付けられる場合には（Ｓ１４，ｙｅｓ）、Ｓ１５に移行する。Ｓ１５の処理においては、データベースサーバ２０は、Ｓ１２で判定した子ノード以降は既存の部分木であるため、以降の部分木についての処理を終了する。一方、データベースサーバ２０は、Ｓ１２の処理の対象ノードが追加インデックスのファイルに出現する子ノードに結び付けられる場合には（Ｓ１４，ｎｏ）、Ｓ１６に移行する。Ｓ１６の処理においては、Ｓ１２で判定した子ノード以降の部分木への枝を追加する。
【０１３９】
図２０に、既存ノードと新規ノード間の枝の追加についての説明図を例示する。図２０において、Ｚ１５に示すＴＦ１０は、データベースサーバ２０の作業ファイルを表し、既存インデックスのファイルが含まれる。また、Ｚ１５に示すＴＦ９は、追加インデックスを表す。
【０１４０】
Ｓ１１の処理により、新規ノードが複写され、作業ファイルＴＦ１０に追加された状態がＺ１６に示される。ＴＦ１０では、既存ノードが“ｇ”、“ｒ”、“ｅ”、“ｅ”、“ｎ”の順に配置され、追加された新規ノードが“ａ”、“ｙ”、“ｒ”、“ｅ”、“ｄ”の順に配置されている。また、追加インデックスファイルＴＦ９では、既存ノードが“ｇ”、“ｒ”の順で根ノード側から配置され、新規ノードがファイルの先端側から“ａ”、“ｙ”、“ｒ”、“ｅ”、“ｄ”の順に配置されている。
【０１４１】
ＴＦ９、ＴＦ１０の走査方法を深さ優先探索とする。深さ優先探索では、Ｓ１２の処理により、ＴＦ１０においては、ノード“ｇ”、“ｒ”が共通する子ノードとして探索される。ＴＦ１０では、“ｒ”の子ノードは“ｅ”であり、ＴＦ９では“ｒ”の子ノードは“ａ”である。このため、図１８に例示のＳ１２の処理は、Ｓ１３の処理に進む。
【０１４２】
Ｓ１３の処理において、ＴＦ１０の既存の部分木については、Ｓ１４（ｎｏ）−Ｓ１５の処理が行われ、ノード“ｅ”以降の既存の部分木（“ｅ”、“ｅ”、“ｎ”）の処理が終了する。また、ＴＦ９については、“ｒ”の子ノード“ａ”およびノード“ａ”の子ノード“ｙ”は、既存インデックスに対して新規の部分木である。このため、ＴＦ１０においては、Ｓ１４（ｙｅｓ）−Ｓ１６の処理が行われ、既存ノード“ｒ”から結合された新規ノード“ａ”への枝Ｒ３８が追加される（Ｚ１７）。
【０１４３】
Ｓ１６の処理後、データベースサーバ２０では、根ノードに結び付く他の枝関係を対象としてＳ１２−Ｓ１３の処理が再帰的に行われる。ＴＦ１０の既存ノードの部分木では、根ノードに結び付くノード“ｇ”以外のノードは存在しない。一方、ＴＦ９の根ノードは、新規ノード“ｒ”への枝を持つ。このため、図１８に例示のＳ１２の処理はＳ１３の処理に進む。Ｓ１３の処理においては、Ｓ１４（ｙｅｓ）−Ｓ１６の処理が行われ、ＴＦ１０の根ノードから結合された新規ノード“ｒ”への枝Ｒ４０が追加される（Ｚ１７）。
【０１４４】
Ｚ１７に示すように、ＴＦ９の既存ノードと新規ノード間の枝に沿って、結合された新規の部分木への枝が書き換えられたＴＦ１０では、更新処理が完了する。更新完了後のＴ
Ｆ１０は、入力データＤ４が追加された後のデータベースに対応するインデックスになる。
【０１４５】
以上、説明したように、本実施形態に係る前処理サーバ１０は、インデックスデータの既存ノード情報に基づいて、インデックスの作成対象になる入力データから新規ノード情報を抽出することができる。前処理サーバ１０は、抽出した新規ノード情報を連続するように並べ替えて追加ツリーデータを生成することができる。前処理サーバ１０は、インデックスの生成対象になる入力データのノード間の相対関係に基づいて、並べ替えたノード間の相対関係を追加ツリーデータに書き込み、インデックスデータを管理するＤＢサーバに送信することができる。
【０１４６】
この結果、本実施形態に係るＤＢサーバは、追加ツリーデータの連続した新規ノード情報を自装置が管理するインデックスのツリーデータに追記し、既存ノードと新規ノードの相対関係を書き直すことで入力データ追加後のインデックスを再構築できる。ＤＢサーバ側の新規ノード間の相対関係を再構築する処理が省略できる。
【０１４７】
《コンピュータが読み取り可能な記録媒体》
コンピュータその他の機械、装置（以下、コンピュータ等）に上記何れかの機能を実現させるプログラムをコンピュータ等が読み取り可能な記録媒体に記録することができる。そして、コンピュータ等に、この記録媒体のプログラムを読み込ませて実行させることにより、その機能を提供させることができる。
【０１４８】
ここで、コンピュータ等が読み取り可能な記録媒体とは、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータ等から読み取ることができる記録媒体をいう。このような記録媒体のうちコンピュータ等から取り外し可能なものとしては、例えばフレキシブルディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ／Ｗ、ＤＶＤ、ブルーレイディスク、ＤＡＴ、８ｍｍテープ、フラッシュメモリなどのメモリカード等がある。また、コンピュータ等に固定された記録媒体としてハードディスクやＲＯＭ等がある。
【符号の説明】
【０１４９】
１  分散システム
１０  データ生成サーバ（前処理サーバ）
１１、２１  ＣＰＵ
１２、２２  主記憶部
１３、２３  補助記憶部
１４、２４  入力部
１５、２５  出力部
１６、２６  通信部
２０  データベースサーバ（ＤＢサーバ）
３０、５０  データベースサーバ
４０  データ生成サーバ
１０１  追加データ作成処理部
１１０、２１０  データベース
２０１  追加データ統合処理部
Ｂ１、Ｂ２  接続バス
【図１】
2018045286.tif 000003
【図２】
2018045286.tif 000004
【図３】
2018045286.tif 000005
【図４】
2018045286.tif 000006
【図５】
2018045286.tif 000007
【図６】
2018045286.tif 000008
【図７】
2018045286.tif 000009
【図８】
2018045286.tif 000010
【図９】
2018045286.tif 000011
【図１０】
2018045286.tif 000012
【図１１】
2018045286.tif 000013
【図１２】
2018045286.tif 000014
【図１３】
2018045286.tif 000015
【図１４】
2018045286.tif 000016
【図１５】
2018045286.tif 000017
【図１６】
2018045286.tif 000018
【図１７】
2018045286.tif 000019
【図１８】
2018045286.tif 000020
【図１９】
2018045286.tif 000021
【図２０】
2018045286.tif 000022