Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Гайдамакин Н. А. Автоматизированные информационные системы, базы и банки данных. Вводный курс - файл Гайдамакин_Автоматизированные информационные системы базы и банки данных Вводный курс_2002 .doc


Гайдамакин Н. А. Автоматизированные информационные системы, базы и банки данных. Вводный курс
скачать (3043.3 kb.)

Доступные файлы (1):

Гайдамакин_Автоматизированные информационные системы базы и банки данных Вводный курс_2002 .doc4199kb.30.12.2002 12:56скачать

содержание

Гайдамакин_Автоматизированные информационные системы базы и банки данных Вводный курс_2002 .doc

1   2   3   4   5   6   7   8   9   10   ...   23
^

2.3. Внутренняя схема баз данных фактографических АИС


Изначально и по сей день программное обеспечение АИС (СУБД) в качестве места физического размещения данных ори­ентировано на внешнюю (дисковую) память. Как уже отмеча­лось, размещение данных во внешней памяти, точнее эффек­тивность доступа к ним во внешней памяти, существенно вли­яет на эффективность обработки данных. В результате важным аспектом АИС является внутренняя схема базы данных, кото­рую организует и поддерживает СУБД.

В общем плане внутренняя схема базы данных включает три основных компонента, представленные на рис. 2.10.



Рис. 2.10. Cocтав внутренней схемы базы данных

Центральным компонентом внутренней схемы являются ин­формационные массивы, включающие собственно данные (ин­формационных объектов логической схемы БД, т.е. в реляци­онных СУБД таблиц), и массивы индексов, являющихся специ­альными дополнительными конструкциями для ускорения доступа к данным основных информационных объектов. Ин­формационные массивы в большинстве СУБД состоят из од­ной или нескольких так называемых страниц, каждая из которых содержит совокупность некоторых единичных элементов, называемых физическими записями. В результате, единичным элементом внутренней схемы баз данных АИС является физи­ческая запись, в большинстве случаев совпадающая по смыслу с логической записью, т. е. в реляционных СУБД с табличной строкой.

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

Важным компонентом внутренней структуры является ка­талог БД, в котором размещается системная информация по логической структуре БД, включающая описание основных ин­формационных объектов (имена, структура, параметры, связи) и ограничения целостности данных. Организация системной информации БД определяется особенностями конкретной СУБД, а сам каталог может входить непосредственно в файлы данных (область описателей данных) или составлять отдель­ный информационный массив.

Как уже отмечалось, в состав автоматизированного банка данных АИС помимо самой базы данных входит и прикладной компонент, образуемый совокупностью интерфейсных элемен­тов представления, ввода и обработки данных, типовых запро­сов и процедур обработки данных, а также «событий» и «пра­вил», отражающих правила и специфику предметной области АИС (так называемые «правила бизнеса»). Соответственно во внутренней схеме БД выделяется специальная область, в кото­рой размещается информация по прикладному компоненту АИС.

Все три части внутренней структуры и их составные эле­менты (например, информационные массивы отдельных инфор­мационных объектов БД) могут размещаться в одном едином файле базы данных или в разных файлах. Во втором случае внутренняя схема БД определяется совокупностью и порядком расположения данных файлов.
^

2.3.1. Физические структуры данных


Страничная организация информационных массивов БД оп­ределяется общей спецификой доступа к данным больших объе­мов. Доступ к физическим записям во внешней памяти в боль­шинстве СУБД осуществляется через считывание в оператив­ную память страниц файла данных, содержащих соответствующие записи. Непосредственная обработка записей производится в оперативной памяти, для чего СУБД образует и поддерживает, как уже отмечалось, специальные буферы, в ко­торых временно размещаются страницы, содержащие обраба­тываемые записи. После завершения обработки страница с со­ответствующими записями «выталкивается» из буфера и фик­сируется в дисковом файле.

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

^ Физические структуры организации файлов данных под­разделяются на линейные и нелинейные.

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

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



^ Рис. 2.11. Общий принцип организации внутренней схемы базы данных

