Я сейчас читаю книгу Advance UNIX Programming У. Ричарда Стивенса и прочитал там, что все файлы в UNIX имеют номер, и что имена файлов создаются только для удобства пользователя. Когда вводится каталог, система ищет номер для введенного имени.
Я подумал, как они ищут номер? Файлы хранятся отсортированными по имени, чтобы их можно было найти бинарным поиском? Или они просто добавляют новые файлы в конец списка?
решение1
Существует множество различных форматов файловых систем, и они обеспечивают различные компромиссы между производительностью в разных сценариях (большие каталоги против маленьких, чтение против записи, одновременный доступ и т. д.), простотой конструкции (вероятность ошибок, усилия по разработке и т. д.), накладными расходами на диске (пространство, используемое для чего-либо, кроме содержимого файла) и т. д.
Старые файловые системы (например,УФС, ФФС,ехт2, оригинальныйext3, …) имеют тенденцию хранить каталоги как массив записей (каждая запись содержит имя файла, номер inode и, возможно, некоторые дополнительные метаданные) и выполнять линейный поиск. Новые файлы добавляются в первую свободную запись в массиве; если свободной записи нет, массив сначала увеличивается. Это приводит к плохой производительности с большими каталогами.
Новые файловые системы (например,ext3с dir_indexопцией,ext4,зфс,btrfs,рейзерфс,ХФС,ХФС+, …) имеют тенденцию хранить каталоги как структуру данных с логарифмическим временем поиска, своего рода сбалансированное дерево поиска, хэш-таблицу или комбинацию этих двух (сбалансированное дерево поиска хэшей) — как правило, некоторый вариантB-дерево. Это усложняет код файловой системы, но сохраняет хорошую производительность при работе с большими каталогами.
решение2
Число называетсяиноды. Ext4, один из самых популярных типов файловых систем Linux, использует хэш-дерево, см.kernel.org - Разметка диска Ext4.
Более подробная информация о хэш-деревьях на сайтевикипедия.
решение3
Это зависит от файловой системы. Давным-давно каталог Unix был по сути файлом, состоящим из 16-байтовых записей, два байта для внутреннего номера и 14 байт для имени файла. Это причина старого ограничения в 14 символов для имен файлов. Записи не сортировались, поэтому требовался линейный поиск по файлу.
Более современные файловые системы, такие как Ext4 в Linux, имеют хэш-таблицу для ускорения поиска.
решение4
Педант оповещения: описание не полное. Имена файлов не могут быть описаны как только удобство для пользователей. Имена файлов оказалисьочень сильноважно в системах на базе Unix.
Номера инодов не могут иметь значения, поскольку они выбираются модулем файловой системы. Первоначально они идентифицировали слот в таблице инодов, хранящейся на диске. Другим частям системы необходимо получать доступ к файлам, имеющим определенное значение, например /dev/tty1или /etc/passwd.
Если не привязываться к конкретному слову, «удобство» слишком тривиально для описания механизма, который используется для предоставления пользовательскому интерфейсу возможности выбора команд, таких как catили edпо имени.
Если бы не было каталогов имен файлов, вам очень скоро пришлось бы изобрести несколько очень похожих реестров имен для номеров inode, чтобы поддерживать эти варианты использования.
Записи каталога .и ..также имеют особое значение. Виртуальные файловые системы, такие как procпредоставляют собственное значение, используя имена файлов, например, делая /proc/1/commдоступным для предоставления информации о процессе 1. VFS также позволяет использовать различные файловые системы, которые не обязательно должны быть основаны на unix и могут не работать с той же самой точной концепцией номеров inode.
ZFS, похоже, считает, что и имена файлов, и метаданные inode, такие как разрешения, принадлежат к отдельному слою. Мне еще предстоит понять, какое преимущество это дает. Похоже, это скорее способ предоставить различные ручки производительности для объектов-эквивалентов-файлов при использовании для хранения вложенных файловых систем.
Также пользователи обычно не могут открывать файлы по номеру inode. Если бы они могли, вы бы не смогли контролировать доступ к файлу через разрешения содержащего его каталога{y,ies}...
Возможно, еще один способ взглянуть на последний пункт — это то, что это особенность каталогов. Весь принцип каталога заключается в отображении имен файлов, так что без этого они не имеют никакого эффекта.
Подождите, скажете вы, они все равно будут иметь эффект контейнера для ссылок на файлы, также известные как «жесткие ссылки». У вас могут быть файлы, перечисленные в нескольких каталогах; удаление файла из одного каталога ( unlink) на самом деле не удаляет его, если он все еще остается в другом каталоге. Жесткие ссылки являются интересной частью реализации unix, но, насколько мне известно, они никогда не были действительно полезны! Обычно их рассматривают только как возможность для путаницы. Пример раскрытия деталей реализации, потому что это очень облегчало предоставление интересных функций, без реального рассмотрения того, была ли эта функция необходима. Похоже на «ошибку на миллиард долларов», хотя этот конкретный недостаток дизайна не был таким опасным.
Тем не менее, стоит отметить, как каталоги гарантируют существование содержащихся в них файлов. Если вы хотите реализовать какую-то другую систему для идентификации файлов, вам придется учитывать возможность того, что удаление файла оставит вам запись, ссылающуюся на несуществующий файл, или даже на новый и несвязанный файл, которому позже был назначен тот же номер inode.