база данных:. Внутренняя организация СУБД

раскрыты вопросы в ниже перечисленных списках ...

1.Теоретическое задание. Внутренняя организация СУБД
2.Практическая часть. Расчет заработной платы
3.Выводы
4.Список литературы

Отсутствует (таковы требования к выполнению работы)

Поиск и выборка нужных записей в базе данных осуществляются в следующей последовательности:
1.   Выбирается индекс, соответствующий условию поиска (например Товар, если в запросе выполняется поиск товара с конкретным названием).
2.   В индексе находится строка с заданным условием поиска (например Туфли).
3.    Из найденной строки выбираются номера страниц, где хранятся искомые записи.
4.   Полученные номера страниц используются для чтения необходимой информации.
Большинство СУБД реализует этот процесс автоматически, без участия пользователя.
Если для таблицы определены несколько индексов по отдельным полям, при поиске записей в данной таблице по условиям поиска, заданным в этих полях, соответствующие индексы используются совместно.
Например, для поля Дата поставки табл. 3.3 создан также индекс Дата (табл. 3.5):
Таблица 3.5
Индекс Дата
Дата поставки
Номера страниц
10.12.05
1, 2
11.12.05
3, 4
12.12.05
5, 6, 7
Для больших таблиц сами индексы могут занимать несколько страниц во внешней памяти. В таких ситуациях создаются многоуровневые индексы, например, в виде сбалансированных деревьев (B-дерево или Balanced-tree), имеющих иерархическую структуру. Целью создания B-дерева является ускорение поиска, стремление избежать просмотра всего индекса.
Рассмотрим процесс построения B-дерева на простом примере. Предположим, таблица сведений о поставках товаров в магазин включает 18 записей и индексируется по номерам накладных: 18, 28, 37, 54, 59, 60, 61, 67, 68, 70, 77, 80, 83, 91, 93, 96, 98, 99. На каждой странице в памяти содержатся только два адреса (фактически их может быть больше).
Размещаем на корневой странице дерева значения данных в поле Номер накладной, равные 60 и 82, и три указателя (рис. 2). Данные со значениями в поле Номер накладной, меньшие или равные 60, могут быть найдены с помощью левого указателя; бульшие 60 и меньшие или равные 82 – с помощью среднего указателя; бульшие 82 – с помощью правого указателя (см. рис. 2). Другие страницы индекса интерпретируются аналогичным образом.
На нижнем уровне B-дерева находится множество страниц с указателями на страницы, где хранятся данные (см. рис. 2).
Для нахождения с помощью B-дерева адреса размещения во внешней памяти любой страницы с данными, достаточно последовательно рассмотреть только три страницы индекса (на рис. 2 жирными стрелками указан маршрут поиска страницы с номером накладной 77), что существенно меньше общего количества страниц с данными.
 
указатели на страницы, где находятся данные
Рисунок 2 –  Индекс в виде B-дерева
Реальные данные, для которых строится многоуровневый индекс, часто не позволяют непосредственно получить сбалансированное дерево, построенное на рис. 2. В таких случаях для его создания применяются специальные алгоритмы, рассмотренные, например, в работе.
Недостатком индексирования является необходимость выделения во внешней памяти дополнительного места для хранения индексов. Существуют оценки, что файл, в котором созданы индексы для всех полей размещенной в нем таблицы, занимает практически вдвое больше места на внешнем носителе по сравнению с исходным файлом. Кроме того, наличие индексов затрудняет обновление информации, хранящейся в базе данных, и требует дополнительных затрат времени на данный процесс.
Поэтому не рекомендуется индексировать все поля таблиц или поля, данные в которых часто изменяются. Наиболее эффективным является создание индексов для первичных и внешних ключей, для полей, по которым в основном выполняются запросы.
Хеширование (Hashing) – алгоритмическое преобразование значений некоторого поля записей (первичного ключа или любого другого поля) в адреса их размещения на внешнем носителе.
При вводе данных СУБД вычисляет адрес страницы, на которой будет храниться запись, и заносит запись на эту страницу. При выполнении запросов реализуются аналогичные расчеты адреса страницы с последующим чтением записей с этой страницы. Достоинством такого метода является быстрый прямой доступ к данным. При этом время доступа практически не зависит от количества хранимых записей.
Рассмотрим технологию хеширования на примере данных, приводимых в табл. 1. Используем для вычисления адресов страниц значения данных в поле первичного ключа таблицы Номер накладной: 18, 28, 37. Предположим, что на каждой странице внешней памяти можно разместить только одну запись.
Номера накладных представляют собой целые двузначные числа. Поэтому если использовать номера накладных в качестве адресов страниц, для организации хранения информации потребуется 99 страниц с адресами от 01 до 99. Очевидно, что это нерационально, так как записей в исходной таблице всего семь и абсолютное большинство страниц останутся пустыми (приводимые рассуждения будут более убедительными, если значения данных, используемые для хеширования, пятизначные или шестизначные числа).
По указанной причине адреса страниц вычисляются с помощью специальной хеш-функции. Используем в качестве адресов страниц остаток от деления каждого значения номера накладной на простое натуральное число (например, 11), называемое сверткой ключа (обычно хеш-функции имеют более сложный вид) (табл. 3.6):
Таблица 3.6
Сведения о поставках товаров в магазин
Номер накладной
Название товара
Артикул
Количество
Дата
поставки
Адрес № стр.
37
Костюм
500
50
10.12.05
4
54
Сапоги
200
75
10.12.05
10
18
Туфли
100
120
11.12.05
7
80
Туфли
100
100
12.12.05
3
С помощью выполненного хеширования записи размещаются на семи страницах внешней памяти с адресами от 00 до 10.
Рассмотренный пример иллюстрирует и недостатки хеширования:
1.   Страницы с записями во внешней памяти могут располагаться неравномерно, с различным количеством пустых страниц между ними.
2.   Возможно совпадение рассчитанных адресов страниц для двух или нескольких записей (например адреса, вычисленные для номеров накладных 18, 29, 40, будут равны одному числу – семи).
Совпадение вычисленных адресов называется коллизией, значения данных, для которых получены одинаковые адреса – синонимами.
Существует много стратегий разрешения коллизий, но основные из них две:
а) с областью переполнения;
б) свободного замещения.
Стратегия разрешения коллизий с помощью области переполнения
Область хранения разбивается на две части: основную область и область переполнения (рис. 6).
При вводе в базу данных новой записи вычисляется значение хеш-функции, которое используется для определения места расположения страницы в основной области памяти. Например, если номер накладной равен 12, запись будет размещена на странице с адресом 1 (см. обозначения курсивом на рис. 6).
Когда страница с полученным адресом занята и возникает коллизия, новая запись заносится на первое свободное место в области переполнения. Например, запись с номером накладной 29, следовательно, значением хеш-функции, равным 7, будет размещена по адресу 500. В записи-синониме, которая находится в основной области, делается ссылка на адрес записи, размещаемой в области переполнения. В ситуациях повторения коллизий (номер накладной равен 40, значение хеш-функции – 7) вновь вводимая запись помещается на свободное место в области переполнения  (например, если страница с номером 501 занята, по адресу 502). Она становится второй в цепочке синонимов (этим обеспечивается сокращение времени на размещение новых записей) с помощью изменения ссылок на адреса синонимов (см. рис. 6).
При поиске нужной записи вычисляется значение ее хеш-функции, указывающее на адрес страницы в основной памяти. Если эта запись не является искомой, последовательно просматривается цепочка синонимов до получения необходимого результата. Очевидно, что скорость поиска существенно зависит от длины цепочки синонимов. Считается, что в цепочке не должно быть более 10 синонимов [ 4 ].
При удалении записи в основной области памяти на ее место перемещается вторая запись в цепочке синонимов, при этом все ссылки на синонимы в цепочке сохраняются. Если удаляется запись в области переполнения, изменяется адрес ссылки на следующий синоним в записи, предшествующей удаляемой записи.
Основная область
Адрес
(номер
страницы)
Номер накладной
Название
товара
Арти-
кул
Коли-чество
Дата
поставки
Ссылка на
синонимы
0
1
12
Сапоги
150
150
13.12.05
2
Область переполнения
Адрес
(номер страницы)
Номер
накладной
Название
товара
Арти-
кул
Коли-чество
Дата