JPH1074154A - ファイル管理装置 - Google Patents

Abstract

(57)【要約】 【課題】 外的には多層構造を維持しつつも内的にはフ
ラットなファイル管理を行うことにより多層化した場合
のファイルアクセスの効率改善を図る。 【解決手段】 任意の一つのディレクトリに含まれるす
べてのファイル名をフルパス付きで格納するとともにそ
れぞれのファイルの記憶装置内における格納位置の情報
をファイル名に関連付けて格納するテーブルと、入力フ
ァイル名がフルパス付きのときフルパス付きの入力ファ
イル名を用いてテーブルを検索し入力ファイル名の記憶
装置内における格納位置の情報を検索する検索手段とを
備える。ユーザ若しくはプログラムから見える入力ファ
イル名は、階層構造を持つ一般的なファイルシステムと
まったく変わりなく、外的な多層構造を維持でき、しか
も、任意の一つのディレクトリに含まれるすべてのファ
イル名が一つのテーブルで管理されるため、内的にフラ
ットなファイル管理とすることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、階層構造の入出力
管理機能（ファイルシステムとも言う）を有するＯＳ
（オペレーティングシステム）に適用できるファイル管
理装置に関する。

【０００２】

【従来の技術】パーソナルコンピュータやワークステー
ションにおけるファイル管理はＯＳによって行われてお
り、一般に多くのＯＳでは、多種多様なファイルを種類
や用途ごとに分類して階層的に管理できるようになって
いる。この種のＯＳの典型例としてＵＮＩＸのファイル
管理システムを説明すると、このファイル管理システム
では、ファイル名とその属性（作成日時、更新日時、種
類、アクセス権など）を記入した一覧表へのインデック
スの組からなる表（ディレクトリと言う）を持ち、ディ
レクトリ単位でファイルを管理する。ファイルの種類や
用途に応じた適切な名前のディレクトリを作成すること
により、ファイルの整理や分類を容易化できる。

【０００３】ディレクトリは、ファイルシステムを初期
化したときに自動的に作られるルートディレクトリと、
このルートディレクトリの下に任意に作られるサブディ
レクトリとがあり、サブディレクトリを階層化すること
によって、多層のファイルシステムを構築できる。ここ
で、任意のサブディレクトリのファイルを読み出すとき
は、パス名とファイル名を連結した文字列をファイル管
理システムに渡す。パス名とは、ルートディレクトリ
（またはカレントディレクトリ）から該当サブディレク
トリまでのすべてのディレクトリ名を連結した文字列で
あり、特に、ルートディレクトリを含む完全なパス名を
フルパスと言う。

【０００４】たとえば、図６に示すファイルシステムの
例では、“ｆｉｒｓｔ．ＴＸＴ”という名前のファイル
を“ｍａｓａｈｉｋｏ”という名前のサブディレクトリ
に格納しているが、この“ｍａｓａｈｉｋｏ”はルート
ディレクトリから数えて４階層目のサブディレクトリで
あるから、“ｆｉｒｓｔ．ＴＸＴ”のフルパス名は、
“／ｕｓｒ／ｈｏｍｅ／ｍａｓａｈｉｋｏ／”となる。
したがって、“ｆｉｒｓｔ．ＴＸＴ”を読み出すときの
ファイルシステムに渡す文字列は、“／ｕｓｒ／ｈｏｍ
ｅ／ｍａｓａｈｉｋｏ／ｆｉｒｓｔ．ＴＸＴ”となる。

【０００５】なお、パス名の先頭のスラッシュ
（“／”）はルートディレクトリを表わし、それ以外の
スラッシュは、各コンポーネント（“ｕｓｒ”、“ｈｏ
ｍｅ”、“ｍａｓａｈｉｋｏ”）のデリミタすなわち区
切り記号である。ファイル管理システムは、入力された
パス名のルートディレクトリ及び各コンポーネントを手
がかりに各階層のディレクトリを参照し、最終的に、対
象ファイルのファイルシステム内の格納位置情報（ＵＮ
ＩＸではｉｎｏｄｅ、ＭＳ−ＯＳではＦＣＢ）を特定す
る。各々のファイルの格納位置情報は番号によって区別
される。

