(57)【要約】【課題】本発明は、ノードの木構造の全体が必要とするメモリ領域を低減することを目的とする。【解決手段】本発明のデータ索引装置Ｉは、複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶しているデータ集合１１と、木構造のインナーノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲を記載されている索引範囲表１２であって、木構造のインナーノードに対する複数の各子ノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲及び記載行番号を対応付けて記載されている索引範囲表１２と、木構造のルートノードについての索引範囲表１２における複数の各属性及び記載行番号の対応関係を記載されている行番号管理表１３と、を備える。【選択図】図３
2014041438.tif 000002
【特許請求の範囲】
【請求項１】
複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶しているデータ集合記憶部と、
前記木構造のインナーノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲を記載されている索引範囲表であって、前記木構造のインナーノードに対する複数の各子ノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲及び記載行番号を対応付けて記載されている索引範囲表を記憶している索引範囲表記憶部と、
前記木構造のルートノードについての前記索引範囲表における複数の各属性及び記載行番号の対応関係を記載されている行番号管理表を記憶している行番号管理表記憶部と、
を備えることを特徴とするデータ索引装置。
【請求項２】
前記データ集合記憶部が記憶しているデータの集合について、検索対象属性の情報及び検索対象範囲の情報を取得する検索対象情報取得部と、
前記検索対象情報取得部が取得した検索対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するルートノード検索対象選択部と、
前記検索対象情報取得部が取得した検索対象属性の情報及び検索対象範囲の情報、並びに前記ルートノード検索対象選択部あるいは自己が選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、検索対象属性及び検索対象範囲を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するインナーノード検索対象選択部と、
前記インナーノード検索対象選択部が選択した当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記検索対象情報取得部が取得した検索対象属性の情報及び検索対象範囲の情報に基づくデータの検索を実行するデータ検索実行部と、
をさらに備えることを特徴とする請求項１に記載のデータ索引装置。
【請求項３】
前記データ集合記憶部が記憶しているデータの集合について、挿入対象属性の情報及び挿入対象値の情報を取得する挿入対象情報取得部と、
前記挿入対象情報取得部が取得した挿入対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するルートノード挿入対象選択部と、
前記挿入対象情報取得部が取得した挿入対象属性の情報及び挿入対象値の情報、並びに前記ルートノード挿入対象選択部が選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、挿入対象属性及び挿入対象値を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するインナーノード挿入対象選択部と、
前記インナーノード挿入対象選択部が選択した当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記挿入対象情報取得部が取得した挿入対象属性の情報及び挿入対象値の情報に基づくデータの挿入を実行するデータ挿入実行部と、
をさらに備えることを特徴とする請求項１又は２に記載のデータ索引装置。
【請求項４】
複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶し、
前記木構造のインナーノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲を記載されている索引範囲表であって、前記木構造のインナーノードに対する複数の各子ノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲及び記載行番号を対応付けて記載されている索引範囲表を記憶し、
前記木構造のルートノードについての前記索引範囲表における複数の各属性及び記載行番号の対応関係を記載されている行番号管理表を記憶するデータ構造記憶ステップ、
を備えることを特徴とするデータ索引方法。
【請求項５】
記憶しているデータの集合について、検索対象属性の情報及び検索対象範囲の情報を取得する検索対象情報取得ステップと、
前記検索対象情報取得ステップで取得した検索対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するルートノード検索対象選択ステップと、
前記検索対象情報取得ステップで取得した検索対象属性の情報及び検索対象範囲の情報、並びに前記ルートノード検索対象選択ステップで選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、検索対象属性及び検索対象範囲を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するインナーノード検索対象選択ステップと、
前記インナーノード検索対象選択ステップで選択した当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記検索対象情報取得ステップで取得した検索対象属性の情報及び検索対象範囲の情報に基づくデータの検索を実行するデータ検索実行ステップと、
を前記データ構造記憶ステップの後に順に備えることを特徴とする請求項４に記載のデータ索引方法。
【請求項６】
記憶しているデータの集合について、挿入対象属性の情報及び挿入対象値の情報を取得する挿入対象情報取得ステップと、
前記挿入対象情報取得ステップで取得した挿入対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するルートノード挿入対象選択ステップと、
前記挿入対象情報取得ステップで取得した挿入対象属性の情報及び挿入対象値の情報、並びに前記ルートノード挿入対象選択ステップで選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、挿入対象属性及び挿入対象値を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するインナーノード挿入対象選択ステップと、
前記インナーノード挿入対象選択ステップで選択した当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記挿入対象情報取得ステップで取得した挿入対象属性の情報及び挿入対象値の情報に基づくデータの挿入を実行するデータ挿入実行ステップと、
を前記データ構造記憶ステップの後に順に備えることを特徴とする請求項４又は請求項５に記載のデータ索引方法。
【請求項７】
コンピュータに対して、請求項４から請求項６のいずれかに記載の前記データ構造記憶ステップを実行させることを特徴とするデータ索引プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶しているうえで、データの集合に対してデータの検索やデータの挿入を実行する装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、データベース技術分野において、検索を高速化するための技術として、Ｂ−ＴｒｅｅやＲ−Ｔｒｅｅなど、木構造をもつ多くの索引技術があった。
【０００３】
Ｂ−Ｔｒｅｅは、１種類の属性に対する属性値（リレーショナルデータベースで言えば、ある１つのカラムに入る値）の集合に対して、索引付けができる技術である。Ｒ−Ｔｒｅｅは、複数種類の属性に対する属性値の集合に対して、索引付けができる索引である。
【０００４】
一方、センサの計測データの情報すなわちセンサ情報など、多様な属性及び属性値の組（ｋｅｙ−ｖａｌｕｅ  ｐａｉｒとも呼ばれる）を１つ以上含むデータに対する索引技術として、ＵＢＩ−Ｔｒｅｅ（非特許文献１）があった。
【０００５】
ＵＢＩ−Ｔｒｅｅも木構造をもつ索引技術であるが、Ｂ−ＴｒｅｅやＲ−Ｔｒｅｅとは異なり、多様なデータの集合、すなわち、各データが含む属性の数や種類が異なるデータの集合に対しても、効率的に索引付けができるという特徴がある。
【０００６】
ＵＢＩ−Ｔｒｅｅでは、例えば、「センサＩＤ＝１、時間＝３、温度＝２０」のように、センサＩＤ、時間及び温度という３つの属性を含むデータと、「センサＩＤ＝３、時間＝７、照度＝６、音量＝４」のように、センサＩＤ、時間、照度及び音量という４つの属性を含むデータを、１つの索引に効率的に索引付けすることができる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】荒川豊、中村隆幸、中村元紀、松尾真人、「ユビキタスデータのためのインデキシング技術ＵＢＩ−ｔｒｅｅの改良」、電子情報通信学会  データ工学研究会技術報告、信学技報、ｖｏｌ．１１０、ｎｏ．１６２、ＤＥ２０１０−２２、ｐｐ．４７−５２、２０１０年８月．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来技術の行番号管理表を図１に示し、従来技術の木構造を図２に示す。木構造は、上位のルートノードＲ及び下位のリーフノードＬ１、Ｌ２から構成される。上位のルートノードＲは、データ１１−１、１１−２、１１−３、１１−４を管理している。下位のリーフノードＬ１は、データ１１−１、１１−２を管理しており、下位のリーフノードＬ２は、データ１１−３、１１−４を管理している。
【０００９】
ルートノード索引範囲表１２Ｒは、リーフノードＬ１、Ｌ２における、各属性に対する属性値の分布範囲を記載されている。リーフノード索引範囲表１２Ｌ１は、リーフノードＬ１における、各属性に対する属性値を、各データ１１−１、１１−２について記載されている。リーフノード索引範囲表１２Ｌ２は、リーフノードＬ２における、各属性に対する属性値を、各データ１１−３、１１−４について記載されている。
【００１０】
行番号管理表１３Ｃは、ルートノード索引範囲表１２Ｒ及びリーフノード索引範囲表１２Ｌ１、１２Ｌ２に共通して、各属性及び行番号の対応関係を記載されている。属性「センサＩＤ」、「時間」、「温度」、「照度」及び「音量」に対して、それぞれ、行番号「１」、「２」、「３」、「４」及び「５」が対応付けられている。
【００１１】
リーフノードＬ１は、属性「照度」及び「音量」に対する属性値のデータを管理していない。リーフノードＬ２は、属性「温度」に対する属性値のデータを管理していない。
【００１２】
ルートノード索引範囲表１２Ｒは、リーフノードＬ１における、属性「照度」（４行目）及び「音量」（５行目）について、「−」を記載されており、リーフノードＬ２における、属性「温度」（３行目）について、「−」を記載されている。
【００１３】
リーフノード索引範囲表１２Ｌ１は、属性「照度」（４行目）及び「音量」（５行目）について、「−」を記載されている。リーフノード索引範囲表１２Ｌ２は、属性「温度」（３行目）について、「−」を記載されている。
【００１４】
このように、従来技術のＵＢＩ−Ｔｒｅｅでは、多様なデータの集合に対しても、１つの索引に効率的に索引付けすることができる。しかし、従来技術のＵＢＩ−Ｔｒｅｅでは、多様なデータの集合においては、属性の種類数が多くなり、メモリ領域を多く必要とする。このため、従来技術のＵＢＩ−Ｔｒｅｅの全体が必要とするメモリ領域が増大してしまうという問題があった。
【００１５】
そこで、前記課題を解決するために、本発明は、複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶している索引技術において、ノードの木構造の全体が必要とするメモリ領域を低減することを目的とする。
【課題を解決するための手段】
【００１６】
上記目的を達成するために、索引範囲表において、木構造のインナーノード（図２のルートノードＲ）に対する複数の各子ノード（図２のリーフノードＬ１、Ｌ２）において管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲及び記載行番号を対応付けて記憶する。そして、行番号管理表において、ルートノードについての索引範囲表における複数の各属性及び記載行番号の対応関係を記憶する。
【００１７】
具体的には、本発明は、複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶しているデータ集合記憶部と、前記木構造のインナーノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲を記載されている索引範囲表であって、前記木構造のインナーノードに対する複数の各子ノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲及び記載行番号を対応付けて記載されている索引範囲表を記憶している索引範囲表記憶部と、前記木構造のルートノードについての前記索引範囲表における複数の各属性及び記載行番号の対応関係を記載されている行番号管理表を記憶している行番号管理表記憶部と、を備えることを特徴とするデータ索引装置である。
【００１８】
また、本発明は、複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶し、前記木構造のインナーノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲を記載されている索引範囲表であって、前記木構造のインナーノードに対する複数の各子ノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲及び記載行番号を対応付けて記載されている索引範囲表を記憶し、前記木構造のルートノードについての前記索引範囲表における複数の各属性及び記載行番号の対応関係を記載されている行番号管理表を記憶するデータ構造記憶ステップ、を備えることを特徴とするデータ索引方法である。
【００１９】
また、本発明は、コンピュータに対して、前記データ構造記憶ステップを実行させることを特徴とするデータ索引プログラムである。
【００２０】
この構成によれば、ノードの木構造の全体で共通して、各属性及び行番号を対応付ける必要がなくなる。よって、インナーノードにおいて或る属性に対する属性値のデータが管理されているが、子ノードにおいて当該属性に対する属性値のデータが管理されていないとき、子ノードの索引範囲表において当該属性に対応する行を省略することができる。
【００２１】
ここで、子ノードの索引範囲表において当該属性に対応する行を省略すれば、後続の行に対応する属性について、インナーノードの索引範囲表及び子ノードの索引範囲表において、異なる行番号が設定される。しかし、子ノードの索引範囲表における各属性及び行番号の対応関係が、インナーノードの索引範囲表において記載されている。よって、木構造を上位から下位へと辿るにあたり、子ノードの索引範囲表においてどの行にどの属性の情報が記載されているか、インナーノードの索引範囲表において正しく読み取ることができる。
【００２２】
つまり、属性の種類数が多くなる多様なデータの集合であり、かつ個々のデータの属性数が少ない場合においては、このような行の省略を大量に行うことが可能となり、特にリーフノードに近づくにつれて、各ノードの索引範囲表が必要とするメモリ領域を低減することが可能となる。
【００２３】
ここで、子ノードの索引範囲表における各属性及び行番号の対応関係が、インナーノードの索引範囲表において従来技術と比較してオーバーヘッドとなる。しかし、属性の種類数が多くなる多様なデータの集合であり、かつ個々のデータの属性数が少ない場合においては、行の省略によるメモリ領域の低減の効果が、オーバーヘッドによるメモリ領域の増大の効果を上回る。よって、ノードの木構造の全体が必要とするメモリ領域を低減することが可能となる。
【００２４】
また、本発明は、前記データ集合記憶部が記憶しているデータの集合について、検索対象属性の情報及び検索対象範囲の情報を取得する検索対象情報取得部と、前記検索対象情報取得部が取得した検索対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するルートノード検索対象選択部と、前記検索対象情報取得部が取得した検索対象属性の情報及び検索対象範囲の情報、並びに前記ルートノード検索対象選択部あるいは自己が選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、検索対象属性及び検索対象範囲を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するインナーノード検索対象選択部と、前記インナーノード検索対象選択部が選択した当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記検索対象情報取得部が取得した検索対象属性の情報及び検索対象範囲の情報に基づくデータの検索を実行するデータ検索実行部と、をさらに備えることを特徴とするデータ索引装置である。
【００２５】
また、本発明は、記憶しているデータの集合について、検索対象属性の情報及び検索対象範囲の情報を取得する検索対象情報取得ステップと、前記検索対象情報取得ステップで取得した検索対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するルートノード検索対象選択ステップと、前記検索対象情報取得ステップで取得した検索対象属性の情報及び検索対象範囲の情報、並びに前記ルートノード検索対象選択ステップで選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、検索対象属性及び検索対象範囲を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号を選択するインナーノード検索対象選択ステップと、前記インナーノード検索対象選択ステップで選択した当該インナーノードについての前記索引範囲表における検索対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記検索対象情報取得ステップで取得した検索対象属性の情報及び検索対象範囲の情報に基づくデータの検索を実行するデータ検索実行ステップと、を前記データ構造記憶ステップの後に順に備えることを特徴とするデータ索引方法である。
【００２６】
この構成によれば、子ノードの索引範囲表において行の省略を大量に行ったとしても、データの検索を正しく実行することが可能となる。
【００２７】
また、本発明は、前記データ集合記憶部が記憶しているデータの集合について、挿入対象属性の情報及び挿入対象値の情報を取得する挿入対象情報取得部と、前記挿入対象情報取得部が取得した挿入対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するルートノード挿入対象選択部と、前記挿入対象情報取得部が取得した挿入対象属性の情報及び挿入対象値の情報、並びに前記ルートノード挿入対象選択部が選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、挿入対象属性及び挿入対象値を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するインナーノード挿入対象選択部と、前記インナーノード挿入対象選択部が選択した当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記挿入対象情報取得部が取得した挿入対象属性の情報及び挿入対象値の情報に基づくデータの挿入を実行するデータ挿入実行部と、をさらに備えることを特徴とするデータ索引装置である。
【００２８】
また、本発明は、記憶しているデータの集合について、挿入対象属性の情報及び挿入対象値の情報を取得する挿入対象情報取得ステップと、前記挿入対象情報取得ステップで取得した挿入対象属性の情報、及び前記行番号管理表に基づいて、前記木構造のルートノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するルートノード挿入対象選択ステップと、前記挿入対象情報取得ステップで取得した挿入対象属性の情報及び挿入対象値の情報、並びに前記ルートノード挿入対象選択ステップで選択した前記木構造のルートノードを含むインナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、挿入対象属性及び挿入対象値を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号を選択するインナーノード挿入対象選択ステップと、前記インナーノード挿入対象選択ステップで選択した当該インナーノードについての前記索引範囲表における挿入対象属性に対応する記載行番号に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、前記挿入対象情報取得ステップで取得した挿入対象属性の情報及び挿入対象値の情報に基づくデータの挿入を実行するデータ挿入実行ステップと、を前記データ構造記憶ステップの後に順に備えることを特徴とするデータ索引方法である。
【００２９】
この構成によれば、子ノードの索引範囲表において行の省略を大量に行ったとしても、データの挿入を正しく実行することが可能となる。
【発明の効果】
【００３０】
本発明は、複数の属性のうちいずれかの属性に対する属性値を含むデータの集合を、ノードの木構造を用いて記憶している索引技術において、ノードの木構造の全体が必要とするメモリ領域を低減することができる。
【図面の簡単な説明】
【００３１】
【図１】従来技術の行番号管理表を示す図である。
【図２】従来技術の木構造を示す図である。
【図３】本発明のデータ索引装置の構成を示す図である。
【図４】本発明の行番号管理表を示す図である。
【図５】本発明の木構造を示す図である。
【図６】本発明のデータ検索処理における木構造を示す図である。
【図７】本発明のデータ検索処理のフローチャートである。
【図８】本発明のデータ挿入処理における木構造を示す図である。
【図９】本発明のデータ挿入処理のフローチャートである。
【発明を実施するための形態】
【００３２】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施の例であり、本発明は以下の実施形態に制限されるものではない。
【００３３】
（データ索引構成）
本発明のデータ索引装置の構成を図３に示す。データ索引装置Ｉは、ネットワークＮに接続され、木構造記憶部１、ネットワーク通信部２、データ検索部３及びデータ挿入部４から構成される。まず、木構造記憶部１を用いた、データ索引構成について説明する。次に、ネットワーク通信部２の後述の検索対象情報取得部２１及びデータ検索部３を用いた、データ検索処理について説明する。次に、ネットワーク通信部２の後述の挿入対象情報取得部２２及びデータ挿入部４を用いた、データ挿入処理について説明する。
【００３４】
木構造記憶部１は、データ集合１１、索引範囲表１２及び行番号管理表１３を記憶している。
【００３５】
データ集合１１は、ノードの木構造を用いて記憶されている、複数の属性のうちいずれかの属性に対する属性値を含むデータの集合である。データ集合１１は、図５に後述のデータ１１−１、１１−２、１１−３、１１−４に対応している。
【００３６】
索引範囲表１２は、木構造のインナーノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲を記載されている。インナーノードは、図５に後述のルートノードＲに対応している。索引範囲表１２は、図５に後述のルートノード索引範囲表１２Ｒに対応している。
【００３７】
そして、索引範囲表１２は、木構造のインナーノードに対する複数の各子ノードにおいて管理されているデータの集合に含まれる各属性に対する属性値についての分布範囲及び記載行番号を対応付けて記載されている。
【００３８】
行番号管理表１３は、ルートノードＲについての索引範囲表１２における複数の各属性及び記載行番号の対応関係を記載されている。行番号管理表１３は、図４に後述の行番号管理表１３Ｒに対応している。
【００３９】
本発明の行番号管理表を図４に示し、本発明の木構造を図５に示す。木構造は、上位のルートノードＲ及び下位のリーフノードＬ１、Ｌ２から構成される。上位のルートノードＲは、データ１１−１、１１−２、１１−３、１１−４を管理している。下位のリーフノードＬ１は、データ１１−１、１１−２を管理しており、下位のリーフノードＬ２は、データ１１−３、１１−４を管理している。
【００４０】
ノードとは、木構造を構成する節に相当し、図５では四角形で表現されている。ノードには、ルートノード、リーフノード及びインナーノードの３種がある。木構造において、最も上位に位置するのがルートノードであり、最も下位に位置するのがリーフノードであり、リーフノード以外のノードはインナーノードと呼ばれる。図５では、ルートノードＲは、インナーノードでもあり、リーフノードＬ１、Ｌ２を子ノードとして保持する。
【００４１】
図５では、簡単のため、高さが２の木構造を示したが、より高い階層をもつ木構造でもよく、また逆に高さが１である木構造でもよい。高さが１である木構造の場合、ノードは１つしか存在せず、当該ノードはルートノードでありかつリーフノードである。図５では、簡単のため、各インナーノードが保持する子ノードの数を２としたが、各インナーノードがより多くの子ノードを保持する木構造でもよい。
【００４２】
データ１１−１、１１−２、１１−３、１１−４は、センサ情報である。データ１１−１は、「センサＩＤ」、「時間」及び「温度」の３つの属性をもち、その属性値としてそれぞれ「１」、「３」及び「２０．３」をもつ。データ１１−２は、「センサＩＤ」、「時間」及び「温度」の３つの属性をもち、その属性値としてそれぞれ「２」、「４」及び「２１．１」をもつ。データ１１−３は、「センサＩＤ」、「時間」、「照度」及び「音量」の４つの属性をもち、その属性値としてそれぞれ「３」、「７」、「６」及び「４」をもつ。データ１１−４は、「センサＩＤ」、「時間」、「照度」及び「音量」の４つの属性をもち、その属性値としてそれぞれ「４」、「９」、「１１」及び「５」をもつ。
【００４３】
このように、各センサ情報は、１つ以上の属性及び属性値の組をもつ。そして、属性の数や種類は、各センサ情報間で異なり得る。なお、本発明のいうセンサ情報は、温度や湿度、電流値や電圧値、流体の流量、物質の濃度、明度、騒音、位置、加速度などを含むセンサデバイスが計測した情報であってもよい。または、センサ以外の例えばＷｅｂやインターネットを経由して取得した情報であってもよい。さらに、センサの特性や状態、計測日時などを示すメタデータを含む情報であってもよい。
【００４４】
ルートノード索引範囲表１２Ｒは、リーフノードＬ１、Ｌ２における、各属性に対する属性値の分布範囲及び行番号を、対応付けて記載されている。本発明では、従来技術と異なり、ルートノード索引範囲表１２Ｒは、リーフノードＬ１、Ｌ２における、各属性に対する行番号を記載されている。リーフノード索引範囲表１２Ｌ１は、リーフノードＬ１における、各属性に対する属性値を、各データ１１−１、１１−２について記載されている。リーフノード索引範囲表１２Ｌ２は、リーフノードＬ２における、各属性に対する属性値を、各データ１１−３、１１−４について記載されている。図５では、簡単のため、各リーフノード（Ｌ１、Ｌ２）が保持するデータ（１１−１、１１−２、１１−３、１１−４）の数を２としたが、各リーフノードがより多くのデータを保持する木構造でもよい。
【００４５】
行番号管理表１３Ｒは、ルートノード索引範囲表１２Ｒにおける、各属性及び行番号の対応関係を記載されている。属性「センサＩＤ」、「時間」、「温度」、「照度」及び「音量」に対して、それぞれ、行番号「１」、「２」、「３」、「４」及び「５」が対応付けられている。本発明では、従来技術と異なり、行番号管理表１３Ｒ及びリーフノード索引範囲表１２Ｌ１、１２Ｌ２において、各属性に対する行番号は必ずしも一致せず、行番号管理表１３Ｒは、リーフノード索引範囲表１２Ｌ１、１２Ｌ２における、各属性及び行番号の対応関係を記載されていない。
【００４６】
リーフノードＬ１は、属性「照度」及び「音量」に対する属性値のデータを管理していない。リーフノードＬ２は、属性「温度」に対する属性値のデータを管理していない。
【００４７】
ルートノード索引範囲表１２Ｒにおけるリーフノード索引範囲表１２Ｌ１に関する記載内容について説明する。属性「センサＩＤ」（行番号管理表１３Ｒに基づく１行目）について、範囲「１〜２」及び行番号「１」を記載されている。属性「時間」（行番号管理表１３Ｒに基づく２行目）について、範囲「３〜４」及び行番号「２」を記載されている。属性「温度」（行番号管理表１３Ｒに基づく３行目）について、範囲「２０．３〜２１．１」及び行番号「３」を記載されている。属性「照度」（行番号管理表１３Ｒに基づく４行目）について、範囲「−」及び行番号「−」を記載されている。属性「音量」（行番号管理表１３Ｒに基づく５行目）について、範囲「−」及び行番号「−」を記載されている。
【００４８】
ルートノード索引範囲表１２Ｒにおけるリーフノード索引範囲表１２Ｌ２に関する記載内容について説明する。属性「センサＩＤ」（行番号管理表１３Ｒに基づく１行目）について、範囲「３〜４」及び行番号「１」を記載されている。属性「時間」（行番号管理表１３Ｒに基づく２行目）について、範囲「７〜９」及び行番号「２」を記載されている。属性「照度」（行番号管理表１３Ｒに基づく４行目）について、範囲「６〜１１」及び行番号「３」を記載されている。属性「音量」（行番号管理表１３Ｒに基づく５行目）について、範囲「４〜５」及び行番号「４」を記載されている。属性「温度」（行番号管理表１３Ｒに基づく３行目）について、範囲「−」及び行番号「−」を記載されている。
【００４９】
リーフノード索引範囲表１２Ｌ１における記載内容について説明する。属性「センサＩＤ」（ルートノード索引範囲表１２Ｒに基づく１行目）について、値「１、２」をデータ１１−１、１１−２について記載されている。属性「時間」（ルートノード索引範囲表１２Ｒに基づく２行目）について、値「３、４」をデータ１１−１、１１−２について記載されている。属性「温度」（ルートノード索引範囲表１２Ｒに基づく３行目）について、値「２０．３、２１．１」をデータ１１−１、１１−２について記載されている。
【００５０】
ここで、本発明では、従来技術と異なり、リーフノード索引範囲表１２Ｌ１において、属性「照度」及び「音量」について、何らも記載されておらず、「−」すら記載されていない。このように、リーフノード索引範囲表１２Ｌ１において、行の省略を大量に行うことが可能となり、メモリ領域を低減することが可能となる。
【００５１】
リーフノード索引範囲表１２Ｌ２における記載内容について説明する。属性「センサＩＤ」（ルートノード索引範囲表１２Ｒに基づく１行目）について、値「３、４」をデータ１１−３、１１−４について記載されている。属性「時間」（ルートノード索引範囲表１２Ｒに基づく２行目）について、値「７、９」をデータ１１−３、１１−４について記載されている。属性「照度」（ルートノード索引範囲表１２Ｒに基づく３行目）について、値「６、１１」をデータ１１−３、１１−４について記載されている。属性「音量」（ルートノード索引範囲表１２Ｒに基づく４行目）について、値「４、５」をデータ１１−３、１１−４について記載されている。
【００５２】
ここで、本発明では、従来技術と異なり、リーフノード索引範囲表１２Ｌ２において、属性「温度」について、何らも記載されておらず、「−」すら記載されていない。このように、リーフノード索引範囲表１２Ｌ２において、行の省略を大量に行うことが可能となり、メモリ領域を低減することが可能となる。
【００５３】
なお、リーフノードＬ１、Ｌ２では、子ノードを保持しないため、リーフノード索引範囲表１２Ｌ１、１２Ｌ２では、行番号の列は省略されている。図５では、各属性に対する行番号をルートノード索引範囲表１２Ｒに保持させているが、各属性に対する行番号をルートノード索引範囲表１２Ｒとは別途に管理してもよい。
【００５４】
以上に説明したように、ノードの木構造の全体で共通して、各属性及び行番号を対応付ける必要がなくなる。よって、インナーノード（図５のルートノードＲ）において、或る属性に対する属性値のデータが管理されているが、子ノード（図５のリーフノードＬ１、Ｌ２）において、当該属性に対する属性値のデータが管理されていないとき、子ノードの索引範囲表（図５のリーフノード索引範囲表１２Ｌ１、１２Ｌ２）において、当該属性に対応する行を省略することができる。
【００５５】
ここで、子ノードの索引範囲表において、当該属性に対応する行を省略すれば、後続の行に対応する属性について、インナーノードの索引範囲表及び子ノードの索引範囲表において、異なる行番号が設定される。例えば、属性「照度」及び「音量」について、ルートノード索引範囲表１２Ｒにおいては、それぞれ行番号「４」及び「５」が設定されるが、リーフノード索引範囲表１２Ｌ２においては、それぞれ行番号「３」及び「４」が設定される。しかし、子ノードの索引範囲表における各属性及び行番号の対応関係が、インナーノードの索引範囲表において記載されている。よって、木構造を上位から下位へと辿るにあたり、子ノードの索引範囲表においてどの行にどの属性の情報が記載されているか、インナーノードの索引範囲表において正しく読み取ることができる。
【００５６】
つまり、属性の種類数が多くなる多様なデータの集合であり、かつ個々のデータの属性数が少ない場合においては、このような行の省略を大量に行うことが可能となり、特にリーフノードに近づくにつれて、各ノードの索引範囲表が必要とするメモリ領域を低減することが可能となる。
【００５７】
ここで、子ノードの索引範囲表における各属性及び行番号の対応関係が、インナーノードの索引範囲表において従来技術と比較してオーバーヘッドとなる。しかし、属性の種類数が多くなる多様なデータの集合であり、かつ個々のデータの属性数が少ない場合においては、行の省略によるメモリ領域の低減の効果が、オーバーヘッドによるメモリ領域の増大の効果を上回る。よって、ノードの木構造の全体が必要とするメモリ領域を低減することが可能となる。
【００５８】
なお、本発明は、多様な属性を含むデータ集合であり、かつ、各データが含む属性数が少ないデータ集合において、より大きな効果が得られる。なぜならば、このような性質をもつデータ集合においては、ルートノードからリーフノードへ近づくほど、そのノードにより管理されているデータが含む属性数が少なくなり、それだけ省略できる行数が多くなるためである。多種のデバイスを用いて計測したセンサ情報は、このような性質をもつデータ集合となりやすく、本発明の効果が出やすいデータ集合の１つと言える。
【００５９】
木構造をもつ索引技術においては、多くの場合、各ノードが保持しうる子ノード数又はデータ数に上限が定められており、上限を超えた場合にはノード分割が行われる。ノード分割とは、ノードを２つに分割し、上限を超えた子ノード群又はデータ群を分割後の２つのノードに振り分けることで、各ノードが保持する子ノード数又はデータ数を上限以下に留める操作を指す。このようなノード分割を行う場合にも、分割後の各ノードにおいて行番号の更新を行うことにより、本発明の木構造を維持することは可能である。
【００６０】
本発明のデータ索引装置Ｉのデータ構造記憶機能は、コンピュータ及びプログラムによっても実現することができる。そして、当該プログラムを、記録媒体に記録することもでき、ネットワークを通して提供することもできる。
【００６１】
（データ検索処理）
次に、データ検索処理について説明する。データ検索部３は、ルートノード検索対象選択部３１、インナーノード検索対象選択部３２及びデータ検索実行部３３から構成される。
【００６２】
検索対象情報取得部２１は、木構造記憶部１が記憶しているデータ集合１１について、検索対象属性の情報及び検索対象範囲の情報を取得する。
【００６３】
ルートノード検索対象選択部３１は、検索対象情報取得部２１が取得した検索対象属性の情報、及びルートノード行番号管理表１３Ｒを参照する。そして、参照した情報に基づいて、ルートノード索引範囲表１２Ｒにおける検索対象属性に対応する記載行番号を選択する。
【００６４】
インナーノード検索対象選択部３２は、検索対象情報取得部２１が取得した検索対象属性の情報及び検索対象範囲の情報、並びにルートノード検索対象選択部３１が選択したルートノード索引範囲表１２Ｒにおける検索対象属性に対応する記載行番号を参照する。そして、参照した情報に基づいて、検索対象属性及び検索対象範囲を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについてのインナーノード索引範囲表における検索対象属性に対応する記載行番号を選択する。
【００６５】
データ検索実行部３３は、インナーノード検索対象選択部３２が選択した当該インナーノードについてのインナーノード索引範囲表における検索対象属性に対応する記載行番号を参照する。そして、参照した情報に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、検索対象情報取得部２１が取得した検索対象属性の情報及び検索対象範囲の情報に基づくデータの検索を実行する。
【００６６】
このようなデータ検索処理は、再帰的に実行される。つまり、まず、ルートノードＲ及びその子ノード（第１の子ノード）の間で、上述のデータ検索処理を実行する。そして、次に、第１の子ノード及びその子ノード（第２の子ノード）の間で、上述のデータ検索処理を実行する。これを、リーフノードＬに到達するまで繰り返す。
【００６７】
本発明のデータ検索処理における木構造を図６に示し、本発明のデータ検索処理のフローチャートを図７に示す。データ検索処理前後の木構造は、図５と同様である。
【００６８】
検索対象情報取得部２１は、ネットワークＮを介して、検索対象情報を取得する（ステップＳ１）。検索対象情報は、「時間＝４〜８及び照度＝３〜１０」とする。
【００６９】
ルートノード検索対象選択部３１は、検索対象ノードとして、ルートノードＲを選択する（ステップＳ２）。そして、ステップＳ２で選択した検索対象ノードは、リーフノードでないと判断し、ステップＳ４に進む（ステップＳ３においてＮＯ）。
【００７０】
ルートノード検索対象選択部３１は、検索対象属性「時間」及び「照度」、並びにルートノード行番号管理表１３Ｒを参照する。そして、参照した情報に基づいて、ルートノード索引範囲表１２Ｒにおける、検索対象属性「時間」及び「照度」に対応する行番号「２」及び「４」を選択する（ステップＳ４）。
【００７１】
インナーノード検索対象選択部３２は、検索対象属性「時間」及び「照度」、検索対象範囲「４〜８」及び「３〜１０」、並びにルートノード索引範囲表１２Ｒにおける、検索対象属性「時間」及び「照度」に対応する行番号「２」及び「４」を参照する。そして、参照した情報に基づいて、検索対象属性「時間」及び「照度」並びに検索対象範囲「４〜８」及び「３〜１０」を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについてのインナーノード索引範囲表における、検索対象属性「時間」及び「照度」に対応する行番号を選択する（ステップＳ５）。
【００７２】
具体的には、インナーノード検索対象選択部３２は、検索対象属性「時間」及び「照度」並びに検索対象範囲「４〜８」及び「３〜１０」を満足するデータの集合を管理しているインナーノードとして、属性「時間」及び「照度」並びに範囲「７〜９」及び「６〜１１」を包含するデータの集合を管理しているリーフノードＬ２を選択する。そして、リーフノードＬ２についてのルートノード索引範囲表１２Ｌ２における、検索対象属性「時間」及び「照度」に対応する行番号「２」及び「３」を選択する。
【００７３】
インナーノード検索対象選択部３２は、今回の子ノードであるリーフノードＬ２を、次回の検索対象ノードに設定し、ステップＳ３に戻る（ステップＳ６）。インナーノード検索対象選択部３２は、ステップＳ６で設定された検索対象ノードは、リーフノードであると判断し、ステップＳ７に進む（ステップＳ３においてＹＥＳ）。
【００７４】
データ検索実行部３３は、インナーノード検索対象選択部３２が選択したリーフノードＬ２についてのリーフノード索引範囲表１２Ｌ２における、検索対象属性「時間」及び「照度」に対応する行番号「２」及び「３」を参照する。そして、参照した情報に基づいて、リーフノード１２Ｌ２において管理されているデータ１１−３、１１−４に対して、検索対象属性「時間」及び「照度」並びに検索対象範囲「４〜８」及び「３〜１０」に基づく、データの検索を実行する（ステップＳ７）。
【００７５】
具体的には、データ検索実行部３３は、検索対象属性「時間」及び「照度」のそれぞれについて、検索対象範囲「４〜８」及び「３〜１０」を満足しているデータ１１−３を抽出する。そして、検索対象情報取得部２１は、抽出されたデータ１１−３を、ネットワークＮを介して、検索依頼元に対して送信する。
【００７６】
このように、インナーノード索引範囲表において行の省略を大量に行ったとしても、データの検索を正しく実行することが可能となる。
【００７７】
本発明のデータ索引装置Ｉのデータ検索機能は、コンピュータ及びプログラムによっても実現することができる。そして、当該プログラムを、記録媒体に記録することもでき、ネットワークを通して提供することもできる。
【００７８】
（データ挿入処理）
次に、データ挿入処理について説明する。データ挿入部４は、ルートノード挿入対象選択部４１、インナーノード挿入対象選択部４２及びデータ挿入実行部４３から構成される。
【００７９】
挿入対象情報取得部２２は、木構造記憶部１が記憶しているデータ集合１１について、挿入対象属性の情報及び挿入対象値の情報を取得する。
【００８０】
ルートノード挿入対象選択部４１は、挿入対象情報取得部２２が取得した挿入対象属性の情報、及びルートノード行番号管理表１３Ｒを参照する。そして、参照した情報に基づいて、ルートノード索引範囲表１２Ｒにおける挿入対象属性に対応する記載行番号を選択する。
【００８１】
インナーノード挿入対象選択部４２は、挿入対象情報取得部２２が取得した挿入対象属性の情報及び挿入対象値の情報、並びにルートノード挿入対象選択部４１が選択したルートノード索引範囲表１２Ｒにおける挿入対象属性に対応する記載行番号を参照する。そして、参照した情報に基づいて、挿入対象属性及び挿入対象値を満足するデータの集合を管理しているインナーノード、並びに当該インナーノードについてのインナーノード索引範囲表における挿入対象属性に対応する記載行番号を選択する。
【００８２】
データ挿入実行部４３は、インナーノード挿入対象選択部４２が選択した当該インナーノードについてのインナーノード索引範囲表における挿入対象属性に対応する記載行番号を参照する。そして、参照した情報に基づいて、当該インナーノードに対するリーフノードにおいて管理されているデータの集合に対して、挿入対象情報取得部２２が取得した挿入対象属性の情報及び挿入対象値の情報に基づくデータの挿入を実行する。
【００８３】
このようなデータ挿入処理は、再帰的に実行される。つまり、まず、ルートノードＲ及びその子ノード（第１の子ノード）の間で、上述のデータ挿入処理を実行する。そして、次に、第１の子ノード及びその子ノード（第２の子ノード）の間で、上述のデータ挿入処理を実行する。これを、リーフノードＬに到達するまで繰り返す。
【００８４】
本発明のデータ挿入処理における木構造を図８に示し、本発明のデータ挿入処理のフローチャートを図９に示す。データ挿入処理前の木構造は、図５と同様であるが、データ挿入後の木構造は、図８のようになる。
【００８５】
挿入対象情報取得部２２は、ネットワークＮを介して、挿入対象情報を取得する（ステップＳ１１）。挿入対象情報は、「センサＩＤ＝３、時間＝１０、照度＝７、音量＝３及び加速度＝２」とする。
【００８６】
ルートノード挿入対象選択部４１は、挿入対象ノードとして、ルートノードＲを選択する（ステップＳ１２）。そして、ステップＳ１２で選択した挿入対象ノードは、リーフノードでないと判断し、ステップＳ１４に進む（ステップＳ１３においてＮＯ）。
【００８７】
ルートノード挿入対象選択部４１は、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」、並びにルートノード行番号管理表１３Ｒを参照する。そして、参照した情報に基づいて、ルートノード索引範囲表１２Ｒにおける、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」に対応する記載行番号「１」、「２」、「４」、「５」及び「６」を選択する（ステップＳ１４）。
【００８８】
図８では、ルートノード挿入対象選択部４１は、ステップＳ１４の処理前では、ルートノード行番号管理表１３Ｒ及びルートノード索引範囲表１２Ｒにおいて、挿入対象属性「加速度」に対応する記載行番号を選択することができない。そこで、ステップＳ１４の処理において、ルートノード行番号管理表１３Ｒでは、挿入対象属性「加速度」に対応する記載行番号「６」を設定するとともに、ルートノード索引範囲表１２Ｒでは、挿入対象属性「加速度」に対応する記載行番号「５」を設定する。
【００８９】
インナーノード挿入対象選択部４２は、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」、挿入対象値「３」、「１０」、「７」、「３」及び「２」、並びにルートノード索引範囲表１２Ｒにおける、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」に対応する行番号「１」、「２」、「４」、「５」及び「６」を参照する。そして、参照した情報に基づいて、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」並びに挿入対象値「３」、「１０」、「７」、「３」及び「２」を満足するデータの集合を管理しているインナーノードを選択する。さらに、参照した情報に基づいて、当該インナーノードについてのインナーノード索引範囲表における、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」に対応する行番号を選択する（ステップＳ１５）。
【００９０】
図８では、インナーノード検索対象選択部３２は、ステップＳ１５の処理前では、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」並びに挿入対象値「３」、「１０」、「７」、「３」及び「２」を満足するデータの集合を管理している下位ノードを選択することができない。そこで、ステップＳ１５の処理において、新規データとなるべく同じ次元をもつ下インナーノードに対して、新規データが挿入されるように、リーフノードＬ１を選択せず、リーフノードＬ２を選択する。
【００９１】
そして、ステップＳ１５の処理において、新規データである「センサＩＤ＝３、時間＝１０、照度＝７、音量＝３及び加速度＝２」の挿入にあたり、ルートノード索引範囲表１２Ｒにおいて、リーフノードＬ２について、属性「時間」（２行目）の範囲を「７〜９」から「７〜１０」へと変更し、属性「音量」（５行目）の範囲を「４〜５」から「３〜５」へと変更し、属性「加速度」（６行目）の範囲を「２〜２」に新たに設定する。さらに、ステップＳ１５の処理において、リーフノードＬ２についてのリーフノード索引範囲表１２Ｌ２における、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」に対応する行番号「１」、「２」、「３」、「４」及び「５」を選択する。
【００９２】
インナーノード挿入対象選択部４２は、今回の子ノードであるリーフノードＬ２を、次回の挿入対象ノードに設定し、ステップＳ１３に戻る（ステップＳ１６）。インナーノード挿入対象選択部４１は、ステップＳ１６で設定された挿入対象ノードは、リーフノードであると判断し、ステップＳ１７に進む（ステップＳ１３においてＹＥＳ）。
【００９３】
データ挿入実行部４３は、インナーノード挿入対象選択部４２が選択したリーフノードＬ２についてのリーフノード索引範囲表１２Ｌ２における、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」に対応する行番号「１」、「２」、「３」、「４」及び「５」を参照する。そして、参照した情報に基づいて、リーフノード１２Ｌ２において管理されているデータ１１−３、１１−４に対して、挿入対象属性「センサＩＤ」、「時間」、「照度」、「音量」及び「加速度」並びに挿入対象値「３」、「１０」、「７」、「３」及び「２」に基づく、データの挿入を実行する（ステップＳ１７）。
【００９４】
具体的には、データ検索実行部３３は、リーフノード索引範囲表１２Ｌ２において、挿入対象属性「加速度」に対応する記載行番号「５」を設定する。そして、データ１１−５である「センサＩＤ＝３、時間＝１０、照度＝７、音量＝３及び加速度＝２」の挿入にあたり、リーフノード索引範囲表１２Ｌ２において、データ１１−５について、属性「センサＩＤ」（１行目）の値を「３」に新たに設定し、属性「時間」（２行目）の値を「１０」に新たに設定し、属性「照度」（３行目）の値を「７」に新たに設定し、属性「音量」（４行目）の値を「３」に新たに設定し、属性「加速度」（５行目）の値を「２」に新たに設定する。さらに、挿入対象情報取得部２２は、新規データの挿入完了通知を、ネットワークＮを介して、挿入依頼元に対して送信する。
【００９５】
このように、インナーノード索引範囲表において行の省略を大量に行ったとしても、データの挿入を正しく実行することが可能となる。
【００９６】
本発明のデータ索引装置Ｉのデータ挿入機能は、コンピュータ及びプログラムによっても実現することができる。そして、当該プログラムを、記録媒体に記録することもでき、ネットワークを通して提供することもできる。
【産業上の利用可能性】
【００９７】
本発明に係るデータ索引装置、データ索引方法及びデータ索引プログラムは、Ｂ−ＴｒｅｅやＲ−Ｔｒｅｅに対しても適用可能であるが、ＵＢＩ−Ｔｒｅｅに対して特に有利な効果を発揮することができる。
【符号の説明】
【００９８】
Ｉ：データ索引装置
Ｎ：ネットワーク
Ｒ：ルートノード
Ｌ１、Ｌ２：リーフノード
１：木構造記憶部
２：ネットワーク通信部
３：データ検索部
４：データ挿入部
１１：データ集合
１１−１、１１−２、１１−３、１１−４、１１−５：データ
１２：索引範囲表
１２Ｒ：ルートノード索引範囲表
１２Ｌ１、１２Ｌ２：リーフノード索引範囲表
１３：行番号管理表
１３Ｃ：行番号管理表
１３Ｒ：行番号管理表
２１：検索対象情報取得部
２２：挿入対象情報取得部
３１：ルートノード検索対象選択部
３２：インナーノード検索対象選択部
３３：データ検索実行部
４１：ルートノード挿入対象選択部
４２：下位ノード挿入対象選択部
４３：インナー挿入実行部
【図１】
2014041438.tif 000003
【図２】
2014041438.tif 000004
【図３】
2014041438.tif 000005
【図４】
2014041438.tif 000006
【図５】
2014041438.tif 000007
【図６】
2014041438.tif 000008
【図７】
2014041438.tif 000009
【図８】
2014041438.tif 000010
【図９】
2014041438.tif 000011