Понятие ключа и индекса. Прямая и инвертированная формы индекса. Примеры.
Ключевая запись или ключ - значение (элемент данных), используемое для идентификации или определения адреса записи (логическое определение).
Ключ сцепленный (составной) – несколько элементов данных, которые в совокупности обеспечивают уникальность идентификации каждой записи набора данных.
Первичный ключ - идентифицирует запись единственным образом
Вторичный ключ – идентифицирует некоторую группу записей объединенных одним свойством
Индекс – физическая реализация ключа, обеспечивающая доступ к записям, соответствующим отдельным значениям ключа.
Логически индекс есть бинарное отношение I(v,a), где v – значение атрибута, а a – список адресов элементов хранения (записей, кортежей, документов), соответствующих данному значению атрибута. Для повышения эффективности поиска отдельных значений и слияния/пересечения списков значения v и адреса элементов в списке a хранятся в упорядоченном виде, что обеспечивает применение процедур быстрого поиска.
Индекс I(v,a) часто называют инвертированным индексом. Каждый элемент а инвертированного индекса называется инвертированным списком.
Прямая реализация индекса представляет собой расширение бинарного отношения до совокупности записей, состоящих из 2-ух полей – значения атрибута и адреса размещения одного элемента хранения. Отдельное значение атрибута повторяется в индексе столько раз, сколько оно встречается в файле данных, а длина индекса (в записях) совпадает с длиной файла данных.
В инвертированной форме:
В случае, когда списки а достаточно длинные, инвертированный индекс хранится в двух разных файлах, связанных указателями. Такая организация требует меньше памяти для хранения значений ключей и поиск в ней более эффективен.
Способы реализации указателя пересылок:
- Указанием ссылки на первый и последний адреса размещения элементов для отдельного ключевого значения;
- Заданием ссылки на адрес размещения первого элемента и длиной списка адресов.
Характерные свойства и отличия линейных и нелинейных структур данных. Примеры.
К линейным структурам относятся массивы и последовательности, таблицы. Порядок следования (и, соответственно, выборки) элементов таких структур имеет линейный характер и соответствует порядку расположения элементов в памяти: один за другим без каких-либо промежутков. Адрес элемента соответствует его положению и определяется индексом – порядковым номером элемента в последовательности размещения. К элементу имеется прямой доступ, если известен его индекс. Особенностью линейной структуры является то, что при последовательной организации (размещении) она допускает возможность прямого доступа к произвольному элементу, поскольку условие однородности (однотипности) предполагает, что все элементы занимают расположенные строго последовательно области одинакового размера, что и позволяет достаточно просто вычислять значение физического адреса элемента по значению его индекса.
Линейные — структуры данных, в которых переход от одного элемента данных к другому не зависит от каких-либо логических условий, т.е. в линейных структурах используются лишь безусловные связи элементов.
Массив – совокупность однотипных элементов, размер известен заранее
Последовательность – так же, как и массив, представляет собой совокупность однотипных элементов. Однако число элементов до размещения неизвестно.
Таблица – это последовательности, обычно представляемые строками – совокупностями разнотипных элементов. Или, иначе, таблица – это множество записей, каждая из которых представляет набор поименованных полей.
Нелинейные — структуры данных, в которых переход от одного элемента данных к другому может зависеть от выполнения некоторого логического условия, т.е. в нелинейных структурах могут использоваться условные связи элементов. В качестве примеров нелинейных структур рассмотрим списки, деревья и сети.
Списки – совокупность однотипных элементов. Каждый элемент имеет ссылку на следующий элемент.
Сети – каждый элемент связан с каждым.