Древовидная структура каталогов на диске

Обновлено: 05.07.2024

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

Что такое каталог с древовидной структурой?

Древовидная структура является наиболее распространенной структурой каталогов. У дерева есть корневой каталог, и каждый файл в системе имеет уникальное имя пути. Каталог (или подкаталог) содержит набор файлов или подкаталогов. Один бит в каждой записи каталога определяет запись как файл (0) или как подкаталог (1).

Каковы особенности каталогов с древовидной структурой?

Древовидная структура является наиболее распространенной структурой каталогов. У дерева есть корневой каталог, и каждый файл в системе имеет уникальный путь. Преимущества: очень общие, так как можно указать полное имя пути.

Какие существуют типы каталогов?

Одноуровневый каталог.
Двухуровневый каталог.
Каталог с древовидной структурой.
Каталог ациклических графов.
Каталог General-Graph.
Одноуровневый каталог. Одноуровневый каталог — самая простая структура каталогов.

Что такое структура каталогов?

Что такое структура каталогов? Структура каталогов — это организация файлов в виде иерархии папок. Он должен быть стабильным и масштабируемым; он не должен кардинально меняться, а только дополняться. Компьютеры десятилетиями использовали метафору папки, чтобы помочь пользователям отслеживать, где что-то можно найти.

Файловые каталоги | Одноуровневые, двухуровневые, древовидные и ациклические каталоги графов

Найдено 41 связанный вопрос

Как вы объясните структуру файла?

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

Где хранится структура каталогов?

Юникс. Unix и Unix-подобные операционные системы используют стандарт иерархии файловой системы в качестве общей формы для своих структур каталогов. Все файлы и каталоги отображаются в корневом каталоге "/", даже если они хранятся на разных физических устройствах.

Как используются каталоги?

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

Какую файловую систему использует DOS?

DOS использует файловую систему таблицы размещения файлов (FAT). Первоначально это была FAT12, которая поддерживала до 4078 кластеров на диск. В DOS 3.0 добавлена поддержка FAT16, которая использует 16-битные записи распределения и поддерживает до 65 518 кластеров на диск.

Как вы отображаете структуру папок?

Откройте Проводник в Windows. .
Нажмите в адресной строке и замените путь к файлу, введя cmd, а затем нажмите Enter.
При этом должна открыться черно-белая командная строка с указанным выше путем к файлу.
Введите dir /A:D. .
Теперь в указанном выше каталоге должен быть новый текстовый файл с именем FolderList.

Каковы преимущества использования каталогов?

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

Что такое файловая структура ОС?

Структура файла должна соответствовать требуемому формату, понятному операционной системе. . Объектный файл представляет собой последовательность байтов, организованных в блоки, понятные машине. Когда операционная система определяет различные файловые структуры, она также содержит код для поддержки этой файловой структуры.

Что представляют собой различные уровни каталогов, поясняемые диаграммой?

Иерархический каталог выходит за рамки двухуровневой структуры каталогов. Здесь пользователю разрешено создавать множество подкаталогов. В каталоге дерева каждый каталог имеет только один родительский каталог, кроме корневого каталога. Структура ациклического графа, каталог может иметь более одного родительского каталога.

Является ли Unix операционной системой?

UNIX – это операционная система, которая была впервые разработана в 1960-х годах и с тех пор постоянно развивается. Под операционной системой мы подразумеваем набор программ, обеспечивающих работу компьютера.Это стабильная многопользовательская многозадачная система для серверов, настольных компьютеров и ноутбуков.

Как сделать дерево каталогов?

Создание всего дерева каталогов может быть выполнено с помощью команды mkdir, которая (как следует из ее названия) используется для создания каталогов. Параметр -p указывает mkdir создать не только подкаталог, но и любой из его родительских каталогов, которые еще не существуют.

В чем разница между файлом и папкой?

Файл — это общая единица хранения данных в компьютере, и все программы и данные «записываются» в файл и «читаются» из файла. Папка содержит один или несколько файлов, и папка может быть пустой, пока не будет заполнена. . Файлы всегда хранятся в папках.

Кто изобрел DOS?

Американский программист Тимоти Патерсон, разработчик Seattle Computer Products, написал исходную операционную систему для микропроцессора 8086 корпорации Intel в 1980 году, первоначально назвав ее QDOS (Quick and Dirty Operating System), которая вскоре была переименована в 86-DOS.

