5. 10. Организация файлов баз данных



Скачать 149.52 Kb.
Дата08.10.2012
Размер149.52 Kb.
ТипДокументы


5.10. Организация файлов баз данных

Если размер файла данных ограничен, то для поиска в нем достаточно использовать последовательный просмотр его записей. Кроме того, для выполнения более сложных операций, например сортировки, он может быть полностью прочитан в память и там обработан. Для файлов большого объема, а также в случае постоянного поиска и обновления в нем информации такой подход уже неэффективен. В общем случае в файл вводится некоторая избыточная информация, которая позволяет значительно ускорить поиск в условиях постоянного обновления данных. Наиболее распространенным примером таких файлов являются файлы баз данных. Рассмотрим применительно к ним некоторые основные понятия.

Запись. Kлюч. Индекс

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

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

Индексная таблица. Индексный файл

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

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

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


Значение, в порядке возрастания или убывания которого строится индекс, может быть значением одного поля (простой индекс), а может быть составлено из значений нескольких полей (составной индекс). Один файл может иметь несколько индексов, составленных для различных полей.

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

Операции над индексными таблицами и файлами

Создание индексной таблицы (файла) заключается в заполнении и последующей сортировке таблицы ссылок.

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

При редактировании записей соответствующие изменения файла должны отражаться в индексе:

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

- при удалении записи ссылка на нее должна быть удалена из индекса с соответствующим "уплотнением" индексной таблицы;

- при обновлении (Update) записи могут быть изменены значения индексируемых полей, в результате чего нарушается порядок следования записей в индексе. Индекс корректируется путем извлечения из таблицы ссылки на обновленную запись и включения ее в новое место.

Область переполнения

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

- при поиске по индексу производится двоичный поиск в основной области и последовательный в области переполнения;

- при добавлении записи ссылка на нее заносится в область переполнения;

- при удалении записи и удалении ссылки на нее из основной области "уплотнение" этой области не производится, в индексной таблице возникает "пустое место";

- при обновлении записи ссылка на нее может быть исключена из основной области и включена в область переполнения;

- при увеличении области переполнения выше некоторого предела индекс пересобирается заново.

Многоуровневые индексы

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

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

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

Индексное дерево

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

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

Второй способ основан на естественном хранении дерева в массиве в следующем виде: индексы вершин левого и правого поддерева для вершины с номером n имеют значения 2n и 2n+1 соотвественно. Однако если различные ветви дерева имеют разную длину, то такое представление неэффективно использует память. Кроме того, при выполнении сложных преобразований структуры дерева требуется выполнять копирование его вершин.

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

Условие сбалансированности является рекурсивным: если сбалансировано все дерево, то сбалансированы все его поддеревья. Для контроля сбалансированности в каждой вершине дерева вводится переменная balance, которая содержит разницу длин правого и левого поддерева и в сбалансированном дереве принимает следующие значения:

- -1 - левое поддерево на 1 длиннее правого;

- 0 - длины поддеревьев совпадают;

- 1 - правое поддерево на 1 длиннее левого.

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

В приведенном примере используется ссылка на указатель для передачи в функцию указателя на текущую вершину с возможностью его изменения:
//-----------------------------------------------------------------------

struct tree

{

int value; // Значение элемента

tree *left,*right; // Ссылки на поддеревья

int balance; // Значение разницы длин

}; // поддеревьев

int insert(tree *&pp, int v) // Включение вершины со значением v

{

tree *pnew;

if (pp == NULL) // Включить на место пустой ссылки

{

pnew = new tree;

pnew->right = NULL; // Правое и левое поддерево

pnew->left = NULL; // пусты

pnew->balance = 0; // Вершина сбалансирована

pp = pnew; // Включить новую вершину

return 1; // Длина увеличилась

}

if (pp->value) > v) // Включить в левое поддерево

{

if (!insert(pp->left, v))

return 0 ; // Длина дерева не возросла

pp->balance --; // Иначе - баланс влево

switch(pp->balance)

{

case 0: return 0; // Длина уменьшилась

case -1: return 1; // Длина возросла

case -2: .... // Выполнить балансировку

} // левого поддерева

}

else // Включить в правое поддерево

{

if (!insert(pp->right, v))

return 0; // Длина дерева не возросла

pp->balance ++; // Иначе - баланс вправо

switch(pp->balance)

{

case 0: return 0; // Длина уменьшилась

case 1: return 1; // Длина возросла

case 2: .... // Выполнить балансировку

} // правого поддерева

}

}

