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

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

 

 

Орел 2011

 

Авторы:

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

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

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

 

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

 

 

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

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

 

 

Редактор _________________

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

 

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

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

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

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

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

 

Подписано к печати ___________г. Формат 60 84 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

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

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

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

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

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

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

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

1.12 B-деревья 21

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

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

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

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

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

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

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

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

Введение

 

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

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

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

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

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

База данных (БД) – это совместно используемый набор логически связанных данных и описание этих данных, предназначенное для удовлетворения информационных потребностей организации.

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

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

 

Пример,

Отношение Сотрудник (табельный номер, номер отдела, имя):

record num: integer;

depNum: integer;

name: string [20];

end;

 

Часто при обсуждении физического хранения БД используется термин файл. В данном случае под файлом понимают набор записей одинакового формата. Под форматом записи понимают список полей с указанием их типов. То есть термин «файл» применяют для обозначения физического представления отношения БД. На самом деле БД может хранится в одном файле операционной системы (СУБД Interbase), во многих файлах, причем для каждого отношения существует свой файл (СУБД Paradox), или независимо от количества файлов, то есть БД может быть размещена в нескольких файлах, одновременно файл может включать несколько баз (СУБД MSSQL 6.5).

Рассмотрим организацию записи на диске.

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

1. Некоторые байты могут свидетельствовать о формате записи. Это необходимо, если совместно могут храниться записи различных форматов.

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

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

4. Бит использования. Он хранит информацию о наличии свободного места.

5. Неиспользуемое пространство. Байты, не хранящие никакой информации. Такие байты необходимы для более удобного чтения записей. Например, для достижения кратности разрядности процессора.

Если запись подразумевает такие типы данных как text, image, blob (двоичная информация), то такие данные не хранятся вместе с записью, а хранятся в отдельном блоке. В записи же хранится адрес.

 

Пример,

Пусть храним вышеописанную запись. В файле хранятся записи только одного формата. СУБД обеспечивает сборку мусора.

Отношение Сотрудник (табельный номер: integer, номер отдела: integer, фамилия: char(20), фото: image)

Рисунок 1 – Схема записи отношения сотрудник (в байтах)

 

1 - служебная информация;

2 - 5 – табел. номер;

6 - 9 – номер отдела;

10 - 29 – фамилия;

30 - 33 – ссылка на фото.

 

Если записи имеют переменную длину:

Сотрудник (табельный номер: integer, номер отдела integer, адрес varchar(100)) и СУБД имеет ограничение на длину строки с переменной длиной равной 255 символам (рисунок 2).

 

Рисунок 2 – Схема записи отношения сотрудник с переменной длинной (в байтах)

 

1 - служебная информация;

2-5 - табельный номер;

6-9 - номер отдела;

10 - фактическая длина фамилии;

11-109 – байты для хранения фамилии;

 

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

Наиболее быстрая обработка данных была бы возможна, если размещать БД целиком в оперативной памяти. Однако практически размеры БД гораздо больше, поэтому возникает необходимость переноса фрагментов данных с диска (внешней памяти) в оперативную (первичную) память. Поэтому можно говорить, что данные на диске хранятся разделенными на части. Такие части называются блоками или страницами. Размер блока зависит от количества байт, которые считываются с диска за один раз.

Чаще всего запись по размеру намного меньше, чем блок (исключения составляют поля типа рисунок и текст, то есть строка неограниченной длины). Поэтому в блоке храниться множество записей. Кроме записей блок включает специальное пространство для указателя. Это связано с тем, что блоки в файле хранятся в виде списка, и каждый блок должен содержать указатель на связанный блок. Таким образом, блок графически можно представить в следующем виде – рисунок 3.

 

 

Рисунок 3 – Схема блока

 

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

 

⇐ Предыдущая12345Следующая ⇒

Поделиться: