Работа с базами данных 2 (стр. 10 из 18)
9) СУБД передает данные из системного буфера в рабочую область прикладной программы А.
10) СУБД передает прикладной программе информацию о результатах выполнения различных процедур по обслуживанию ее запросов. Эта информация содержит также сведения о возможных ошибках.
11) Прикладная программа обрабатывает данные, помещенные в рабочую область.
2.3 Организация данных
2.3.1 Физическая организация данных
Проблема физической организации данных: каким образом можно представить структуры данных в памяти компьютера в виде последовательной цепи?
1) Как можно найти необходимую запись среди множества данных? Группа битов, которую можно прочитать с помощью одной машинной инструкции, называется одной физической записью. Программы идентифицируют логическую запись с помощью ключа.
Ключ® машинный адрес
Переход от ключа к адресу определяет сущность способа адресации, которые будут рассмотрены ниже.
2) Каким образом организовать данные, чтобы поиск был эффективным, а выборку записей можно было бы осуществлять по нескольким ключам?
3) Каким образом древовидные сетевые структуры можно представить в виде последовательности битов?
4) Как добавить новую запись к данным, уничтожить старые записи, не нарушая структуры адресации и поиска, а также структуру данных?
КлючБД — RID (Record IDentificator)
Каждой записи СУБД присваивается внутренний идентификатор. Ключ БД не следует приравнивать ключу записи. Если значение ключа записей задается пользователем, то RID устанавливается системой при размещении.
Пример:
1) RID состоит из номера страницы и номера записи на странице;
2) Последовательный номер записи в файле.
В некоторых системах пользователь не знает RID, в других — он доступен пользователю, который может его использовать.
При описании типа записи (имя таблицы) администратором БД определяется область хранения. ОХ — участок памяти, т.е. совокупность страниц, внутри которого могут размещаться записи описываемого типа. Вне области хранения записи размещаться не могут.
В некоторых системах для любой записи используется своя область хранения, в других они могут пересекаться, и тогда на одной странице могут оказаться записи разных типов.
Характеристики файла данных: Параметры блокирования страниц
Формат и длина страницы
Запись может быть сегментирована, если она не умещается на одной странице.
Файл БД:
Как по первичному ключу определить месторасположение записи с данным ключом?
1) Последовательное сканирование файла — сканируется файл с проверкой ключа каждой записи. Эффективен только для файлов с последовательным доступом. Записи должны быть упорядочены по ключу.
2) Блочный поиск — записи упорядочиваются по ключу. И при сканировании файла можно рассматривать не каждую запись, а каждую сотую в последовательности возрастающих ключей. Затем область поиска сужается.
3) Двоичный поиск — рассматривается запись в середине области, в которой выполняется поиск и ее запись сравнивается с поисковым ключом. Делится пополам.
4) Индекс на последовательный файл — последовательное сканирование файла для нахождения записи требует много времени, если оно выполняется над всем файлом. Но сканирование можно использовать для небольшой области, которая представляет весь файл. Пусть файл упорядочен по ключу. Для адресации к такому упорядоченному файлу используется таблица, называемая индексом.
5) Индекс на произвольные файлы — записи располагаются в произвольной последовательности, как правило, в порядке ввода в БД. Непоследовательный файл можно индексировать точно также, как и последовательный. Но для этого требуется значительно больший по размеру индекс, т.к. он должен содержать по одному элементу для каждой записи файла, а не для блока записей. Кроме того, в нем должны содержаться полные абсолютные адреса.
6) Адресация с помощью ключа, эквивалентного адресу. Известны много методов преобразования ключа непосредственно в адрес в файле. Когда такое преобразование возможно, оно обеспечивает самую быструю адресацию. Например, в некоторых банковских системах номера счетов изменялись так, чтобы номер счета или его часть являлись бы адресом записи в БД.
7) Алгоритм преобразования ключа в адрес дает почти ту же скорость, что и предыдущий. Но характеризуется неэффективным использованием памяти. Поскольку ключи преобразуются в непрерывное множество адресов, в файле остаются свободные участки.
8) Хеширование. При запоминании новой записи специальная программа ставит в соответствие значению первичного ключа номер страницы, куда следует поместить запись. Таким образом, перемешиваются по страницам все записи. Записи, для которых хеширование выдает одинаковые страницы, называются синонимами. Синонимы объединяются в связанный список, начало которого находится в заголовке таблицы. Если при заполнении очередного синонима для него не хватило места на одной странице, он размещается на другой странице, но включается в цепь синонимов той области, куда был хеширован. При извлечении записи по первичному ключу СУБД подключает программу хеширования, вычисляет номер страницы, а затем просматривает цепь синонимов на этой странице до нахождения нужной записи.
2.3.2 Организация индексных таблиц
Индекс можно определять как таблицу, воспринимающую на входе информацию о некоторых значениях атрибутов и выдающую на выходе информацию, соответствующую быстрому поиску записей, которые имеют заданное значение атрибутов.
Индексная таблица должна быть упорядочена по входному индексу.
Следует различать индексирование по первичному ключу и вторичное индексирование.
СУБД, размещая записи на странице данных, формирует специальные индексные таблицы. Они используются для нахождения адреса записи по значению первичного ключа. При этом СУБД производит поиск записи не в файле, а в индексе. Если записи файла упорядочены по ключу, индекс обычно содержит не ссылки на каждую запись, а ссылки на блоки записи, внутри которых можно выполнять поиск или сканирование.
Рассмотрим один из известных механизмов индексирования. Пусть записи имеют ключи со значениями из натурального ряда. Перед загрузкой записи должны быть упорядочены по значению ключей.
Особенности первичного индексирования:
1) Ключ индексирования должен иметь уникальное неизменное значение;
2) Первоначальная загрузка должна выполняться обязательно с предварительной сортировкой;
3) Формирование индексной таблицы происходит одновременно с загрузкой записей файлов, а значение ключей индексирования влияют на размещение записей в памяти.
При обработке БД возникает потребность извлечения записи по значению данных, отличных от первичного ключа, например, извлечь данные из записи о студентах данной специальности или по специальности — номер группы. Последовательный просмотр большого числа записей может оказаться неэффективным. Другой вариант состоит в использовании вторичного индексирования.
Вторичные ключи могут идентифицировать записи неединственным образом. Одному вторичному ключу могут соответствовать несколько записей
КБД — ключ БД
Особенности вторичного индексирования:
1) Вторичные ключи могут иметь неуникальное значение. Допускается изменение значений вторичных ключей. При этом системой автоматически будут корректироваться соответствующие таблицы.
2) Вторичное индексирование служит только для выборки данных и никак не используется при размещении данных в памяти.
3) Таблицы вторичного индексирования можно создавать не только при первоначальной загрузке, но и в любое другое время.
Организация индексных таблиц должна обеспечивать быстрое нахождение адреса записи по значению ключа. Один из механизмов индексирования нам уже известен, это иерархия индексных таблиц с последовательным просмотром внутри таблицы. Этот механизм работает только если записи перед загрузкой накапливаются и упорядочиваются. Если же загрузка БД происходит в реальном времени, то этот механизм малоэффективен. Рассмотрим другие механизмы индексирования.
Индексная таблица при этом механизме индексирования состоит из множества записей, связанных адресными ссылками в иерархическую структуру. Такие записи называют индексными.
Каждая индексная запись (ИЗ) содержит
1) Значение ключа записи;
2) Адрес этой записи (ключ БД);
3) Адресная ссылка на ИЗ с ключом меньше данного;
4) Адресная ссылка на ИЗ с ключом больше данного.
При этом механизму не требуется, чтобы записи предварительно накапливались и упорядочивались. Каждой записи БД соответствует одна ИЗ. Первая ИЗ становится корневой.
Пример:
| # записи | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Ключ записи | 12 | 8 | 4 | 9 | 6 | 13 | 14 | 16 | 100 | 10 | 25 | 31 |
Поиск записи по значению ключа выполняется по тому же алгоритму, начиная с корня БД. Механизм основан на известном дихотомическом поиске. Наряду с достоинствами, бинарные деревья имеют значительные недостатки. В нашем примере для извлечения записи с ключом записи, равным 31, требуется 7 шагов, а для записи, с КЗ=6 — 4 шага, хотя обе записи конечны. Такое дерево называется несбалансированным.