Варианты балансировки левого и правого поддерева абсолютно симметричны. Структура фрагмента дерева и фрагмент алгоритма балансировки приводятся ниже для правого поддерева:
C > B B > C

pp->balance == 2 p1->balance == 1 p1->balance == -1

┌─┐ ┌─┐ ┌─┐

pp ──>│5│ pp ───>│7│ pp─────>│B│

└─┘ └─┘ └─┘

┌────┴──┐ ┌───┴───┐ ┌───┴─────┐

┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐

│A│ │7│<── p1 │5│ │C│ │5│ │7│

└─┘ └─┘ └─┘ └─┘ └─┘ └─┘

┌────┴────┐ ┌──┴──┐ ┌────┴───┐ ┌──┴───┐

┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐ ┌─┐┌─┐ ┌─┐

p2-─>│B│ │C│ │A│ │B│ │A│ │D││E│ │C│

└─┘ └─┘ └─┘ └─┘ └─┘ └─┘└─┘ └─┘

D ──┴── E
//-------------------------------------------------------------

tree *p1,*p2;

p1 = pp-> right;

if (p1->balance == 1) // Вариант 1

{

pp->balance = 0;

pp->right = p1->left; // Правый (5) = B

p1->left = pp; // Левый (7) = 5

pp = p1; // Вершина поддерева = 7

}

else // Вариант 2

{

p2 = p1->left; //

p1->left = p2->right; // Левый (7) = E

p2->right = p1; // Правый (B) = 7

pp->right = p2->left; // Правый (5) = D

p2->left = pp; // Левый (B) = 5

// Баланс (5) = 0 или -1

// Баланс (7) = 0 или 1

pp->balance = -(p2->balance == 1);

p1->balance = (p2->balance == -1);

pp = p2; // Вершина поддерева = B

}

pp->balance = 0;

return 0;

Преобразование ключей

Наиболее часто встречается операция поиска записи по идентифицирующему его полю - ключу. Поэтому файл, как правило, индексируется по ключевому полю. Поиск по ключу в общем виде может рассматриваться как преобразование значения ключевого поля в адрес записи в файле (или номер записи), то есть как функция вида
f(key) -> m

Очевидно, можно сформулировать обратную задачу: если некоторым образом подобрать функцию f(), то ее можно использовать для определения места в файле, куда следует поместить запись с ключом key. Основное требование к такой функции: она должна как можно более равномерно распределять записи с различными значениями ключа по файлу, то есть иметь "случайный" вид. Кроме того, необходимо каким-то образом решить проблему "коллизий", то есть попадания нескольких записей с различными ключами в один физический адрес (номер записи).

Функция f() называется распределяющей или рассеивающей функцией. Пример одной из таких функций: берется квадрат значения ключа, из него извлекаются n значащих цифр из середины, которые и дают значение номера записи в файле:
int Place1024(key) // Функция рассеивания для файла из

unsigned key; // 1024 записей и 16 разрядного

{ // ключа

unsigned long n,n1;

int m;

n = (unsigned long)key * key;

for (m=0, n1 = n; n1 !=0; m++, n1 >>= 1);

// Подсчет количества значащих

if (m < 10) return(n); // битов в n

m = (m - 10) / 2; // m - количество битов по краям

return( (n >> m) & 0x3FF);

}

Известны два способа решения проблемы коллизий. В первом случае файл содержит область переполнения. Если функция f() вычисляет адрес записи в файле, а соответствующее место уже заполнено записью с другим значением ключа, то новая запись помещается в область переполнения. При этом возможны два варианта:

- записи в области переполнения не связаны между собой, и для поиска в ней используется последовательный просмотр всех записей;

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

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

- первая свободная позиция, начиная от текущей;

- проверяются позиции, пропорциональные квадрату шага относительно текущей занятой, то есть m = ( f(key) + i * i ) mod n, где i - номер шага, n - размер таблицы. Такое размещение позволяет лучше "рассеивать" записи при коллизии.

Рассматриваемый метод обозначается терминами расстановка или хеширование (от hash - смешивать, перемалывать).

Одним из существенных недостатков метода является необходимость заранее резервировать файл для размещения записей с номерами от 0 до m - в диапазоне возможных значений функции рассеивания. Кроме того, при заполнении файла увеличивается количество коллизий и эффективность метода падает. Если же количество записей возрастает настолько, что файл необходимо расширять, то это связано с изменением функции рассеивания и перераспределением (перезаписью) уже имеющихся записей в соответствии с новой функцией.

Задания к лабораторным работам

