Теория и практика построения баз данных (1088289), страница 159
Текст из файла (страница 159)
Но представьте, что сортировку требуется выполнить одновременно обоилси способами, поскольку два параллельно работающих пользователя имеют различные представления файла ЗАНЯТИЯ. Что делать в этом случае? Одно из решений — создать две копни файла ЗАНЯТИЯ и отсортировать пх в нужном порядке, как показано на рпс. А.2. В связи с тем, что данные в такой структуре упорядочены в определенной логической последовательности, ее иногда называют лоследаеиглсльным списком (зечцепсьа! 1!зс).
Последовательные списки можно хранить в виде файлов с последовательным доступом. Однако обычно СУБД не делают этого, так как последовательное чтение файла — процесс долгий. Кроме того, файлы последовательного доступа невозможно обновить в середине без перезаписи всего файла. К тому же, хранение нескольких копий одного и того же последовательного списка неэффективно, так как это может привести к нарушеьшю целоспюсти данных. К счастью, сушествукьт структуры данных, позволяющие обрабатывать записи в различном порядке, но не требуюшие дублирования данных. Такими структурами являются, среди прочих, индексы (шс1ехез) и сеязньье списки Гйл)тес! Гиг4.
Замечание по поводу адресации записей Обычно СУБД создает в своих файлах прямого доступа физические записи боль- шого размера, плп блоки. В этих блоках содержатся логические записи. Как пра- вило, одна физическая запись содержит множество логических. Здесь мы предпо- ложны, что обрашенне к физической записи происходит по ее относительному номеру. Например, лопьческая запись может принадлежать физической записи с номером 7, 77 или 10 000. Таким образом, относительный номер записи — это физический адрес логической записи.
Если одна физическая запись содержит несколько логических записей, адрес логической записи должен также указывать ее положение внутри физической записи. Следовательно, полный адрес логической записи может иметь структуру вида «относительный номер записи 77, смешение 100». Это означает, что запись начинается с байта 100 физической заппсси 77, а б Рнс. А.2. Файл ЗАНЯТИЯ, организованный в виде последовательного списка: а — с упорядочением по полю НомврСтудента; б — с упорядочением по полю Номергруппы Для упрощения примеров в тексте мы будем предполагать, что одна физическая запись содержит только одну логическую, чтобы нам не пришлось задумываться о смешениях байтов внутри физических записей. Хотя это и не соответствует действительности, зато ограничивает изложение тазько суШественпыми моментами. Упорядочение с помощью связных списков Связные списки 1!ьп1сед 1ьзгз) позволяют производить логическое упорядочение записей, в общем случае не упорядоченных физически.
Для создания связного списка к каждой записи добавляется специальное поле — поле ссылки. Это поле содержит адрес (в нашем случае — относительный номер) следуьоисей записи в логической последовательности. Например, на рис. А.З изображен модифицированный файл ЗАНЯТИЯ со связным списком, в котором записи упорядочены по полю НомерСтудента. Обратите внимание, что поле ссылки в последней по логическому порядку запнсп имеет нулевое значение. На рис. А.4 показан файл ЗАНЯТИЯ с двумя связными списками, один из которых упорядочен по полю НомерСтудента, а другой — по полю НомерГруппы.
Каждая запись имеет два поля ссылки, по одному на каждый список. Прп вставке и удалении связные списки имеют огромное преимушество над последовательными. Например, чтобы вставить в файл ЗАНЯТИЯ запись о студенте 200 и группе 45, пришлось бы переписать оба списка, приведенные на рис. А.2. В случае связных списков новую запись можно добавить в конец физического списка, а чтобы она завяла правильное место в связных списках, потребуется изменить только значения двух полей ссылок.
Эти изменения показаны на рис, А.5. Плоские Файлы 733 Относительный Номер- Номер- номер звпиаи Студента Предмета Семестр Ссылка Ссылка на студента на предмет Начало апиака = 2 Рис. А.4. Файл Номер- Намер- Ссылка Студента Предмета Семестр на студента Ссылка нв предмет Относительный номер записи Начало спиака = 2 Ссылка Ссылка на апиаок, на спивак, упорядоченный упорядоченный Семестр по возрастанию по убыванию Относительный Номер- Номер- номер записи Студента Предмета 732 Приложение д.
Структуры данных Относительный Номер- Намерномер записи Студента Предмета Семеатр Ссылка Рис. А.З. Файл ЗАНЯТИЯ, упорядоченный по палю НомврСтудвнта с помощью связного описка Относительный Номер- Номер- Ссылка Ссылка номер записи Студента Предмета Семестр на студенте нв предмет Начало списка студентов = 2 Начало списка предметов = 6 ЗАНЯТИЯ, упорядоченный двумя различными способами с помощью связных аписков Начало спиакв атудентов = 2 Начало списка предметов = 6 Рис. А.в.
Файл ЗАНЯТИЯ после вставки новой записи (упорядоченный двумя способами а помощью связных списков) Когда запись удаляется пз последовательного списка, на ее месте возникает пустота. Но в связанных списках запись можно удалить, просто изменив значения полей ссылок, или указал)елей, На рис. А.б запись о студенте 200 из группы 30 логически удалена из файла ЗАНЯТИЯ. Ни одна другая запись не имеет ссылки па ее адрес, так что она оказывается аффективно удаленной пз цепочки, хотя физически по-прежнему существует.
Начало списка атудентов = 2 Начало списка предметов = б Рис. А.б. Файл ЗАНЯТИЯ после удаления студента 200 из группы ЗО (упорядоченный двумя способами с иапользованием связных аписков) Есть много вариантов связных списков. Можно создать кольцевой список Сс!гоп)аг 1!зг), или кольцо (г!пя), записав в поле ссылки последней записи вместо нуля адрес первой записи в спинке. Теперь можно найти любой элемент в списке, начав с произвольного элемента. На рис. А.7, а показан кольцевой список, упорядоченный по полю НамерСтудента. Двусвяэттгнй список С(що-угау 1!п)тес) 1!з() имеет ссылки в обоих направлениях. На рис.
А.7, б изображен двусвязпый список, упорядоченный по возрастанию и по убываншо поля НоиерСтудента. Относительный Номер- Номер. номер записи Студента Предмета Семестр Саылкв Начало списка, упорядоченного по возрватанию = 2 Начало описка, упорядоченнага по убыванию = б б Риа. АЛ. Файл ЗАНЯТИЯ, упорядоченный по полю НомврСтудента с использованием. а — кольцевого списка; б — двусвязного списка 734 Приложение А. Структуры данных Плоские файлы 735 Записи, упорядоченные посредством связных списков, це могут храниться в файлах с послеловательиым доступом, так как для работы со ссылками необходима та или иная форма прямого доступа.
Таким образом, лля обработки связных списков требуется либо последовательный доступ с индексацией, либо прямой доступ. Упорядочение с помощью индексов Логическое упорядочение записей может также производиться с помощью иььдсксое (ьььоехеа), или, как их еще называют, иььвертпированьььст списков (шуегсет1!1асз). Индекс представляет собой таблицу, где значениям некоторого поля сопоставлены ссылки иа записи, солержащие эти значения. Например, иа рис. А.8, а показан файл ЗАНЯТИЯ с пеуцорядочеииыми записями, а иа рис. А.8, б изображен индекс иа поле НомерСтудента.
В этом индексе номера студентов расположены цо порядку, и ущя каждого номера имеется ссылка на соответствукццую запись в исходных данных Относительный Номер- Номер- номер записи Студента Предмета Семестр Номер- Относительный Студента номер записи Номер- Относительный Студента номер записи в Рис. А.8. Файл ЗАНЯТИ я с соответствующими индексами: в — файл ЗАНяТИя; о — индекс по полю НомерСтудента; в — индекс по полю Номергруппы Как можно видеть, ицлекс представляет собой це что ипое, как отсортированный список номеров студентов.
Для последовательной обработки файла ЗАНЯТИЯ по полю НомерСтудента иужью просто последовательно обрабатывать индекс, читая из файла записи, иа которые указывают ссылки. На рис. А.8, е изображен еще один индекс для файла ЗАНЯТИЯ, упорядочепцый по полю Номер- Группы. Для работы с индексами упорядочиваемые даьшые должны содержаться в файле с прямым пли цпдексируемым последовательным доступом, хотя лля хранения самих шьдексов можно использовать любой тип файлов. В реальности почти все СУБД хранят и данные, и индексы в файлах прямого доступа. Если сравнить связцый список с индексом, межлу ними обнаружится коренное различие. В связиом списке указатели хранятся вместе с даьтыми.
Каждая запись имеет поле ссылки, содержащее указатель иа следукццуьо по порядку запись. При использовании же индексов указатели хранятся отдельно от данных— собственно в иилексах. Таким образом, сами по себе данные це содержат указателей. В коммерческих СУБД используются оба полхода к храиешпо указателей.
Бинарные деревья Специальным приложением концепции индексов, или инвертированных списков, являются бинарные деревья — многоуровневые индексы, предоставляющие возможность как последовательной, так и прямой обработки записей. Благодаря особенностям своей структуры они также обеспечивают определепиое повышен ис эффектив ности обработки. Бинарное дерево — это цилекс, состояьций из двух частей: последовательного набора (зес1цепсе зсс) и индексного пабора (1пь)ех аеС). (Эти термины попользуются в документации компаииц 1ВМ, описывающей структуру ЛБАМ-файла. Вам могут встретиться лругие, сииопимичиыс термины.) ПосведоватеяьньььТ набор представляет собой индекс, содержащий указатели иа все записи в файле.
Этот индекс физически упорядочен, обычно по значению первичного ключа. Такая структура позволяет обращаться к записям последовательна, считывая один за другим адреса записей яз последовательного набора и по ипм считывая сами записи. Оидексььььй набор — это индекс, указывающий иа группу записей в последовательном наборе. Эта структура обеспечивает быстрый доступ к записям в фаГьле, и имсиио в индексном наборе а заключается уникальность бинарных леревьев, Пример бинарного лерева изображен иа рис. А.9, а конкретный экземпляр этой структуры показан ца рис.
А.10. Обратите внимание, что иижпяя строчка ца рис. А.9 — последовательиьш набор — представляет собои обычный индекс. Оц содержит указатель ца каждую запись в файле (хотя для краткости лаииые и адреса записей были опущены). Также заметьте, что элементы послеловательиого набора сгруппированы по трп. Зшшси в каждом группе физически упорялочеиы, и каждая группа связана со следующей посредством связного списка, как можно видеть иа рпс.
А.10. Взгляните иа индексный набор иа рцс. А.9. Верхняя запись содержит два значения, 45 и 77. Следуя левой линии связи (к записи с относительным номером 2), мы можем обратиться к записям, значения ключей которых меньше цли равны 45; следуя средней линии связи, мы можем обратиться к записям, зиачеиия ключей которых больше 45 и меньше или равны 77; наконец, следуя правой линии связи (к записи с относительным номером 4),мы можем обратиться к записям, значения ключей которых больше 77.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
