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

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

Базы данных
Виноградова М.В.
МГТУ им. Н.Э. Баумана, ИУ5

2. Обмен данными между внешней памятью и оперативной памятью

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

3. Хранение записей

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

4. Модель внешней памяти

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

5. Неплотный индекс

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

6. В-дерево

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

7. Плотный индекс

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

8. Инвертированный файл

• Основной файл F, записи не
упорядочены по полю К2
• Инвертированный файл FD
(инвертирован по полю К2)
– Записи вида (К2,Р), где К2 –
поле, Р – указатели на
записи с полем К2
– Записи индекса
упорядочены по полю К2
– Переменное количество
указателей, возможна
цепочка (доп.служ.файл)
– Количество записей
индекса = количеству
значений поля К2