Модели внутренней структуры для файловой системы

Обмен данными между внешней памятью и оперативной памятью
Оперативная память
Внешняя память
Файл 1
Блок 1
Блок N
Блок 2
Буфер
Блок 1
Блок 2
Блок 1
Блок 5
Чтение и запись
Блок 5
Файл 2
Блок N
Блок 1
Блок N
Блок 1
Буферный пул
Чтение блока
Запись блока
Чтение блока
Запись блока

Хранение записей
Файл состоит из блоков
Обмен данными с ОП блоками (страницами)
Блок состоит из записей и служ.инф.
Запись м.б. в нескольких блоках
Запись содержит служ.инф.; фикс/перем. длины
Байты блока пронуменованы
Номер записи в блоке – номер ее первого байта от начала блока
Номер (адрес) записи в файле:
Абсолютный (машинный),
Относительный (номер в файле или номер блока + относ.адрес в блоке или номер блока + ключ записи)
Ключ записи

Модель внешней памяти
З-1
З-2
З-1
З-2
Бл.1
З-3
З-4
З-4.1
З-4.2
Бл.2
З-5
З-6
З-6.1
З-6.2
Бл.3
З-X
З-Y
Бл.N
Бл.п.1
З-6.4
З-6.3
З-4.3
Бл.п.2
Бл.п.M
Область переполнения
Основная область памяти

Неплотный индекс
F – файл данных. Записи упорядочены по ключу K
FD – файл индекса, одна запись на один блок файла
Содержит записи вида (K,P), где K-ключ первой записи блока, P-указатель на блок

В-дерево
Неплотный индекс над неплотным индексом, до единственного блока
В-дерева порядка m, где m – количество уровней дерева
Блоки 1-го уровня могут быть связаны в цепь
Число обменов = числу уровней
Поиск по интервалу: сначала по дереву, потом по цепи 1-го уровня

Плотный индекс
Основной файл (F) не упорядочен по ключу К
Файл индекса (FD)
Записи вида (К,Р), где К – ключ, Р – указатель на запись
запись индекса на каждую запись данных
Записи индекса упорядочены по ключу К
Возможно В-дерево над плотным индексом