【０００６】図６において、楕円の脇に記載した数字は
ｉｎｏｄｅ番号を表わしている（ただし、値は便宜
値）。上記の文字列（“／ｕｓｒ／ｈｏｍｅ／ｍａｓａ
ｈｉｋｏ／ｆｉｒｓｔ．ＴＸＴ”）をファイル管理シス
テムに与えると、ファイル管理システムは、まず、ルー
トディレクトリから“ｕｓｒ”ディレクトリのｉｎｏｄ
ｅ番号（“１０”）を探し出し、次いで、“ｕｓｒ”デ
ィレクトリから“ｈｏｍｅ”ディレクトリのｉｎｏｄｅ
番号（“１２３”）を探し出し、次いで、“ｈｏｍｅ”
ディレクトリから“ｍａｓａｈｉｋｏ”ディレクトリの
ｉｎｏｄｅ番号（“６３”）を探し出し、最後に、“ｍ
ａｓａｈｉｋｏ”ディレクトリから対象ファイル（“ｆ
ｉｒｓｔ．ＴＸＴ”）のｉｎｏｄｅ番号（“５００”）
を探し出すという処理を順次に実行する。

【０００７】

【発明が解決しようとする課題】しかしながら、かかる
従来のファイル管理装置にあっては、ファイルの種類や
用途に応じた適切な名前のディレクトリを作成すること
により、ファイルの整理や分類を容易化できる点で好都
合であるが、ディレクトリの階層数に比例してディレク
トリの検索回数が増えるため、多層化した場合にファイ
ルアクセスの効率が悪くなるという問題点があった。

【０００８】そこで、本発明は、外的には多層構造を維
持しつつも内的にはフラットなファイル管理を行うこと
により、多層化した場合のファイルアクセスの効率改善
を図ることを課題とする。

【０００９】

【課題を解決するための手段】本発明の上記課題は、任
意の一つのディレクトリに含まれるすべてのファイル名
をフルパス付きで格納するとともにそれぞれのファイル
の記憶装置内における格納位置の情報をファイル名に関
連付けて格納するテーブルと、入力ファイル名がフルパ
ス付きのとき該フルパス付きの入力ファイル名を用いて
前記テーブルを検索し該入力ファイル名の記憶装置内に
おける格納位置の情報を検索する検索手段と、を備える
ことによって達成できる。

【００１０】また、入力ファイル名がフルパス付きでな
いとき該入力ファイル名に前記一つのディレクトリのフ
ルパス名を連結してフルパス付きの入力ファイル名を生
成する生成手段を備えることが望ましい。また、前記テ
ーブルは、検索効率の点でハッシュテーブルであること
が望ましい。これらの手段によれば、ユーザ若しくはプ
ログラムから見える入力ファイル名は、階層構造を持つ
一般的なファイルシステムとまったく変わりなく、外的
な多層構造を維持でき、しかも、任意の一つのディレク
トリに含まれるすべてのファイル名が一つのテーブルで
管理されるため、内的にフラットなファイル管理とする
ことができる。したがって、多層化した場合でも一つの
テーブルを検索すればよいから、ファイルアクセスの効
率を改善できる。

【００１１】

【発明の実施の形態】以下、本発明の実施例を図面に基
づいて説明する。図１〜図３は本発明に係るファイル管
理装置の一実施例を示す図である。なお、本実施例のフ
ァイル管理装置は、パーソナルコンピュータやワークス
テーション等のハードウエアと、そのハードウエア上で
動作するＯＳやドライバプログラム等のソフトウエアと
の有機的結合によって仮想的に実現されるもので、実体
は存在しない。

【００１２】本実施例のファイル管理装置が具備すべき
特徴的な事項は、以下の説明でも明らかになるが、少な
くとも次の三つである。 任意の一つのディレクトリに含まれるすべてのファ
イル名をフルパス付きで格納するとともにそれぞれのフ
ァイルの記憶装置内における格納位置の情報をファイル
名に関連付けて格納するテーブル 入力ファイル名がフルパス付きでないとき、該入力
ファイル名に前記一つのディレクトリのフルパス名を連
結してフルパス付きの入力ファイル名を生成する生成手
段 入力ファイル名がフルパス付きのときは該フルパス
付きの入力ファイル名を用いて、または、入力ファイル
名がフルパス付きでないときは前記生成手段の出力を用
いて前記テーブルを検索し該入力ファイル名の記憶装置
内における格納位置の情報を検索する検索手段 これらの事項は、パーソナルコンピュータやワークステ
ーション等の特長（汎用性や拡張性）を考慮すると、ソ
フトウエアの改修や追加によって実現するのが実際的で
あるが、場合によっては、ハードウエアの改修や追加に
よって実現してもよいことはもちろんである。

