1. 概要

このチュートリアルでは、基本的なファイルの構造を見ていきます。 最初に、基本的な概念を簡単に説明してから、最も一般的なファイル構造に関する情報を提供します。

2. 序章

ディスクは低速ですが、メモリよりも低コストで巨大な容量を提供します。 また、オフになっている場合でも、情報は保存されたままになります。 ファイル構造設計の背後にある主な推進力は、ディスクのアクセス時間が遅いことと、ディスクの膨大な不揮発性容量にあります。

詳細に入る前に、データ構造とファイル構造の主な違いを見てみましょう。 データ構造はメインメモリ内のデータを処理しますが、ファイル構造はハードディスクなどのセカンダリストレージデバイス内のデータを処理します。どちらもデータの表現とデータへのアクセス操作を伴います。 そのため、これら2つの概念は文献で互いに混同される可能性があります。 ただし、メモリアクセステクノロジの開発は、ファイル構造に取り組んでいる研究者に直接影響を与えると言えます。

3. ファイル構造

ファイル構造は、ファイル内のデータの表現を組み合わせたものです。これは、データにアクセスするための操作のコレクションでもあります。 これにより、アプリケーションはデータの読み取り、書き込み、および変更を行うことができます。 ファイル構造は、特定の基準に一致するデータを見つけるのにも役立つ場合があります。 ファイル構造の改善は、アプリケーションを数百倍高速化する上で大きな役割を果たします。

ファイル構造を開発する主な目標は、必要な情報を取得するためにディスクへのトリップ数を最小限に抑えることです。理想的には、1回のディスクアクセスで必要なものを取得するか、わずかなディスクアクセスで取得することに対応します。できるだけ。

適切なファイル構造は次のとおりです。

  • 大容量への高速アクセス
  • ディスクアクセスの数を減らす
  • これらのコレクションを分割して成長を管理します。

ファイルが変更されない場合、これらの目標を満たすファイル構造設計を開発するのは比較的簡単です。 ただし、ファイルが変更、拡大、または縮小すると、これらの品質を備えたファイル構造を設計することがより困難になります。

3.1. ファイル構造の短い歴史

1950年代にはほとんどのファイルがテープ上にあったため、アクセスはシーケンシャルであり、アクセスのコストはファイルのサイズに正比例して増加しました。 ファイルが大きくなり、ディスクドライブなどのストレージデバイスが利用可能になると、インデックスがファイルに追加されました。これらのインデックスにより、キーとポインターのリストをより小さなファイルに保持して、より迅速に検索できるようになりました。 ただし、これらのインデックスは同じシーケンシャルな動作をするため、管理が困難になりました。

1960年代初頭、ツリー構造を適用するというアイデアが生まれました。 ユーザーがレコードを追加および削除すると、ツリーの成長が非常に不均一になる可能性があるため、検索に時間がかかります。

3.2. AVL木

研究者たちはツリー構造の開発を続け、メモリ内のデータ用にAVLツリーと呼ばれるエレガントな自己平衡二分探索木を考案しました。 ファイルシステムに取り組んでいる研究者は、AVLツリーをファイルに適用する方法を探し始めました。

3.3. BツリーとB+ツリー

10年間の設計作業の後、彼らはBツリーのアイデアを思いつきました。 Bツリーは優れたパフォーマンスを提供しましたが、1つの欠点があります。それは、効率的にファイルに順番にアクセスできないことです。 幸いなことに、彼らはリンクリスト構造を使用してこの問題を取り除きました。 そして彼らはこの新しい構造をB+ツリーと呼びました。

下の図を見て、BツリーとB+ツリーの主な違いを見てみましょう。

何年にもわたって、BツリーとB +ツリーは、に比例して増加するアクセス時間を保証するため、多くのファイルシステムの標準になりました。ここで、はファイル内のエントリの数であり、はBツリー構造。 実際には、ディスクへの3〜4回のトリップで、他の何百万ものファイルの中から1つのファイルを見つけることができます。

3.4. ハッシュ

ディスクへの3〜4回のトリップでデータにアクセスすることは、非常に効率的です。 ただし、1つのリクエストで必要なものを正しく取得する方が効率的です。 ハッシュは、1回のリクエストでデータにアクセスする方法です。ファイルのサイズが時間の経過とともに変化しない場合は、ハッシュが適切に機能します。 しかし、逆の状況では、ハッシュは動的ファイルではうまく機能しません。 研究者は、ファイルの大きさに関係なく1回のアクセスで情報を取得できる動的ハッシュを使用してこの問題を解決します。

ハッシュメカニズムがどのように機能するかを見てみましょう。

上の図で見たように、ハッシュは、アルゴリズムを使用して入力を固定サイズに変換するプロセスです。 ハッシュの主なアイデアは、特定の入力をより小さな数に変換するハッシュ関数を使用することです。 この小さい数値をハッシュテーブルと呼ばれるテーブルのインデックスとして使用します。

4. 結論

この記事では、ファイル構造に関する簡単な情報を共有し、データ構造とファイル構造の間のあいまいさを解消しました。

また、AVLツリー、BおよびB +ツリー、ハッシュなどの一般的なファイル構造に関する情報も簡単に説明しました。