Puc. 21.2. Нормализованный аналог таблицы SP, представленной на рис. 21.1

Сначала разберемся в разбиении таблиц на разделы, что иначе называется фрагментацией. Фрагментация представляет собой возможный подход к решению проблемы больших баз данных . Каждая таблица делится на группу непересекающихся разделов или фрагментов, предназначенных для независимого физического хранения (см. обсуждение вопроса о фрагментации в главе 20). Такое разделение может существенно расширить возможности управления и доступа к данной таблице. Обычно за каждым разделом закрепляются определенные выделенные (в той или иной степени) ресурсы, например диск или процессор, вследствие чего конкуренция между разделами за такие ресурсы минимизируется. Таблицы разделяются горизонтально * с помощью функции разделения, которая использует значения выбранных столбцов, составляющих ключ раздела, в качестве аргументов, а возвращает номер раздела или его адрес. Такие функции обычно поддерживают разделение по диапазонам (range), кэшированное (hash) разделение, круговое (round-robin) разделение и прочие виды разделения (см. аннотацию к [17.58] в главе 17).

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

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

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

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

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

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

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

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

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

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

Первый вид включает обслуживание точных копий или реплик базы данных.

Замечание. Управление копированием, которое может рассматриваться как менее амбициозная форма репликации, также широко поддерживается (см. ниже).

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

Рассмотрим каждый из этих видов по порядку.

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

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

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

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

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