Что такое экстенты ntfs mft

Обновлено: 21.11.2024

Основная таблица файлов (MFT) — это сердце NTFS, поскольку она содержит информацию обо всех файлах и каталогах. Каждый файл и каталог имеет по крайней мере одну запись в таблице, и сами по себе записи очень просты. Они имеют размер 1 КБ, но только первые 42 байта имеют определенное назначение. Остальные байты хранят атрибуты, представляющие собой небольшие структуры данных, имеющие очень специфическое назначение. Например, один атрибут используется для хранения имени файла, а другой используется для хранения содержимого файла. На рис. 11.1 показан базовый макет записи MFT, где есть некоторая информация заголовка и три атрибута.

Рисунок 11.1. Запись MFT имеет небольшой заголовок, а остальная его часть используется для хранения различных типов атрибутов. Эта запись имеет три атрибута.

Майкрософт называет каждую запись в таблице записью файла, но я думаю, что называть каждую запись записью MFT проще, и это приводит к меньшему количеству терминов для запоминания. Каждой записи присваивается адрес в зависимости от ее положения в таблице, начиная с 0. На сегодняшний день все записи имеют размер 1024 байта, но точный размер определяется в загрузочном секторе.

Как и все в NTFS, MFT представляет собой файл. Что сбивает с толку, так это то, что MFT имеет запись для себя. Первая запись в таблице называется $MFT и описывает расположение MFT на диске. По сути, это единственное место, где описывается местонахождение МФТ; поэтому вам необходимо обработать его, чтобы определить макет и размер MFT. Начальное расположение MFT указывается в загрузочном секторе, который всегда находится в первом секторе файловой системы. Мы можем видеть это на рис. 11.2, где загрузочный сектор используется для поиска первой записи MFT, что показывает, что MFT фрагментирована и идет от кластеров 32 к 34 и от 56 к 58. Как и FAT, NTFS использует кластеры, которые представляют собой группы последовательных секторов.

Рисунок 11.2. Связь между загрузочным сектором и $MFT в отношении определения макета MFT.

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

Содержимое записи MFT

Размер каждой записи MFT определяется в загрузочном секторе, но во всех версиях Microsoft используется размер 1024 байта. Первые 42 байта структуры данных содержат 12 полей, а остальные 982 байта неструктурированы и могут быть заполнены атрибутами. Вы можете думать о записи MFT как о большом ящике, который используется для хранения ваших вещей. На внешней стороне коробки находится основная информация, такая как ваше имя и адрес. Основная информация эквивалентна фиксированным полям записи MFT. Внутренняя часть коробки изначально пуста, но ее можно использовать для хранения чего угодно, если это находится в контейнере, который меньше коробки. Это похоже на то, что запись MFT не имеет внутренней структуры и содержит несколько атрибутов, содержащих определенную информацию.

Первое поле в каждой записи MFT — это подпись, а стандартная запись будет иметь строку ASCII "ФАЙЛ". Если в записи обнаружена ошибка, она может иметь строку «BAAD». Существует также поле флага, которое определяет, используется ли запись и относится ли она к каталогу. Статус выделения записи MFT также можно определить по атрибуту $BITMAP в файле $MFT, который показан в главе 13.

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

В главе 13 показана структура данных для записи MFT и анализируется наш пример образа файловой системы.

Адреса входа в MFT

Каждая запись MFT также имеет 16-битный порядковый номер, который увеличивается при выделении записи. Например, рассмотрим запись MFT 313 с порядковым номером 1. Файл, в котором размещена запись 313, удаляется, а запись перераспределяется в новый файл. Когда запись перераспределяется, она получает новый порядковый номер 2. Запись MFT и порядковый номер объединяются с порядковым номером в старших 16 битах, чтобы сформировать 64-битный адрес ссылки на файл, как показано на рис. 11.3.

Рисунок 11.3. Пример объединения адреса записи MFT и порядкового номера для формирования адреса ссылки на файл.

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

Файлы метаданных файловой системы

Поскольку каждый байт тома выделяется файлу, должны существовать файлы, в которых хранятся административные данные файловой системы. Microsoft называет эти файлы файлами метаданных, но это может вызвать путаницу, поскольку мы также ссылаемся на метаданные файлов. Я буду называть эти специальные файлы файлами метаданных файловой системы.

