В начало

Лекция

Физическая организация данных.

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

 

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

 

1. Организация данных на машинных носителях

С общепринятой точки зрения к вопросам организации данных относятся (слайд 2):

-         выбор типа записи – единицы обмена в операциях ввода-вывода;

-         выбор способа размещения записей в файле и, возможно метода оптимизации размещения;

-         выбор способа адресации и метода доступа к записям.

Целесообразность выделения именно таких аспектов организации была предельно очевидна на начальной стадии развития таких запись-ориентированных систем и устройств внешней памяти, как магнитные ленты и диски. Но, следует отметить, что широкое использование современных поток-ориентированных систем ввода-вывода не уменьшило принципиальное, да и практическое, значение давно известных методов и решений, построенных на запись-ориентированных принципах. Основные понятия и подходы к физической организации и обработке данных иллюстрируются на слайде

 

19.1.1. Типы записей (слайд 3)

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

Физическая запись, с которой работает файловая система - это совокупность данных, которые размещаются в файле обычно на внешнем носителе, и могут быть считаны или записаны как единое целое одной командой ввода-вывода. Здесь файл[1] – это последовательность физических записей, размещаемых в линейном пространстве носителя но, в общем случае, не обязательно в линейном порядке.

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

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

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

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

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

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

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

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

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

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

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

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

 

19.1.2. Организация файлов - способ размещения записей

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

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

Выбор последовательности связывается с одним из следующих обстоятельств:

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

2.   Ускорением или упрощением средств адресации файла (например, средств прямой адресации или хэшивания).

3.   Уменьшением размера используемого индекса и сокращением таким образом времени поиска в нем.

4.   Сокращением среднего времени доступа за счет размещения в наиболее доступных местах записей, к которым происходит наиболее частое обращение.

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

 

Можно выделить две «чистые» стратегии определения места (адреса) для размещения записей: последовательное (sequential) и произвольное (random) размещение. В этом смысле алгоритм размещения определяет тип организации файла.

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

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

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

 

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

 

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

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

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

 

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

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

 

 

19.1.3. Способы адресации и методы доступа к записям

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

В некоторых файлах записи имеют несколько ключей. Запись ЗАКУПКА может иметь различные НОМЕР ПОСТАВЩИКА и НОМЕР ПОКУПАТЕЛЯ, каждый из которых является ключом.

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

Основную проблему при адресации файла можно сформулировать следующим образом: как по первичному ключу определить местоположение записи с данным ключом? и как надо организовать набор записей, чтобы поиск потребовал как можно меньше затрат?

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

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

 

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

 

Блочный поиск. Если записи упорядочены по ключу, то при сканировании файла не требуется чтение каждой записи. ЭВМ могла бы, например, просматривать каждую сотую запись в последовательности возрастания ключей. При нахождении записи с ключом большим, чем искомое значение, просматриваются последние 99 записей, которые были пропущены.

Этот способ называется блочным поиском. Записи группируются в блоки и каждый блок проверяется по одному разу до тех пор, пока не будет найден нужный блок. Иногда данный способ называют поиском с пропусками.

 

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

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

Т.е., двоичный поиск более пригоден для поиска в индексе файла, чем в самом файле.

 

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

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

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

 

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

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

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

 

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

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

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

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

 

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

Более экономичным является указание на область, в которой размещается группа записей. Эта область называется участком записей (slot, bucket).

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

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

2. Число преобразуется в адрес участка и, если на участке есть свободное место, то логическая запись размещается на нем.

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

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

Из-за вероятностной природы алгоритма в этом способе не удается достичь 100% плотности заполнения памяти, однако для большинства файлов может быть достигнута плотность 80 или 90%; при этом память для индексов не требуется. Большинство записей можно найти за одно обращение, но для некоторых потребуется второе обращение (при переполнении). Для очень небольшой части записей потребуется третье или четвертое обращение к файлу.

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

 

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

 

19.2. Схемы организации данных на внешних носителях

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

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

Для иллюстрации взаимосвязи схем адресации и организации наборов данных рассмотрим процедуру ведения массива индексно-последовательной организации

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

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

На слайде (слайд 7) приведена схема индексно-последовательного файла, в который добавлены 3 новые записи.

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

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

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

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

 

19.3. Методы включения записей, основанные на резервировании

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

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

 

Резюмируя, перечислим способы включения в файл новых записей:

1). При включении новых записей файл перезаписывается с размещением записей в соответствующих местах.

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

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

 

19.4. Физическое представление иерархических структур

Рассмотрим физическое представление древовидных структур на примере обновления дерева с использованием следующих методов (слайд 8):

1. Физически последовательное размещение.

2. Указатели.

3. Цепи и кольца.

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

 

Физически последовательное размещение. На слайде (слайд 8) представлен пример реализации иерархической структуры путем физически последовательного размещения данных на носителе.

