Распределенная обработка данных. Найханова Л.В. - 67 стр.

кортежа отношения хранится кортеж той же степени, состоящий из ссылок на места
расположения соответствующих значений столбцов. В последней лекции мы будем
рассматривать особенности организации распределенных реляционных СУБД. Одним из
приемов является так называемое вертикальное разделение отношений, когда в разных
узлах сети хранятся разные проекции данного отношения. Хранение отношения по
столбцам в некотором смысле является предельным случаем вертикального разделения
отношений.
Индексы
     Как бы не были организованы индексы в конкретной СУБД, их основное назначение
состоит в обеспечении эффективного прямого доступа к кортежу отношения по ключу.
Обычно индекс определяется для одного отношения, и ключом является значение
атрибута (возможно, составного). Если ключом индекса является возможный ключ
отношения, то индекс должен обладать свойством уникальности, т.е. не содержать
дубликатов ключа. На практике ситуация выглядит обычно противоположно: при
объявлении первичного ключа отношения автоматически заводится уникальный индекс, а
единственным способом объявления возможного ключа, отличного от первичного,
является явное создание уникального индекса. Это связано с тем, что для проверки
сохранения свойства уникальности возможного ключа так или иначе требуется индексная
поддержка.
     Поскольку при выполнении многих операций языкового уровня требуется
сортировка отношений в соответствии со значениями некоторых атрибутов, полезным
свойством индекса является обеспечение последовательного просмотра кортежей
отношения в диапазоне значений ключа в порядке возрастания или убывания значений
ключа.
     Наконец, одним из способов оптимизации выполнения эквисоединения отношений
(наиболее распространенная из числа дорогостоящих операций) является организация так
называемых мультииндексов для нескольких отношений, обладающих общими
атрибутами. Любой из этих атрибутов (или их набор) может выступать в качестве ключа
мультииндекса. Значению ключа сопоставляется набор кортежей всех связанных
мультииндексом отношений, значения выделенных атрибутов которых совпадают со
значением ключа.
     Общей идеей любой организации индекса, поддерживающего прямой доступ по
ключу и последовательный просмотр в порядке возрастания или убывания значений
ключа является хранение упорядоченного списка значений ключа с привязкой к каждому
значению ключа списка идентификаторов кортежей. Одна организация индекса
отличается от другой главным образом в способе поиска ключа с заданным значением.

     B-деревья

     Видимо, наиболее популярным подходом к организации индексов в базах данных
является использование техники B-деревьев. С точки зрения внешнего логического
представления B-дерево - это сбалансированное сильно ветвистое дерево во внешней
памяти. Сбалансированность означает, что длина пути от корня дерева к любому его
листу одна и та же. Ветвистость дерева - это свойство каждого узла дерева ссылаться но
большое число узлов-потомков. С точки зрения физической организации B-дерево
представляется как мультисписочная структура страниц внешней памяти, т.е. каждому
узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые
страницы обычно имеют разную структуру.
     В типовом случае структура внутренней страницы выглядит следующим образом:
                 N1 ключ(1) N2 ключ(2) … Nn ключ(n) Nn+1 ключ(n+1)


                                                                                    67