Microsoft резервирует первые 16 записей MFT для файлов метаданных файловой системы.[2] Зарезервированные записи, которые не используются, находятся в выделенном состоянии и содержат только основную и общую информацию. Каждый файл метаданных файловой системы указан в корневом каталоге, хотя обычно они скрыты от большинства пользователей. Имя каждого файла метаданных файловой системы начинается с «$», а первая буква — заглавной. Мы рассмотрим каждый из файлов метаданных файловой системы в главе 12, но они перечислены в Таблице 11.1 для удобства.

[2] В документации Microsoft говорится, что она резервирует только первые 16 записей, но на практике первой записью, выделяемой пользовательскому файлу или каталогу, является запись 24. Записи с 17 по 23 иногда используются как переполнение, когда зарезервированных записей недостаточно.

Каждый файл на томе NTFS представлен записью в специальном файле, называемом главной таблицей файлов (MFT). NTFS резервирует первые 16 записей таблицы для специальной информации.

Первая запись этой таблицы описывает саму основную таблицу файлов, за которой следует зеркальная запись MFT.

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

Полный список файлов метаданных представлен в главе «Системные файлы».

Структура MFT

Главная таблица файлов выделяет определенное пространство для каждой записи файла. Атрибуты файла записываются в выделенное пространство в MFT. Небольшие файлы и каталоги (обычно 512 байт или меньше), такие как файл, показанный на следующем рисунке, могут полностью содержаться в записи таблицы главного файла.

Запись MFT для небольшого файла или каталога

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

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

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

Небольшие записи каталогов полностью находятся в структуре MFT. Большие каталоги организованы в B-деревья, содержащие записи с указателями на внешние кластеры, содержащие записи каталогов, которые не могут содержаться в структуре MFT.

О нас

LSoft Technologies Inc. — частная североамериканская компания-разработчик программного обеспечения. Наша цель — создавать лучшие в мире решения для восстановления данных, безопасности и резервного копирования, обеспечивая высочайшую производительность, инновации и непревзойденное обслуживание клиентов.

В этой статье описывается, как NTFS резервирует место для своей основной таблицы файлов (MFT).

Относится к: Windows 10 — все выпуски, Windows Server 2012 R2
Исходный номер базы знаний: 174619

Обзор

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

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

В Windows утилита дефрагментации выполняет дефрагментацию MFT.

Утилита дефрагментации

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

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

Подробнее

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

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

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

Из-за важности MFT для NTFS и возможного влияния на производительность, если этот файл станет сильно фрагментированным, NTFS прилагает особые усилия, чтобы этот файл был непрерывным. NTFS резервирует 12,5% объема для исключительного использования MFT до тех пор, пока оставшаяся часть объема не будет израсходована. Таким образом, пространство для файлов и каталогов не выделяется из этой зоны MFT до тех пор, пока не будет выделено все остальное пространство.

Вы можете изменить раздел реестра NtfsMFTZoneReservation, чтобы увеличить громкость в Windows. Дополнительные сведения о MFT см. в разделе Ключевые элементы процесса дефрагментации диска документа Поддержание максимальной производительности Windows 2000 посредством дефрагментации.

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

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

Новый параметр реестра может увеличить процентную долю тома, который NTFS резервирует для своей главной файловой таблицы. NtfsMftZoneReservation — это значение REG_DWORD, которое может принимать значения от 1 до 4, где 1 соответствует минимальному размеру зоны MFT, а 4 — максимальному. Если параметр не указан или указано недопустимое значение, NTFS использует для этого параметра значение по умолчанию, равное 1. Точные коэффициенты, соответствующие каждой настройке, не задокументированы, поскольку они не стандартизированы и могут измениться в будущих версиях. Чтобы узнать, какой параметр лучше всего подходит для вашей среды, может потребоваться поэкспериментировать с различными значениями.

Чтобы определить текущий размер MFT на компьютере с Windows, введите команду dir /a $mft на томе NTFS.

Чтобы определить текущий размер MFT на компьютере с Windows, используйте программу дефрагментации диска для анализа диска NTFS, а затем нажмите «Просмотреть отчет». Отображает статистику диска, включая текущий размер MFT и количество фрагментов.

Дефрагментация диска отображает зеленым то, что называется системными файлами, а на томе в формате NTFS это просто комбинация MFT, pagefile.sys (если таковая существует на этом томе) и то, что называется «зоной MFT» или зарезервированным пространством для расширения MFT. В отчете о дефрагментации отображается только информация о файле подкачки и MFT; в нем не упоминается зона MFT, поскольку она никоим образом не влияет на использование или емкость диска.

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

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

