Каталоги, эффективность при поиске

Каталог на NTFS представляет собой специфический файл, хранящий ссылки на другие файлы и каталоги, создавая иерархическое строение данных на диске. Сами записи каталога содержат имя файла, его длину, некоторые другие его параметры (атрибуты), а самое главное содержат номер (индекс) записи MFT для данного файла, в которой содержится уже полная информация о файле.

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