【００１３】図１は、上記事項のとを実現するため
のソフトウエアの要部フローチャートである。このフロ
ーチャートにおいて、１は、ユーザによって指定され若
しくはプログラムタスクによって作られたファイル名を
取り込むステップである。このステップで入力されるフ
ァイル名は、（１）パス名を持たないファイル名〔例：
“ｆｉｒｓｔ．ＴＸＴ”〕、（２）完全なパス名を持つ
ファイル名〔例：“／ｕｓｒ／ｈｏｍｅ／ｍａｓａｈｉ
ｋｏ／ｆｉｒｓｔ．ＴＸＴ”〕、（３）不完全なパス名
を持つファイル名………カレントディレクトリを示すコ
ンポーネント（．）や親ディレクトリを示すコンポーネ
ント（．．）を含むパス名を持つもの………のいずれか
である。なお、スペルミス等による正しくないファイル
名も存在するが、説明の簡素化のために無視する。

【００１４】２は、入力ファイル名のコンポーネント数
が「１」であるか否かを判定するステップであり、コン
ポーネント数＝１の場合は、カレントディレクトリ直下
のファイルを検索することになり、従来どおりのファイ
ルシステムを用いてもファイルアクセスの効率をそれぼ
と低下しないことから、ステップ３で従来どおりの方法
でファイル検索を行うというものである。なお、カレン
トディレクトリ直下のファイル数が多い場合、従来どお
りの手法では効率が悪くなるおそれがあるから、ステッ
プ２にファイル数の判定を加えてもよい。

【００１５】４は、入力されたファイル名がフルパス付
きか否かを判定するステップである。すなわち、完全な
パス名を持つファイル名〔例：“／ｕｓｒ／ｈｏｍｅ／
ｍａｓａｈｉｋｏ／ｆｉｒｓｔ．ＴＸＴ”〕であるか否
かを判定するステップである。フルパス付きでない場合
（ステップ４の判定結果がＮＯの場合）は、入力ファイ
ル名にフルパスを付加してフルパス付きのファイル名を
生成する。５〜７は、そのためのステップである。すな
わち、ステップ５で、入力ファイル名にカレントディレ
クトリのコンポーネント（．）が含まれているか否かを
判定し、含まれている場合には、ステップ６で、そのコ
ンポーネント（．）を取り除き、ステップ７で、カレン
トディレクトリ文字列（便宜的に“／ｕｓｒ／ｈｏｍｅ
／ｍａｓａｈｉｋｏ／”とする）と入力ファイル名（便
宜的に“ｆｉｒｓｔ．ＴＸＴ”とする）を連結して、完
全なパス名を持つファイル名（“／ｕｓｒ／ｈｏｍｅ／
ｍａｓａｈｉｋｏ／ｆｉｒｓｔ．ＴＸＴ”）を生成す
る。したがって、これらのステップ５〜７は、本実施例
のファイル管理装置の必須の事項の一つである「生成手
段」を具現化したものである。

【００１６】８〜１１は、入力されたフルパス付きのフ
ァイル名、または、生成されたフルパス付きのファイル
名に、親ディレクトリのコンポーネント（．．）が含ま
れている場合、当該コンポーネントの後ろに続く２文字
で同コンポーネントの文字列を上書きして取り除くステ
ップ（ステップ８、９）、及び、同ファイル名のデリミ
タ（“／”）が連続している場合、単一のデリミタに直
すステップ（ステップ１０、１１）である。

【００１７】１２〜１７は、本実施例のファイル管理装
置の必須の事項の一つである「検索手段」を具現化し
たものであり、ここでは、同装置の必須の事項の一つで
ある「テーブル」をハッシュテーブルとした場合の好
ましい構成を示してある。なお、ハッシュテーブルと
は、サーチの一手法であるハッシュサーチ（hash searc
h）に用いるインデックステーブルに相当するものであ
る。ハッシュサーチでは、実際のキーから作成した疑似
キーをインデックスとし、アクセスはインデックステー
ブルを介して行うため、エントリが多大になっても高速
なダイレクトサーチが可能である。