Результаты, возвращаемые командой dir, могут быть устаревшими. Размер, сообщаемый командой dir, может отражать кэшированные данные, отражающие размер MFT на момент запуска системы после нормального завершения работы.

Этот раздел, метод или задача содержат инструкции по изменению реестра. Однако при неправильном изменении реестра могут возникнуть серьезные проблемы. Поэтому убедитесь, что вы внимательно выполните следующие действия. Для дополнительной защиты создайте резервную копию реестра перед его изменением. Затем вы можете восстановить реестр, если возникнет проблема. Дополнительные сведения о резервном копировании и восстановлении реестра см. в разделе Резервное копирование и восстановление реестра в Windows.

Чтобы добавить это значение, выполните следующие действия:

Запустите редактор реестра (Regedt32.exe) и перейдите к следующему подразделу:

В меню "Правка" нажмите "Добавить значение".

Введите следующую информацию в диалоговом окне:

  • Имя значения: NtfsMftZoneReservation
  • Тип данных: REG_DWORD
  • Данные: (допустимый диапазон: 1–4)

Закройте редактор реестра и перезагрузите компьютер.

Это параметр времени выполнения, который не влияет на фактический формат тома. Скорее, это влияет на то, как NTFS распределяет пространство на всех томах данной системы. Поэтому, чтобы быть полностью эффективным, параметр должен действовать с момента форматирования тома и на протяжении всего срока службы тома. Если параметр реестра будет уменьшен или удален, зона MFT будет соответственно уменьшена, но это не повлияет на уже выделенное и используемое пространство MFT.

Глава 22, раздел 22.5 в разделе «Концепции операционных систем».
Не входит в OSTEP.

Фон

Файловая система Windows называется NTFS. Она была представлена ​​в Windows NT 4.0 и является стандартной файловой системой в Windows 2000 и более поздних системах, таких как Windows XP. Его цель состояла в том, чтобы устранить ограничения размера, производительности, надежности и гибкости в DOS (также известной как файловая система FAT).

  • Основная таблица файлов
  • файлы данных
  • каталоги
  • свободный список (битовая карта)
  • загрузочные изображения
  • журналы восстановления

В файловой системе также есть функции поддержки избыточности и транзакций, которые мы не будем обсуждать. Отличным справочником по деталям является книга Хелен Кастер «Внутри файловой системы Windows NT», опубликованная (что неудивительно) Microsoft Press.

Разметка диска

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

Основная таблица файлов (MFT)

  • Логически диск состоит из единиц распределения, называемых кластерами.
  • Кластер представляет собой степень двойки, кратную размеру блока физического диска. Размер кластера задается при форматировании диска. Небольшой кластер обеспечивает более высокую степень детализации распределения, но может потребовать больше места для описания файла и большего количества отдельных операций для передачи данных в память или из памяти.
  • Список свободных мест — это битовая карта, каждый бит которой описывает один кластер.
  • Кластеры на диске нумеруются от нуля до максимального количества кластеров (минус один). Эти номера называются номерами логических кластеров (LCN) и используются для именования блоков (кластеров) на диске.
  • Все файлы и, следовательно, все объекты, хранящиеся на диске, описываются MFT.
  • Все файлы логически хранятся в MFT, а небольшие файлы физически находятся в пределах MFT. В этом смысле MFT является файловой системой.
  • Логически MFT можно описать как таблицу с одной строкой на файл.
  • В первых строках таблицы описаны важные файлы конфигурации, в том числе для самой MFT.