Почему DOS используется до сих пор?

MS-DOS по-прежнему используется во встроенных системах x86 из-за ее простой архитектуры и минимальных требований к памяти и процессору, хотя некоторые текущие продукты перешли на все еще поддерживаемую альтернативу FreeDOS с открытым исходным кодом. В 2018 году Microsoft опубликовала исходный код MS-DOS 1.25 и 2.0 на GitHub.

Что такое три файла MS-DOS?

Зачем нам нужен каталог?

Почему Active Directory так важна? Active Directory помогает организовать пользователей вашей компании, компьютер и многое другое. Ваш ИТ-администратор использует AD для организации полной иерархии вашей компании: какие компьютеры принадлежат к какой сети, как выглядит изображение вашего профиля или какие пользователи имеют доступ к хранилищу.

Что вы подразумеваете под каталогами файлов?

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

Являются ли каталоги файлами?

Каталог на самом деле не более чем файл, но его содержимое контролируется системой, а содержимое — это имена других файлов. (Каталог иногда называют каталогом в других системах.)"

Как называется каталог?

Каталог. Также известный как "папка", каталог представляет собой набор файлов, обычно создаваемых для организационных целей. Файл Файл — это единица информации (обычно именованная), хранящаяся на компьютере. Это может быть документ, веб-страница или множество других типов информации.

Как хранятся каталоги в Linux?

Имена индексных дескрипторов (имена файлов, каталогов, устройств и т. д.) хранятся на диске в каталогах. В каталоге хранятся только имена и связанные с ними номера инодов; фактическое дисковое пространство для данных, которым присваивается имя, хранится в пронумерованном индексном узле, а не в каталоге.

Какая информация хранится в структуре каталогов файловой системы?

Каталог — это файл особого типа, который содержит список своих файлов и подкаталогов. Он также может содержать метаданные о каталоге, например, кто может получить к нему доступ и его атрибуты. Файл — это основной логический контейнер для хранения информации, такой как изображение, документ, программа, текст или база данных.

В большинстве компьютерных операционных систем, например в Microsoft Windows, данные на жестком диске организованы иерархически.

С одной стороны есть файлы, которые имеют определенный размер и содержат действующие данные. Каждый файл имеет имя. В Microsoft Windows «расширение имени файла» информирует о типе файла. Например, расширение «.exe» указывает на то, что это файл программы. Расширение «.doc» указывает на документ WinWord, «.jpg» — на фотографию и т. д. Но как ни странно, Microsoft Windows Explorer по умолчанию скрывает эти расширения имен файлов. Вы можете изменить это поведение в меню параметров проводника Windows.

С другой стороны, есть каталоги. Проводник Windows и WinDirStat также обозначают каталоги желтыми папками. Каталоги также имеют имя, но обычно без расширения имени файла. Каталоги служат только для хранения файлов и других каталогов ("подкаталогов"). Из-за того, что каталоги могут содержать подкаталоги, а те, в свою очередь, могут содержать подкаталоги, в результате получается иерархическая структура на диске.

Вместо "иерархическая структура" мы говорим просто древовидная структура. Поскольку дерево также построено иерархически: ствол разветвляется на ветви, ветви на подветви, веточки и, наконец, на листья. В файловой системе так называемый корневой каталог является стволом, каталоги — ветвями, а файлы — листьями.

Вот почему мы называем файловую систему компьютера просто "деревом каталогов".

В отличие от большинства настоящих деревьев, на диске ствол и ветки уже имеют листья. И, в отличие от большинства настоящих деревьев, также: файлы — это объемные объекты (размер которых измеряется мегабайтами или гигабайтами), тогда как фактические каталоги пренебрежимо малы. Кстати, абстрактные деревья мы представляем перевёрнутыми: корень вверху, листья внизу.

Если отпилить ветку от дерева и воткнуть ее в землю, то она сама становится деревцем (ну, по крайней мере, похоже на деревце): Каждая ветка вместе со своими подветвями и листьями есть сама по себе дерево, поддерево.

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

Если бы вы попросили меня реализовать древовидную структуру данных, я бы написал что-то вроде этого:

(В этом посте я использую Rust, но вы должны быть в состоянии следовать ей без предварительного знания Rust.)