Удаление записей в линейных структурах может произво­диться двумя способами. В первом способе при удалении запи­си сразу же осуществляется автоматическое перезаписывание на новых позициях всех строк-записей, лежащих за удаляемой, с целью уплотнения и ликвидации появляющихся пустых мест. Подобный подход обеспечивает максимальную эффективность использования дискового пространства, но вызывает существен­ные накладные расходы при любых операциях по удалению записей. Поэтому другим, достаточно распространенным спо­собом является простое «вычеркивание» удаляемой записи без перезаписывания всех записей, лежащих за удаляемой, с соот­ветствующим появлением пустых мест в страницах файла дан­ных. Ведение базы данных в этом случае может быть организо­вано так, чтобы при превышении общего объема пустых мест в странице выше определенного значения (скажем, больше 30%) специальный компонент СУБД автоматически производил дефрагментацию страниц, устраняя пустые места по ранее удален­ным записям. В некоторых СУБД запуск данной процедуры предоставляется непосредственно самому пользователю (адми­нистратору) для периодического уплотнения (сжатия) файла базы данных.

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

^ Первая разновидность основана на подходе, позаимство­ванном из структуры текстовых файлов. Текстовый файл со­стоит из последовательно расположенных строк символов (на­бора байтов, определяющих номера символов строки в соот­ветствии с кодовой таблицей). Строки имеют различную длину и отделяются друг от друга символом возврата каретки. Строка в данном случае является физической записью, а доступ к ней осуществляется по ее номеру k путем последовательного счи­тывания (продвижения) k-1 предшествующих строк-записей (см. рис. 2.12).



Рис. 2.12. Линейная структура текстового файла

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

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

Такой подход применяется в широко используемых для со­здания «настольных информационных систем» (системы «ра­бочего стола») СУБД куста dBASE (dBase, FoxPro, Clipper), ко­торые создают и оперируют базами данных в формате так на­зываемых dbf-файлов. Структура dbf-файла состоит из трех частей* — заголовка, блока описания структуры базы и инфор­мационной части (см. рис. 2.13). В заголовке последовательно представлены поля, которые определяют тип файла базы дан­ных (с memo-полями или без них), дату последнего изменения, номер последней записи, смещение, с которого начинается ин­формационная часть (записи), размер каждой записи. Блок опи­сания структуры размещается после заголовка до информаци­онной части и состоит из последовательности элементов, каж­дый из которых описывает определенное поле логической структуры (схемы) базы данных. Структура описания поля со­держит последовательное описание имени поля, типа поля (чис­ловое, текстовое, дата и т. д.), длины поля и заканчивается спе­циальным символом для отделения описания одного поля от другого. Информационная часть состоит из последовательнос­ти групп байтов одинаковой длины без специальных раздели­телей, каждая из которых собственно и выражает содержимое конкретной физической записи.

* Спенс Р. Сliрреr. Руководство по программированию. Версия 5.01 / Пер. с англ — Мн.: Tивали, 1994-480 с (с.428).



Рис. 2.13. Линейная структура dbf-файла

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

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



Рис. 2.14. Нелинейная структура данных ни примере односвяз­ного списка (поля указателей выделены жирными рамками)

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

* Реализуется в виде прямой или косвенной адресации. При прямой адресации в указателях размещаются физические адреса начала связанных записей. При косвенной адресации в указателях находятся номера связанных записей, физические адреса кото­рых отыскиваются по специальному справочнику, в который ставятся на учет физичес­кие адреса всех новых записей.
Образование страниц физических записей файлов данных осуществляется на основе той или иной стратегии минимиза­ции расходов на доступ к записям и расходов на операции их добавления, удаления и корректировки, и существенным обра­зом зависит от типа конкретной нелинейной структуры. Одной из таких стратегий является минимизация расходов на доступ к записям, связанным на логическом уровне отношением «Один-ко-многим», что обусловлено широкой распространенностью таких отношений в огромном количестве предметных облас­тей АИС. Данная стратегия основывается на использовании иерархических древовидных структур.

