Ковалевич И.А. Основы баз данных: учебное пособие
Подождите немного. Документ загружается.
Следовательно, при удалении необходимо выполнить шаг назад в цепном
списке. Ссылка на «предыдущий» позволяет совершить этот шаг наиболее
эффективно.
Упрощается и процедура включения новых элементов в
информационные структуры. При использовании связанных схем, новый
элемент можно размещать в первом свободном участке памяти, достаточно
лишь корректно изменить адресные ссылки у элементов, между которыми
производится включение, и правильно назначить ссылки у нового. При
последовательной организации структур данных операции обновления,
потребовали бы перемещения значительных частей списка, что в свою
очередь вед привело бы к большим затратам времени.
Дополнительные ссылки позволяют повысить эффективность
обработки данных, но в то же время являются причиной дополнительных
затрат внешней памяти.
Существуют и другие способы реализации структурных ассоциаций.
6.1.2.СТРАНИЦЫ
Страницей называется участок памяти,
предназначенный для хранения подмножества данных . Количество
байтов в странице жестко регламентировано для конкретной
системы и почти всегда кратно двум.
В большинстве систем в начале страницы размещается служебная
запись, называемая заголовком страницы. Она используется СУБД для
управления содержимым страницы.
На странице обычно хранится несколько записей базы данных и
имеется свободный участок, предназначенный для размещения новых
записей. В некоторых системах, когда запись базы данных не умещается
целиком на странице, она разбивается на несколько сегментов. При этом
сегменты одной записи хранятся на разных страницах. Адресные ссылки
между сегментами позволяют запись целиком выбрать в оперативную
память.
Страницы, как правило, нумеруются, и СУБД умеет извлекать
страницы по их номерам.
Обработку данных на уровне блоков и страниц может выполнять
система управления вводом-выводом операционной системы, а обработку
записей внутри страницы обеспечивает только СУБД. Для поиска записи
базы данных необходим просмотр страницы, а если запись
сегментированная, то просматривается содержимое нескольких страниц.
6.1.3.ХРАНИМАЯ ЗАПИСЬ
Каждой записи, определенной в схеме БД на внутреннем уровне,
соответствует хранимая запись. Она состоит из двух частей - служебной и
информационной.
Поля служебной части используются СУБД для идентификации
записи, задания ее типа, хранения признака логического удаления, для
кодирования значений элементов, для установления структурных
ассоциаций между записями. Никакие пользовательские программы не
имеют доступа к служебной части записи.
Поля информационной части содержат значения элементов данных.
Существует несколько способов размещения значения элементов в записи.
Рассмотрим наиболее употребимые.
Размещение с заранее предписанных позиций предполагает, что
значение элемента в каждом экземпляре записи появляется с одной и той же
позиции, определенной в описании БД. Например:
31 22 41
ИВАНОВ Л. А.
МОРГУНОВСКИИ А. Е.
МУС В. Ф.
ЗАВ. КАФЕДРОЙ
ЗАВ. ЛАБОРАТОРИЕЙ
ДОЦЕНТ
1922
1947
1941
Для хранения представленных так значений достаточно:
31+41+22=94 символа.
Рассмотрим, как те же три записи представлены в памяти при
размещении с разделителем:
/ИВАНОВ Л.А./ЗАВ. КАФЕДРОЙ /1922/
/МОРГУНОВСКИЙ А.Е./ЗАВ. ЛАБОРАТОРИЕЙ/1947
/МУС В.Ф./ДОЦЕНТ/1941/
В примере в качестве разделителя использован символ «/». На
практике разделитель часто несет дополнительную смысловую нагрузку,
например определяет длину размещенного за ним значения.
Существуют СУБД, в которых используется несколько способов
размещения значений элементов. При этом для части элементов записи
может быть выбран первый способ размещения (эти поля система поместит
в начале записи), для других - второй.
6.1.4.КЛЮЧ БАЗЫ
Ключ базы (КБД) — это внутренний
идентификатор каждой записи.
Ключ базы данных не следует отождествлять с ключом записи.
Значения ключа записи, равно как и неключевых элементов данных,
задаются и используются пользователем. Так, ключом записи СОТРУДНИК
может быть его табельный номер.
Значение КБД формируется системой при размещении записи в
памяти ЭВМ. В некоторых системах пользователь не знает КБД
извлеченных записей. В других КБД извлеченных записей доступны
пользователю, и он может их применить для повторного извлечения ранее
обработанной записи.
Есть системы, в которых значения КБД жестко закрепляются за
записями вплоть до их удаления из БД. В других СУБД значения КБД могут
изменяться при реорганизациях БД, инициируемых администратором, в
процессе обновления БД.
6.1.5.ОБЛАСТЬ ХРАНЕНИЯ
Область хранения—это участок памяти
(совокупность страниц), внутри которого могут размещаться
записи описываемого типа.
Никакая запись этого типа не будет размещена вне области хранения.
В некоторых системах для каждого типа записи используется своя область
хранения ,в других - допускается пересечение областей хранения. В
последнем варианте на одной странице данных могут оказаться записи
разных типов.
6.2. ОБНОВЛЕНИЕ БАЗЫ ДАННЫХ
Под обновлением БД понимаются процедуры
внесения в память новых записей, удаление ненужных,
корректировка значений элементов данных и структурных
ассоциаций.
Режим обновления зависит от способа организации файлов и
особенностей СУБД. В общем случае можно говорить о двух режимах
обновления БД: не допускающем повторное использование внешней памяти
и позволяющем многократно применять один и тот же участок памяти.
Кроме того, существенно, с какой скоростью выполняются обновления и как
они сказываются на последующем использовании БД.
6.2.1.УДАЛЕНИЕ ЗАПИСЕЙ ИЗ БАЗЫ ДАННЫХ
Существует две разновидности удаления записей: логическое и
физическое.
При логическом удалении запись сохраняется в БД но в служебной
части помечается как удаленная. Прикладная программа, как правило, не
будет иметь доступа к логически удаленным записям. Фактическое
удаление записи из памяти ЭВМ будет выполнено либо при реорганизации
БД, либо специально сервисной программой, инициируемой
администратором БД.
Недостаток логического удаления состоит в накоплении «мусора»—
неиспользуемых данных, что приводит к дополнительным затратам внешней
памяти.
При физическом удалении ранее занятый участок освобождается и
становится доступным для повторного использования. Система
автоматически управляет свободным пространством памяти на страницах.
Это обеспечивается, как правило, одним из двух способов: ведением цепей
свободных участков или динамической реорганизацией страниц.
На странице или на группе страниц данных поддерживается цепь
свободных участков. Ссылка на первый свободный участок содержится в
заголовке страницы (Рис.Y 6 .3). При удалении записи занимаемый ею
участок памяти включается в цепь свободных участков. Смежные
свободные участки объединяются в один суммарной длины.
Рис.Y6.3.Цепи свободных участков
до удаления записи БД (а) и после (б).
Заголовок страницы Заголовок страницы
Запись A Запись B Запись A Запись B
ЗаписьC Запись D ЗаписьC Свободный
участок – 2
Запись E Запись F Запись E Запись F
Свободный участок – 1 Свободный участок - 1
а б
При динамической реорганизации страниц записи БД плотно
размещаются в начале каждой страницы, а в конце страницы расположен
свободный участок. Адрес начала свободного участка хранится в заголовке
страницы.
При удалении некоторой записи оставшиеся сжимаются и
увеличивается длина свободного участка. Тем самым на каждой странице
содержится не несколько свободных участков, а только один суммарной
длины, и всякое обновление страницы приводит к ее динамической
реорганизации (Рис.Y 6 .4).
Для учета свободных участков на страницах в большинстве СУБД
поддерживаются инвентарные страницы. Одна инвентарная страница
создается для группы страниц данных и содержит сведения о наличии на
них свободных участков памяти. Инвентарные страницы позволяют
существенно сократить время поиска свободного участка памяти при
запоминании новых записей.
Рис.Y6.4. Динамическая реорганизация страницы
до удаления записи БД (а) и после (б)
6.2.2.ЗАПОМИНАНИЕ НОВЫХ ЗАПИСЕЙ
При запоминании новой записи система ищет ей место в области
хранения. Поиск места первоначально ведется через инвентарные страницы,
а затем на страницах данных.
Заголовок страницы Заголовок страницы
Запись A Запись B Запись A Запись B
Запись C Запись D ЗаписьC Запись E
Запись E Запись F Запись F
Свободный участок Свободный участок
а б
Если для учета свободных участков используются цепи участков, то
система, просматривая цепь, выбирает первый свободный участок,
пригодный по длине. Когда длина выбранного участка превышает длину
записи, то остаток оформляется в виде нового свободного участка. В
результате на странице может образоваться несколько небольших
свободных участков, не позволяющих запомнить новую запись, хотя
суммарная длина может быть для этого достаточна.
При динамической реорганизации страниц подобное случиться не
может, поскольку на каждой странице поддерживается один свободный
участок. Новая запись запоминается всегда в начале участка вслед за
последней записью на странице.
После запоминания записи система корректирует содержимое
соответствующей инвентарной страницы.
Если при запоминании новой записи система не находит свободного
участка в области хранения, то пользователь уведомляется о том, равно как
и о причине ненормального завершения запрошенной операции.
6.2.3.КОРРЕКТИРОВКА ЗНАЧЕНИЙ ЭЛЕМЕНТОВ ДАННЫХ
Если значения элементов данных имеют фиксированную длину, то
обновленные значения помещаются на место прежних.
Когда система допускает переменную длину значений (размещение с
разделителями), то обновленная запись может иметь длину, отличную от
прежней. В этом случае процедуры корректировки приводят либо к
реорганизации страницы, либо к перемещению записи на другой участок
памяти, что, в свою очередь, приведет к обновлению нескольких страниц.
В заключении отметим, что запрос пользователя на обновление
одной записи БД может привести к корректировке нескольких страниц, к
невидимым для пользователя довольно сложным процедурам,
автоматически выполняемым СУБД.
6.3. СПОСОБЫ ДОСТУПА К ЗАПИСЯМ
Последовательная обработка области БД. Последовательная
обработка предполагает выборку записей из области БД независимо от
структурных ассоциаций, в которых участвуют записи. Система
последовательно перебирает страницы области, пропускает свободные
участки и выдает пользователю записи БД в физической
последовательности их хранения.
Доступ по ключу базы данных. Ключ базы данных определяет
расположение записи в памяти ЭВМ. Зная КБД, система может наиболее
быстро извлечь требуемую запись. Иногда КБД выдается пользователям и
его можно явно применять при обработке записей.
Доступ по первичному ключу. Первичный ключ идентифицирует
записи внутри типа, его значения не меняются в течение времени
существования записи.
Если система обеспечивает доступ по первичному ключу, то он
(ключ) используется также при запоминании записи. Более того, значение
первичного ключа влияет на размещение записи в памяти ЭВМ.
Наиболее распространенные механизмы доступа по первичному
ключу—хеширование и индексирование.
6.3.1.ХЕШИРОВАНИЕ
При запоминании новой записи специальная программа, называемая
программой хеширования, ставит в соответствие значению первичного
ключа номер страницы, куда следует поместить запись. Так, все записи
распределяются по страницам области хранения (английское «hash»
означает размешивание).
Записи, для которых алгоритм хеширования выдает одинаковый
результат, называются синонимами. Синонимы объединяются в цепной
список, начало которого находится в заголовке страницы (Рис.Y 6 .5.). Если
при запоминании очередного синонима для него не хватило места на
странице, то он размещается на другой странице из области хранения, но
включается в цепь синонимов той области, куда был хеширован. Когда
области хранения записей разных типов пересекаются, то на одной странице
в цепи синонимов могут участвовать записи нескольких типов.
При извлечении записи по первичному ключу СУБД подключает
программу хеширования, вычисляет номер страницы, а затем просматривает
цепь синонимов на этой странице до нахождения искомой записи.
Как правило, СУБД содержит стандартную программу хеширования.
Но если алгоритм хеширования не устраивает администратора БД,
стандартная программа хеширования может быть заменена на
оригинальную—самостоятельно разработанную.
Рис.Y6.5.Пример двух цепей синонимов.
6.3.2.ИНДЕКСИРОВАНИЕ
Смысл индексирования состоит в том, что СУБД, размещая записи
на страницах данных, формирует специальные индексные таблицы. Они
используются для нахождения адреса записи по значению первичного
ключа.
Заголовок
Запись B
Запись N
Запись
K
Страница m
Заголовок
Запись A
Запись F
Запись M
Страница n
Для пояснения рассмотрим один из известных механизмов
индексирования. Положим, записи имеют ключи со значением из
натурального ряда. Перед загрузкой записи должны быть упорядочены по
возрастающим значениям ключей.
В файл они будут загружаться, плотно заполняя страницы данных.
После заполнения страницы система формирует одну строку в таблице,
называемой младшим индексом. Эта строка устанавливает соответствие
между номером страницы и максимальным ключом на этой странице (Рис.Y
6 .6).
Рис.Y6.6.Пример, поясняющий заполнение индексных таблиц.
Таблица младшего индекса создается на определенную совокупность
страниц данных, поэтому по мере заполнения файла будет создано много
таблиц младшего индекса и каждая из них имеет уникальный номер. После
заполнения всех страниц, обслуживаемых одним младшим индексом,
система формирует строку в таблице, называемой старшим индексом. Здесь
строка устанавливает соответствие между номером таблицы младшего
индекса и максимальным ключом в этом младшем индексе. Для файлов
Страницы
данных
Младший индекс Старший
индекс
1 1 5 16 24 30 48 1 1 48
2 51 56 62 70 78 2 78
1 100
3 84 86 88 90 95 100 3 100 2 512
4 117 128 130 137 149 2 4 149
3 900
5 172 184 191 200 210 213 5 213
6 464 472 485 490 499 512 6 512
4 1087
5 3154
7 544 576 583 600 610 616 3 7 616
8 637 678 690 712 714 8 714
9 750 753 814 837 857 900 9 900