Задание рассчитано на выполнение в течение 2-3 лабораторных занятий и предполагает разработку функций поддержки индексного файла с заданной структурой, заполнение файла данных, построение индекса и выполнение операций поиска, добавления, удаления и обновления записи.

1. Построение двухуровнего индекса. Выполнение операций над записями файла с коррекцией таблиц верхнего и нижнего уровней. Сохранение индекса нижнего уровня в файле. Построение индекса верхнего уровня при открытии индекса.

2. Индексный файл с областью переполнения. Выполнение операций с коррекцией области переполнения и основной области. При превышении размера области переполнения 10% от размера основной области производится операция повторного построения основной области.

3. Индексный файл с индексируемым полем переменной длины. Значение поля хранится в отдельном файле записей переменной длины, а запись файла данных содержит ссылку на него.

4. Файл содержит записи переменной длины – текстовые строки, организованные в виде дерева: каждая запись содержит ссылки (адреса в файле) двух других записей. Реализовать операции двоичного поиска и включения записи в файл без чтения в память всего файла. Обеспечить сохранение сбалансированности дерева.

5. Индексный файл представляет собой индексное дерево, которое сохраняется в файле записей фиксированной длины "естественным" образом. Записи индексного файла содержат номера записей файла данных. Индекс считывается в память полностью, для записей первых m уровней (задается при загрузке) обеспечивается считывание и связывание записей файла данных для ускорения поиска по индексу. Обеспечить сохранение сбалансированности дерева.

6. Ключом в файле записей фиксированной длины является поле name[30], содержащее строку ограниченного размера. Реализовать функции добавления, удаления и поиска записей по ключу с использованием метода расстановки ключей (хеширования). Для исключения коллизий использовать область переполнения с организацией списков записей. Предложить функцию расстановки и проверить ее эффективность.

7. Ключом в файле записей является целая переменная. Используется хеширование на основе функции середины квадрата. Размер таблицы изменяется: 16,32,64 и так далее записей. При отсутствии в области переполнения свободного места создается новый файл вдвое большего размера и в него переписываются записи из старого файла с использованием новой функции размещения (количество разрядов в "середине квадрата" увеличивается на 1).

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


Романов Е.Л. Информатика и программирование. Язык Си. (конспект лекций) .


Похожие:

5. 10. Организация файлов баз данных iconПроектирование базы данных
В результате появились модели баз данных, методики проектирования баз данных, специальное программное обеспечение для работы с базами...
5. 10. Организация файлов баз данных iconНаучная работа по информатике «Использование баз данных и субд для обработки экономической информации»
В состав банка данных входят одна или несколько баз данных, справочник баз данных, субд, а также библиотеки запросов и прикладных...
5. 10. Организация файлов баз данных icon1. Назначение и основные компоненты среды базы данных. Предшественники баз данных. Необходимость централизованного управления данными. Концепция интеграции. Предшественники баз данных. База данных
База Данных — совместно используемый набор логически связанных данных (и их описание!), предназначенных для удовлетворения информационных...
5. 10. Организация файлов баз данных iconУчебная программа курса «Основы баз данных» Введение в базовый курс «Основы баз данных»
«Сущность-связь». В курсе рассматриваются вопросы теории нормализации реляционных баз данных. В качестве манипуляционной части в...
5. 10. Организация файлов баз данных iconЕвдокимов А. В., к ф. м н
Со времени появления компьютерных систем появилось большое количество различных баз данных для различных целей. Различие характеристик...
5. 10. Организация файлов баз данных icon4 Языки баз данных
Субд данной функции (формат файлов данных, индексирование, хэширование и буферизация) во многом зависит и эффективность функционирования...
5. 10. Организация файлов баз данных iconБазы данных Лектор 2010/11 уч года: д ф. м наук, профессор Кумсков М. И
В курсе обсуждаются общие вопросы систем управления базами данных (субд) и основы реляционных баз данных: введение в реляционные...
5. 10. Организация файлов баз данных iconВопросы к экзамену по курсу «базы данных»
Компоненты субд. Применение sql для доступа к бд. Основные функции языка sql. Язык интерактивных запросов. Язык программирования...
5. 10. Организация файлов баз данных iconАдминистратора баз данных должностная инструкция
На должность администратора баз данных назначается лицо, имеющее высшее математическое, экономическое или техническое образование...
5. 10. Организация файлов баз данных iconОсновы работы с базами данных Содержание
В хорошо спроектированной базе данных избыточность данных исключается, и вероятность сохранения противоречивых данных минимизируется....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org