ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ – УЧЕБНО-НАУЧНО-ПРОИЗВОДСТВЕННЫЙ КОМПЛЕКС» Учебно-научно-исследовательский институт информационных технологий

Кафедра «Информационные системы»

Д.В. Рыженков, С.В. Новиков, А.В. Артемов

Физическая организация данных в

информационных системах

Методические указания

по выполнению лабораторных работ

Дисциплина – «Базы данных»

Специальность – 080801.62 «Прикладная информатика»

Допущено ФГБОУ ВПО «Госуниверситет-УНПК»

для использования в учебном процессе в качестве методических указаний для высшего

профессионального образования

Орел 2011

Авторы:

доцент кафедры «ИС», к.т.н. Д.В. Рыженков

доцент кафедры «ИС», к.т.н. С.В. Новиков

доцент кафедры «ИС», к.т.н. А.В. Артемов

Рецензент: к.т.н. доцент кафедры «ИС» А.И. Фролов

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

Методические указания предназначены для студентов очной (дневной) формы обучения по специальности 0800801.62 «Прикладная информатика».

Редактор _________________

Технический редактор _________________

Федеральное государственное бюджетное образовательное

учреждение высшего профессионального образования

«Государственный университет – учебно-научно-

производственный комплекс»

Лицензия ИД 00670 от 5.01.2000

Подписано к печати ___________г. Формат 6084 1/16

Усл. печ. л. ___. Тираж __ экз.

Заказ №____

Отпечатано с готового оригинал-макета

© ФГБОУ ВПО «Госуниверситет-УНПК», 2011

© Рыженков Д.В., Новиков С.В., Артемов А.В., 2011

Содержание

Введение 4

1. Теоретические сведения 5

1.1 Физическая организация данных. Основные понятия 5

1.2 Эффективность организации блоков в файле 8

1.3 Организация файлов в виде кучи 9

1.4 Эффективность организации файлов в виде кучи 10

1.5 Организация хешированных файлов 11

1.5.1 Статическое хеширование 11

1.5.2 Динамическое хеширование 12

1.6 Операции над хешированными файлами 13

1.7 Эффективность хешированных файлов 14

1.8 Индексированные файлы 15

1.9 Операции над индексированными файлами 17

1.10 Эффективность индексированных файлов 21

1.11 Плотное индексирование 21

1.12 B-деревья 21

1. 13 Операции на В-деревьях. 22

1.14 Эффективность В-дерева. 24

2 Задания на лабораторные работы 25

2.1 Задание 1. Организация файла в виде кучи 25

2.2 Задание 2. Организация хешированного файла 26

2.3 Задание 3. Организация индексного файла 27

2.4 Задание 4. Организация файла в виде В-дерева 28

Рекомендуемая литература 31

Введение

Физические модели баз данных определяют способы размещения данных в среде хранения и способы доступа к этим данным, которые поддерживаются на физическом уровне. Исторически первыми системами хранения и доступа были файловые структуры и системы управления файлами, которые фактически являлись частью операционных систем. СУБД создавала над этими файловыми моделями свою надстройку, которая позволяла организовать всю совокупность файлов таким образом, чтобы она работала как единое целое и получала централизованное управление от СУБД. Однако непосредственный доступ осуществлялся на уровне файловых команд, которые СУБД использовала при манипулировании всеми файлами, составляющими хранимые данные одной или нескольких баз данных.

Однако механизмы буферизации и управления файловыми структурами не приспособлены для решения задач собственно СУБД, эти механизмы разрабатывались просто для традиционной обработки файлов, и с ростом объемов хранимых данных они стали неэффективными для использования СУБД. Тогда постепенно произошел переход от базовых файловых структур к непосредственному управлению размещением данных на внешних носителях самой СУБД. И пространство внешней памяти уже выходило из-под владения операционных систем и управлялось непосредственно СУБД.

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