(57)【要約】【課題】メモリの容量が乏しい組込み機器において、挿入性能と検索性能とを両立させることができるようにする。【解決手段】撮影終了を検知すると、挿入が高速だが検索が低速な低速検索インデクス６０２から、挿入が低速だが検索が高速な高速検索インデクス６０３が生成される。そして、写真撮影が再開されると、高速検索インデクス６０６が無効化され、低速検索インデクス追加分６０５にデータが挿入される。撮影終了を再度検知すると、さらに今後の再撮影に備えて低速検索インデクス６０７に低速検索インデクス追加分６０５の内容がマージされ、高速検索インデクス６０８が再生成される。【選択図】図６
2013097536.tif 000002
【特許請求の範囲】
【請求項１】
データベースを記録する記録メモリにデータを挿入するとともに、前記記録メモリからデータの検索を行う検索装置であって、
前記データの挿入を第１のインデクスに反映する挿入手段と、
前記挿入手段によるデータの挿入の終了を検知する検知手段と、
前記検知手段によりデータの挿入の終了を検知したことに応じて、前記第１のインデクスよりもインデクスロード領域の空き領域を削減した第２のインデクスを生成する生成手段と、
前記生成手段によって生成された第２のインデクスに基づいて検索を実行する検索手段とを有することを特徴とする検索装置。
【請求項２】
前記生成手段によって前記第２のインデクスが生成された後にデータの挿入が指示された場合に、前記第２のインデクスを無効化する無効化手段をさらに有することを特徴とする請求項１に記載の検索装置。
【請求項３】
前記無効化手段により前記第２のインデクスが無効化された場合に、前記生成手段は、前記指示されたデータの挿入を反映する第３のインデクスを生成し、前記検知手段によりデータの挿入の終了を検知したことに応じて、前記第１のインデクスに前記第３のインデクスの内容を反映させることを特徴とする請求項２に記載の検索装置。
【請求項４】
前記検知手段は、前記記録メモリの空き領域が所定サイズよりも小さくなった場合に、前記挿入手段によるデータの挿入が終了したものと検知することを特徴とする請求項１〜３の何れか１項に記載の検索装置。
【請求項５】
前記検知手段は、前記記録メモリのライトプロテクト状態を検知することにより前記挿入手段によるデータの挿入の終了を検知することを特徴とする請求項１〜３の何れか１項に記載の検索装置。
【請求項６】
前記検知手段は、前記記録メモリを前記検索装置から取り出す指示を検知することにより前記挿入手段によるデータの挿入の終了を検知することを特徴とする請求項１〜３の何れか１項に記載の検索装置。
【請求項７】
データベースを記録する記録メモリにデータを挿入するとともに、前記記録メモリからデータの検索を行う検索方法であって、
前記データの挿入を第１のインデクスに反映する挿入工程と、
前記挿入工程におけるデータの挿入の終了を検知する検知工程と、
前記検知工程においてデータの挿入の終了を検知したことに応じて、前記第１のインデクスよりもインデクスロード領域の空き領域を削減した第２のインデクスを生成する生成工程と、
前記生成工程において生成された第２のインデクスに基づいて検索を実行する検索工程とを有することを特徴とする検索方法。
【請求項８】
データベースを記録する記録メモリにデータを挿入するとともに、前記記録メモリからデータの検索を行う検索装置を制御するためのプログラムであって、
前記データの挿入を第１のインデクスに反映する挿入工程と、
前記挿入工程におけるデータの挿入の終了を検知する検知工程と、
前記検知工程においてデータの挿入の終了を検知したことに応じて、前記第１のインデクスよりもインデクスロード領域の空き領域を削減した第２のインデクスを生成する生成工程と、
前記生成工程において生成された第２のインデクスに基づいて検索を実行する検索工程とをコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は検索装置、検索方法及びプログラムに関し、特に、データの挿入とデータの検索との両方を行うために用いて好適な技術に関する。
【背景技術】
【０００２】
近年では、記憶装置や記録メディアの大容量化が進み、カメラ等の小型機器においても検索などの処理負荷の重いデータ処理が行われるようになりつつある。例えば、カメラに着脱可能であり、撮影写真等のデータが格納される記録メディアとして、１２８ＧＢの容量のＳＤＸＣ規格のメモリカードが市販されている。このメモリカードには、１枚あたり１ＭＢの撮影画像データを１２万枚以上格納することができる。さらに、ＳＤＸＣの規格上では２ＴＢまで記憶容量を拡張することができる。
【０００３】
一方、大規模なシステムにおいては、このようにデータ処理の負荷が増大することに対応するため、データベースマネジメントシステム（ＤＢＭＳ）が開発されている。そして、このＤＢＭＳの利用を推進することによってアプリケーションシステムを構築するための開発がより効率良く進んできた。そこで、小型機器においても組込み機器の用途としてＤＢＭＳ（組込みデータベース）を搭載し、活用しようという動きが加速しつつある。
【０００４】
ところが、カメラ等に代表される組込み機器では、大規模なサーバと異なり、メモリ等のリソースが貧弱であることが多い。一般のデータベースでは、一般にインデクスを使用し、インデクスへのディスクアクセスを軽減するよう使用頻度の高いインデクスを極力メモリに常駐してキャッシュ効果が上がるよう制御し、検索を高速化している。このため、メモリの容量が少ない組込み機器では、インデクスサイズの縮小がわずかでもメモリの使用効率の改善が検索性能の向上に大きく寄与することがある。
【０００５】
一般に、インデクスはデータを新規に記憶する挿入性能を確保するために相当量の空き領域をメモリの内部に維持しているため、メモリのサイズが大きくなりがちである。したがって、インデクスの空き領域を小さくしたり無くしたりすることができれば、メモリへの常駐効果によって検索性能が大きく向上する。ところが、空き領域を無くしてしまうと挿入性能が大きく劣化することになるので、現実には空き領域を削減することはできない。このような事情から、従来は、組込み機器のデータベースにおいては十分な検索性能を実現できていなかった。
【０００６】
挿入性能及び検索性能の二律背反という課題は、データベースにとっては一般的な課題であり、その解消方法について、従来から多くの提案がなされている。例えば特許文献１に記載されている方法はそのような例の１つである。特許文献１に記載の方法では、高速検索低速更新の第１のデータ保持手段と低速検索高速更新の第２のデータ保持手段との２種類のデータ保持手段を用意している。そして、第１のデータ保持手段が処理中で忙しいときに、第２のデータ保持手段へデータを挿入することにより、高速検索を実現するとともに高速挿入を実現している。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００４−１３４９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１に記載の方法は、高速に検索が可能だが挿入が低速なデータ保持手段に対して、別のデータ保持手段に暫定的に高速にデータを挿入する工夫がなされている。ところが、メモリの容量が乏しい組込み機器に対しては十分に検索性能を向上させることはできない。
【０００９】
本発明は前述の問題点に鑑み、メモリの容量が乏しい組込み機器において、挿入性能と検索性能とを両立させることができるようにすることを目的としている。
【課題を解決するための手段】
【００１０】
本発明の検索装置は、データベースを記録する記録メモリにデータを挿入するとともに、前記記録メモリからデータの検索を行う検索装置であって、前記データの挿入を第１のインデクスに反映する挿入手段と、前記挿入手段によるデータの挿入の終了を検知する検知手段と、前記検知手段によりデータの挿入の終了を検知したことに応じて、前記第１のインデクスよりもインデクスロード領域の空き領域を削減した第２のインデクスを生成する生成手段と、前記生成手段によって生成された第２のインデクスに基づいて検索を実行する検索手段とを有することを特徴とする。
【発明の効果】
【００１１】
本発明によれば、インデクスのメモリへの常駐効果を改善し、メモリの乏しい組込み機器において、挿入性能と検索性能とを両立させることができる。
【図面の簡単な説明】
【００１２】
【図１】実施形態の検索装置の構成例を示すブロック図である。
【図２】実施形態の検索装置が効果的となる使用例を説明する図である。
【図３】実施形態におけるデータベースの構成例を示した図である。
【図４】実施形態のデータベースのノードの物理構成例を示した図である。
【図５】実施形態の検索装置におけるインデクスロード領域の構成例を示す図である。
【図６】ユーザの操作に応じて生成されるデータベースのインデクスの状況を説明する図である。
【図７】実施形態の検索装置による処理結果を示す処理手順の一例を示すフローチャートである。
【図８】実施形態における検索処理手順の一例を示すフローチャートである。
【図９】第１の実施形態における写真登録処理の手順一例を示すフローチャートである。
【図１０】実施形態におけるＳＤカード取り出し処理、高速検索インデクスを生成する詳細な処理、その他のイベントに応じた処理、及び無挿入段階検知処理の一例を示すフローチャートである。
【図１１】実施形態における低速検索インデクスから高速検索インデクスを作成する詳細な処理手順の一例を示すフローチャートである。
【図１２】第２の実施形態における写真登録処理の手順一例を示すフローチャートである。
【図１３】第２の実施形態における高速検索インデクスを生成する詳細な処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
（第１の実施形態）
以下、図面を参照しながら本発明に好適な第１の実施形態を詳細に説明する。
図１は、本実施形態の検索装置１００の構成例を示すブロック図である。
図１において、ＣＰＵ１０１はマイクロプロセッサであり、検索処理、写真登録処理、画面制御処理、写真撮影処理等のための演算、論理判断等を行い、バス１０６を介してバス１０６に接続された各デバイスを制御する。バス１０６は、ＣＰＵ１０１の制御対象である各デバイスを指示するアドレス信号、コントロール信号を転送する。また、各デバイス間でデータの転送を行う。
【００１４】
入力部１０２はボタン、タッチパネル等であり、オペレータが各種の指示を行う。表示部１０３は液晶ディスプレイ等である。撮像部１０４は撮像センサ等であり、映像を読み取って電子データに変換する。通信部１０５はネットワークコントローラであり、有線あるいは無線の通信路を介して外部とのデータの交換を行う。
【００１５】
ＲＯＭ１０７は読出専用の不揮発性メモリであり、ＣＰＵ１０１によるブートプログラム、システムの制御プログラム、各種処理で参照される各種初期データ等を記憶する。ブートプログラムはシステム起動時に初期データをＲＡＭ１０８にロードし、ＣＰＵ１０１に制御プログラムを実行させる。制御プログラムの内容については、後にフローチャートを参照して詳述する。
【００１６】
ＲＡＭ１０８は読み書き可能なランダムアクセスメモリであって、各デバイスからの各種データの一次記憶に用いられ、処理に必要なデータを記憶する各種ワーク領域、処理中に必要なスタック、及び処理中に値変更が行われる各種データが格納される。また、後述するデータベース１１０を構成する各ノードのノードＩＤと格納される先頭キーとの対応表、データベース１１０のインデクスが一時的にメモリ中にロードされるインデクスロード領域等もＲＡＭ１０８に格納される。
【００１７】
ＤＩＳＫ１０９はＳＤカード等の記録メモリ、あるいは、ハードディスク等で構成される大量記憶装置であり、大量のデータを記憶する。写真を検索するための撮影日時などの属性情報を記憶するデータベース１１０や、写真データそのものを記憶するコンテンツ１１１はＤＩＳＫ１０９に格納され、必要に応じて随時内容が修正される。なお、ＣＰＵ１０１により実行される制御プログラムをＤＩＳＫ１０９に格納するようにしてもよい。その場合は、必要に応じてＲＡＭ１０８に示す主記憶にロードし、実行することになる。そのようにすることでプログラムを固定化せず途中で修正可能に構成することができ、柔軟なシステムを実現することができる。
【００１８】
以上の構成からなる検索装置１００は、入力部１０２等からの各種イベントに応じて作動する。入力部１０２等からのインタラプトが供給されるとインタラプト信号がＣＰＵ１０１に送られる。それに伴ってイベントが発生し、イベントに応じてＣＰＵ１０１がＲＯＭ１０７またはＲＡＭ１０８内に記憶されている各種命令を読み出し、ＣＰＵ１０１の実行によって各種の制御が行われる。
【００１９】
図２は、本実施形態の検索装置１００が効果的となる使用例を説明する図である。図２（ａ）は、カメラ２０１にＳＤカード２０２が装着され、写真撮影が行われている状況を示した図である。このとき、ＳＤカード２０２中のデータベース１１０の第１のインデクスとして、検索が低速だが挿入が高速なインデクス（低速検索高速挿入インデクス、以下、低速検索インデクスとも呼称）が存在して使用される。
【００２０】
この状況では、データの挿入が起こる写真撮影が頻繁に行われるため、挿入が高速で行われる必要がある。しかし、無限に写真撮影が継続されることはまれであり、通常は、ある時点で撮影が終了する。この撮影終了の判定は、例えば、以下のような場合を判定して行われる。
【００２１】
１つ目は、ＳＤカード２０２の空き領域が所定値以下になった場合である。２つ目は、ＳＤカード２０２のライトプロテクト状態が設定された場合である。また、３つ目は、カメラ２０１からＳＤカード２０２を取り出そうとした場合である。さらに４つ目は、ＳＤカード２０２への挿入が所定期間以上行われなくなった場合である。
【００２２】
本実施形態では、この状況変化を検知し、第２のインデクスとして、挿入が低速だが検索が高速なインデクス（高速検索低速挿入インデクス、以下、高速検索インデクスとも呼称）を生成する。これにより、撮影終了後は、ＳＤカード２０２の検索を高速化できる。具体的には、ＳＤカード２０２の空き領域が所定値以下であることを判定することにより、それ以上の写真が追加されそうにないＳＤカードに対して、ユーザが特別な指示をすることなく検索を高速化できる。また、ＳＤカード２０２のライトプロテクト状態を判定することにより、それ以上の写真が追加されそうにないＳＤカードに対して、ユーザが特別な指示をすることなく検索を高速化できる。また、カメラ２０１からのＳＤカード２０２取り出し指示を判定することにより、それ以上の写真が追加されそうにないＳＤカードに対して、ユーザが特別な指示をすることなく検索を高速化できる。また、ＳＤカード２０２への挿入が所定期間以上行われなくなった状態を検知して判定することにより、それ以上の写真が追加されそうにないＳＤカードに対して、ユーザが特別な指示をすることなく検索を高速化できる。
【００２３】
図２（ｂ）は、ＳＤカード２０４が読み出し専用で使用される状況を説明した図である。図２（ｂ）に示す例では、カメラ以外の機器２０３にＳＤカード２０４が装着されている。この状況では、新規の写真撮影が行われず、データの挿入が行われることはなく、一覧表示、印刷等の写真撮影以外の処理が行われるのみである。この状況では、写真データの検索のみが行われ、高速検索インデクスによって高速に処理される。この場合、データの挿入が行われると処理が低速となるが、実際には写真撮影が行われることはないので問題にならない。
【００２４】
一方、ＳＤカード２０４がカメラに再度装着される場合など、もう一度撮影が開始される場合がある。このようなときは、一旦、高速検索インデクスを無効化（使用禁止）し、旧インデクスである低速インデクスを復活させて、データを挿入するようにする。このようにすることによって、撮影（データ挿入）が無い状態での検索を高速化でき、その後の再撮影があってもスムーズに再開することができる。
【００２５】
図３は、本実施形態におけるデータベース３００の構成例を示した図である。図３（ａ）には、データベース３００全体の構成を示している。
図３（ａ）に示すように、データベース３００は表３０１とインデクス群３０２とから構成されている。また、インデクス群３０２は更に細分され、低速検索インデクス３０３、低速検索インデクス追加分３０４、高速検索インデクス３０５等から構成されている。
【００２６】
図３（ｂ）は、表３０１の構成を更に詳細に示した図である。表３０１は行データの集合として記憶され、行データは行を一意に特定可能なＩＤ（ＲｏｗＩＤと呼ぶ）の列３０６とその他の列３０７とを対応付けて記憶される。
【００２７】
図３（ｃ）は、インデクスの構成を示す図である。図３（ｃ）に示すように、インデクスの論理構成は、基本的にはいわゆるＢ−Ｔｒｅｅの構造である。インデクスは複数の固定長のノードで構成され、ノード内に各キーがバランスよく格納されている。各ノードは下位ノードへのリンク３０８とキー３０９とからなり、最も上位のノード（ルートノード）から、キーの大小関係を判断してリンクをたどることによって目的のキーを参照することができる。また、最下層のノード（リーフノード）にはキー３１０とＲｏｗＩＤ３１１とが対応づけられて格納されている。ここで得られたＲｏｗＩＤ３０１に従って表３０１を参照することにより、目的の行データを参照することができる。
【００２８】
図４は、本実施形態のデータベース３００のノードの物理構成例を示した図である。図４（ａ）は、低速検索インデクスの場合のノード４０２の構成例を示す図である。図４（ａ）に示すように、先頭付近にはセルへのリンク４０１が格納されている。また、末尾付近には実際のセル４０３が格納されている。各セルは下位ノードへのリンク４０５とキー４０６とから構成されている。ノードの末尾のリンク４０４は、Ｂ−Ｔｒｅｅの論理構成における末尾の下位ノードへのリンクを意味している。また、セルへのリンク４０１とセル４０３との間には空き領域４０７が配置されている。
【００２９】
このように、セルへのリンク４０１とセル４０３とが分離された構造になっているのは、キーのソート順にセルを取得できるようにする必要があり、セルを挿入する際にソート順の維持を高速化するためである。セルは一般にデータ長が長いため、セルへのリンクを再配置するだけで、ソート順を維持した高速の挿入処理が可能となる。空き領域４０７のサイズは任意のサイズに決めることができるが、挿入のことを考えて、通常は全体の半分程度の量を確保しておく。
【００３０】
図４（ｂ）は、高速検索インデクスの場合のノード４０８の物理構成例を示す図である。高速検索インデクスにおいては基本的に挿入が行われないので、挿入を高速化するための工夫がなされておらず、検索の高速化に特化している。そのため、セルへのリンクを別途用意することはなく、単純にセルのデータだけがキーの順番になるように詰め合わせて構成されている。
【００３１】
図５は、本実施形態の検索装置１００におけるインデクスロード領域の構成例を示す図である。図５（ａ）は、インデクスロード領域の概略構成例を示す図である。インデクスロード領域は、データベース３００中のインデクスの各ノードをメモリ上にロードするための領域であり、いわゆるキャッシュメモリの役割を持つ。インデクスロード領域の各領域５０１はノードサイズと同じ固定長で構成されている。
【００３２】
組込み機器では、メモリの断片化を避けるために動的に確保、解放される領域は基本的に固定長で管理され、その時々で必要なノードがオンデマンドでロードされる。一度ロードされたノードは必要がなくなるまでメモリ上に存在し、再度、該当ノードが必要になったときにメモリ上に存在するデータが参照される。これにより高速処理が可能となる。インデクスロード領域には、全ノード数分に対応するほどのメモリが割り当てられないので、インデクスロード領域があふれた場合には、使用されていない古いノードから追放されてメモリ上から消えてしまう。
【００３３】
図５（ｂ）は、低速検索インデクスのノードをロードした状態を説明する図である。図５（ｂ）に示すように、各ノードはセルへのリンク５０２、空き領域５０３、及びセル５０４から構成されている。空き領域５０３は、検索のためには不要な領域であるが、固定長単位でアクセスされるので、検索の際にもメモリ上に存在することになる。このように平均的に約半分が空き領域であるので、その分、メモリ常駐できるセル数が少なくなり、メモリの使用効率が下がって相対的に検索速度が低下することになる。
【００３４】
図５（ｃ）は、高速検索インデクスのノードをロードした状態を説明する図である。図５（ｃ）に示すように、インデクスロード領域は基本的にはすべてセルのデータで占められ、空き領域が存在しないため、検索にとっては、低速検索インデクスに比べてメモリの使用効率が大幅に向上する。すなわち、平均的には倍以上のメモリを実装した場合と等価になり、メモリの乏しい組込み機器においては極めて有利であることが分かる。
【００３５】
図６は、本実施形態の検索装置１００において、ユーザの操作に応じて生成されるデータベース３００のインデクスの状況を説明する図である。図６（ａ）は、写真撮影がまだ行われている段階のインデクスの状況を示す図である。図６（ａ）に示すように、表６０１に対応して低速検索インデクス６０２のみが存在し、低速検索インデクスに基づいて検索が行われる。写真撮影等によるデータの挿入は高速であるが、検索は低速となる。
【００３６】
図６（ｂ）は、写真撮影が終了した段階のインデクスの状況を示す図である。この状況では、撮影終了を検知して高速検索インデクス６０３が生成される。これ以降の検索は高速検索インデクスに基づいて高速に行われる。
【００３７】
図６（ｃ）は、高速検索インデクスを生成した後に、写真撮影が再開された段階のインデクスの状況を示す図である。写真撮影に基づいて新たなデータが表６０４に挿入され、インデクスに対応データが挿入される。このとき、高速検索インデクスへの挿入は低速なので行わず、代わりに、第３のインデクスとして低速検索インデクス追加分６０５にデータが挿入される。このとき、高速検索インデクス６０６を無効化することによりインデクスを無効化する。これ以降の検索は低速検索インデクス６０２と低速検索インデクス追加分６０５とに基づいて行われることになる。
【００３８】
図６（ｄ）は、再撮影後に撮影が終了した段階のインデクスの状況を示す図である。撮影終了を受けて高速検索インデクス６０８が再生成される。さらに今後の再撮影に備えて低速検索インデクス６０７に低速検索インデクス追加分６０５の内容がマージされる。
【００３９】
次に、上述の動作について、図７〜図１１のフローチャートを参照しながら説明する。なお、後述する図７〜図１１に示す各処理はＣＰＵ１０１の制御により行われる。
図７は、本実施形態の検索装置１００のＣＰＵ１０１による処理結果を示す処理手順の一例を示すフローチャートである。
まず、ステップＳ７０１は、システムの初期化処理であり、各種パラメータを初期化したり初期画面を表示部１０３に表示したりする処理である。次のステップＳ７０２は、タッチパネル等の入力部１０２から何らかのイベントが発生するのを待機する処理である。
【００４０】
イベントが発生すると、ステップＳ７０３において、ＣＰＵ１０１がこのイベントを判別する。その後、ステップＳ７０４において、イベントの種類に応じて各種の処理を行う。ステップＳ７０４で行う処理としては、図８の説明で後述する検索処理、図９の説明で後述する写真登録処理、図１０（ａ）の説明で後述するＳＤカード取り出し処理、図１０（ｃ）の説明で後述するその他の処理がある。なお、その他の処理としては、画面制御処理、写真撮影処理などの処理がある。
【００４１】
次のステップＳ７０５は、上記の各処理の処理結果や処理終了を通知する画面を各処理の指示に従って表示部１０３に表示する処理である。例えば、検索結果を出力する画面表示、エラーがあった場合のエラー表示、正常な処理が行われた場合の画面表示など通常広く行われる処理である。
【００４２】
図８は、ステップＳ７０３の判別結果が検索処理である場合のステップＳ７０４における検索処理手順の一例を示すフローチャートである。
まず、ステップＳ８０１において、どのようなインデクスが存在し、有効あるいは無効であるかを調査する。そして、ステップＳ８０２において高速検索インデクスが存在し、かつ有効であるかどうかを判定する。この判定の結果、高速検索インデクスが存在し、かつ有効である場合はステップＳ８０３に分岐し、高速検索インデクスが存在しないまたは無効である場合はステップＳ８０４に分岐する。
【００４３】
ステップＳ８０３においては、高速検索インデクスを使用して検索を実行し、検索結果を求める。そして、検索結果を出力し、処理を終了する。一方、ステップＳ８０４においては、低速検索インデクスを利用して検索を実行し、検索結果を求める。そして、ステップＳ８０５において、図６（ｃ）に示した低速検索インデクス追加分が存在するかどうかを判定する。この判定の結果、低速検索インデクス追加分が存在しない場合は、そこまでの検索結果を出力し、処理を終了する。
【００４４】
一方、ステップＳ８０５の判定の結果、低速検索インデクス追加分が存在する場合は、ステップＳ８０６において、低速検索インデクス追加分を使用した検索も実行し、検索結果を求める。その後、検索結果を先の低速検索インデクスを使用した検索結果とマージする。これにより低速検索インデクスと低速検索インデクス追加分との両方のインデクスに基づいた検索結果がマージされることになる。そして、マージされた検索結果を出力し、処理を終了する。図８に示すフローチャートの処理が終了すると、図７のステップＳ７０５では、検索結果を表示部１０３に表示することになる。
【００４５】
図９は、ステップＳ７０３の判別結果が写真登録処理である場合のステップＳ７０４における写真登録処理の手順一例を示すフローチャートである。
ステップＳ９０１において、登録する写真データをコンテンツ１１１に登録するとともに、検索に使用される属性を表に登録する。そして、ステップＳ９０２において、高速検索インデクスが存在するかどうかを判定する。この判定の結果、高速検索インデクスが存在すする場合はステップＳ９０４に進み、高速検索インデクス存在しない場合はステップＳ９０３に進む。
【００４６】
ステップＳ９０３においては、属性を低速検索インデクスに登録、すなわち低速検索インデクスに挿入し、ステップＳ９０９にスキップする。一方、ステップＳ９０４においては、高速検索インデクスが存在する場合の処理であり、高速検索インデクスが有効であるかどうかを判定する。この判定の結果、高速検索インデクスが有効である場合は、ステップＳ９０５において、高速検索インデクスを無効化し、その後、ステップＳ９０６に進む。一方、ステップＳ９０４の判定の結果、高速検索インデクスが無効である場合は、ステップＳ９０６に進む。
【００４７】
次に、ステップＳ９０６において、低速検索インデクス追加分が既に存在しているかどうかを判定する。この判定の結果、低速検索インデクス追加分が存在する場合はステップＳ９０８にスキップする。一方、ステップＳ９０６の判定の結果、低速検索インデクス追加分が存在しない場合は、ステップＳ９０７において、低速検索インデクス追加分を生成し、ステップＳ９０８に進む。
【００４８】
次に、ステップＳ９０８において、属性を低速検索インデスク追加分に挿入する。そして、ステップＳ９０９において、図１０（ｄ）の説明で後述する無挿入段階検知処理、すなわち、今後のデータの挿入が起こりそうにないかどうかを判定して起こりそうにない場合に高速検索インデクスを生成するインデクス生成処理を行い、処理を終了する。
【００４９】
図１０（ａ）は、ステップＳ７０３の判別結果がＳＤカード取り出し処理である場合のステップＳ７０４におけるＳＤカード取り出し処理の手順の一例を示すフローチャートである。
ＳＤカードの取り出しがオペレータから指示されると処理を開始する。そして、ステップＳ１００１において、図１０（ｂ）の説明で後述する高速検索インデクスを生成する処理を行う。この処理は、物理的にＳＤカードを取り出す前に行う。このように高速検索インデクスが生成された後に、ステップＳ１００２において、物理的なＳＤカードの取り出しに関わる処理を行い、処理を終了する。具体的には、ＳＤカードのイジェクト処理、あるいは、ＳＤカードが取り出し可能であることを表示部１０３に表示する処理などである。
【００５０】
図１０（ｂ）は、図１０（ａ）のステップＳ１００１及び後述する図１０（ｄ）のステップＳ１０１５における高速検索インデクスを生成する詳細な処理手順の一例を示すフローチャートである。
まず、ステップＳ１００３において、低速検索インデクス追加分が存在するかどうかを判定する。この判定の結果、低速検索インデクス追加分が存在しない場合はステップＳ１００５にスキップし、低速検索インデクス追加分が存在する場合はステップＳ１００４に進む。
【００５１】
ステップＳ１００４においては、低速検索インデクス追加分を低速検索インデクスにマージする処理を行う。そして、ステップＳ１００５において、高速検索インデクスが存在するかどうかを判定する。この判定の結果、高速検索インデクスが存在する場合はステップＳ１００６に進み、高速検索インデクスが存在しない場合はステップＳ１００７に進む。
【００５２】
ステップＳ１００６においては、高速検索インデクスが有効であるかどうかを判定する。この判定の結果、高速検索インデクスが有効である場合は処理を終了し、高速検索インデクスが有効でない場合はステップＳ１００７に進む。そして、ステップＳ１００７において、図１１の説明で後述する低速検索インデクスから高速検索インデクスを作成する処理を実行する。その後、処理を終了する。
【００５３】
図１０（ｃ）は、ステップＳ７０３の判別結果がその他の処理である場合のステップＳ７０４における処理手順の一例を示すフローチャートである。
ステップＳ１００８において、イベントの種類に応じて定まる処理を遂行する。例えば、画面制御関係のイベントであれば画面制御処理、写真撮影関係のイベントであれば写真撮影処理を遂行することになる。そして、ステップＳ１００９において、図１０（ｄ）の説明で後述する無挿入段階検知処理、すなわち、今後のデータの挿入が起こりそうにないかどうかを判定して起こりそうにない場合に高速検索インデクスを生成する処理を行い、処理を終了する。
【００５４】
図１０（ｄ）は、図９のステップＳ９０９及び図１０（ｃ）のステップＳ１００９における無挿入段階検知処理の詳細な処理手順の一例を示すフローチャートである。
まず、ステップＳ１０１０において、ＳＤカードへデータの挿入が行われた直近の日時情報を、挿入されたデータから取得する。そして、ステップＳ１０１１において、その日時が所定の日よりも以前であるかどうかを判定する。この判定の結果、所定の日よりも以前である場合、すなわち、長期間ＳＤカードへデータの挿入が行われていない場合は、ステップＳ１０１５に進み、図１０（ｂ）で説明した高速検索インデクスを作成する処理を行い、処理を終了する。
【００５５】
一方、ステップＳ１０１１の判定の結果、所定の日よりも以前でない場合は、ステップＳ１０１２において、ＳＤカードの使用可能な残り容量を算出する。そして、ステップＳ１０１３において、その残り容量が所定サイズ以下であるかどうかを判定する。この判定の結果、残り容量が所定サイズ以下である場合は、前述のステップＳ１０１５に進み、残り容量が所定サイズを超えている場合はステップＳ１０１４に進む。そして、ステップＳ１０１４において、ＳＤカードにライトプロテクト状態、すなわち書込み禁止が設定されているかどうかを判定する。この判定は、ＳＤカードの特定の領域を読み出してフラグを判定することにより行うことができる。
【００５６】
この判定の結果、ライトプロテクト状態である場合は、前述のステップＳ１０１５に進み、ライトプロテクト状態でない場合は、処理を終了する。
【００５７】
図１１は、図１０（ｂ）のステップＳ１００７における低速検索インデクスから高速検索インデクスを作成する詳細な処理手順の一例を示すフローチャートである。
まず、ステップＳ１１０１において、低速検索インデクス及び高速検索インデクスの最下層の最初のノードを設定する。すなわち、低速検索インデクスの最下層の最初のノードをカレントノードとしてポインタを設定して高速検索インデクスの最下層の最初のノードを生成し、カレントノードと設定する。
【００５８】
次に、ステップＳ１１０２において、低速検索インデクスのカレントノードの最初のセルをカレントセルとしてポインタを設定する。そして、ステップＳ１１０３において、低速検索インデクスの最下層のすべてのノードについて処理が終了したかどうかを判定する。この判定の結果、最下層のすべてのノードについて処理が終了した場合はステップＳ１１１２に進む。
【００５９】
一方、ステップＳ１１０３の判定の結果、最下層のすべてのノードについて処理が終了していない場合は、ステップＳ１１０４において、低速検索インデクスのカレントノードからカレントセルを１つ取得する。そして、ステップＳ１１０５において低速検索インデクスの１つのカレントノードからすべてのセルを取得したかどうか判定する。この判定の結果、すべてのセルを取得した場合はステップＳ１１１１において、低速検索インデクスのカレントノードが次のノードを指すようポインタをずらし、ステップＳ１１０２に戻る。一方、ステップＳ１１０５の判定の結果、すべてのセルを取得していない場合はステップＳ１１０６に進む。
【００６０】
次に、ステップＳ１１０６において、高速検索インデクスのカレントノードの容量が満タンになっているかどうかを判定する。この判定の結果、容量が満タンになっている場合はステップＳ１１０７に進み、容量にまだ余裕がある場合はステップＳ１１０８にスキップする。ステップＳ１１０７においては、高速検索インデクスの次のノードを生成し、カレントノードとする。
【００６１】
次に、ステップＳ１１０８において、高速検索インデクスのカレントノードにステップＳ１１０４で取得したセルの内容を付加する。そして、ステップＳ１１０９において、高速検索インデクスのカレントノードのノードＩＤ及び先頭キーの情報を記録したノードＩＤ／先頭キー対応表の情報を更新する。そして、ステップＳ１１１０において、低速検索インデクスのカレントノードのカレントセルが次のセルを指すようポインタをずらし、ステップＳ１１０４に戻る。
【００６２】
一方、ステップＳ１１１２においては、高速検索インデクスの上位層の最初のノードを設定する。すなわち、高速検索インデクスの上位層の最初のノードを生成し、カレントノードとする。次に、ステップＳ１１１３において、ノードＩＤ／先頭キー対応表を参照し、高速検索インデクスの下層ノードの先頭キーとノードＩＤとからなるセルを生成し、高速検索インデクスのカレントノードにセルの内容を付加していく。そして、ステップＳ１１１４において、カレントノードのノードＩＤ及び先頭キーの情報を記録したノードＩＤ／先頭キー対応表の情報を更新する。
【００６３】
次に、ステップＳ１１１５において、カレントノードの容量が満タンになったかどうかを判定する。この判定の結果、容量にまだ余裕がある場合は、ステップＳ１１１７に進み、容量が満タンになった場合はステップＳ１１１６に進み、次の上位層ノードを設定し、カレントノードとする。
【００６４】
次に、ステップＳ１１１７において、高速検索インデクスのすべての下層ノードに対して処理が終了したかどうかを判定する。この判定はどこからもリンクされないノードが唯一になったかどうか（すなわちルートノードのみになったかどうか）を判定することにより行われる。この判定の結果、すべての下層ノードに対して処理が終了した場合は処理を終了する。一方、ステップＳ１１１７の判定の結果、全ての下層ノードに対して処理が終了していない場合は、ステップＳ１１１８において、次のどこからもリンクされない最も下層のノードを取得してカレントノードとし、ステップＳ１１１３に戻る。
【００６５】
以上のように本実施形態によれば、データの挿入が発生する可能性のある段階においては、インデクスに空き領域を十分にとって挿入が高速となるようにする。そして、挿入が発生する可能性が低くなった段階を検知して、インデクスの空き領域を大幅に削減し、挿入が低速となるが高速に検索可能なインデクスを生成するようにした。これにより、閲覧が主目的となった段階での検索を高速化できる。また、そのようにインデクスを検索に最適化した状態で、もう一度挿入が行われる場合にも、高速検索インデクスを無効化して元の低速検索インデクスを復活させ、そこにデータを挿入することにより、高速に挿入が可能となる。
【００６６】
（第２の実施形態）
第１の実施形態においては、高速検索インデクスを無効化した後に、低速検索インデクスから高速検索インデクスを再作成した。この場合、実際に再挿入するデータ量がごく少量であっても、高速検索インデクスの再作成に多大な時間がかかってしまう。本実施形態では、このような場合、途中で再挿入が行われるデータをロギングしておき、そのデータを高速検索インデクスに追加するよう制御する。本実施形態では、写真登録処理及び高速検索インデクス生成処理が第１の実施形態とは異なる。なお、それ以外については第１の実施形態と同様であるため、説明は省略する。
【００６７】
図１２は、本実施形態における写真登録処理の手順の一例を示すフローチャートである。なお、図１２に示す各処理は、ＣＰＵ１０１の制御により行われる。図１２のステップＳ９０１〜Ｓ９０９については、第１の実施形態で説明した図９のステップＳ９０１〜Ｓ９０９と同じであるため、説明は省略する。本実施形態では、ステップＳ９０５の処理を行った後、ステップＳ１２０１において、挿入されたデータをロギングする。
【００６８】
図１３は、本実施形態における高速検索インデクスを生成する詳細な処理手順の一例を示すフローチャートである。なお、図１３に示す各処理は、ＣＰＵ１０１の制御により行われる。
まず、ステップＳ１３０１において、高速検索インデクスが存在するかどうかを判定する。この判定の結果、高速検索インデクスが存在する場合はステップＳ１３０２に進み、高速検索インデクスが存在しない場合はステップＳ１３０４に進む。
【００６９】
次に、ステップＳ１３０２においては、高速検索インデクスが有効であるかどうかを判定する。この判定の結果、高速検索インデクスが有効である場合はステップＳ１３０５にスキップする。一方、ステップＳ１３０２の判定の結果、高速検索インデクスが有効でない場合は、ステップＳ１３０３において、ロギングされていたクエリを高速検索インデクスに反映する。高速検索インデクスであるため、データの挿入は低速となってしまうが、挿入件数がごく少量である場合には高速検索インデクスを最初から作り直すよりも処理時間が短くて済む。その後、ステップＳ１３０５に進む。
【００７０】
一方、ステップＳ１３０４においては、図１１に示した手順により低速検索インデクスから高速検索インデクスを生成する。そして、ステップＳ１３０５において、低速検索インデクス追加分が存在するかどうかを判定する。この判定の結果、低速検索インデクス追加分が存在しない場合は処理を終了する。一方、ステップＳ１３０５の判定の結果、低速検索インデクス追加分が存在する場合は、ステップＳ１３０６において、低速検索インデクス追加分を低速検索インデクスにマージし、処理を終了する。
【００７１】
以上のように本実施形態によれば、データの挿入が終了したと検知された後に、データの再挿入が行われる場合も、挿入するデータ数が少ない場合には、データを再挿入した後の高速検索インデクスの再作成時間を短縮することができる。
【００７２】
（その他の実施形態）
以上、実施形態を詳述したが、本発明は、例えば、システム、装置、方法、プログラムもしくは記憶媒体等としての実施態様をとることが可能である。具体的には、複数の機器から構成されるシステムに適用しても良いし、また、一つの機器からなる装置に適用しても良い。
【００７３】
なお、実施形態の検索装置１００のＣＰＵ１０１はプログラムを実行することで各種の手段として機能する。ＣＰＵ１０１と協調して動作するＡＳＩＣなどの制御回路がこれらの手段として機能してもよい。また、ＣＰＵ１０１と制御回路との協調によってこれらの手段が実現されてもよい。また、ＣＰＵ１０１は単一のものである必要はなく、複数であってもよい。この場合、複数のＣＰＵは分散して処理を実行する。また、複数のＣＰＵは単一のコンピュータに配置されていてもよいし、物理的に異なる複数のコンピュータに配置されていてもよい。なお、ＣＰＵがソフトウェアを実行することで実現する手段が専用の回路によって実現されてもよい。
【００７４】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００７５】
１０１  ＣＰＵ
１０７  ＲＯＭ
１０８  ＲＡＭ
１０９  ＤＩＳＫ
１１０  データベース
１１１  コンテンツ
【図１】
2013097536.tif 000003
【図２】
2013097536.tif 000004
【図３】
2013097536.tif 000005
【図４】
2013097536.tif 000006
【図５】
2013097536.tif 000007
【図６】
2013097536.tif 000008
【図７】
2013097536.tif 000009
【図８】
2013097536.tif 000010
【図９】
2013097536.tif 000011
【図１０】
2013097536.tif 000012
【図１１】
2013097536.tif 000013
【図１２】
2013097536.tif 000014
【図１３】
2013097536.tif 000015