Последовательность элементов иногда называется левосписковой структурой (последовательность типа «сверху вниз - слева направо»).

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

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

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

 

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

На слайде (слайд 9) представлен пример реализации иерархической структуры до и после обновления путем использования области переполнения.

В этом случае для определения местонахождения записей А, В или С можно использовать индексы.

 

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

-         указатели на порожденные записи;

-         указатели на подобные записи;

-         указатели на исходные записи.

 

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

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

 

 

На рис. ссылки образуют кольца двух типов: подобных записей и кольца «исходный–порожденный». В записях самого нижнего уровня показаны указатели на исходные записи. Для единообразия здесь каждая запись имеет два указателя. Однако кольца большей частью создаются двусторонними. В этом случае число указателей в каждой записи увеличится до четырех.

 

19.5. Физическое представление сетевых структур

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

 

Физически последовательное размещение. Если древовидные структуры можно представить без избыточности с помощью физически последовательного размещения, то для сетевых структур это обычно невозможно. Однако в некоторых случаях может оказаться удобным представить один набор связей типа  «исходный-порожденный»  путем физически последовательного размещения, а для остальных связей использовать другой метод. Например, можно использовать физически последовательное размещение для представления связей А и С (слайд 13).

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

Обычно для представления сетевых структур физически последовательное размещение не применяется.

 

Использование указателей. Если для реализации сетевых структур используются указатели, то они должны представлять все связи, причем какие-то записи должны называться исходными (например, верхние), а какие-то – порожденными (нижние записи).

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

Однако если какая-нибудь связь между записями относится к типу «многие ко многим», то названные три метода физического представления сетевых структур оказываются непригодными. Более того, если в простых сетевых структурах на предыдущих рисунках для хранения указателей на исходные записи требовался один или два указателя в каждой записи, то здесь необходимы списки указателей переменной длины.

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

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

 

19.6. Физическое представление с разделением данных и связей

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

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

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

Рассмотрим пример разделения линейных записей исходной таблицы «Штатное расписание факультета» (слайды 16, 17) на связи и собственно данные.

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

Такое представление обладает следующими важными свойствами:

-                   каждый элемент таблицы – это один элемент данных;

-                   таблица не содержит одинаковых строк, т.е. содержащих попарно равных значений элементов данных;

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

 

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

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

Однородность реляционных баз данных, построенных на основе бинарных отношений, обеспечивает:

-         унифицированность средств работы с базой: необходимы только средства для работы с бинарными таблицами;

-         простоту расширения состава логической записи.

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

 

19.7. Архитектура  файловой организации баз данных (слайд 18)

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

Прямое использование файловой системы для организации хранения и доступа к данным оказывается менее эффективным (отличие составляет, по крайней мере, 10%), поскольку при выполнении каждого обращения к диску со стороны СУБД в работу включается дополнительный слой системного ПО. Хранение данных в файловой системе приводит также к определенной потере емкости памяти. Файловая система, например Unix, потребляет примерно 10% от форматированной емкости дисков для метаданных о файлах и файловой системе. Более того, файловая система резервирует некоторое пространство, чтобы обеспечить быстрый поиск свободного пространства в случае расширения файлов.

Это послужило причиной того, что СУБД берут на себя непосредственное управление внешней памятью, минимально используя файловую систему ОС.

 

19.7.1. Файл-ориентированная организация данных

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

Таким образом, БД физически состоит из нескольких файлов: основного, индексного, файла метаданных, файлов указателей и т.д. Такого типа организация файловой структуры БД представлена в приложении примерами организации данных dBase-подобных и документальных баз данных.

 

19.7.2. Страничная организация данных

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

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

При распределении дискового пространства рассматриваются следующая схема структуризации пространства в зависимости от типов данных:

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

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

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

Все страницы данных имеют одинаковую структуру, включающую:

-       Заголовок страницы, содержащий номер страницы, номера предыдущей и следующей страниц, сведения о свободном пространстве на странице;

-       Содержание – строки данных (последовательность кодов), каждая из которых имеет уникальный идентификатор в рамках всей базы данных, который состоит из номера страницы и номера строки на странице;

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

Для организации быстрого доступа создаются страницы индексов, которые организованы обычно в виде В-деревьев.

 

19.7.3. Модели распределения данных по физическим носителям

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

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

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

Примером, иллюстрирующим подход с точки зрения практических компромиссов выбора решения, являются RAID-массивы. На слайдах (слайд 19, 20) приведены два варианта: RAID-0, обеспечивающий максимальную производительность при «стандартной» надежности, и RAID-1, обеспечивающий «двойную» надежность при «стандартной» производительности. На следующих слайдах (слайд 21, 22) представлены вариант RAID-10, совмещающий возможности RAID-1 и RAID-0, и вариант RAID-5.

Рис. 4.18. Распределение данных в RAID-массивах

Время чтения

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

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

Главное отличие между сцеплением и расщеплением заключается в размещении смежных данных.

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

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