B-деревья в файловых системах
В дополнение к его использованию в базах данных, B-дерево также используется в файловых системах, чтобы обеспечить быстрый произвольный доступ к произвольному блоку в определенном файле. Основная проблема заключается в том, чтобы превратить адрес файла i в адрес блока диска (или, возможно, в сектор головки цилиндров).
Некоторые операционные системы требуют, чтобы пользователь выделял максимальный размер файла при его создании. Затем файл может быть выделен как непрерывные блоки диска. В этом случае, чтобы преобразовать адрес блока файла i в адрес блока диска, операционная система просто добавляет адрес блока файла i к адресу первого блока диска, составляющего файл. Схема проста, но файл не может превышать созданный размер.
Другие операционные системы позволяют файлу расти. Результирующие дисковые блоки могут не быть смежными, поэтому отображение логических блоков на физические блоки является более сложным.
MS-DOS, например, использовал простую таблицу размещения файлов (FAT). FAT имеет запись для каждого блока диска, и эта запись определяет, используется ли его блок файлом и, если да, какой блок (если есть) является следующим дисковым блоком того же файла. Итак, распределение каждого файла представлено в виде связного списка в таблице. Чтобы найти адрес диска файлового блока i, операционная система (или дисковая утилита) должна последовательно следовать списку связанных файлов в FAT. Хуже того, чтобы найти свободный блок диска, он должен последовательно сканировать FAT. Для MS-DOS это не было большой проблемой, потому что диски и файлы были маленькими, а в FAT было мало записей и относительно короткие цепочки файлов. В файловой системе FAT12 (используемой на гибких дисках и ранних жестких дисках) было не более 4080 записей, и обычно FAT находился в памяти. Поскольку диски становились больше, архитектура FAT начала сталкиваться с проблемами. На большом диске, использующем FAT, может потребоваться выполнить чтение с диска, чтобы узнать местоположение на диске блока файла для чтения или записи.
В TOPS-20 (и, возможно, в TENEX) использовалось дерево уровней от 0 до 2, которое имеет сходство с B-деревом. Дисковый блок состоял из 512 36-битных слов. Если файл помещается в блок из 512 (29) слов, тогда каталог файлов будет указывать на этот блок физического диска. Если файл умещается в 218 слов, то каталог будет указывать на вспомогательный индекс; 512 слов этого индекса будут либо NULL (блок не выделен), либо указывают на физический адрес блока. Если файл умещается в 227 слов, то каталог будет указывать на блок, содержащий индекс aux-aux; каждая запись будет либо NULL, либо будет указывать на вспомогательный индекс. Следовательно, блок физического диска для файла из 227 слов может быть помещен в две операции чтения с диска и чтения на третьей.
В файловой системе Apple HFS+, Microsoft NTFS, AIX (jfs2) и некоторых файловых системах Linux, таких как btrfs и Ext4, используются B-деревья.
B* деревья используются в файловых системах HFS и Reiser4.
Файловая система HAMMER в DragonFly BSD использует модифицированное дерево B+.
Читайте также:
Комментарии
Отправить комментарий