Файловая система NTFS выдерживает каталоги с сотнями тысяч элементов и при этом открывает нужный файл почти мгновенно. Секрет состоит из нескольких слоёв: главная таблица файлов MFT хранит метаданные записями фиксированного размера, каталоги организованы отсортированными индексами на основе B+-дерева, а двоичный поиск по такому дереву заменяет линейный перебор. Понимание этой механики объясняет и скорость работы, и ограничения: почему миллион файлов в одной папке всё равно бьёт по производительности, почему дефрагментация была страшным сном владельца HDD, и как поисковые движки вроде Everything выдают результаты за миллисекунды, читая таблицу напрямую.
MFT хранит метаданные записями по 1 КБ
Сердце NTFS - это Master File Table, по сути обычный файл с неприметным именем $MFT, разбитый на записи фиксированного размера. По умолчанию одна запись занимает 1024 байта, и каждый файл или каталог получает как минимум одну такую запись. Номер записи одновременно служит внутренним адресом файла в системе: ссылки между объектами идут через 64-битные файловые референсы, где младшие биты кодируют номер записи, а старшие - порядковый номер для защиты от устаревших ссылок.
Внутри записи живут не данные как таковые, а набор атрибутов. Атрибут $STANDARD_INFORMATION содержит временные метки создания, изменения и доступа, флаги вроде "скрытый" или "только чтение". Атрибут $FILE_NAME хранит имя, номер родительского каталога и реальный размер; таких атрибутов может быть несколько, если у файла есть жёсткие ссылки или короткое имя 8.3 для совместимости. Атрибут $DATA содержит само содержимое, причём двумя способами. Если файл крошечный и умещается в запись вместе с остальными атрибутами, данные хранятся резидентно, прямо в MFT. Если не умещается, атрибут становится нерезидентным и вместо данных хранит список экстентов - пар "начальный кластер, длина", указывающих, где на диске лежат фрагменты файла.
Когда атрибутов слишком много для одной записи, NTFS подключает атрибут $ATTRIBUTE_LIST со ссылками на дополнительные записи. Первые строки таблицы зарезервированы под служебные файлы: сама $MFT, зеркало её первых записей $MFTMirr, журнал $LogFile, битовая карта кластеров $Bitmap и другие. Это делает дизайн самоописательным: файловая система описывает саму себя теми же механизмами, которыми описывает пользовательские данные.
Каталоги работают отсортированными индексами B+-деревом
Каталог в NTFS - это тоже файл, но его содержимое организовано как индекс имён. Маленький каталог держит все записи в атрибуте $INDEX_ROOT прямо внутри своей MFT-записи. Когда записей становится много, корневой список перестаёт помещаться, и система выносит основную массу в атрибут $INDEX_ALLOCATION - отдельные блоки, обычно по 4 КБ, которые образуют узлы B+-дерева. Дополнительный атрибут $BITMAP помечает, какие из этих блоков заняты.
Структура дерева классическая: корень содержит разделительные ключи, внутренние узлы направляют поиск, листья хранят сами записи с именами, размерами и ссылками на MFT-записи. Имена отсортированы по лексикографическому порядку с учётом регистра в виде Unicode-строк, поэтому поиск сводится к спуску по дереву: на каждом уровне двоичный поиск внутри узла показывает, в какое поддерево идти дальше. Глубина дерева растёт логарифмически, и даже для миллиона имён достаточно нескольких уровней - вся навигация укладывается в горсть дисковых чтений, а чаще вообще в обращения к кэшу.
Разница со старым подходом разительна. Линейный перебор каталога стоит O(n) сравнений, и миллион имён превращается в миллион проверок на каждый запрос. Двоичный спуск по B+-дереву стоит O(log n), и тот же запрос требует порядка двадцати сравнений плюс два-три обращения к узлам. Причём широкие узлы по 4 КБ выбраны не случайно: один узел вмещает десятки записей, поэтому ветвление огромное, а высота дерева остаётся маленькой. Каждое удаление и вставка балансируют дерево расщеплением и слиянием узлов, сохраняя гарантированную глубину.
Последовательность работы с файлом раскрывает, как слои складываются в единую картину:
- драйвер разбирает путь по компонентам и для каждого уровня ищет имя в индексе родительского каталога, спускаясь по B+-дереву;
- найденная запись индекса даёт файловый референс, по которому вычисляется смещение нужной записи внутри $MFT;
- из MFT-записи читаются атрибуты, включая список экстентов нерезидентного $DATA;
- по экстентам вычисляются физические кластеры, и запрошенные байты поднимаются с диска или из кэша.
На каждом шаге система опирается на упорядоченные структуры, и ни один шаг не требует перебора всего тома.
Миллион файлов в одной папке остаётся плохой идеей
Логарифмический поиск звучит как разрешение на любые объёмы, но практика безжалостнее теории. Первый удар наносит себестоимость вставки. Каждое новое имя должно попасть в строго отсортированное место дерева, поэтому создание файла в переполненном каталоге вызывает расщепление узлов, перезапись страниц индекса и обновление родительских разделителей. При массовом создании файлов затраты растут быстрее линейно, а журналирование удваивает объём записи на диск.
Второй удар приходится на перечисление. Прикладные программы и проводник не только ищут, но и показывают содержимое каталога, и прочитать миллион записей индекса - это прочитать миллион имён, независимо от того, дерево позади или плоский список. Дерево ускоряет точечный поиск, но не ускоряет полный обход. Третий удар - операции удаления и переименования, которые тоже трогают структуру дерева и оставляют в индексных блоках пустоты, которые переиспользуются не всегда идеально. Наконец, сторонние сканеры и антивирусные движки, обходящие каталог целиком, упираются в чистый объём данных. Поэтому классическая рекомендация инженеров - shard-структура: раскладывать объекты по подкаталогам с устойчивым числом элементов, а не сваливать их в один узел. Дерево спасает от линейного перебора, но не от самого факта миллиона записей.
Хронометраж одиночного доступа при этом остаётся впечатляющим. Чтение одной MFT-записи из кэша измеряется микросекундами, а даже холодное чтение с SSD укладывается в доли миллисекунды. Спуск по дереву каталога добавляет единицы таких чтений. На практике открытие файла по полному пути среди миллиона соседей занимает миллисекунды - именно поэтому пользователь не замечает, что файловая система проделала поиск в огромном пространстве имён.
USN-журнал и прямое чтение MFT питают мгновенный поиск
Обычный поиск по дереву каталогов быстр на точечных запросах, но медленен на глобальных: чтобы найти файл по имени в любом месте тома, пришлось бы обойти все каталоги. Поисковые движки класса Everything решают задачу радикально иначе - они читают $MFT целиком. Таблица компактна: даже на большом томе это несколько гигабайт последовательных данных, и первая полная загрузка занимает секунды. Из каждой записи движок извлекает имя, путь через ссылку на родителя, размер и метки времени, а затем строит в памяти собственный индекс, оптимизированный под подстроковый поиск.
Актуальность индекса поддерживает USN-журнал - служебный поток $Extend\$UsnJrnl, куда NTFS пишет каждое значимое изменение: создание, переименование, запись данных, удаление. Каждая запись журнала содержит номер Update Sequence Number, файловый референс и тип события. Движок запоминает последний обработанный USN и при следующем запуске дочитывает только новый хвост журнала, применяя изменения инкрементально. Если журнал успел перезаписаться, делается полное перечитывание таблицы. Благодаря этой связке поиск "все файлы с таким фрагментом имени" выполняется за миллисекунды - запрос уходит не на диск вообще, а в индекс в оперативной памяти. Это наглядный пример того, как знание внутреннего устройства файловой системы превращается в преимущество на два порядка скорости.
Управление свободным пространством тоже устроено предельно прямолинейно. Битовая карта $Bitmap хранит по одному биту на кластер тома: ноль означает свободен, единица - занят. Выделение места сводится к поиску подходящей серии нулевых битов, причём система старается выделять кластеры непрерывными экстентами, чтобы будущий файл читался последовательно. Экстентная модель выгодно отличается от поздних схем со случайным разбросом: один экстент описывает целый непрерывный участок, и список экстентов большого файла часто умещается в пару десятков записей.
FAT32 держит данные связным списком против порядка NTFS
Сравнение с FAT32 показывает, что именно купила индустрия усложнением NTFS. В FAT размещение файла описывается таблицей, где каждый кластер хранит номер следующего - фактически связный список. Каталоги же представляют собой обычные файлы с записями по 32 байта, упорядоченными только порядком создания. Поиск имени - это линейное чтение каталога от начала до совпадения, и большие папки деградируют прямо пропорционально размеру. Удалённая запись просто помечается стёртой первым байтом, и со временем каталог зарастает мусором.
NTFS отвечает на каждую из этих слабостей: экстенты вместо цепочек, отсортированные B+-индексы вместо неупорядоченных списков, журналируемые метаданные вместо хрупкой таблицы без защиты от сбоя посреди записи. Платой служит заметно больший объём метаданных на том же томе и более тяжёлый код драйвера.
Любопытно сравнение и в другую сторону, с объектными хранилищами. Там вместо иерархии каталогов лежит плоское пространство ключей, а "папки" эмулируются префиксами в имени объекта. Поиск по ключу обычно опирается на распределённые хэш-таблицы или LSM-деревья, дающие O(1) или O(log n), зато операция "переименовать каталог с миллионом объектов" превращается в миллион отдельных копирований. NTFS же за счёт родительских ссылок переименовывает каталог изменением одной записи - иерархия оказывается не пережитком, а осознанным компромиссом, выгодным именно для локальной файловой семантики.
Ещё два приёма показывают гибкость атрибутной модели. Сжатие NTFS включается флагом на атрибуте $DATA: система прозрачно жмёт данные блоками по шестнадцать кластеров и распаковывает при чтении, экономя место ценой процессорного времени. Разреженные файлы работают похоже: флаг разреженности позволяет не хранить нулевые области, и в списке экстентов такие диапазоны просто отмечены как пустые. Образы виртуальных дисков и базы данных с огромными нулевыми прослойками занимают при этом килобайты реального пространства. Оба механизма не потребовали пересмотра структуры файловой системы - хватило новых флагов и договорённостей внутри существующей схемы атрибутов.
Дефрагментация выматывала HDD механическими переездами
Экстентная модель стремится к непрерывности, но со временем свободное место дробится, и новые файлы ложатся кусками. Для SSD это почти безразлично: время доступа одинаково к любой ячейке. Для HDD фрагментация означала физическую работу: после каждого куска головка совершала seek, тратя пять-десять миллисекунд на переезд, и файл из сотни фрагментов читался в десятки раз медленнее последовательного. Дефрагментация переписывала файлы в непрерывные области, и процесс был именно "страшным": часами долбящий диск, заметная нагрузка, риск при внезапном отключении питания. Современные Windows справляются в фоне маленькими порциями, но сама глава истории объясняет, почему создатели NTFS так упирали на экстенты и резервирование места заранее - дешевле не допустить дробления, чем потом собирать файл обратно.
Отдельного упоминания заслуживает кэширование: диспетчер кэша Windows держит горячие MFT-записи и узлы индексов каталогов в оперативной памяти, поэтому повторные обращения к популярным путям вообще не касаются диска. Планировщик ввода-вывода при этом объединяет соседние чтения таблицы, и даже холодный старт после перезагрузки прогревается за считанные секунды. Именно сочетание компактных структур на диске и агрессивного кэша в памяти даёт тот субъективный эффект мгновенности, к которому привыкли пользователи.
Индексация NTFS - редкий пример дизайна, где несколько простых структур данных, записи фиксированного размера, отсортированные B+-деревья и битовые карты, складываются в систему, которая три десятилетия спустя находит нужный файл среди миллиона быстрее, чем экран успевает отрисовать курсор.