Дерево состоит из узлов, которые я назвал SimpleTreeNode. Каждый узел представляет собой структуру, содержащую некоторые данные и список дочерних элементов. Поскольку потомки содержат другие узлы, эта структура может представлять произвольные древовидные иерархии. Атрибут данных не является обязательным для создания дерева, но он понадобится почти во всех случаях. Обычно вы хотите связать некоторые данные с каждым узлом в дереве.

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

На этот раз наш FileSystemNode представляет собой перечисление, а не структуру. Он содержит два разных случая, один для каталогов и один для файлов. Оба они содержат атрибут имени, который является метаданными. Кроме того, случай Directory также содержит дочерний атрибут, который содержит список дочерних узлов. Это эквивалентно предыдущему примеру и позволяет представить древовидную структуру. Другой случай перечисления, File , содержит фактические данные, но не содержит дочерних элементов.

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

Мы можем видеть это очень практически, используя стандартные инструменты Linux/программирования. Хотя вы можете использовать cat для отображения данных файла, он не будет работать для каталогов. И наоборот, вы не можете использовать cd для перехода к файлу или ls для просмотра его дочерних элементов. Другой пример можно найти в вашей среде IDE: двойной щелчок по папке не отображает содержимое в области основного редактора, и вы не можете создавать вложенные файлы файла с помощью пункта контекстного меню.

Сейчас вы можете подумать: "Зачем мне это делать?". Если вы думаете о файлах и папках, используя их фактические аналоговые эквиваленты (листы бумаги в папке), открытие листа бумаги (эквивалент компакт-диска) не имеет никакого смысла. С другой стороны, вы, вероятно, могли бы возразить, что бумажные папки сами могут содержать данные, если написать их на обложке, но это не решение для больших объемов данных.

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

Во всяком случае, я пытаюсь сказать, что файловые системы наших компьютеров вдохновлены аналоговыми файловыми системами и что это, вероятно, не имеет большого смысла (уже?).

Ограничивает тот факт, что внутренние узлы в иерархии файловой системы не могут хранить данные. Во многих случаях было бы естественно иметь узлы, которые могут хранить данные И иметь потомков. Поскольку файловые системы этого не позволяют, мы часто используем обходные пути. Давайте рассмотрим несколько примеров:

Модули Rust

Полное объяснение того, как работают модули в Rust, выходит за рамки этого текста. Если вы хотите узнать о них больше, я могу порекомендовать официальную книгу по Rust. В главе 7 объясняется, что такое модули и как их можно разделить на разные файлы.

В Rust корнем вашего ящика обычно является src/lib.rs (для библиотек) или src/main.rs (для бинарных файлов). В этом корневом файле вы можете создавать модули, используя блоки модов. Модули могут быть вложенными, а их определение может быть встроенным или в отдельных файлах. При использовании отдельных файлов существуют правила их именования.

Допустим, у нас есть следующая иерархия модулей, реализованных как встроенные модули в корневом файле:

Есть модуль foo, который содержит другую панель модулей, и оба они могут содержать больше кода. Если мы хотим разделить эти модули на отдельные файлы, мы можем сделать это так:

Модули первого уровня (в нашем примере foo) можно поместить в ту же папку, что и корневой файл ( main.rs ), и назвать их по имени модуля ( foo.rs ). Вложенные модули (bar в нашем примере) необходимо поместить в подпапки, названные в честь родительских модулей. Таким образом, путь к модулю bar — foo/bar.rs .

Содержание различных файлов также необходимо адаптировать:

При извлечении встроенных модулей в отдельные файлы определение модуля изменяется с mod foo <. >в мод foo; в родительском модуле. Содержимое блока перемещается во вновь созданный файл модуля ( foo.rs ). То же самое изменение внесено и в панель вложенных модулей.

Rust также позволяет использовать src/foo/mod.rs вместо src/foo.rs. Содержимое всех файлов может остаться прежним, но тогда структура будет выглядеть так:

Вы запутались? По крайней мере, я был немного сбит с толку, когда впервые попытался изучить Rust в 2018 году, и я слышал от других, у которых тоже были проблемы с изучением того, как модули работают в Rust. Однако, как только вы это поймете, это обретет смысл, и единственное, что осталось запомнить, — это куда поместить файлы модулей и как правильно их назвать. Кроме того, при чтении чужого кода всегда есть два места для поиска файла модуля. Это необходимо?