Общая схема этой стратегии такова. Для записей информа­ционного объекта на стороне «Один» образуется страница файла данных, в которую последовательно (как в линейных структу­рах) помещаются соответствующие записи. При появлении в базе данных связанных записей для каждой записи из страни­цы объекта на стороне «Один» образуются «подчиненные стра­ницы» для размещения соответствующих связанных записей объекта на стороне «Многие». В свою очередь, подчиненные записи сами могут иметь свои подчиненные записи, для кото­рых создаются соответствующие страницы, и т. д. (см. рис. 2.15, а.



Рис. 2.15. а. Пример нелинейной древовидной иерархической структуры данных

Если в процессе ведения базы данных какая-либо страни­ца переполняется, то для нее образуется связанная страница-продолжение на основе техники односвязного списка.*

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

Однако во многих предметных областях АИС отношения между информационными объектами могут порождать ситуа­ции наличия у определенных записей на стороне «Многие» сра­зу нескольких разных предков на стороне «Один» (см., например, рис. 2.3), что не вписывается в рамки подобных древовид­ных иерархических структур. Решение таких проблем обычно осуществляется через введение избыточности (дублирования) данных по связанным записям или другими способами.

Для формализованного описания нелинейных структур при­меняют аппарат теории графов, в рамках которого подобные иерархические древовидные структуры называются деревья­ми.* На рис. 2.15, б приведено условное изображение корневого дерева, соответствующего иерархической нелинейной струк­туре данных на рис. 2.15, а, а также термины и понятия, связан­ные с ним. Вершины (узлы) дерева по отношению друг к другу могут быть предками или потомками. Предок может иметь не­сколько потомков, но каждый потомок имеет только одного предка. Вершины, имеющие общего предка, называются бра­тьями. Вершины, имеющие потомков, называются внутренни­ми. Внутренняя вершина, не имеющая предков, называется корнем дерева. Вершины, не имеющие потомков называются лис­тьями. Все внутренние вершины корневого дерева упорядочиваются по уровням иерархии. Уровень узла определяется количеством предков до корня дерева. Количество уровней называется высотой дерева.

* Деревом называется связный неориентированный граф без циклов (см., напри­мер^ Лекции по теории графо / Емелнчев В. А., Мельников О. И., Сарванов В.И., Тышкевич Р.И.—М.: Наука, 1990, или Асанов М.О. Дискретная оптимизация: Учеб­ное пособие. —Екатеринбург: УралНАУКА, 1998.


Рис. 2.15, 6. Условное изображение средствами теории графов нелинейной древовидной иерархической структуры

Еще одним важным параметром деревьев является макси­мально возможное количество потомков у одного предка. Дан­ный параметр называется степенью дерева. Деревья степени больше двух называются сильноветвистыми. И наконец, важ­ным в практическом плане для нелинейных структур данных является понятие сбалансированности дерева. Различают сба­лансированность по степени вершин, когда каждая внутрен­няя вершина может иметь количество потомков, ограниченное определенной и одинаковой для всех вершин величиной {ар­ность дерева) и сбалансированность по высоте, когда путь (ко­личество вершин) от корня до любого листа дерева одинаков или различается не более чем на единицу.

Развитый математический аппарат теории графов позволил разработать для древовидных структур данных оптимальные по определенным критериям операции обхода (поиска нужной записи), включения (добавления новой записи) и исключения (удаления записи) с целью минимизации расходов как по дос­тупу, так и по изменению данных. Хорошая алгоритмизируемость этих операций предопределила широкое использование нелинейных древовидных структур в схемах физической орга­низации данных, обеспечиваемых СУБД.
^

2.3.2. Индексирование данных


Как уже отмечалось, стандартным приемом повышения эф­фективности доступа к записям в базах данных является созда­ние индексных массивов по отдельным, обычно ключевым по­лям. Идея индексов основана на том факте, что если для повы­шения эффективности доступа к конкретному кортежу-записи использовать линейное упорядочение кортежей в таблице (ска­жем, по алфавиту для текстовых ключевых полей или по возра­станию для числовых ключевых полей), то накладные расходы по «перетряске» всей таблицы после добавления/удаления строк-кортежей превысят выигрыш во времени доступа. Струк­тура индексов (индексных массивов) строится так, чтобы на основе некоторого критерия можно было бы быстро находить по значению индексируемого поля указатель на нужную запись (строку) таблицы и получать к ней доступ. При этом совокуп­ность записей-кортежей базовой таблицы не обязательно упо­рядочивать, а при их изменении необходимо изменить только лишь индексный массив.

Как и для информационных массивов самих данных (таб­лиц), так и для индексных массивов применяются линейные и нелинейные структуры. В качестве линейных структур ин­дексов в большинстве случаев выступают инвертированные списки. Инвертированный список строится по схеме таблицы с двумя колонками — «Значение индексируемого поля» и «Но­мера строк»* (см. рис. 2.16). Инвертированные списки чаще все­го применяются для индексации полей, значения которых в раз­ных строках-записях могут повторяться, к примеру, поле «Год рождения» таблицы «Сотрудники» (в реляционных базах дан­ных такие поля не могут быть ключевыми).

* На практике не номера строк базовой таблицы, а номера страниц файла БД, где находится соответствующая строка.


Значение индексируемого поля ("Год рождения")

Номера, строк

1958

3

1959

5, 17, 123, 256

1960

31, 32, 77

1961

11, 45, 58, 167, 231

1962

7, 8, 9, 10, 234, 235, 236

^ Рис. 2.16. Пример инвертированного списка

Строки инвертированного списка упорядочиваются по зна­чению индексируемого поля. Для доступа к нужной строке исходной таблицы сначала в упорядоченном инвертированном списке отыскивается строка с требуемым значением поля,* за­тем считывается номер соответствующей строки (строк) в ис­ходной таблице и далее по нему уже осуществляется непосред­ственный доступ к искомой строке базовой таблицы.

* Способы поиска в линейно упорядоченных структурах см., например, в работе: Вирт Н.. Алгоритмы и структуры данных: Пер. с англ.—М.: Мир, 1989.
При добавлении новой строки в базовую таблицу ее значение по индексируемому полю ищется в ранее составленном индексе. Если соответствующая строка инвертированного спис­ка отыскивается (т.е. подобное значение индексируемого поля среди строк таблицы уже встречалось и было поставлено на учет), то в ячейку второго столбца соответствующей строки индекса дописывается номер страницы, куда была помещена соответствующая строка базовой таблицы. Если такого значе­ния в индексе нет, то создается новая строка индекса и осуще­ствляется переупорядочение нового состояния индексного мас­сива.

При удалении строки из базовой таблицы также осуществ­ляется поиск соответствующей строки в индексном массиве и осуществляется вычеркивание в индексе соответствующего номера отсылаемой строки базовой таблицы. Если при этом других строк в базовой таблице с таким же значением индекси­руемого поля не осталось (соответствующая ячейка индекса стала пустой), то удаляется и вся данная строка индекса с пос­ледующим переупорядочением всего индексного массива. При этом за счет того, что индекс в виде инвертированного списка содержит лишь один столбец значений, затраты на «перетряс­ку» при добавлении или удалении записей существенно мень­ше по сравнению с тем, если бы переупорядочение происходи­ло непосредственно в самой базовой таблице.*

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

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

Каждая внутренняя вершина, если она полностью запол­нена, содержит информацию о n–1 различных последователь­но возрастающих значениях индексируемого поля по следую­щей схеме, приведенной на рис. 2.17.



где: Хi i значение индексируемого поля, при этом ХiJXi+1 – указатель на вершину, содержащую значения индексируе­мого поля, меньшие или равные Xi.

Рис. 2.17. Структура внутренней вершины Б-дерева

Число n называется порядком Б-дерева.

Листовая вершина, в отличие от внутренней, содержит ин­формацию о нахождении страницы в файле базы данных с за­писями-кортежами, имеющими соответствующие значения ин­дексируемого поля. Схема листовой страницы представлена на рис.2.18.



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

Рис. 2.18. Структура листовой вершины Б-дерева

Сбалансированность Б-дерева означает одинаковое количество потомков до листовой вершины по любым раз­ветвлениям от корневой вершины. В качестве примера на рис. 2.19 приведено Б-дерево 3-го порядка уровня 2, пост­роенное для поля «Год рождения» таблицы «Сотрудники».



Рис. 2.19. Пример Б-дерева 3-го порядки уровня 2

Как правило, порядок Б-дерева выбирается таким, что­бы информация одной полностью заполненной вершины соответствовала странице файла данных. В силу того что объем одной страницы файлов данных существенно боль­ше размера полей, то в большинстве случаев в одну пол­ностью заполненную страницу вместе с указателями по­мещается большое количество значений индексируемого поля, исчисляемое сотнями и даже тысячами значений (n >> 100...1000). Это обстоятельство обусловливает сравни­тельно небольшой уровень Б-деревьев на практике (поряд­ка 2...4) даже в тех случаях, когда количество строк в ба­зовой таблице исчисляется десятками тысяч. В результате доступ к нужной записи по определенному значению ин­дексируемого поля через Б-дерево осуществляется за небольшое количество страничных обменов между внутрен­ней и внешней памятью по следующему алгоритму:

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

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

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

Анализ данного алгоритма показывает, что при поиске нуж­ного значения индексируемого поля по индексу в виде Б-дерева требуется такое количество страничных обменов между внеш­ней и внутренней памятью, которое равно уровню Б-дерева плюс единица. При достаточно большом значении n, а это, как уже отмечалось, наиболее распространенная ситуация, уровень m Б-дерева невелик (m >> 2..3), и, следовательно, количество страничных индексных обменов с памятью также невелико. При этом сбалансированность Б-дерева обусловливает одинаковые затраты по доступу к любой записи с любым значением индек­сируемого поля. Сбалансированность Б-деревьев обеспечива­ется легко алгоритмизируемым правилом их построения (рос­та) при включении нового значения индексируемого поля.

Включение нового значения индексируемого поля осуще­ствляется следующим образом.

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

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

• Если листовая страница уже заполнена, то она делится «пополам», и тем самым порождается новая листовая страни­ца. Среднее значение исходной листовой страницы записыва­ется в вершину-предок на соответствующее место.* При этом после вставленного значения образуется указатель-ссылка на новую листовую страницу, образованную остатком от ополо­виненной исходной листовой страницы.

* Так, чтобы в странице обеспечивался последовательный порядок расположе­ния -значений индексируемого поля по схеме, приведенной на рис. 2.17.
• Если при занесении среднего значения переполненной листовой страницы в страницу-предок происходит переполне­ние самой страницы-предка, то она аналогично делится попо­лам, «посылая» свое среднее значение своему предку. Если при этом происходит переполнение корневой страницы, то она так­же делится на две новые внутренние страницы, а ее среднее значение образует новую корневую страницу, повышая уровень дерева на единицу и т. д. (говорят, что Б-дерево «растет» вверх).

Удаление определенного значения индексируемого поля производится следующим образом:

• Производится поиск требуемого значения индексируе­мого поля и в результате в оперативную память считывается нужная листовая страница.

• Из нее удаляется соответствующее значение индексиру­емого поля и указатель-адрес соответствующей страницы фай­ла данных.

• Если после удаления размер занятого пространства па­мяти текущей листовой страницы в сумме с размером занятого пространства левого (правого) брата больше, чем размер памя­ти одной страницы, то процесс заканчивается.

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

Описанный алгоритм удаления значений индексируемого поля соответствует одной из наиболее широко применяемых разновидностей Б-деревьев—Б*-деревьев, которые позволя­ют использовать в среднем до 2/3 пространства всех страниц (вершин) дерева.

Структура Б-деревьев является эффективным способом ин­дексации больших массивов данных и широко применяется в современных СУБД.
^

2.3.3. Расстановка (хеширование) записей


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

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

* От англ. to hash – нарезать, крошить, делить месиво, т.е. равномерно перема­лывать ключи нолей в адреса (номера) записей.

** Отсюда еще одно название данного подхода—«преобразование ключей», впер­вые введенное в русской литературе еще в 1956 г. будущим академиком А. П. Ершо­вым.


Рис. 2.20. Принцип расстановки записей по значению ключей

При доступе (поиске) нужной записи над значением ее клю­чевого поля также осуществляется хеш-свертка, что сразу же даст возможность определить местоположение искомой запи­си и получить к ней доступ.

Таким образом, в идеале хеширование обеспечивает дос­туп к нужным записям за одно (!!!) обращение к области раз­мещения данных.

Функция преобразования h(Клj) выбирается на основе двух требований: 1) ее результат для возможного диапазона значе­ний ключевого поля должен находиться в пределах диапазона адресов (номеров) области памяти, выделяемой подданные, и 2) значения функции в пределах выделенного диапазона адре­сов должны быть равномерными. На практике наиболее широ­кое распространение нашли хеш-функции, основанные на опе­рациях деления по модулю:

