Теория и практика построения баз данных (1088289), страница 160
Текст из файла (страница 160)
Плоские файлы 737 ОНЗ Ссылка Значение Ссылка 2 Значение 2 Ссылка 3 Индексный набор 101 102 103 104 105 108 10т 108 109 Последовательный набор (адресе записей с данными опущены) тт О Ю О а х й й тт о о й с й й й я И х и й Х о о 3 и о о. й о. о ю и й к й с Ф $ о й й о. и тт о о с й 1о о о о с й «1 й о. й 9 ю О ог й о к о. и! Адрес 1 гт2 Адрес 2 гтЗ Адрес 3 Ссылка Рис.
А.10. Пример бинврнога дерева со структурой, соответствующей рис. А.9 Аналогичным образом, на следующем уровне имеется трн значения н трп указателя на каждый элемент индекса. Всякий раз, когда мы спускаемся па уровень ниже, мы сужаем область своего поиска. Например, если от верхней записи мы проследуем по левой линии связи, а от следующего уровня — по правой линии, мы сможем обратиться ко всем записям, значения ключей которых больше 27, но меньше пли равны 45 На первом уровне мы исключили все записи, значения ключей которых больше 45. Бинарные деревья по определению являются сбалансированными. Это значит, что все записи находятся на одинаковом расстоянии от верхней записи индексного набора.
Это свойство бинарных деревьев обусловливает их эффективность, хотя алгоритмы вставки л удаления записей оказываются сложнее, чем для обычных деревьев (которые могут быть несбалансированными), поскольку для того, чтобы при этих операцтиях сохранить все записи на одинаковом расстоянии, может потребоваться модификация нескольких записей.
Резюме по структурам данных На рис. А.11 изображены все методы упорядочения плоских файлов. Для этой цели могут применяться три различных структуры данных. Одна из таких структур — последовательный список; его недостаток заключается в следующем: чтобы одновременно иметь записи, отсортированные в различном порядке, требуется дублировать данные. В связи с тем, что последовательные списки не используются прп работе с базами данных, далее мы пх рассматривать нс будем.
Нрн псполь- Упорядоченна логическая структура Возможная структура данных Метод доступа 733 Приложение А. Структуры данных зовании связных списков и бинарных деревьев дублирования данных не требует- ся. Бинарныс деревья являются особым приложением индексов. Обычно ---------------- Редко Рис. А.11. Структуры данных и принципы доступа, используемые для упорядочения плоских файлов Как показано на рис. А.11, последовательные списки могут храниться в файлах с любым принципом доступа. На практике, однако, обычно опп хранятся в файлах последовательного доступа.
Кроме того, хотя и связные списки, н индексы могут храниться и в файлах последовательного доступа с индексированием, и в файлах прямого доступа, СУБД всегда хранят пх в файлах прямого доступа. Представление бинарных связей В зтом разделе мы рассмотрим, каким образом каждьш из рассмотренных нами в данной главе шести видов связей между записями (деревья, простые сети и слож- ные сети) представляется с помощью связных списков н индексов. Обзор видов связей между записями Записи могут быть связаны между собой тремя способами. Дерево имеет одну или несколько связей «однн ко многим», но каждая дочерняя запись имеет мак- симум одного родителя. Данные сотрудника профессорско-преподавательского Представление бинарных связей 739 состава, показанные на рнс.
А.12, являют собой пример дерева. Дерево имеет не- сколько связей 1:Х, но каждая дочерняя запись, как можно видеть из рис. А.13, имеет только одного родителя. Рис. А.12. Пример записи о сотруднике профессорско-преподавательского состава Рис. А.13. Схема дерева, описывающего сотрудника ППС Просглая сеть — совокушюсть записей н связей вила 1:1ч между ними. Отличие простой сети от дерева состоит в том, что в простой сети дочерний узел может иметь более одного родителя, если родители принадлежат различным типам записей. Экземпляр показанной на рис. А.14 простой сети, состоящей из записей о студентах, пх руководителях и специальностях, схематически изображен на рис. А.1бт. Сложная сеть также является совокупностью записей и связей между ними, но связи в нен имеют вид «многие ко многим», а не «одни ко многим». Связь межлу студентами и занятиями, которые охи посещают, представляет собой сложную сеть.
Экземпляр такой связи можно видеть на рис. А.16, а общую схему — на рис. А.!7. СПЕЦИАЛЬНОСТИ РУКОВОДИТЕЛИ СТУДЕНТЫ Рис. А.14. Пример простой сети Рис. А.15. Общая структура простой сети СТУДЕНТЫ ПРЕДМЕТЫ Рис. А.18. Пример сложной сети Номер записи Содержимое записи Рис.
А.17. Общая структура сложнои сети 740 Приложение А. Структуры данных Ранее мы видели, что связные списки и индексы можно использовать лля обработки записей в порядке, отличном от того, в котором они физически хранятся. Эти же структуры данных можно использовать лля хранения и обработки связей между записями.
Представление деревьев Деревья могут представляться с помощью последовательных списков, связных списков и индексов. В варианте с последовательными списками приходится дуб- Представление бинарных связей 741 лировать большое количество данных, и кроме того, СУБД не используют после- довательные списки для представления деревьев.
Поэтому речь здесь будет идти только о связных списках и индексах Представление деревьев с помощью связных списков На рис. А.18 показана древообразная структура, в которой записи типа ПОСТАВЩИК являются родителями, а записи типа СЧЕТ вЂ” потомками. На рис. А.19 изображены два вкземпляра этой структуры, а на рис. А.20 показан послеловательный файл, в котором хранятся все записи ПОСТАВЩИК и СЧЕТ. Запись ПОСТАВЩИК АА имеет относительный номер 1, а запись ПОСТАВЩИК В — относнтельный номер 2. Как показано на рисунке, записи типа СЧЕТ расположены одна за другой. Обратите внимание, что эти записи никак не упорядочены, и упорядочение здесь не нужно.
Рис. А.18. Пример дерева, связывающего записи ПОСТАВЩИК и СЧЕТ Рис. А.19. Два экземпляра дерева ПОСТАВЩИК-СЧЕТ Рис. А.йо. Представление деревьев на рис. А.19 в файле трудность состоит в том, что из этого файла невозможно определить, какие счета пришли от каких поставщиков. Решить эту проблему можно с помощью связного списка. Для этого в каждую запись следует добавить поле ссылки. В этом поле будет храниться адрес некоторой лругой записи, связанной с ней. Например, в поле ссылки записи ПОСТАВЩИК АА мы поместим адрес записи, представляющей первый счет от данного поставщика. Это запись СЧЕТ 110, имеющая Вставленная запись Родительская Дочерняя запись запись Относительный номер записи 1 2 Содержимое записи Поле ссылки 742 Приложение А.
Структуры данных относительный номер 7. В поле ссылки этой записи мы поместим указатель на запись, представляющую следу1ощий счет от поставщика АА, то есть на запись СЧЕТ118 с относительным номером 3. Чтобы показать, что больше потомков в данной цепочке нет, в поле ссылки записи с относительным номером 3 мы запишем О. Пример реализации этого метода показан на рис. А.21.
Исследовав этот рисунок, вы увидите, чта аналогичный набор ссылок использован для представления связей между поставщиком ВВ н счетами от него. Относительный номер записи Содержимое записи Поле ссылки Рно. А.21. Представление деревьев с помощью связных списков В структуру на рис. А.21 намного легче вносить изменения, чем в последовательный список записей. Предположим, например, что нам нужно добавить новый счет за номером 111, пришедший от поставщика АА. Для этого нужно только добавить в файл новую запись и вставить ее в связный список.
Физически данную запись можно поместить куда угодно. Но куда ее следует поместить логически? Обычно у приложения на этот счет имеется некоторое требование, например такое: потомки должны быть логически упорядочены в порядке возрастания номера счета. В этом случае запись СЧЕТ ПО должна указывать на запись СЧЕТ П1 (с относительным нолтером 8), а новая запись, СЧЕТ 111, должна указывать на запись СЧЕТ 118 (с относительным номером 3).
Эти изменения показаны на рис. А.22. 3 4 б б 7 е Вставленная запись Рно. А.22. Файл, показанный на рнс. А.21 после добавления счета номер 111 Удаление счета происходит так же просто. Чтобы удалить счет номер 114, мы проста изменяем указатель записи, которая в данный момент указывает на за- Представление бинарных связей 743 пись СЧЕТ 114. В данном случае это запись СЧЕТ 112 с относительным номером 5.
В поле ссылки этой записи мы записываем значение, которое имел указатель записи СЧЕТ П4 до се удаления. Таким образом, запись СЧЕТ П2 теперь указьзвает на запись СЧЕТ П9 (рпс. А.23). Итак, мы исключили одно звено из цепочки и соединили между собой два других звена, которые оно ранее связывало. Относительный номер записи Содержимое записи Поле ссылки Рнс.
А.23. Удаление счета номер 114 нз файла, показанного на рнс. А.22 Представление деревьев с помощью индексов Древоабразную структуру можно также представить с помощью индексов. Метод заключается в хранении каждой связи «один ко мпап1мь в виде индекса. По этим спискам далее устанавливается связь между родителем и потомками. Обратившись к записям ПОСТАВЩИК и СЧЕТ па рис. А.21, мы увидим, что записи ПОСТАВЩИК АЯ (с относительным номером 1) принадлежат записи СЧЕТ 110 (относительный номер 7) и СЧЕТ ПВ (относительпый номер 3). Таким образом, запись с относительным номером 1 является родителем записей с относительными номерами 7 и 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
