UNIXはディレクトリを検索するためにバイナリ検索を使用しますか?

UNIXはディレクトリを検索するためにバイナリ検索を使用しますか?

私は現在W. Richard Stevensが書いた「Advanced UNIXプログラミング」という本を読んでいます。ディレクトリを入力すると、システムは入力された名前の番号を検索します。

私は中だと思った。彼らはこの番号をどのように確認しますか?保存されたファイルは、バイナリ検索で検索できるように名前でソートされていますか?それとも、リストの最後に新しいファイルを追加しますか?

答え1

さまざまなファイルシステム形式、さまざまなシナリオでのパフォーマンス(大きなディレクトリと小さなディレクトリ、読み取りと書き込み、同時アクセスなど)、設計の単純さ(エラーの可能性、開発努力など)、ディスクのオーバーヘッドが異なります。ファイルコンテンツ以外の項目に対する(スペース)などの間でトレードオフが行われます。

古いファイルシステム(例:UFS、FFS外部2、元外部3、...)はディレクトリをエントリの配列(各エントリにはファイル名、inode番号、およびいくつかの追加のメタデータを含む)として保存し、線形検索を実行することを好みます。新しいファイルは、配列の最初の空き項目に追加されます。空き項目がない場合、配列は最初に展開されます。これにより、大規模ディレクトリのパフォーマンスが低下する可能性があります。

最新のファイルシステム(例:外部3オプションとしてdir_index外部4ジブスBTFSレイセルフス高周波FS高周波FS+,...) ログ時間照会、ある種のバランス検索ツリー、ハッシュテーブル、またはその両方の組み合わせ(ハッシュバランス検索ツリー)を使用して、ディレクトリをデータ構造として保存する傾向があります。Bツリー。これはファイルシステムコードをより複雑にしますが、大きなディレクトリで良いパフォーマンスを維持します。

答え2

この番号はインデックスノード。 Ext4は、ハッシュツリーを使用する最も広く使用されているLinuxファイルシステムタイプの1つです。kernel.org - Ext4ディスクレイアウト

ハッシュツリーの詳細については、以下を参照してください。ウィキペディア

答え3

ファイルシステムによって異なります。以前は、Unixディレクトリは本質的に16バイトのレコード(内部番号2バイト、ファイル名14バイト)で構成されていました。これがファイル名に既存の14文字の制限がある理由です。レコードがソートされないため、ファイルの線形検索が必要です。

より近代的なファイルシステム(たとえば、LinuxのExt4)には、検索を高速化するためのハッシュテーブルがあります。

答え4

賢明な警告:説明が不完全です。ファイル名はユーザーにとって便利であると説明することはできません。ファイル名が次のように確認されました。極度にUNIXベースのシステムでは重要です。

inode番号はファイルシステムモジュールによって選択されるので意味がありません。最初は、ディスクに格納されているinodeテーブルのスロットを識別します。システムの他の部分は、/dev/tty1などの特定の意味を持つファイルにアクセスする必要があります/etc/passwd

特定の単語を使用せずにコマンドを選択するcatためのユーザーインターフェースを提供するために使用されるメカニズム(例:名前による)を説明するには、「利便性」はあまりにも面倒です。ed

ファイル名ディレクトリがない場合は、これらの目的をサポートするために、inode番号に対して非常によく似た名前レジストリをすばやく作成する必要があります。

ディレクトリエントリには特別な意味.もあります。..仮想ファイルシステムは、たとえばプロセス1に関する情報を提供するprocためにファイル名を使用します。/proc/1/commVFSはまた、Unixベースである必要はなく、同じinode番号の概念を使用しない可能性があるさまざまなファイルシステムの使用を可能にします。

ZFSは、ファイル名とinodeメタデータ(権限など)が別々のレイヤに属すると考えているようです。私はこれの利点が何であるかをまだ理解していません。ネストされたファイルシステムを保存するために使用される場合、そのファイルに対してさまざまなパフォーマンスノブを提供する方法に近いです。

また、ユーザーは通常、inode番号でファイルを開くことはできません。可能であれば、 Director{y,ies} を含む権限でファイルへのアクセスを制御できません。

おそらく最後のポイントを見るもう一つの方法は、それがディレクトリの属性であるということです。ディレクトリの完全な原則はファイル名をマッピングすることであるため、これがなければ何の効果もありません。

ちょっと待って、ファイル参照用のコンテナ(例えば、「ハードリンク」)の役割を続けることができると言いました。複数のディレクトリにあるファイルを一覧表示できます。あるディレクトリ()からファイルを削除しても、そのファイルが別のディレクトリに残っている場合、unlink実際には削除されません。ハードリンクはUnixの実装の興味深い部分ですが、私が知っている限り、実際にはどのユーティリティも見つかりませんでした!彼らはしばしば混乱の機会と見なされます。これは、機能が必要かどうかを実際に考えなくても興味深い機能を提供することが非常に簡単であるため、実装の詳細を公開する例です。この特定の設計上の欠陥はそれほど危険ではありませんが、「10億ドルの間違い」に似ています。

つまり、ディレクトリを含むファイルの存在を確実にする方法に注目する価値があります。ファイルを識別するために別のシステムを実装するには、ファイルを削除すると、存在しないファイルを参照するエントリが残るか、同じinodeが割り当てられている関連性のない新しいファイルが残る可能性があることを考慮する必要があります。後で番号を付けました。

関連情報