Модули в Rust могут иметь подмодули И сами содержать код. Это как раз тот случай, о котором я говорил ранее: нужен узел, который имеет дочерние элементы и сами данные. Файловые системы не могут напрямую представлять это, поэтому обходной путь Rust состоит в том, чтобы иметь папку, содержащую дочерние модули ( src/foo ) И специальный файл либо рядом с ( src/foo.rs ), либо внутри ( src/foo/mod.rs ).

Что, если бы у нас были файлы с дочерними элементами (или каталоги с данными соответственно)? Структура примера выше может выглядеть следующим образом:

В этой гипотетической файловой системе файл foo.rs будет одновременно и каталогом, и файлом. Использование cat на нем отобразит содержимое модуля, а ls / cd можно будет использовать для запроса его дочерних элементов.

Выглядит круто и очень полезно. Мало того, что мы исключили один элемент файловой системы, вам также не нужно думать о том, поместить ли специальный файл (рядом или внутри папки?). Это хороший намек на то, что структура этой гипотетической файловой системы естественным образом соответствует структуре нашего варианта использования.

HTML-сайты

Я выбрал Rust в качестве примера выше, но та же проблема (и те же обходные пути) можно увидеть и во многих других областях. Например, простой HTML-сайт может иметь следующую структуру:

Это очень похоже на пример с Rust, за исключением того, что «специальный файл каталога» называется index.html вместо mod.rs. И, как и в примере с Rust, мы могли бы упростить структуру, разрешив файлы, которые могут иметь как данные, так и дочерние элементы:

В этом примере данные, которые были сохранены в blog/index.html и blog/posts/index.html соответственно, теперь хранятся непосредственно в родительских узлах (которые я назвал blog.html и blog.html/). posts.html соответственно).

Сохранение веб-страницы

Это похоже на другой подход Rust: использование файла рядом с папкой, содержащей дочерние элементы ( src/foo.rs ). Вместо этого гипотетическая файловая система может разрешить эту структуру:

Таких примеров еще много. Как только вы начнете их искать, вы увидите их повсюду.

Другое дерево файловой системы

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

На первый взгляд, второе определение проще. Больше нет разделения между файлами и папками, только узлы. Это также является более общим, поскольку эти узлы могут иметь как дочерние элементы, так и данные.

При внимательном рассмотрении мы видим, что можно использовать SimpleTreeNode так, чтобы он содержал те же данные и структуру, что и FileSystemNode.

Здесь мы используем кортеж строки и вектор байтов в качестве универсального параметра T SimpleTreeNode . Строка может содержать имя узла и байтовый вектор данных. Доступ к атрибутам будет выглядеть немного по-другому, но в основном это та же структура данных.

Увлекательно, не так ли? Сняв ограничение, которое мы видели раньше, и упростив структуру данных, мы получили одну из самых фундаментальных структур данных в информатике. Это приятно!

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

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

Как разработчики программного обеспечения, мы привыкли создавать слои за слоями. Чем ниже по стеку мы сможем добиться улучшений, тем больше может быть положительное влияние. Файловые системы являются фундаментальной частью всех операционных систем и находятся довольно низко в этом стеке. Важно попытаться переосмыслить и улучшить эти фундаментальные строительные блоки. Я надеюсь, что мысли, изложенные выше, станут небольшим вкладом в достижение этой цели.

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

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

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

Существуют различные типы информации, которые хранятся в каталоге:

Имя
Тип
Местоположение
Размер
Позиция
Защита
Использование
Монтаж

Имя: — Имя — это имя каталога, которое видно пользователю.
Тип: тип каталога означает, какой тип каталога присутствует, например, одноуровневый каталог, двухуровневый каталог, каталог с древовидной структурой и каталог с ациклическим графом.
Местоположение. Местоположение – это место на устройстве, на котором находится заголовок файла.
Размер. Размер означает количество слов/блоков/байтов в файле.
Позиция: – позиция означает положение следующего указателя чтения и следующего указателя записи.
Защита: - Защита означает контроль доступа на чтение/запись/удаление/выполнение.
Использование: – использование означает время создания, модификации, доступа и т. д.
Монтирование: - Монтирование означает, что корень файловой системы привит к существующему дереву других файловых систем.

Операции с каталогом

Создание
Удаление
Поиск
Список каталогов
Переименование
Ссылка
Отключить

