(57)【要約】【課題】ツリー構造を有するデータベースにおいて，高速にツリー構造を構築させることのできるプログラムを提供する。【解決手段】ツリー構造を有するデータベースの各ノードを，ルートノード，親ノード，階層情報およびソート情報をフィールドに持つレコードとして所定の記憶領域に記憶させる。記憶された複数のレコードのソート情報をもとに並び替えることにより元のツリー構造を構築することができるため，再帰処理によりツリー構造をたどることなく高速かつ容易にツリー構造を構築することができる。【選択図】図３
2013239050.tif 000002
【特許請求の範囲】
【請求項１】
木構造データベース構造を所定の形式で保持させるプログラムであって，
コンピュータを，
前記木構造データベースの最上位ディレクトリ情報を取得する最上位ディレクトリ情報取得手段，
前記最上位ディレクトリよりも下位である任意のディレクトリまたはファイルを基準として，その親のディレクトリ情報を取得する親ディレクトリ情報取得手段，
前記任意のディレクトリまたはファイルの階層を取得する階層情報取得手段，
前記任意のディレクトリまたはファイルの情報を含むソート情報を生成するソート情報生成手段，
前記任意のディレクトリまたはファイルの情報，取得した最上位ディレクトリ情報，親ディレクトリ情報，階層情報および生成したソート情報をフィールドに持つレコードを所定の記憶手段に記憶させるレコード記憶手段，
前記最上位ディレクトリに含まれる全ディレクトリおよび全ファイルに対し前記レコード記憶手段を実行させる走査手段，
記憶された全レコードのうち，最上位ディレクトリ情報を同一とするレコードについて，当該レコードのソート情報にしたがって並び替えるソート手段，
として機能させるプログラム。
【請求項２】
木構造データベース構造を所定の形式で保持させるプログラムであって，
コンピュータを，
前記木構造データベースの最上位ノード情報を取得する最上位ノード情報取得手段，
前記最上位ノードよりも下位である任意のノードを基準として，その親のノード情報を取得する親ノード情報取得手段，
前記任意のノードの階層を取得する階層情報取得手段，
前記任意のノードの情報を含むソート情報を生成するソート情報生成手段，
前記任意のノードの情報，取得した最上位ノード情報，親ノード情報，階層情報および生成したソート情報をフィールドに持つレコードを所定の記憶手段に記憶させるレコード記憶手段，
前記最上位ノードに含まれる全ノード対し前記レコード記憶手段を実行させる走査手段，
記憶された全レコードのうち，最上位ノード情報を同一とするレコードについて，当該レコードのソート情報にしたがって並び替えるソート手段，
として機能させるプログラム。
【請求項３】
木構造データベース構造を所定の形式で保持させるプログラムであって，
コンピュータを，
少なくとも自身よりも下位のノードを含む第１の所定ノードの情報を取得する第１の所定ノード情報取得手段，
前記第１の所定ノードよりも下位である第２の所定ノードを基準として，その親ノード情報を取得する親ノード情報取得手段，
前記第２の所定ノードの階層を取得する階層情報取得手段，
前記木構造データベースにおける前記第２の所定ノードの位置情報を含み，かつユニークであるソート情報を生成するソート情報生成手段，
前記第２の所定ノードの情報，取得した第１の所定ノード情報，親ノード情報，階層情報および生成したソート情報をフィールドに持つレコードを所定の記憶手段に記憶させるレコード記憶手段，
前記第１の所定ノードに含まれる全ノードに対し前記レコード記憶手段を実行させる走査手段，
記憶された全レコードのうち，前記第１の所定ノード情報を同一とするレコードについて，当該レコードのソート情報にしたがって並び替えるソート手段，
として機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明はデータベースのプログラムに関し，特に，ツリー構造（木構造）データベースを高速に構築させるプログラムに関する。
【背景技術】
【０００２】
近年はあらゆる情報がデータベース化されており，情報量も増加の一途をたどっている。さらに，ＰＣやワークステーションといった従来の電子機器だけでなく，デジタルカメラなどの組み込み機器においてさえも，データベースを扱う機会が増加している。たとえば，デジタルカメラ上でストレージデバイスに蓄積された画像データを一覧表示させたり，ファイル操作したりすることが一般的に行われている。
【０００３】
データベースの多くは階層構造いわゆるツリー構造となっており，たとえばファイル管理の場合は，日付やファイル形式などといったデータの属性に応じたディレクトリごとにファイルが保持されている。この階層構造は，単に１つの親と子だけでなく，子の中にさらにディレクトリ（孫）が存在することもあり，複数の階層に及んでデータを保持していることもある。
【０００４】
ツリー構造は，深さが深くなるほどユーザの扱いが面倒になるため，通常はデータベースのツリー構造を視覚的に参照しながら操作することが一般的である。
【０００５】
非特許文献１には，階層構造を有するデータベースをツリー形式として表示する際に一般的に行われるディレクトリ走査処理が開示されている。具体的には，コンピュータは，最上位階層であるルートディレクトリを起点としてすべてのディレクトリを走査し，ディレクトリやファイルをリストアップしていく。ルートディレクトリの走査でディレクトリが見つかれば，さらにそのディレクトリ内を走査するという動作を繰り返し行い，ディレクトリがなくなった時点で最初に見つかったディレクトリの走査が完了となる。勿論，ルートディレクトリに他のディレクトリがあれば，これも同様に走査を行う。このような走査を行うことでツリー構造をコンピュータ内部で構築・保持し，最終的にツリー形式でユーザに閲覧させることができるわけである。なお，上述したリストアップの手法は再帰呼び出し処理と呼ばれ，ツリー構造の走査プログラムではごく一般的かつ定石的に用いられている。
【先行技術文献】
【特許文献】
【０００６】
【非特許文献１】アイティメディア株式会社  ホームページ＜URL :http://www.atmarkit.co.jp/fcoding/articles/algorithm/03/algorithm03a.html＞
【０００７】
上述したように，階層構造のデータベースをツリー形式で視覚的に表示することは一般的に行われている。つまり，データベースを扱う電子機器にとって，ツリー構造の走査プログラムは必須のプログラムといえる。一方，必須ではあるものの，そのプログラムの内部では，すでに述べたように再帰呼び出し処理が行われており，この処理にかかる電子機器への負担が問題となっている。このような問題は，特に，ハードウェア資源の乏しい組み込み機器のようなものにとっては，さらに深刻なものとなる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本願発明はかかる課題を解決するものである。すなわち，ツリー構造を有するデータベースにおいて，高速にツリー構造を構築させることのできるプログラムを提供することである。
【課題を解決するための手段】
【０００９】
本願発明にかかる第１の形態は，木構造データベース構造を所定の形式で保持させるプログラムであって，コンピュータを，木構造データベースの最上位ディレクトリ情報を取得する最上位ディレクトリ情報取得手段，最上位ディレクトリよりも下位である任意のディレクトリまたはファイルを基準として，その親のディレクトリ情報を取得する親ディレクトリ情報取得手段，任意のディレクトリまたはファイルの階層を取得する階層情報取得手段，任意のディレクトリまたはファイルの情報を含むソート情報を生成するソート情報生成手段，任意のディレクトリまたはファイルの情報，取得した最上位ディレクトリ情報，親ディレクトリ情報，階層情報および生成したソート情報をフィールドに持つレコードを所定の記憶手段に記憶させるレコード記憶手段，最上位ディレクトリに含まれる全ディレクトリおよび全ファイルに対しレコード記憶手段を実行させる走査手段，記憶された全レコードのうち，最上位ディレクトリ情報を同一とするレコードについて，当該レコードのソート情報にしたがって並び替えるソート手段，として機能させるプログラムである。
【００１０】
本願発明にかかる第２の形態は，木構造データベース構造を所定の形式で保持させるプログラムであって，コンピュータを，木構造データベースの最上位ノード情報を取得する最上位ノード情報取得手段，最上位ノードよりも下位である任意のノードを基準として，その親のノード情報を取得する親ノード情報取得手段，任意のノードの階層を取得する階層情報取得手段，任意のノードの情報を含むソート情報を生成するソート情報生成手段，任意のノードの情報，取得した最上位ノード情報，親ノード情報，階層情報および生成したソート情報をフィールドに持つレコードを所定の記憶手段に記憶させるレコード記憶手段，最上位ノードに含まれる全ノード対しレコード記憶手段を実行させる走査手段，記憶された全レコードのうち，最上位ノード情報を同一とするレコードについて，当該レコードのソート情報にしたがって並び替えるソート手段，として機能させるプログラムである。
【００１１】
本願発明にかかる第３の形態は，木構造データベース構造を所定の形式で保持させるプログラムであって，コンピュータを，少なくとも自身よりも下位のノードを含む第１の所定ノードの情報を取得する第１の所定ノード情報取得手段，第１の所定ノードよりも下位である第２の所定ノードを基準として，その親ノード情報を取得する親ノード情報取得手段，第２の所定ノードの階層を取得する階層情報取得手段，木構造データベースにおける第２の所定ノードの位置情報を含み，かつユニークであるソート情報を生成するソート情報生成手段，第２の所定ノードの情報，取得した第１の所定ノード情報，親ノード情報，階層情報および生成したソート情報をフィールドに持つレコードを所定の記憶手段に記憶させるレコード記憶手段，第１の所定ノードに含まれる全ノードに対しレコード記憶手段を実行させる走査手段，記憶された全レコードのうち，第１の所定ノード情報を同一とするレコードについて，当該レコードのソート情報にしたがって並び替えるソート手段，として機能させるプログラムである。
【発明の効果】
【００１２】
本願発明に開示のプログラムは，必要に応じて都度再帰呼び出しを行うのでなく，予めツリー構造を有するデータベースの各ノードを，ルートノード，親ノード，階層情報およびソート情報をフィールドに持つ明示的なレコードとして所定の記憶領域に記憶させる。記憶された複数のレコードのソート情報をもとに並び替えることにより元のツリー構造を構築することができるため，再帰処理によりツリー構造をたどることなく高速かつ容易にツリー構造を構築することができる。
【発明を実施するための形態】
【００１３】
以下では図面を参照し本願発明に係る実施例を説明する。
［実施例１］
［ツリー構造データベースの全体図］
【００１４】
図１は本願発明にかかるプログラムが処理対象とするツリー構造データベースの全体図である。なお，図１は例示であるため，いわゆる階層構造を有するものであれば本願発明はすべてに適用可能である。
【００１５】
ルートディレクトリ１０１は，データベースの最も上位の階層に位置するディレクトリであり，通常は１つのボリュームに１つしか存在しない。本実施例ではルートディレクトリ１０１からの距離（深さ）を表すパラメータとして「階層」という概念を用いる。ルートディレクトリ１０１の階層は０（ゼロ）とする。
【００１６】
ディレクトリ１０２，ディレクトリ１０３，およびディレクトリ１０４は，ルートディレクトリ１０１の子ディレクトリである。つまり，ディレクトリ１０２〜ディレクトリ１０４の親ディレクトリはルートディレクトリ１０１となる。なお，これらのディレクトリの階層は親ディレクトリであるルートディレクトリ１０１の１つ下になるので，親ディレクトリの階層である０に１を加えて１となる。
【００１７】
ファイル１０５〜ファイル１０７は，ディレクトリ１０２に属するファイルである。つまり，これらのファイルの親ディレクトリはディレクトリ１０２となる。階層は親ディレクトリであるディレクトリ１０２の階層である１に１を加えて２となる。
【００１８】
ファイル１０８の親ディレクトリはディレクトリ１０３であり，ファイル１０９の親ディレクトリはディレクトリ１０４である。これらのファイルの階層は上述した他のファイルと同じく２となる。
［プログラムの動作フロー］
【００１９】
図２は本願発明にかかるプログラムの動作フローである。本願発明の目的は，すでに述べたように，図１に示すようなツリー構造を高速に構築させることのできるプログラムを提供することである。以下では，このプログラムの詳細な動作フローを説明する。
【００２０】
図２から明らかなとおり，本願発明のプログラムは，テーブル構築タスクおよびツリー表示タスクの２つから構成されている。簡単にいうと，テーブル構築タスクはコンピュータの内部でデータベースのツリー構造を構築・保持させるために動作し，ツリー表示タスクは構築・保持されたツリー構造をツリー形式として視覚的に表示させるためのプログラムである。
【００２１】
まず，テーブル構築タスクから説明する。ステップ２０１にて先頭情報を取得する。ここで先頭情報とは，いわゆるルートディレクトリの名称のことである。ルートのことを先頭と呼んでいるだけである。ただし，後述するように先頭とは必ずしもルートディレクトリ１０１である必要はなく，必要に応じ任意のディレクトリを先頭とすることが可能である。
【００２２】
ステップ２０２にて，所定ディレクトリまたはファイル情報を取得する。これは，所定のディレクトリまたはファイルの名称を取得することを意味する。所定とは，ルートディレクトリ１０１以外の全てを意味する。
【００２３】
ステップ２０３にて親ディレクトリ情報を取得する。つまり，ステップ２０２で取得した所定のディレクトリまたはファイル情報の親となるディレクトリの名称を取得する。
【００２４】
ステップ２０４にて階層情報を取得する。ここで取得する階層情報はステップ２０２で取得した所定のディレクトリまたはファイルの階層のことである。
【００２５】
ステップ２０５にてソート情報を生成する。ソート情報とはステップ２０２で取得した所定のディレクトリまたはファイルに固有の（ユニークな）情報であり。本実施例では当該ディレクトリおよびファイル名称を含む情報をソート情報として生成とする（具体例は後述）。なお，このソート情報は本願発明にとって必須のものであり，重要な役割を果たす。
【００２６】
ステップ２０６にてレコードを記憶させる。このレコードとは，ステップ２０１〜ステップ２０５にて取得および生成した情報をフィールドとするものであり，これを記憶手段２２１に記憶させる。こうしておくことで，必要に応じて都度再帰呼び出しを行う代わりにこのテーブル（レコード群）を参照して高速にツリー構造を構築させることが可能となる。
【００２７】
ステップ２０７にて他のディレクトリまたはファイルが存在するかどうかを判断する。つまり，ステップ２０２で取得した所定のディレクトリおよびファイル以外のものが存在するかどうかを判断し，まだ残っていればステップ２０１に戻り，そうでなければ本動作フローは終了する。このようにして，ルートディレクトリ１０１，つまり先頭情報に含まれる全ディレクトリおよび全ファイルをレコードに持つテーブルが記憶領域２２１に記憶される。言い換えると，これらステップ２０１〜２０７を行うことにより図１で示したツリー構造がテーブルという形として記憶手段２２１に記憶されることとなる。
【００２８】
ここで，動作フローの説明をいったん終了し，図３を参照して記憶領域２２１に記憶されている情報（実際にはテーブル）を説明する。図から明らかなとおり。各レコードは先頭情報，親ディレクトリ情報，子情報，階層，およびソート情報をフィールドとしている。
【００２９】
全てのレコードは，図２のステップ２０２で取得した所定のディレクトリまたはファイルを基準とし，その親ディレクトリ情報，先頭情報，階層，およびソート情報，ならびに子情報自身をフィールドとしたものである。
【００３０】
先に，ソート情報はステップ２０２で取得した所定のディレクトリおよびファイル名称を含むと説明した。図３を参照すると明らかであるが，本実施例では，ソート情報として，単にルートディレクトリ（先頭情報）から自身のディレクトリまたはファイル，すなわち子情報までを示すパス情報としている。このような命名規則とすることによりソート情報は各レコードにユニークなものとすることができる。
【００３１】
もちろん，各レコードにユニークかつ実際のツリー構造を反映することが可能なものであれば，パス情報以外のものもソート情報として利用できる。つまり，図１のツリー構造における所定のディレクトリまたはファイルの位置情報をユニークに識別し当該ディレクトリまたはファイルを整列させることができるものであればどのようなものでもよい。たとえば単に１，２，３などの数字を割り当てることも可能である。
【００３２】
再び図２に戻り，残りのツリー表示タスクを説明する。ステップ２１１にて，ツリー表示の要求があったかどうかを判断する。通常は，他のプログラムからの要求であり，要求があれば，次のステップに進み，そうでなければ当該判断を繰り返す。
【００３３】
ステップ２１２にて同一先頭情報レコードを取得する。つまり，記憶手段２２１を参照して，先頭情報が一致するレコード全てを取得する。本実施例の場合，先頭情報にＲＯＯＴを持つレコードのことである。通常，先頭情報，つまりルートディレクトリが異なるとは，データベースが存在する記憶領域２２１のボリュームが異なることが多いが，それに限定されない。同じボリューム内であっても，それぞれを独立したツリーとして管理したい場合などは，先頭情報をルートディレクトリではなく任意のものにすることができる。つまり，どのディレクトリを先頭としてツリーを管理するかに依存するわけである。
【００３４】
ステップ２１３にて取得した各レコードのソート情報をもとにレコードを並び替える。ソート情報はパス情報となっているため，通常は，ツリー構造を反映した順に並び替えられる。
【００３５】
ステップ２１４にて並び替えたレコード情報をもとにツリー表示する。先のステップ２１３にて，既にツリー構造が反映れた状態でレコードが並んでいるため，ツリー表示のプログラムは単にレコードの先頭から順に表示さえすればよいわけである。
［実施例２］
【００３６】
本実施例ではデータベースにファイルが追加された場合を例示する。なお，ファイルの削除や移動等も以下で説明する方法を拡張すれば可能であるため説明を省略する。
【００３７】
図４は，実施例１で説明したデータベースにファイル４０１が追加された場合を示している。ファイル４０１の親ディレクトリはディレクトリ１０３であり，先頭情報はルートディレクトリ１０１である。なお，階層はファイル１０８と同じく２である。
【００３８】
図５の上部に記載のテーブルは，記憶領域２２１にて記憶されているテーブルに対して，ファイル４０１のレコードが追加される様子を示している。図に示す通りテーブルの末尾に追加される。その後，ソート情報をキーに並び替えることにより，下部に記載のテーブルのようになる。つまり，ツリーの実体と同じくファイル１０８（テーブル上ではＦ４）の次に位置する。これが可能なのは，ソート情報にパス情報を用いているためである。つまり，同じ先頭情報を持つレコードのソート情報をキーとして並び替えるだけで簡単かつ高速にツリー構造が再構築できるわけである。
【００３９】
別の例として，ファイルやディレクトリを削除する場合は，単にレコードを削除して並び替えればよいし，移動の場合は，削除と追加が行われるだけなので，それぞれを実施したあとに並び替えるだけでツリー構造の再構築が可能である。
［まとめ］
【００４０】
以上，本願発明にかかるプログラムの詳細を説明した。すなわち，本願発明に開示のプログラムは，必要の都度再帰呼び出しを行うのでなく，予めツリー構造を有するデータベースの各ノードを，ルートノード，親ノード，階層情報およびソート情報をフィールドに持つ明示的なレコードとして所定の記憶領域に記憶させる。記憶された複数のレコードのソート情報をもとに並び替えることにより元のツリー構造を構築することができるため，再帰処理によりツリー構造をたどることなく高速かつ容易にツリー構造を構築することができる。
【図面の簡単な説明】
【００４１】
【図１】ツリー構造データベースの全体図
【図２】プログラムの動作フロー
【図３】テーブル
【図４】ファイルを追加した場合のツリー構造
【図５】ファイルを追加した場合のテーブル
【符号の説明】
【００４２】
２０１  先頭情報取得
２０２  所定ディレクトリまたはファイル情報取得
２０３  親ディレクトリ情報取得
２０４  階層情報種痘
２０５  ソート情報生成
２０６  レコード記憶
２０７  他のディレクトリまたはファイルの存在判断
２１３  ソート情報をもとに並び替え
【図１】
2013239050.tif 000003
【図２】
2013239050.tif 000004
【図３】
2013239050.tif 000005
【図４】
2013239050.tif 000006
【図５】
2013239050.tif 000007