【００１８】１２は、ハッシュサーチの疑似キーを発生
するステップである。ここでは、フルパス付きファイル
名の文字列を実際のキーとし、いわゆるハッシュ関数を
使用して実際のキーから疑似キーを発生する。ここで、
Ｋを実際のキー、Ｒを疑似キー（ハッシュ値）とする
と、ハッシュ関数は、Ｒ＝Φ（Ｋ）で表わすことができ
る。Ｋは、フルパス付きファイル名の文字列に固有の値
であれば何でもよい。たとえば、同文字列を構成する各
文字コードの値の積をハッシュテーブルのサイズで割っ
た余りとすると、Ｒの値がテーブルのサイズに収まるか
ら好ましい。 （以下余白）

【００１９】説明の都合上、次の九つのファイル（Ａ〜
Ｉ）を考える。 これら九つのファイルのフルパス付きファイル名のハッ
シュ値を、次のとおり仮定する（値はすべて便宜値であ
る）。 （以下余白）

【００２０】 表２において、ファイルＣ、ファイルＧ及びファイルＩ
のハッシュ値が同じ（＝３２）である。また、ファイル
ＤとファイルＨのハッシュ値も同じ（＝４９）である。
このことは、ファイルＣ、Ｇ、Ｉ（またはファイルＤ、
Ｈ）の文字列をキーとするハッシュ値が同じであること
を意味し、いわゆるハッシュ値の衝突が発生することを
示している。

【００２１】図２は、ハッシュテーブル（テーブル）
の概念図である。このテーブルは、特に限定しないが、
０〜１６６までのレコードを有するテーブルであり、各
レコードはハッシュ値の衝突フラグフィールドとデータ
フィールドとを有している。０〜１６６のレコード番号
は表２のハッシュ値に対応する。たとえば、“／ｕｓｒ
／ｈｏｍｅ／Ａ”の場合のハッシュ値は「６７」である
から、６７番のレコードを検索（図１のステップ１３）
し、このレコードのハッシュ値の衝突フラグとデータフ
ィールドを読み込む。ここで、６７番のレコードの衝突
フラグはリセット状態（“１”以外）であり、この場合
のデータフィールドの値（“１２３１”）は、“／ｕｓ
ｒ／ｈｏｍｅ／Ａ”のｉｎｏｄｅ番号そのものを表わし
ている。

【００２２】したがって、一つのテーブルから読み出さ
れたｉｎｏｄｅ番号を用いて、ハードディスク内の“／
ｕｓｒ／ｈｏｍｅ／Ａ”の格納位置を特定（図１のステ
ップ１７）でき、外的にはファイル名の階層構造を維持
したまま、内的にフラットなファイル管理を実現でき、
多層化した場合のファイルアクセスの効率改善を図るこ
とができる。

【００２３】上記のとおり、ファイル名によってはハッ
シュ値が衝突することがある。このハッシュ値の衝突対
策を説明すると、たとえば、“／ｕｓｒ／ｈｏｍｅ／
Ｃ”の場合のハッシュ値は「３２」であるが、“／ｕｓ
ｒ／ｈｏｍｅ／Ｇ”及び“／ｕｓｒ／ｈｏｍｅ／Ｉ”の
ハッシュ値も同じである。図２において、このハッシュ
値（＝３２）と同番号のレコードの衝突フラグはセット
状態（“１”）にあり、そのデータフィールドの値（便
宜的に“ｘ”）がｉｎｏｄｅ番号でないことを示してい
る。すなわち、衝突フラグがセット状態（“１”）にあ
るレコードのデータフィールドの値（“ｘ”）は、ハッ
シュ値を同一にする“／ｕｓｒ／ｈｏｍｅ／Ｃ”、“／
ｕｓｒ／ｈｏｍｅ／Ｇ”及び“／ｕｓｒ／ｈｏｍｅ／
Ｉ”のそれぞれのｉｎｏｄｅ番号を収めたサブテーブル
の開始アドレスを示す情報である。

【００２４】図３は、サブテーブルの概念図であり、ア
ドレスｘに“／ｕｓｒ／ｈｏｍｅ／Ｃ”のｉｎｏｄｅ番
号（“６３３９”）が、また、アドレスｘ＋１に“／ｕ
ｓｒ／ｈｏｍｅ／Ｇ”のｉｎｏｄｅ番号（“４４９
３”）が、さらに、アドレスｘ＋２に“／ｕｓｒ／ｈｏ
ｍｅ／Ｉ”のｉｎｏｄｅ番号（“７７７”）が格納され
ている。なお、サブテーブルのラストフラグは、ハッシ
ュ値を同一にするファイルの最後を示すものである
（“１”で最後）。

