Теория и практика построения баз данных (1088289), страница 162
Текст из файла (страница 162)
Таким образом, использование связного списка экономит 99 900 операций чтения Подход с использованием связных списков для представления вторичных ключей не всегда эффективен. В частности, если записи в наборе обрабатываются не по порядку, связные списки оказываются неэффективными. Например, если часто требуется найти 10-ю, 120-ю плп и-ю запись в множестве с максимальным кредитом $500, обработка булет идти медленно. При прямом доступе связные списки неэффективны.
Кроме того, если приложение требует, чтобы вторичные ключи создавались и разрушались динамически, использование связных списков нежелательно. Всякий раз, когда создается новый ключ, к каждой записи необходимо добавить поле ссылки, для чего зачастую необходимо реорганизовать всю базу данных, а это требует больших затрат времени и средств. Наконец, если вторичные ключи имеют уникальные значения, длина каждого списка будет равна 1, и для каждой записи в базе данных будет иметься отдельный связный список. Поскольку работа в такой ситуации невозможна, связные списки нельзя использовать для представления уникальных ключей. Предположим, например, что файл КЛИЕНТ содержит еще одно поле с уникальным значением — например, НоиерСоциальнойСтраховки.
Если мы попытаемся представить этот уникальный вторичный ключ с помощью связного списка, каждый помер социальной страховки будет отдельным связным списком. Более того, каждый связный список будет иметь всего один элемент — запись, содержашую данный номер социальной страховки. Представление вторичных ключей с помощью индексов Второй способ предст.авления вторичных ключей — это использование индексов. Для каждого вторичного ключа создается свой индекс.
Конкретная реализация этого подхода зависит от того, являются ли значения ключей уникальныхш. Случай уникальных вторичных ключей Предположим, что файл ЗАПИСЬ (см. рис. А.ЗЗ) помимо показанных на рисунке полей содержит поле НомерСоциальнойСтраховки, являющееся вторичным ключом. Чтобы обеспечить доступ к записям в файле по полю НоиерСоциальнойСтраховки, нужно просто построить индекс по этому полю.
Данные для примера показаны на рис. А.З5, а, а соответствуюшнй индекс — на рис. А.35, б. В этом индексе записи адресуются по их относительным номерам. Можно было бы для этой цели использовать поле НоиерСчета; в этом случае СУБД находила бы в индексе нужный номер социальной страховки, получала бы соответствующий номер счета, а затем определяла бы по нему относительный адрес записи. Номер Номер- Максимальный- социальной Счета Кредит страховки Относительный номер записи 1 2 3 Номер Относительный социальной номер страховки записи Рис.
А.зб. Представление уникального вторичного ключа с помощью индексов: а — пример файла КЛИЕНТ (с номером социальной страховки); б — индекс для вторичного ключа НомерСоциальнойСтраховки Случай неуникальных вторичных ключей Индексы могут также использоваться для представления иеуникальных вторичных ключей, но поскольку каждое множество связанных записей может содержать неизвестное число элементов, записи в индексе имеют переменную длину. Например, на рнс. А.36 показан индекс множеств с различным максимальным кредитом для файла КЛИЕНТ. Каждое пз множеств с максимальным кредитом $500 и $700 состоит пз трех элементов, поэтому соответствующие записи в индексе содержат по три номера счета. Множество с максимальным кредитом $1000 состоит из пяти элементов, поэтому запись индекса для этого множества содержит пять номеров счетов.
В реальности представление и обработка неуникальных ключей представляют собой сложные задачи Коммерческие СУБД применяют для этих целей несколько Резюме 753 НомерСчета Максимельный- Кредит Таблица вхождений НомерСчета Таблица значений Резюме МаксимальныйКредит 752 Приложение А. Структуры данных различных схем. В одном популярном методе используются таблица значений (уа1цез таЫе) и таблица вхождений (оссцггепсе гаЫе), Каждая запись в таблице значений состоит из двух полей, первое из которых содержит значение ключа.
Ключ ИаксимальныйКредит файла КЛИЕНТ имеет три значения: 500, 700 и 1000. Второе поле записи в таблице значений представляет собой указатель на запись в таблице вхождений. Таблица вхождений содержит алреса записей, и те пз них, которые имеют одно и то же значение вторичного ключа, расположены в одной строке таблицы.
На рис. А.37 изображены таблица значений и таблица вхождений для ключа МаксимальныйКредит. Рис. А.36. Индекс для ключа МаксимальныйКредит из рис. А.ЗЗ Рио. А.ЗТ. Таблица значений и таблица вхождений для ключа МаксимальныйКредит из рис. А.ЗЗ Для нахождения записей с заданным значением вторичного ключа производится поиск атого значения в таблице значений.
Когда нужное значение найдено, по указателю в таблице вхождений находятся адреса записей, имеющих данное значение ключа. Когда в файл добавляется новая запись, СУБД должна обновить индексы для каждого поля вторичного ключа. В случае неуникальных ключей она должна сначала убедиться, что значение ключа новой записи присутствует в таблице значе~шй; если это так, СУБД добавляет адрес новой записи в соответствующую строку таблицы вхождений. Если такого значения нет, СУБД должна добавить новую запись в таблицу значений и таблицу вхождений.
При удалении записи ее адрес должен быть удален пз таблицы вхождений. Если в строке таблицы вхождений не остается ни одного адреса, соответствующее значение вторичного ключа должно быть также удалено из таблицы значений. Когда изменяется значение поля вторичного ключа записи, адрес этой записи должен быть удален из одной строки таблицы вхождений и добавлен в другую. Если изменение заключается в присваивании ключу нового значения, в таблицу значений необходимо добавить соответствующую запись, Подход с использованием индексов для представления вторичных ключей преодолевает ограничения, которыми характеризуется подход с использованием связных списков.
Прежде всего, возможна непосредственная обработка множеств. Например, можно сразу получить третью запись из множества, не обрабатывая первую и вторую. Кроме того, можно динамически создавать и уничтожать вторичные ключи. Никаких изменений в самих записях не делается: вместо этого СУБД создает дополнительные таблицы — таблицу значений и таблицу вхождений. Наконец, возможна эффективная обработка уникальных ключей.
Недостатки этого подхода заключаются в том, что он требует большего объема файлового пространства (на таблицы расходуется больше избыточного пространства, чем на указатели), и в том, что программирование СУБД оказывается более сложным. Обратите внимание; прикладное программирование не обязательно будет в атом случае проще нли сложнее; просто программное обеспечение для СУБД, обрабатывающее индексы, написать сложнее, чем программное обеспечение, обрабатывающее связные списки.
Наконец, обработка обновлений обычно происходит медленно из-за операций чтения и записи, требуемых для доступа к значениям в таблице вхождений и их поддержания. В этом приложении мы рассмотрели структуры данных, используемые в базах данных. Плоский файл — это файл, не содержагций повторяющихся групп. Плоские файлы могут быть упорядочены с использованием последовательных списков (путем физического упорядочивания записей в необходимой последовательности), связных списков (путем добавления к каждой записи указателя на другую логически связанную с ней запись) и индексов (путем построения отдельной от данных таблицы, содержащей указатели на связанные записи). Бинарные деревья представляют собой специальное приложение индексов. Последовательные списки, связные списки и индексы (или инвертированные списки) являются фундаментальными структурами данных. (Хотя последовательные списки редко используются прп обработке баз данных.) С помощью этих структур можно представлять связи между записями, а также вторичные ключи, Три основные структуры связей между записями — деревья, простые сети и сложные сети — могут быть представлены с помощью связных списков и индексов.
Простую сеть можно разбить на деревья и затем представить с помощью соответствующих структур данных; сложную сеть можно преобразовать в простую сеть, содержащую записи пересечения, и затем представить теми же способами, что и простую сеть. Вторичные ключи используются для доступа к данным по значениям некоторых полей, отличных от поля первичного клю рь Вторичные ключи могут быть уникальными и неуникальными. Неуникальные вторичные кл|очи могут быть представлены с помощью связных списков или индексов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
