Предисловие (стр. 34 )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Контрольные вопросы

Какой уровень архитектурной модели ANSI/X3/SPARC представляет среду хранения базы данных?

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

Какими видами ресурсов управляют механизмы среды хранения базы данных в СУБД?

Перечислите функции механизмов среды хранения базы данных.

Какая схема определяет организацию хранимых данных в СУБД с управляемым внутренним уровнем?

Существуют ли различия между внутренней схемой и схемой хранения?

С помощью какого языка специфицируется схема хранения базы данных в СУБД с управляемым внутренним уровнем?

Кратко охарактеризуйте используемые в СУБД подходы к структурированию хранимых данных.

Какие задачи решаются средствами управления пространством памяти среды хранения и размещением хранимых данных?

Чем прямая адресация хранимых записей отличается от косвенной?

Какие принципы размещения хранимых данных используются в СУБД с управляемым внутренним уровнем?

Для каких целей в СУБД используются методы хеширования и каковы их основные принципы?

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

Назовите достоинства и недостатки методов хеширования.

Для каких целей разработаны методы динамического хеширования?

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

Какие индексы называют первичными?

Чем вторичные индексы отличаются от первичных?

Что такое инвертированный список?

Какие виды индексов чаще всего используются в настоящее время в СУБД?

Каковы достоинства битовых индексов, для каких целей их можно эффективно использовать?

8.10. Администратор системы базы данных 

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

Четкая структуризация функций персонала администрирования данными была предложена Рабочей группой по базам данных ANSI/X3/SPARC – автора рассмотренной выше архитектурной модели системы базы данных (см. разд. 5.7) в ее широко известном отчете, опубликованном в 1975 г. В этой работе предполагается, что персонал администрирования системой базы данных выполняет несколько функций. Каждая из них возлагается на одно или несколько лиц, в зависимости от масштабов системы, количества ее пользователей, поддерживаемого набора приложений и других факторов. В небольших системах каждая из этих функций или даже все они могут выполняться одним лицом. Более того, в простейших случаях, особенно часто встречающихся при работе с базами данных на персональных компьютерах, одно лицо может совмещать в себе функции и пользователя, и персонала администрирования данными.