Записи MFT

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

  • Стандартная информация. Этот атрибут включает стандартную информацию в мире MS-DOS:
    • разрешения на чтение/запись,
    • время создания
    • время последнего изменения
    • количество каталогов, указывающих на этот файл (количество жестких ссылок).
    • файл имеет несколько ссылок или
    • файл имеет короткое имя MS-DOS.

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

    • Указатели на данные на самом деле являются указателями на последовательности логических кластеров на диске.
    • Каждая последовательность состоит из трех частей:
      • начальный кластер в файле, называемый номером виртуального кластера (VCN),
      • запуск логического кластера (LCN) последовательности на диске,
      • длина, учитываемая как количество кластеров.

      Каталоги

      • Запись каталога содержит имя файла и ссылку на файл. Ссылки на файлы идентифицируют файл на этом томе. Другими словами, это внутреннее имя файла. Ссылка представляет собой пару (номер файла, порядковый номер). Номер файла — это смещение записи файла в таблице MFT. Он похож на номер Unix (номер Inode).
      • Список имен файлов в каталогах хранится не в виде простого списка, а в виде лексико-сортированного дерева, называемого деревом B+ (это будет знакомо тем, кто имеет опыт работы с базами данных). Структура данных называется индексом в NFTS (опять же, следуя терминологии баз данных).
      • В структуре NTFS указано, что индекс может быть создан для любого атрибута, но в настоящее время поддерживаются только индексы имен файлов.
      • Имя файла отображается как в записи его каталога, так и в записи MFT для самого файла.
      • Как и в случае с обычными файлами, если каталог достаточно мал, он может полностью поместиться в записи MFT.

      Если каталог больше, то верхняя часть (дерево B+) каталога находится в записи MFT, которая указывает на экстенты, содержащие остальные сопоставления имени/файла.

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

      Каждая запись в MFT обычно имеет фиксированный размер 1 КБ, а первые 16 записей содержат информацию об объеме. Эти относящиеся к тому записи называются файлами метаданных, что является терминологией, используемой для служебных структур в файловой системе.

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

      IJ^I Запись имени файла обычно содержит два имени файла: длинное имя файла и имя файла, совместимое с DOS (8.3).

      Что еще более важно и, безусловно, сильно отличается от FAT, файловые данные — это просто еще один атрибут NTFS. Существует ограничение на объем данных, которые могут поместиться в запись MFT, и все, что превышает этот предел, заменяется в записи указателями на то, где на диске находятся данные файла. Запись MFT может содержать около 750 байт данных файла (фактический объем зависит от количества атрибутов, хранящихся в записи MFT). Небольшие файлы данных (менее 750 байт) могут полностью помещаться в свои записи MFT, обеспечивая невероятно высокую производительность и отсутствие риска фрагментации этих файлов.

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

      Конечно, большинство файлов недостаточно малы, чтобы поместить их данные в записи MFT, поэтому MFT хранит их данные на диске. NTFS размещает файлы в единицах кластеров, на которые ссылаются двумя способами:

      ■ Номера виртуальных кластеров (VCN) от 0 до n-1, где в файле содержится n кластеров.

      ■ Номера логических кластеров (LCN), которые соответствуют номерам кластеров на томе.

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

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

      Если какой-либо атрибут не помещается в запись MFT, NTFS сохраняет его в новом отдельном наборе кластеров на диске, называемом прогоном или экстентом. Обычно атрибут данных файла является атрибутом, который слишком велик для записи MFT.Однако другие атрибуты, помимо атрибута данных, могут стать достаточно большими, чтобы вызвать новые экстенты. Например, длинные имена файлов могут содержать до 255 символов, каждый из которых занимает 2 байта (вызвано тем, что имена файлов хранятся в Юникоде).

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

      Когда экстент необходимо увеличить (обычно из-за того, что пользователь добавляет данные в уже большой файл), NTFS пытается выделить физически смежные кластеры в одном и том же экстенте. Если непрерывного пространства больше нет, NTFS выделит новый экстент в другом месте на диске, разделив файл на два фрагмента. Если новый экстент также не обеспечивает достаточного непрерывного пространства, действие повторяется. Заголовок атрибута данных (хранящийся в записи MFT) хранит эту информацию в виде LCN и длин серий, и NTFS использует эту информацию для поиска экстентов.

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

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

      Если имеется больше записей, чем может поместиться в записи MFT, NTFS создает новый экстент с нерезидентным атрибутом, который называется индексным буфером. Для этих каталогов индексные буферы содержат так называемое дерево b+, представляющее собой структуру данных, предназначенную для сведения к минимуму количества сравнений, необходимых для поиска конкретной записи файла.

      Дерево Ab+ хранит информацию (или индексирует информацию) в отсортированном порядке. Запрос на отсортированный список записей в каталоге выполняется быстро, потому что это порядок хранения в индексном буфере. Чтобы найти конкретную запись, поиск выполняется быстро, потому что деревья имеют тенденцию становиться широкими, а не глубокими, что сводит к минимуму количество обращений, необходимых для достижения определенной точки в дереве.

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