h(Клj)=(Клj mod М) + 1,

где (Клj mod М) означает операцию деления по модулю М,* а число М выбирается исходя из необходимости попадания зна­чений хеш-функции в требуемый диапазон.

* Значением операции деления по модулю М является остаток от обычного деле­ния числа на М, например результат деления 213 по модулю 20 равен 13.
Если в качестве М выбрать число, являющееся степенью двух, то подобная хеш-функция эффективно вычисляется про­цедурами выделения нескольких двоичных цифр.

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

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

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

^ Второй подход к разрешению коллизий основывается на использовании дополнительного преобразования ключей по схеме:



где n – исходное конфликтующее значение адреса записи; g(Клi) – дополнительное преобразование ключа; n – допол­нительное значение адреса.

При этом могут встречаться ситуации, когда и такое допол­нительное преобразование приводит к коллизии, т.е. новое зна­чение n также оказывается уже занятым. В таких случаях дополнительное преобразование g(Клi) чаще всего организуют на основе рекуррентной процедуры по следующей схеме:



где f(k) – некоторая функция над номером итерации (пробы).

В зависимости от вида функции f(k) такие подходы назы­вают линейными или квадратичными пробами.

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

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



Рис. 2.21. Принцип хеширования записей но страницам файла данных

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

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

Внутренняя схема базы данных обычно скрыта от пользо­вателей информационной системы, за исключением возможно­сти установления и использования индексации полей. Вместе с тем, особенности физической структуры файлов данных и ин­дексных массивов, принципы организации и использования дис­кового пространства и внутренней памяти, реализуемые конк­ретной СУБД, должны учитываться проектировщиками банков данных, так как эти «прозрачные» для пользователей-абонен­тов особенности СУБД критично влияют на эффективность об­работки данных в информационной системе.
^

