Структуры данных, используемые для создания файловых систем?

Ответ 1

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

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

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

Файловая система XFS славилась тем, что использует B + -trees практически все, включая структуры каталогов и систему ведения журнала. Из того, что я помню из моего курса под управлением ОС, философия заключалась в том, что, поскольку потребовалось столько времени, чтобы писать, отлаживать и выполнять настройку реализации B + -tree, было бы целесообразно использовать его как можно больше.

Другие файловые системы (ext3 и ext4) используют вариант B-дерева, называемый HTree, с которым я не очень хорошо знаком. По-видимому, он использует какую-то схему хэширования, чтобы поддерживать высокий коэффициент ветвления, так что используется очень мало доступа к диску.

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

В системе Microsoft FAT32 использовался огромный массив (таблица размещения файлов), в котором хранятся файлы, где хранятся файлы, и какие сектора диска логически следуют друг за другом в файле. Главный недостаток заключается в том, что таблица должна была быть установлена ​​заранее, поэтому в верхних границах были ограничены размеры файлов, которые можно было сохранить на диске. Тем не менее, система на основе массива была довольно легко реализована.

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

Надеюсь, это поможет!