【００２５】たとえば、“／ｕｓｒ／ｈｏｍｅ／Ｇ”を
検索する場合は、まず、ハッシュテーブルの３２番のレ
コードから“ｘ”を取り出し、アドレスｘから順次にサ
ブテーブルを検索（図１のステップ１５）する。ここで
は、サブテーブルのアドレスｘ＋１に“／ｕｓｒ／ｈｏ
ｍｅ／Ｇ”が格納されているため、一致が判定（図１の
ステップ１６）される。したがって、サブテーブルから
読み出されたｉｎｏｄｅ番号を用いて、ハードディスク
内の“／ｕｓｒ／ｈｏｍｅ／Ｇ”の格納位置を特定（図
１のステップ１７）でき、外的にはファイル名の階層構
造を維持したまま、内的にフラットなファイル管理を実
現でき、多層化した場合のファイルアクセスの効率改善
を図ることができる。

【００２６】なお、以上は、ハッシュ値の衝突が起こり
得るという前提のもとで説明したが、ハッシュ値の衝突
を回避するようにハッシュ関数を定義するなどして衝突
を避ければ、図４に示すように、ハッシュテーブルから
フラグフィールドを取り除くことができる。この場合、
データフィールドの値はすべてｉｎｏｄｅ番号になる。

【００２７】または、ファイル数がそれほど大量でなけ
れば、図５に示すような順編成テーブルを採用すること
もできる。このテーブルのレコードは、フルパス付きの
ファイル名を格納する第１のデータフィールドと、その
ファイルのｉｎｏｄｅ番号を格納する第２のデータフィ
ールドとからなり、入力された（または生成手段によっ
て生成された）フルパス付きのファイル名に一致する文
字列を第１のデータフィールドから見つけ出し、そのレ
コードの第２のデータフィールドからｉｎｏｄｅ番号を
取り出すというものである。

【００２８】

【発明の効果】本発明によれば、外的には多層構造を維
持しつつも内的にはフラットなファイル管理を行うこと
ができる。したがって、多層化した場合のファイルアク
セスの効率改善を図ることができるという格別有利な効
果を奏することができ、特に、大量のファイルを管理す
るパーソナルコンピュータやワークステーション若しく
はデータ処理装置等に用いて好適な技術を提供できる。

【図面の簡単な説明】

【図１】一実施例の要部フローチャートである。

【図２】一実施例のハッシュテーブルの概念図である。

【図３】一実施例のサブテーブルの概念図である。

【図４】一実施例のハッシュテーブルの他の概念図であ
る。

【図５】一実施例のハッシュテーブルに代える順編成テ
ーブルの概念図である。

【図６】階層構造を持つファイルシステムの概念図であ
る。

【符号の説明】 ：テーブル ：生成手段 ：検索手段

Claims (3)

【特許請求の範囲】
1. 【請求項１】任意の一つのディレクトリに含まれるすべ
   てのファイル名をフルパス付きで格納するとともにそれ
   ぞれのファイルの記憶装置内における格納位置の情報を
   ファイル名に関連付けて格納するテーブルと、 入力ファイル名がフルパス付きのとき該フルパス付きの
   入力ファイル名を用いて前記テーブルを検索し該入力フ
   ァイル名の記憶装置内における格納位置の情報を検索す
   る検索手段と、を備えることを特徴とするファイル管理
   装置。
2. 【請求項２】任意の一つのディレクトリに含まれるすべ
   てのファイル名をフルパス付きで格納するとともにそれ
   ぞれのファイルの記憶装置内における格納位置の情報を
   ファイル名に関連付けて格納するテーブルと、 入力ファイル名がフルパス付きでないとき該入力ファイ
   ル名に前記一つのディレクトリのフルパス名を連結して
   フルパス付きの入力ファイル名を生成する生成手段と、 入力ファイル名がフルパス付きのときは該フルパス付き
   の入力ファイル名を用いて、または、入力ファイル名が
   フルパス付きでないときは前記生成手段の出力を用いて
   前記テーブルを検索し該入力ファイル名の記憶装置内に
   おける格納位置の情報を検索する検索手段と、を備える
   ことを特徴とするファイル管理装置。
3. 【請求項３】前記テーブルがハッシュテーブルであるこ
   とを特徴とする請求項１または請求項２記載のファイル
   管理装置。