Вопросы и упражнения


1. Перечислите основные функции, реализуемые СУБД, и охаракте­ризуйте их с точки зрения системного или прикладного характе­ра решаемых задач.

2. Объясните соотношение понятии «операции», «транзакции» и «работа (действия) пользователя» в базе данных.

3. Перечислите (функциональные компоненты СУБД и охарактери­зуйте системный или прикладной характер решаемых ими задач.

4. Дайте определение «модели организации данных» и перечислите ее составляющие. Охарактеризуйте особенности сетевой модели данных по отношению к иерархической модели.

5. Перечислите основные понятия структурной составляющей ре­ляционной модели данных. Каким образом строятся связи между таблицами-отношениями, какие типы связей и почему обеспечиваются при этом?

6. В чем заключается н каким образом обеспечивается целостность в реляционной модели данных?

7. Какое основное различие между операциями обновления данных и операциями обработки таблиц-отношений в реляционной мо­дели?

8. Дайте определение операции ОБЪЕДИНЕНИЯ таблиц-отноше­ний. Каково наименьшее и наибольшее количество строк может быть в результате объединения таблиц?

9. Дайте определение операции ПЕРЕСЕЧЕНИЯ таблиц-отношений. Каково наименьшее и наибольшее количество строк может быть в результате пересечения таблиц?

10. Дайте определение операции ВЫЧИТАНИЯ таблиц-отношений. Каково наименьшее н наибольшее количество строк может быть в результате вычитания таблиц?

11. Какие нарушения целостности данных могут происходить в ре­зультате операции ПРОЕКЦИЯ (ВЕРТИКАЛЬНОЕ ПОДМНОЖЕ­СТВО)?

12. Дайте определениe операции СОЕДИНЕНИЯ таблиц-отношений. Каково наименьшее n наибольшее количество строк может быть в результате соединения таблиц?

13. Что является единичным элементом в физической структуре дан­ных? В какие структуры более высокого порядка объединяются единичные элементы данных?

14. Дайте сравнительную характеристику преимуществ и недостат­ков разновидностей линейных структур физической организации данных.

15. Охарактеризуйте общий принцип нелинейных структур физической организации данных и перечислите их основные разновидности.

16. Выделите и поясните главную идею использования древовидных иерархических структур физической организации данных. В тер­минологии теории графов дайте определения основных понятий «деревьев».

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


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

18. Обоснуйте выбор типа индексов для полей таблицы «Расписание занятий» со следующей схемой: №№, Дата, Время (1-я пара, 2-я пара, 3-пара, 4-я пара), Аудитория (30 аудиторий), Вид (Лекция, Семинар, Пр. занятие. Лабораторная работа. Зачет, Экзамен), Дис­циплина (100 уч. дисциплин). Преподаватель (80 преподавателей), Учебная группа (15 уч.групп).

19. Произведите преобразование индекса в виде Б-дерева, представ­ленного на рис. 2.18,при:

а) добавлении 13-й записи «Данилов, 1976г. р.»;

б) добавлении 14-й записи «Никаноров, 1967 г. р.»;

в) удалении 9-й записи «Матвеев, 1979 г. р.».

20. Проиллюстрируйте (по шагам добавления записей) процесс по­строения индекса в виде Б-дерева 3-го порядка по полю «Таб_№» таблицы:



21. В чем преимущества и недостатки с точки зрения эффективности операций доступа к данным и преобразования данных между ин­дексированием и хешированием?3. Основы создания автоматизированных информационных систем
1   2   3   4   5   6   7   8   9   10   ...   23



Скачать файл (3043.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации