(57)【要約】【課題】粗く満たされたデータ格納装置用のディレクトリ構造を提供する。【解決手段】粗く満たされたデータ格納装置用のディレクトリ構造は、リンクリスト、二重リンクのリスト、スキップリスト、あるいは他の密に満たされていないリスト手法から構成される。粗く満たされたディレクトリ用にそのようなリストの１つまたは複数のハイアラーキレベルを使うことができる。ディレクトリがあるレベルまで満たされた時点で、ディレクトリを再構築することによってディレクトリ構造を従来の参照テーブルディレクトリに変換することができる。【選択図】図１
2006252421.tif 000002
【特許請求の範囲】
【請求項１】
データ格納装置のディレクトリを維持する方法であって、
粗いディレクトリ構造が変更されるべきであると判断するステップと、
前記粗いディレクトリ構造を密に満たされたディレクトリ構造に再構築するステップと、
から成る方法。
【請求項２】
請求項１に記載の方法であって、さらに
前記密に満たされたディレクトリ構造が変更されるべきであると判断するステップと、
前記密に満たされたディレクトリ構造を粗く満たされたディレクトリ構造に再構築するステップと、
から成る方法。
【請求項３】
請求項１に記載の方法であって、前記粗いディレクトリ構造は
前記アドレス指定可能なスペースの１つのアドレスと、記述子と、前記ディレクトリエントリの異なる一つを指示するポインタである少なくとも１つのリンクと、を有する複数の第一ディレクトリエントリと、
前記複数の第一ディレクトリエントリの少なくとも１つから成る少なくとも１つのボトムレベルリストと、
前記ボトムレベルリストの各々に対する少なくとも１つのトップレベルエントリと、
前記トップレベルエントリから成るトップレベルリストと、
から成る。
【請求項４】
請求項３に記載の方法であって、前記トップレベルリストがスキップリストである方法。
【請求項５】
請求項３に記載の方法であって、前記トップレベルリストがリンクリストである方法。
【請求項６】
請求項３に記載の方法であって、前記トップレベルリストが二重リンクのリストである方法。
【請求項７】
請求項３に記載の方法であって、前記トップレベルリストが順序づけられたアレイである方法。
【請求項８】
請求項３に記載の方法であって、前記ボトムレベルリストがスキップリストである方法。
【請求項９】
請求項３に記載の方法であって、前記ボトムレベルリストがリンクリストである方法。
【請求項１０】
請求項３に記載の方法であって、前記ボトムレベルリストが二重リンクのリストである方法。
【請求項１１】
請求項３に記載の方法であって、前記ボトムレベルリストが順序づけられたアレイである方法。
【請求項１２】
粗く満たされたデータ格納装置用のディレクトリを作成する方法であって、
データ格納装置を定義するステップと、
第一アドレスから成る第一ディレクトリエントリと第一前方リンクを作成するステップと、
第二アドレスから成る第二ディレクトリエントリと第二前方リンクを作成するステップと、
前記第二ディレクトリエントリが前記データ格納装置内において前記第一ディレクトリエントリの後に位置づけられていることを判定するステップと、
前記第二ディレクトリエントリへリンクする前記第一前方リンクを定義するステップと、
前記第一ディレクトリエントリと前記第二ディレクトリエントリから成るボトムレベルリストを作成するステップと、
前記ボトムレベルリストへのリンク、下限範囲および上限範囲から成るトップレベルエントリを作成するステップと、
全利ボトムレベルリストを調べて、前記トップレベルエントリの前記下限範囲と前記上限範囲を決定するステップと、
前記トップレベルエントリから成るトップレベルディレクトリを作成するステップと、
から成る方法。
【請求項１３】
請求項１２に記載の方法であって、前記第一ディレクトリエントリが第一後方リンクから成り、前記第二ディレクトリが第二後方リンクから成り、この方法は
前記第一ディレクトリエントリが前記データ格納装置において前記第二ディレクトリエントリの後に位置づけられていることを判定するステップと、
前記第一ディレクトリエントリへリンクする前記第二後方リンクを定義するステップと、
から成る。
【請求項１４】
請求項１２に記載の方法であって、さらに
前記第一ディレクトリエントリと前記第二ディレクトリエントリとの間の第三アドレスから成る第三ディレクトリエントリと、第三前方リンクとを作成するステップと、
前記第三ディレクトリエントリを次の方法で追加するステップとを有し、
前記追加方法は
前記第三ディレクトリエントリを前記ボトムレベルリストに加えるステップと、
前記第三ディレクトリエントリが前記第一ディレクトリエントリと前記第二ディレクトリエントリとの間にあることを判定するステップと、
前記第三ディレクトリエントリにリンクする前記第一前方リンクを変更するステップと、
前記第二ディレクトリエントリにリンクする前記第三前方リンクを定義するステップと、から成る。
【請求項１５】
請求項１３に記載の方法であって、さらに
前記第一ディレクトリエントリと前記第二ディレクトリエントリとの間の第三アドレスから成る第三ディレクトリエントリと、第三前方リンクと、第三後方リンクとを作成するステップと、
前記第三ディレクトリエントリを次の方法で追加するステップとを有し、
前記追加方法は
前記第三ディレクトリエントリを前記ボトムレベルリストに加えるステップと、
前記第三ディレクトリエントリが前記第一ディレクトリエントリと前記第二ディレクトリエントリとの間にあることを判定するステップと、
前記第三ディレクトリエントリにリンクする前記第一前方リンクを変更するステップと、
前記第二ディレクトリエントリにリンクする前記第三前方リンクを定義するステップと、
前記第三ディレクトリエントリにリンクする前記第二後方リンクを変更するステップと、
前記第一ディレクトリエントリにリンクする前記第三後方リンクを定義するステップと、から成る。
【請求項１６】
データ格納装置と、
前記データ格納装置用の粗いディレクトリ構造を定義し、前記粗いディレクトリ構造を変更すべきであることを判定し、前記粗いディレクトリ構造を密に満たされたディレクトリ構造に再構築するコントローラと、
を有するデータ記憶システム。
【請求項１７】
請求項１６に記載のデータ記憶システムであって、前記粗いディレクトリ構造は
前記アドレス指定可能なスペースの１つのアドレスと、記述子と、前記ディレクトリエントリの異なる一つを指示するポインタである少なくとも１つのリンクと、を有する複数の第一ディレクトリエントリと、
前記複数の第一ディレクトリエントリの少なくとも１つから成る少なくとも１つのボトムレベルリストと、
前記ボトムレベルリストの各々に対する少なくとも１つのトップレベルエントリと、
前記トップレベルエントリから成るトップレベルリストと、
から成る。
【請求項１８】
請求項１７に記載のデータ記憶システムであって、前記ボトムレベルリストはスキップリストである。
【請求項１９】
請求項１７に記載のデータ記憶システムであって、前記ボトムレベルリストはリンクリストである。
【請求項２０】
請求項１７に記載のデータ記憶システムであって、前記ボトムレベルリストは二重リンクのリストである。
【請求項２１】
請求項１７に記載のデータ記憶システムであって、前記ボトムレベルリストは順序づけられたアレイである。
【請求項２２】
請求項１７に記載のデータ記憶システムであって、前記トップレベルリストはスキップリストである。
【請求項２３】
請求項１７に記載のデータ記憶システムであって、前記トップレベルリストはリンクリストである。
【請求項２４】
請求項１７に記載のデータ記憶システムであって、前記トップレベルリストは二重リンクのリストである。
【請求項２５】
請求項１７に記載のデータ記憶システムであって、前記トップレベルリストは順序づけられたアレイである。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータ記憶システムに関し、特に大きな仮想記憶装置を有するコンピュータ記憶システムに関する。
【背景技術】
【０００２】
データ記憶システムは、そのデータ記憶システム内に保持される情報の場所を示すディレクトリを有する。このディレクトリを検索することによって特定のファイルの場所を見つけて、そのディレクトリに保持されるアドレスを使って要求されたファイルを取り出すことができる。項目がデータ記憶システムに格納されるたびに、それら項目のエントリーがディレクトリ内に作られる。
【０００３】
ディレクトリが参照する記憶装置は単一のディスクドライブまたはいくつかのディスクドライブの集合体であってもよい。複数のディスクドライブを編成する方法として、RAID技術の各種組み合わせがある。物理記憶スペースはディレクトリのアドレス指定可能なメモリよりも小さくしてもよい。例えば粗く満たされたデータベースまたは仮想記憶装置などの場合である。
【０００４】
ディレクトリを直ちに検索して任意のファイルの場所を特定することができるように、ディレクトリ情報はランダムアクセスメモリに格納することもできる。従ってディレクトリのサイズはできるだけ小さい方が望ましい。さらに、情報の構造は早い検索になじむものでなければならない。
【０００５】
粗く満たされたデータ格納装置と密に満たされたデータ格納装置では最適ディレクトリの設計を異ならせてもよい。密に満たされたディレクトリでは、すべてのデータブロックについてエントリーを設ける。そのようなディレクトリは大きなルックアップテーブルまたは他の構成を採用することができる。粗く満たされたディレクトリの場合、ルックアップテーブルは非常に効率が悪く、装置に格納された実際のデータ量に比例して大きなスペースを消費する。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、ディレクトリ構成としては、粗く満たされたディレクトリの場合、コンパクトで容易に検索でき、しかもディレクトリが密になってきても効率の良い検索に適応できるような構成とするのがよい。
【課題を解決するための手段】
【０００７】
本発明の実施例は、粗く満たされたディレクトリ用の１つまたは複数の密に満たされていないリストを有するデータ格納装置のディレクトリを提供するシステムおよび方法によって以前の解決方法の欠点および制限を克服するものである。ディレクトリが密になってくると、ディレクトリは従来の参照テーブルに変換することができる。ディレクトリ構造は一連の第二レベルマップを参照するトップレベルマップから構成することができる。第二レベルマップは順序づけられたリストマップ、スキップリスト、リンクリスト、二重リンクのリストあるいは密に満たされていないリスト機構とすることができる。
【０００８】
本発明の実施例は新しくて役に立つコンピュータファイルディレクトリシステムに関わり、ディレクトリ構造は粗く満たされたディレクトリに適した構造から密に満たされたディレクトリに適した構造に変更することができる。粗く満たされたディレクトリの場合、ディレクトリ構造の少なくとも一部はリンクリスト、二重リンクのリスト、スキップリスト等から構成される。そのようなディレクトリ構造が占有するメモリは従来のディレクトリ構造よりも大幅に少ない。ディレクトリがある容量レベルに達したならば、そのディレクトリを再構築することによって粗く満たされたディレクトリ構造を従来の密に満たされたディレクトリ構造に変更することができる。
【発明の効果】
【０００９】
本発明は粗く満たされたディレクトリを含み、その粗く満たされたディレクトリは従来のディレクトリよりもサイズが大幅に小さくより容易にサーチできるディレクトリとして作成することができる。さらに、例えば粗く満たされたディレクトリ構造が従来の参照テーブルディレクトリよりも効率が悪くなったとき、ディレクトリは従来の参照テーブルに再構築できる。従って、適切なディレクトリ構造を最も効率的に使うことができる。
【００１０】
本発明に関するこれらおよびその他の特徴および利点は、以下の詳細な説明と添付図面から明らかとなるであろう。
【実施例】
【００１１】
図１は本発明のデータ記憶システムの実施例を示す。コントローラ１０２は物理データ格納装置１０４に接続されて、装置またはネットワーク１０６とデータを受け渡すように動作する。コントローラは一つまたは複数のディレクトリ１０８、１１０を使ってデータ格納装置１０４内の情報の場所を特定する。
【００１２】
データ格納装置１０４はどのようなタイプの読み書きまたは読み取り専用データ記憶媒体でもよい。例えば、単一のディスクドライブまたはRAIDアレイのような複数ディスクドライブの集合体とすることができる。適用例としてはディスクアレイが代表的であるが、他のデータ記憶機構、例えばフラッシュメモリやランダムアクセスメモリ、をデータ格納装置１０４として採用することもできる。
【００１３】
コントローラ１０２は装置１０６からのデータ格納およびデータ取り出し要求を受け取って処理する。コントローラ１０２は、例えばサーバのようなコンピュータの中央演算ユニットのような装置１０６に接続された独立した専用の記憶装置コントローラとしてもよい。他の例として、コントローラ１０２の機能はコンピュータの中央演算処理ユニット上で動作するソフトウェアとして実現することもできる。
【００１４】
ディレクトリ１０８はデータ格納装置１０４に格納されているデータを展開することもできる。コントローラ１０２はディレクトリ１０８を検索して特定ファイルへのリンクを見つけ出す。そのリンクはディスクドライブ上の特定の物理セクタの場所であったり、要求されたファイルの実際の場所をコントローラ１０２に指示する別のリンクであってもよい。例えば、ディレクトリ１０８はディスクアレイ上の論理アドレスを示すエントリーを有することができる。コントローラ１０２は論理アドレスを特定の物理アドレスに変換してデータにアクセスする。
【００１５】
場合によっては、粗く満たされたデータ格納装置を示すディレクトリ１１０を構築することもできる。粗く満たされたディレクトリとして、例えばスナップショットディレクトリとしてもよい。スナップショットディレクトリは、特定の時間においてデータ格納装置の状態を保存するときに作成することもできる。例えば、週の終わりにおいてデータ格納装置の状態を保存するために、使用中のディレクトリを凍結してバックアップまたはスナップショットディレクトリとして新たに名前を付けることもできる。少しずつ変更した複数ファイルを格納するために新しい粗く満たされたディレクトリを作成してもよい。すなわち、ファイルが変更されると、新しい版のファイルを古い版とは別に格納し、その新しいファイルは粗く満たされたディレクトリに入れる。この例において、粗く満たされたディレクトリにはたった１つのエントリを入れて、非常に大きなデータスペースを参照し展開することもできる。
【００１６】
密に満たされたディレクトリはデータスペースのすべての単一データブロックに対してエントリを有するように構築することができる。そのようなディレクトリにはファイル名またはそのデータを参照する他の識別子を有するエントリも含まれる。要求されたファイルを特定するには各種サーチ方法を使ってディレクトリを検索することができる。この密に満たされたディレクトリはデータスペースの各データブロックに対して専用スペースを設けているので、固定サイズを有する。粗く満たされたデータ格納装置、特に非常に大きなデータ格納装置の場合、密に満たされたディレクトリは効率が悪いかもしれない。
【００１７】
コントローラ１０２は粗く満たされたデータ格納装置に対しては粗いディレクトリ構造を作成することができる。粗いディレクトリ構造は１つまたは複数のリンクリスト、二重リンクのリスト、スキップリスト、ハッシュリスト、バイナリ検索ツリー、あるいは他の粗く満たされたリスト手法で作成できる。粗いディレクトリのサイズは、データ格納装置が粗く満たされている場合、密に満たされたディレクトリ構造よりも大幅に小さくすることができる。データエントリの数が増えるに従って、ディレクトリおよび他の要素に占有させなければならないメモリ量に関して、粗いディレクトリ構造の効率は悪くなる。
【００１８】
粗いディレクトリ構造を用いて作ったディレクトリ内のデータ量があるレベル以上に増えた場合、コントローラ１０２はディレクトリを密に満たされたディレクトリ構造に変換することができるようにしてもよい。さらにコントローラ１０２は密に満たされたディレクトリ構造を使って作られたディレクトリを粗く満たされたディレクトリ構造に変換することもできるようにしてもよい。
【００１９】
図２はディレクトリ構造を適応させる方法の実施例２００を示す。ブロック２０２において新しいディレクトリが開始される。ブロック２０４においてこのディレクトリが粗く満たされた格納装置用であると判断された場合、ディレクトリ構造はブロック２０６において粗く満たされた格納装置用に構成される。ブロック２０８において格納装置にデータが加えられる。ブロック２１０においてディレクトリ構造が効率的であると判断された場合、ブロック２０８でさらにデータが加えられる。ブロック２１０でディレクトリ構造が効率的でないと判断された場合、ブロック２１２においてディレクトリ構造は密に満たされたディレクトリ構造により適した構造に再構成される。そのディレクトリはブロック２１４において密に満たされたディレクトリ構造で運用される。ブロック２０４において最初のディレクトリが粗く満たされた格納装置用ではないと判断された場合、そのディレクトリはブロック２１６において密に満たされたディレクトリ構造に変えられてブロック２１４で運用される。
【００２０】
新しい論理ディスクが作られたときにブロック２０２で新しいディレクトリを開始することができる。論理ディスクはデータを格納したり取り出すための装置に占有させるデータスペースを作ることができる。論理ディスクは単一のディスクドライブ、複数のディスクドライブのアレイまたは他の格納媒体上の物理ディスクスペースに展開することができる。
【００２１】
ブロック２０４において、作ろうとしているディレクトリが粗く満たされた格納装置を参照するものであるかどうかを調べる。これを確認するためにいくつかの機構を使うことができる。ディレクトリが作られたときに、ディレクトリは粗く満たされた格納装置であることを示すフラグまたはインディケータを用いてもよい。別の例では、ディレクトリが粗く満たされた構造または密に満たされた構造のいずれにより適しているかを判断するためにそのデータスペースを解析する。
【００２２】
ブロック２０６において、ディレクトリを粗く満たされた構造として構成する。粗く満たされたディレクトリ構造は検索可能なリストタイプ構造とすることができる。リスト構造は、リンクリスト、二重リンクのリスト、スキップリスト、ハッシュテーブル、レッドブラックツリー、バイナリ検索ツリー、あるいはデータ格納装置内で参照される各格納ブロックに対して専用のメモリスペースを必要としない他の構造とすることができる。当業者は本発明の精神と意図から逸脱することなく、密に満たされていない検索可能な格納構造を様々な形で考案できるであろう。
【００２３】
ブロック２１０においてディレクトリ構造の効率を調べて、ディレクトリ構造を変更する必要があるかどうかを判断する。粗く満たされたディレクトリ構造はデータがディレクトリに追加されていくに従って効率が悪化する。ディレクトリ内のエントリ数が増えると、ある時点で、密に満たされたディレクトリ構造の方が望ましくなる。
【００２４】
ディレクトリ内に一定の数のエントリが登録されたら、ブロック２１０においてディレクトリ構造を変更する判断を行ってもよい。ディレクトリ構造を変える決定は、例えばディレクトリの最終的な用途を知っている人間のオペレータによっておこなうことができる。つまりオペレータがそのディレクトリが大量のデータをすぐに格納しなければならないことを知っているような場合、オペレータはディレクトリ構造を変更することができる。場合によっては、ディレクトリの性能参照テーブルを監視して傾向を調べることもできる。その場合、コントローラが自動的に性能を調べてディレクトリ構造をいつ変更すべきかを判断するようにしてもよい。
【００２５】
ブロック２１２においてディレクトリのデータ構造を再構築する。最初のディレクトリ構造から二番目のディレクトリ構造へ変更するプロセスは構造に依存する。当業者には明らかなように、ディレクトリ構造の変換には様々な機構と技法を使うことができる。
【００２６】
別の例においては、ディレクトリ構造を密に満たされたディレクトリ構造から粗く満たされたディレクトリ構造へ変更することができる。この場合、ディレクトリ構造を定期的に調べて、粗く満たされた構造が検索時間、スペース利用率あるいは他の性能／効率において効率が良いかどうかを判断する。その時点で、データ構造は密に満たされた構造から粗く満たされた構造に変更する。
【００２７】
図３は粗く満たされたデータ格納装置用のディレクトリ構造に関する本発明の実施例３００を示す。トップレベルマップ３０２は複数のボトムレベルマップ３０６、３０８を参照するいくつかのエントリ３０４を有する。ボトムレベルマップ３０６は、リンクリスト、二重リンクのリスト、スキップリストあるいは他のリンクリストデータ構造として、他のエントリへの複数のリンク３１２で構成される。同様に、トップレベルマップ３０２はリンク３１４から成り、リンクリストデータ構造として構成することができる。
【００２８】
ディレクトリ構造３００は複数のディレクトリエントリ３１０を含む。各エントリ３００はそれが参照するファイルの記述およびそのファイルの位置情報を含む。各エントリ３１０はまた他のエントリへの１つまたは複数のリンクやポインタを含むことができる。
【００２９】
ディレクトリ構造３００をサーチするには最初にトップレベルマップ３０２を検索することによっておこなう。トップレベルマップ内の各エントリ３０４はそれぞれのボトムレベルマップに含まれるデータのおよその範囲を示す。適切なボトムレベルマップが特定されたなら、そのボトムレベルマップのリンクされたリストをサーチして適切なエントリを検出する。
【００３０】
トップレベルマップ３０２はシーケンシャルリストまたはリンクリストであってもよい。トップレベルマップ３０２がシーケンシャルリストの場合、リンク３１４は不要である。トップレベルマップ３０２がリンクリストの場合、例えば単一リンクのリスト、二重リンクのリスト、スキップリストあるいは他のデータ構造等各種望みのリンクリストを使うことができる。
【００３１】
データ構造３００は格納装置内の使用可能な各データブロックに個々のエントリ３１０を割り当てる必要がないように設計されている。当業者であれば理解できるように、データ構造３００はわずかなメモリ量を占有し非常に速く結果を返すので、格納装置の割り当てられたデータブロック数に対するエントリ３１０数の比が小さい。
【００３２】
図４は二重リンクのリストへエントリを追加するプロセス４００を示す。最初のリンクリスト４０２は、インデックス、値、前方リンクおよび後方リンクを列とし、エントリを行とするテーブルとして示されている。値１５の新しいエントリがブロック４０４において追加されて、リンクリスト４０６が更新される。
【００３３】
リスト４０２のインデックスはリストのエントリ番号である。インデックスは各種リンクの参照番号として使用できる。
【００３４】
リスト４０２の値はサーチがおこなわれている値である。ディレクトリ構造として使用されているリンクリストの場合、値はデータ格納装置内のアドレスでもよい。
【００３５】
リストを前方にサーチするには、前方リンクを使用する。例えば、インデックス０から始めて、前方リンクはインデックス１を指し、次にインデックス３、さらにインデックス２を指示する。各項目の前方インデックスを追うことによって順番にリストをサーチできる。
【００３６】
同様に、リストを後方にサーチするには、後方リンクを使用する。例えば、インデックス２から始めて、後方リンクはインデックス３、次にインデックス１、さらにインデックス０を指示する。
【００３７】
エントリ４０８がリンクリスト４０６に追加された場合、前方リンク４１０と後方リンク４１２が更新される。このようにして、エントリはリストに追加され、１つまたは２つのリンクを更新することによって検索可能となる。
【００３８】
図５は密に満たされた格納装置に適したディレクトリ構造の実施例５００を示す。トップレベルマップ５０２はボトムレベルマップ５０６、５０８を参照するエントリ５０４を含む。データ格納装置内の独立してアドレス指定可能なデータスペースそれぞれに対して、ボトムレベルマップ内にディレクトリエントリ５１０が存在する。
【００３９】
密に満たされた格納装置に使用した場合、本実施例５００は格納装置のアドレス指定可能なスペース１つ１つに対してディレクトリエントリ５１０が設けられる。実施例５００は構造内のエントリの位置がアドレスとして解釈できるように構成することができるので、各エントリ５１０はリンクやアドレスを持つ必要がない。
【００４０】
実施例５００を検索するには、最初にトップレベルマップ５０２を逐次検索して適切なボトムレベルマップの範囲を見つける。適切な範囲が決まったら、続けて特定のボトムレベルマップを逐次検索しその場所を見つけ出す。
【００４１】
ディレクトリの全内容をコントローラのランダムアクセスメモリに設けるのが好ましい。実施例５００のようなディレクトリエントリの小さい部分のみが設けられたディレクトリのためのデータ構造を使うのはメモリの使用効率が悪い。従って、もし適しているのであれば、ディレクトリは検索可能なリンクリストタイプの粗いディレクトリ構造で最初に構築する。ディレクトリ構造は、粗いディレクトリ構造の性能が密に満たされたディレクトリ構造よりも悪くなったら、変更して密に満たされたディレクトリ構造に適応させることができる。
【００４２】
従って本発明の一実施例は、データ格納装置用の粗いディレクトリ構造を作成するステップと、前記粗いディレクトリ構造が変更されるべきであると判断するステップと、前記粗いディレクトリ構造を密に満たされたディレクトリ構造に再構築するステップと、から成るデータ格納装置のディレクトリを維持する方法として構成することができる。
【００４３】
本発明の別の実施例は、データ格納装置を定義するステップと、第一アドレスを有する第一ディレクトリエントリと第一前方リンクとを作成するステップと、第二アドレスを有する第二ディレクトリエントリと第二前方リンクとを作成するステップと、前記データ格納装置において前記第二ディレクトリエントリが前記第一ディレクトリエントリの後に位置されていることを判定するステップと、前記第二ディレクトリエントリにリンクする前記第一前方リンクを定義するステップと、前記第一ディレクトリエントリと前記第二ディレクトリエントリから成るボトムレベルリストを作成するステップと、前記ボトムレベルリストへのリンクと、下限範囲と上限範囲とから成るトップレベルエントリを作成するステップと、前記ボトムレベルリストを調べて前記トップレベルエントリの下限範囲と上限範囲を決定するステップと、前記トップレベルエントリから成るトップレベルディレクトリを作成するステップと、から成る粗く満たされたデータ格納装置用ディレクトリを作成する方法として構成することができる。
【００４４】
さらに別の実施例は、データ格納装置と、前記データ格納装置用の粗いディレクトリ構造を定義し、前記粗いディレクトリ構造を変更すべきであることを判定し、前記粗いディレクトリ構造を密に満たされたディレクトリ構造に再構築するコントローラと、を有するデータ記憶システムとして構成することができる。
【００４５】
上記の本発明の説明は例示的説明のために提供したものであり、完璧にすべてを網羅した説明でもなければ、開示した形態にのみ本発明を制限するものでもない。また上記に鑑みて様々な変更が可能である。実施例は本発明の原理およびその適用を最善に説明するために選択したものであり、それによって当業者が特定の用途に適した様々な実施例や変更条件において最良に本発明を実施できるようにした。請求項は、先行技術によって制限される場合を除いて、本発明の他の実施例も含むものと解釈すべきである。
【図面の簡単な説明】
【００４６】
【図１】本発明のデータ記憶システムの実施例を示す図。
【図２】ディレクトリ構造を適応させる方法の本発明の実施例を示す図。
【図３】粗く満たされたデータ格納装置のディレクトリ構造の本発明の実施例を示す図。
【図４】二重リンクリストにエントリを追加するプロセスを示す図。
【図５】密に満たされたデータ格納装置に適したディレクトリ構造の本発明の実施例を示す図。
【図１】
2006252421.tif 000003
【図２】
2006252421.tif 000004
【図３】
2006252421.tif 000005
【図４】
2006252421.tif 000006
【図５】
2006252421.tif 000007
【外国語明細書】
2006252421000001.pdf