Лекция №5

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

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

последовательный поиск.

Индексированные файлы

Решение – внешний индекс.

1. Из исходного файла в новый файл копируются

значения одного атрибута для всех записей вместе

с положениями этих записей. То есть каждая

запись в новом файле состоит из значения атрибута

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

2. Затем нужно упорядочить записи нового файла в соответствии со значениями атрибута.

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

основном файле используется дополнительный

индексный файл, который называется внешним индексом, а сам исходный файл, таким образом, стал

индексированным.

Пример: предметный указатель

Внешний индекс

Индексированный файл

База данных - организованный набор взаимосвязанных файлов

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

реализуемого системой управления базой данных (СУБД).

Три основных типа структур базы данных:

иерархическая (древовидная)

сетевая

реляционная (табличная)

Иерархическая структура: отношения «один ко многим»

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

Такая система хорошо иллюстрируется иерархической системой классификации растений и животных,

называемой таксономией.

Например, животные делятся на позвоночные и

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

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

Главной характеристикой иерархической структуры, иллюстрируемой таксономическим деревом, является

прямая взаимосвязь между одной ветвью и другой.

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

новых ветвей и формулированием новых правил

ветвления

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