FAT (FAT12, FAT16 и FAT32) не используют никакое дерево. В дополнение к блоку данных, описывающему сам раздел, используются две интересные структуры данных. Полная информация на уровне, необходимом для написания совместимой реализации во встроенной системе, доступна от Microsoft и третьих сторон. Википедия имеет достойную статью в качестве альтернативной отправной точки, которая также включает в себя большую часть истории того, как все получилось.
Поскольку первоначальный вопрос касался использования деревьев, я кратко расскажу о том, какая на самом деле небольшая структура данных в файловой системе FAT. Обратитесь к приведенным выше ссылкам для точных деталей и истории.
Набор файлов в каждом каталоге хранится в простом списке, первоначально в том порядке, в котором они были созданы. Удаление выполняется путем пометки записи как удаленной, поэтому последующее создание файла может повторно использовать этот слот. Каждая запись в списке является структурой фиксированного размера и достаточно большой, чтобы содержать классическое имя файла 8.3 вместе с битами флага, размером, датами и номером начального кластера. Длинные имена файлов (которые также включают поддержку международных символов) выполняются с помощью дополнительных слотов для записей каталога, чтобы хранить длинное имя вместе с оригинальным слотом 8.3, который содержит все остальные атрибуты файла.
Каждый файл на диске хранится в последовательности кластеров, где каждый кластер представляет собой фиксированное количество смежных дисковых блоков. Каждый каталог (кроме корневого каталога диска) похож на файл и может увеличиваться по мере необходимости за счет выделения дополнительных кластеров.
Управление кластерами осуществляется с помощью (неправильно названной) таблицы размещения файлов, из которой файловая система получает свое общее имя. Эта таблица представляет собой упакованный массив слотов, по одному для каждого кластера в разделе диска. Название FAT12 подразумевает, что каждый слот имеет ширину 12 бит, слоты FAT16 - 16 бит, а слоты FAT32 - 32 бита. Слот хранит значения кода для пустых, последних и поврежденных кластеров или номер кластера следующего кластера файла. Таким образом, фактическое содержимое файла представляется в виде связанного списка кластеров, называемого цепочкой.
Для дисков большего размера требуются более широкие записи FAT и / или большие единицы размещения. FAT12 в основном встречается только на гибких дисках, где его верхняя граница кластеров 4K имеет смысл для носителей, размер которых никогда не превышал 1 МБ. FAT16 и FAT32 обычно встречаются на флэш-накопителях и флэш-картах. Выбор размера FAT там частично зависит от предполагаемого применения.
Доступ к содержимому определенного файла прост. Из его записи в каталоге вы узнаете его общий размер в байтах и номер первого кластера. По номеру кластера вы можете сразу рассчитать адрес первого блока логического диска. В FAT, проиндексированной по номеру кластера, вы найдете каждый выделенный кластер в цепочке, назначенной этому файлу.
Найти свободное место, подходящее для хранения нового файла или расширения существующего файла, не так просто. Файловая система FAT просто помечает свободные кластеры кодовым значением. Поиск одного или нескольких свободных кластеров требует поиска FAT.
Поиск записи каталога для файла также не быстрый, так как каталоги не упорядочены, что требует поиска по линейному времени в каталоге нужного файла. Обратите внимание, что длинные имена файлов увеличивают время поиска, занимая несколько записей каталога для каждого файла с длинным именем.
Преимущество FAT заключается в том, что его достаточно просто реализовать, так как его можно выполнять в небольших микропроцессорах, так что обмен данными между даже небольшими встроенными системами и ПК может осуществляться экономически эффективным способом. Я подозреваю, что в результате его причуды и странности будут с нами надолго.