Создание: - В этой операции создается каталог. Имя каталога должно быть уникальным.
Удаление: - Если есть файл, который нам не нужен, мы можем удалить этот файл из каталога. Мы также можем удалить весь каталог, если каталог не требуется. Пустой каталог также можно удалить. Пустой каталог — это каталог, состоящий только из точек и точек.
Поиск: - Операция поиска означает, что для определенного файла или другого каталога мы можем выполнить поиск в каталоге.
Список каталогов: - В этой операции мы можем получить список всех файлов в каталоге. И мы также можем получить содержимое записи каталога для каждого файла, присутствующего в списке.

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

Типы структуры каталогов

Одноуровневый каталог
Двухуровневый каталог
Каталог с древовидной структурой
Каталог ациклических графов
Общий каталог графиков
Одноуровневый каталог: - Одноуровневый каталог — это самая простая структура каталогов. В одноуровневом каталоге есть только один каталог, и этот каталог называется корневым каталогом. В одноуровневом каталоге все файлы находятся в одном каталоге, что облегчает понимание. При этом в корневом каталоге пользователь не может создавать подкаталоги.

Преимущества одноуровневого каталога

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

Недостатки одноуровневого каталога

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

Двухуровневый каталог — это еще один тип структуры каталогов. При этом можно создать отдельный каталог для каждого из пользователей. В двухуровневом каталоге есть один главный узел, который включает отдельный каталог для каждого пользователя. На втором уровне каталога для каждого пользователя имеется отдельный каталог. Без разрешения ни один пользователь не может войти в каталог другого пользователя.

Характеристики двухуровневого каталога

В двухуровневом каталоге у разных пользователей могут быть одинаковые имена файлов.
Для каждого файла есть путь, например /имя_пользователя/имя_каталога/
В двухуровневом каталоге мы не можем сгруппировать файлы с одинаковыми именами в один каталог для определенного пользователя.
В двухуровневом каталоге поиск более эффективен, поскольку существует только один список пользователей, который необходимо просмотреть.

Преимущества двухуровневого каталога

В двухуровневом каталоге разные пользователи имеют одинаковое имя файла и имя каталога.
Из-за использования группировки пользователей и имени пути поиск файлов довольно прост.

Недостатки двухуровневого каталога

В двухуровневом каталоге один пользователь не может поделиться файлом с другим пользователем.
Еще одним недостатком двухуровневого каталога является его немасштабируемость.
Каталог с древовидной структурой

Каталог с древовидной структурой — это другой тип структуры каталогов, в которой записью каталога может быть подкаталог или файл. Каталог с древовидной структурой снижает ограничения двухуровневого каталога. Мы можем сгруппировать файлы одного типа в один каталог.

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

Преимущества древовидного каталога

Каталог с древовидной структурой легко масштабируется.
В каталоге древовидных структур вероятность коллизии меньше.
В каталоге с древовидной структурой поиск довольно прост, поскольку в нем мы можем использовать оба типа путей: абсолютный и относительный.

Недостатки каталога с древовидной структурой

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

Каталог ациклических графов

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

С помощью псевдонимов и ссылок мы можем создать этот тип графа каталогов. У нас также может быть другой путь для одного и того же файла. Ссылки могут быть двух видов: жесткие (физические) и символические (логические).

Если мы удалим файлы в структурах ациклического графа, то

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

Преимущества каталога с ациклическим графиком

В каталоге ациклического графа возможен общий доступ к файлам.
В каталоге ациклического графа из-за разных путей поиск удобен.

Недостатки каталога с ациклическим графом

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

Каталог General-Graph — еще один важный тип структуры каталогов. В этом типе каталога внутри каталога мы можем создать цикл каталога, в котором мы можем получить различные каталоги с помощью более чем одного родительского каталога.

Основная проблема в каталоге general-graph заключается в подсчете общего пространства или размера, занимаемого каталогами и файлами.

Преимущества каталога General-Graph

Каталог General-Graph более гибок, чем другая структура каталогов.
Циклы разрешены в каталоге общего графа.

Недостатки каталога General-Graph

В каталоге общего графа требуется сборка мусора.
По сравнению с другими структурами каталогов каталог General-graph является более дорогостоящим.

Реализация каталога

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

Мы можем классифицировать алгоритм реализации каталога на основе структуры данных.

В основном мы используем два типа алгоритмов:

Линейный список
Хеш-таблица

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

Характеристики линейного списка

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

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

Читайте также: