БАНКИ ДАННЫХ

страниц с магнитных носителей в оперативную память. Реализует механизм виртуальной

памяти.

фиксированным размером блоков, называемых
страницами,
2. системы с переменным размером блоков, называемых

сегментами.

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

разделяются на отдельные области-сегменты. Каждый сегмент представляет собой отдельную логическую

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

Можно выделить два основных типа сегментов:
1. программные сегменты
2. сегменты данных (сегменты стека являются частным случаем сегментов данных).

100 Гб = 50 млн. страниц
Буфер ввода/вывода – 1 Гб

= 500 тыс. страниц

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

ли страница,
2 – идет ли обмен,
3 – была ли запись.

Наличие двух уровней системы:
a. уровня непосредственного управления данными во внешней

памяти, управления буферами оперативной памяти, управления транзакциями и журнализацией изменений БД
b. языкового уровня (например, уровня, реализующего язык SQL).
2. Поддержание отношений-каталогов.
Информация, связанная с именованием объектов базы данных и их конкретными свойствами (например, структура ключа индекса), поддерживается подсистемой языкового уровня.

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

простую
регулярную структуру. Но для того, чтобы обеспечить возможность эффективного выполнения операторов языкового уровня как над одним отношением (простые селекция и проекция), так и над несколькими
отношениями должны поддерживаться дополнительные "управляющие" структуры - индексы.

отношений - основная часть базы данных, большей частью непосредственно видимая

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

и множество связей между ними. Такое определение охватывает все возможные

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

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

в данной машинной архитектуре, в данной системе программирования мы всегда

можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти.
В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать:
1. Несвязанные структуры (векторы, массивы, строки, стеки, очереди)
2. Связанные структуры (связные списки).
Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры.

однородным, если длина и формат всех элементов одинаковы
Такие массивы замечательны

тем, что легко определяется адрес любого элемента

a11 + ((i –1)n + (j – 1)) d

где d – длина элементов.

формат элементов могут быть разными.
Пусть элементы a1,…,an имеют описатели a1,…,an
Тогда

данные можно представить (a1 a1 ,…, an an)
Или (n a1…an a1…an ), если все описатели ai одинаковой длины и содержат длину данного ai

с
n атрибутами a1,…,an в каждой строке, то в
dbf

-формате это будет будет представлено так
n m a1…an (a1…an )1 … ( a1…an )m
n m
Такой формат применил Рэтлифф в СУБД dBASE, которая быстро получила распространение, а
dbf-формат стал всемирным стандартом на ~ 20 лет.

(Standard Generalized Markup Language)
- XML (Extensible Markup Language)

- HTML (Hypertext Markup Language)

SGML XML HTML

HTML - стандарт для описания страниц в интернет
В XML есть секция DTD (Document Type Definition), которая описывает структуру данных – аналог схемы БД
В HTML заданный набор объектов, в XML можно создавать свои объекты

Общий стиль описания:
<имя объекта1>
<имя подоб1.1>
<имя данного 1> данное 1 < /имя данного 1>
<имя данного 2> данное 2 < /имя данного 2>
……
< /имя подоб1.1>
……
< /имя объекта1>

на одном конце. Метод LIFO (Last In First Out)
Очередь

– список, включение на одном конце, а исключение на другом. Метод FIFO (First In First Out)
Дек – включение и исключение на обоих концах, сокращение от Double Ended Que.

вершина – корень. Если его убрать, все остальные вершины распадаются

на m > 0 поддеревьев

помощи ссылок или матрицами
Матрица инцидентности

Матрица смежности

Р е б р а

В е р ш и н ы

В
е
р
ш
и
н
ы

В
е
р
ш
и
н
ы

Уитни. Матрицы инцидентности и смежности однозначно

определяют граф, кроме одного случая.

1

2

3

3

2

1

В
е
р
ш
и
н
ы

–
выделенных иерархий

индекса – предварительная обработка информации или online поддержка при вводе

данных.

данное 1; Ид 2, дан 2; Ид 3, дан 3;

…. Ид n, дан n.
Плотный индекс: Ид 1, адрес 1; Ид 2, адр 2; Ид 3, адр 3; …. Ид n, адр n.

данное 1; Ид 2, дан 2; Ид 3, дан 3;

…. Ид n, дан n.
Плотный индекс: Ид 1, адрес 1; Ид 2, адр 2; Ид 3, адр 3; …. Ид n, адр n.

Плотный индекс – однородный массив, который можно отсортировать и потом искать делением пополам.

— это порядковый номер записи в основной области, которая имеет

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

Пример организации файла с плотным индексом

Ид 21, дан 21; …. Ид n1, дан n1
Страница

1
……..
Ид 1N, дан 1N; Ид 2N, дан 2N; …. Ид nN, дан nN
Страница N
Индекс:
Ид 11, адрес стр 1; Ид 12, адрес стр 2; …. Ид 1N, адрес стр N

В индекс помещаются Идентификаторы первых данных всех страниц.

ki не помещается на страницу i, то заводится новая страница

и часть страницы переносится в новую (область переполнения).

Ид 1i, дан 1i; …. Ид ki, дан ki; …. Ид ni, дан ni
Страница i


Ид 1i, дан 1i; …. Ид ki, дан ki;
Страница i
Ид (k+1)i, дан (k+1)i; …. Ид ni, дан ni
Страница N+m (область переполнения страницы i)

переполнения.

Ид 1i, дан 1i; …. Ид ki, дан ki; Адрес

Страницы N+m
Страница i
Ид (k+1)i, дан (k+1)i; …. Ид ni, дан ni
Страница N+m (область переполнения страницы i)

Рареженный индекс строится именно для упорядоченных файлов. Для этих файлов

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

В – дерево проверяем,
если x < a1 – налево

x >= a1 – направо,
и так во всех узлах

Обозначим
N – общее количество данных
l – количество данных на одной странице
k – глубина дерева

Тогда
N / l – число страниц
2k >= N / l . Если ветви одной длины, то k = log2 (N/l)

вертикали, если длины всех его ветвей отличаются не более чем

на 1.
Тогда k = [log2 (N/l)] + 1. Это число необходимых сравнений, в больших массивах оно обычно равно числу обменов с внешней памятью.

Определение. Дерево называется сбалансированным по горизонтали, если все веера подчиненных вершин отличаются не более чем на 1, | n - n1 | <= 1.

n

n1

Если n-арное дерево сбалансировано по вертикали и горизонтали, то
k = [logn (N/l)] + 1

Поэтому вместо бинарных деревьев обычно используются n-арные деревья.
n - максимальное число ссылок на странице.

ключа сделать короткий идентификатор, то возможна коллизия: F (ключ1)

= F (ключ2)

На странице, определяемой идентификатором, записываются
Ключ 1, дан 1; Ключ 2, дан 2; …. Ключ n, дан n и м. б. ссылка на страницу переполнения

значением хеш-функции в виде связанных списков

данных на одной странице
n – количество ключей на одной странице

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

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

Пример инвертированного списка индекса номер группы для таблицы студентов

в основной памяти. В основной памяти поддерживается справочник, организованный на

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