2.4.2. Сетевая база данных

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

Рис. 2.11 – Структурная схема иерархической БД

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

2.4.3. Реляционная база данных

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

Например, в иерархической БД наибольшее время займет ответ на запрос о размере стипендии конкретного студента, поскольку поле «сумма», содержащее размер стипендии, находится в таблице самого последнего уровня.

Рис. 2.12 – Пример логической записи в БД

К тому же лишь только после затраты большого труда на создание такой БД может выясниться, что «неудобные» для базы запросы, требующие большого времени на ответ, поступают чаще всего. От подобной неприятности избавлена реляционная БД, потому что все поля в логических записях такой базы равноправны: нет главного поля и подчиненных ему полей. Например, если преобразовать иерархическую БД в реляционную, то получится файл, содержащий 935 + 455 = 1390 логических записей (по одной записи на каждого студента). Каждая из этих записей может содержать, например, следующие поля: факультет, специализация, группа, фамилия, сумма. Так, студенту ИВАНОВУ из группы ФСТ-3-2 соответствует следующая логическая запись (рис. 2.12).

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

Согласно двоичной схеме выбирается запись, находящаяся посредине файла. По фамилии студента в этой записи легко судить, в какой из двух половин файла находится искомая запись. Затем процесс повторяется до тех пор, пока не будет найдена нужная запись. Пусть, например, в самой середине файла оказалась запись с фамилией ОСОКИН. Сравнивая первые буквы этой фамилии и искомой фамилией ИВАНОВ, легко понять, что искомая запись находится в первой половине файла. Пусть далее записью, которая делит первую половину файла пополам, оказалась запись (рис. 2.13). Тогда искомая запись находится во второй четверти файла. Продолжая далее точно так же деление второй половины файла пополам, получим 1/8 и 1/16 части файла и т. д. В конце концов будет найдена нужная запись и дан ответ на запрос о размере стипендии студента ИВАНОВ.

Рис. 2.13 – Запись делящая файл БД пополам

Двоичный поиск ведется быстрее, чем поиск просмотром. Пусть файл, в котором ведется поиск, включает N логических записей. Если эти записи не упорядочены, то окажется, что среднее арифметическое количество записей, которое нужно просмотреть, чтобы ответить на большое количество запросов, приближается к N/2 с ростом числа запросов. Если записи упорядочены, то при двоичном поиске количество просмотренных при ответе на любой запрос записей не будет превышать числа log₂ N, округленного до ближайшего целого.

Поскольку log₂ N во всяком случае намного меньше N/2 при большом N, то максимальное время, необходимое для ответа на запрос при двоичном поиске, значительно меньше среднего времени ответа при поиске в неупорядоченном файле.

Однако упорядоченный файл имеет и недостатки, во-первых, при большом количестве логических записей пополнение такого файла новыми записями связано с перемещением старых записей, чтобы не нарушать упорядоченность файла в целом, во-вторых, всякая запись упорядоченного файла может быть найдена только по значению того поля, по которому упорядочены все записи файла. Например, если бы все 1390 записей в примере были упорядочены в файле не по фамилиям, а скажем по номерам студенческих групп, то найти размер стипендии студента ИВАНОВА (с помощью двоичного поиска, не зная номера группы этого студента) было невозможно. Конечно, можно создать несколько дубликатов одного и того же файла, упорядоченных по значению разных полей, но для этого потребуется много дополнительного места в памяти ЭВМ. Еще более гибкая (двоичная схема), процедура связана с хешированием (перемешивание — англ.).

Согласно этой процедуре, каждой логической записи в файле по некоторому правилу ставится в соответствие число, которое аналогично адресу этой записи в памяти компьютера. Например, если пронумеровать все буквы русского алфавита, то отдельные буквы фамилии студента ИВАНОВ будут иметь соответственно двухрядные номера: 10, 03, 01, 15, 16, 03. Составленное из этих номеров число 100301151603 порождает адрес логической записи в памяти ЭВМ.

Сложность такого подхода заключается в том, что адреса логических записей будут получаться очень большими (например, адрес записи с фамилией ИВАНОВ получится больше 100 млрд.!), так что для размещения этих записей потребуется невероятно большой объем памяти компьютера, а при этом память может оставаться очень слабо заполненной, поскольку большинство комбинаций букв не образуют фамилий.

Выход из этого затруднения можно найти, если предложить другое правило вычисления адреса логической записи, например, если сложить номера (10 + 3 + 1 + 15+16 + 3 = 48) букв фамилии ИВАНОВ, то полученную сумму 48 тоже можно рассматривать, как адрес записи и разместить эту запись в 48-й ячейке памяти.

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

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

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

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