Поиск UNIX каталогов с помощью бинарного поиска?

В настоящее время я читаю книгу Advance UNIX Programming от W. Richard Stevens, и я читаю, что все файлы в UNIX имеют номер и имена файлов создаются только для удобства пользователя. Когда каталог вводится, система выполняет поиск номера для введенного имени.

Я подумал про себя, как они ищут номер? Сохраняются ли файлы отсортированными по имени, чтобы они могли найти их путем бинарного поиска? Или они просто добавляют новые файлы в конец списка?

4 Solutions collect form web for “Поиск UNIX каталогов с помощью бинарного поиска?”

Существует много разных форматов файловой системы, и они создают разные компромиссы между производительностью в разных сценариях (большие каталоги против небольших каталогов, чтение и запись, параллельный доступ и т. Д.), Простота проектирования (вероятность ошибок, усилия по разработке и т. Д.), Накладные расходы на диск (пространство используется для вещей, отличных от содержимого файла) и т. д.

Старые файловые системы (например, UFS, FFS , ext2 , original ext3 , …) имеют тенденцию хранить каталоги в виде массива записей (каждая запись содержит имя файла, номер inode и, возможно, некоторые дополнительные метаданные) и выполнять линейный поиск. Новые файлы добавляются при первой свободной записи в массиве; если нет свободной записи, массив сначала увеличивается. Это приводит к плохой производительности с большими каталогами.

Новые файловые системы (например, ext3 с опцией dir_index , ext4 , zfs , btrfs , reiserfs , HFS , HFS + , …) имеют тенденцию хранить каталоги как структуру данных с логарифмическим временем поиска, какое-то сбалансированное дерево поиска, хэш-таблицу или комбинация из двух (сбалансированное дерево поиска хешей) – обычно некоторый вариант B-дерева . Это делает код файловой системы более сложным, но сохраняет хорошие результаты с большими каталогами.

Номер называется inode . Ext4, один из наиболее популярных типов файловой системы Linux, использует хеш-дерево, см. Kernel.org – Ext4 Disk Layout .

Подробнее о хэш-деревьях в Википедии .

Это зависит от файловой системы. Давным-давно каталог Unix был по существу файлом, состоящим из 16 байтовых записей, двух байтов для внутреннего номера и 14 байтов для имени файла. Это и есть причина для ограничения количества символов в 14 символов для имен файлов. Записи не были отсортированы, поэтому потребовался линейный поиск по файлу.

Более современные файловые системы, такие как Linux Ext4, имеют хеш-таблицу для ускорения поиска.

Предупреждение о педанте: описание не завершено. Имена файлов не могут быть описаны как удобство для пользователей. Имена файлов оказались чрезвычайно важными в системах на основе unix.

Номера Inode не могут иметь значения, поскольку они выбираются модулем файловой системы. Первоначально они идентифицировали слот в таблице inode, хранящейся на диске. Остальные части системы должны иметь доступ к файлам с определенным значением, например /dev/tty1 или /etc/passwd .

Не удерживая вас до определенного слова, «удобство» слишком тривиально, чтобы описать механизм, который используется для предоставления пользовательскому интерфейсу выбора команд, таких как cat или ed по имени.

Если бы не были каталоги имен файлов, вам очень скоро пришлось бы изобретать некоторые очень похожие реестры имен для номеров inode для поддержки этих видов использования.

Записи в каталоге . и .. также имеют особое значение. Виртуальные файловые системы, такие как proc предоставляют свое собственное значение, используя имена файлов, например, делая /proc/1/comm доступными для предоставления информации о процессе 1. VFS также позволяет использовать разные файловые системы, которые не должны основываться на unix и не могут работать с той же точной концепцией чисел inode.

Кажется, что ZFS думает, что имена файлов и метаданные inode, например разрешения, принадлежат отдельному слою. Мне еще предстоит понять, какую пользу это дает. Кажется, что это больше способ предоставить разные ручки производительности для файлов-эквивалентных объектов при использовании для хранения вложенных файловых систем.

Также пользователи обычно не могут открывать файлы по номеру inode. Если бы они могли, вы не смогли бы контролировать доступ к файлу с помощью разрешений содержащего директора {y, ies} …

Возможно, еще один способ взглянуть на последний момент – это функция каталогов. Весь принцип каталога состоит в том, чтобы отображать имена файлов, поэтому без этого они действительно не имеют никакого эффекта.

Подождите, вы говорите, они все равно будут иметь эффект как контейнер для ссылок на файлы, а также «жесткие ссылки». Вы можете иметь файлы, перечисленные в нескольких каталогах; удаление файла из одного каталога ( unlink ) фактически не удаляет его, если оно все еще остается в другом каталоге. Жесткие ссылки – это интересная часть реализации unix, но AFAIK они никогда не находили никакой полезности! Их обычно рассматривают только как возможность для путаницы. Пример раскрытия детали реализации, поскольку он очень легко предоставил интересные функции, не учитывая, нужна ли эта функция. Подобно «ошибке в миллиард долларов», хотя эта конкретная ошибка дизайна не была настолько опасной.

Тем не менее, стоит отметить, как каталоги гарантируют существование файлов, которые они содержат. Если вы хотите внедрить некоторую другую систему для идентификации файлов, вам нужно будет рассмотреть возможность того, что удаление файла оставит вас с ссылкой на несуществующий файл или даже с новым и несвязанным файлом, которому был назначен тот же индекс число позже.

Linux и Unix - лучшая ОС в мире.