Структуры данных и алгоритмы (1021739), страница 89
Текст из файла (страница 89)
Корень принимает пару "указатель-ключ" для нового узла, однако корень не расщепляется, поскольку он располагает достаточной емкостью.Удаление записи с ключом 10 из В-дерева, показанного на рис. 11.8, приводит к В-дереву, показанному на рис. 11.9. В этом случае блок, содержащий запись с ключом 10, отбрасывается. У его родителя теперь оказывается только два1Чтобы предотвратить возможное полное опустошение блоков листов, можно применятьразличные стратегии. В частности, ниже мы описываем схему предотвращения опустошениявнутренних узлов более чем наполовину.
Этот метод можно применить и к листьям.332ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИсына, а у правого "брата" этого родителя имеется минимальное количество сыновей — три. Таким образом, мы объединяем родителя с его "братом" и получаемодин узел с пятью сыновьями. Пт т т12 1416 1820 2223 2426 28 30 32 3436 38 40 42Рис. 11.8. В-дерево после вставки записи>1 2 у 1 б у 22 JJ244 6 812 14 16Т ^YSt182022 23 242638343628 30 3238 40 42- - •-•Рис. 11.9. В-дерево после удаления записиВремя выполнения операций с В-дереволлДопустим, есть файл с п записями, организованный в виде В-дерева порядка т.Если каждый лист содержит в среднем Ь записей, тогда дерево содержит примерно[п/Ь] листьев. Самые длинные пути в таком дереве образуются в том случае, есликаждый внутренний узел имеет наименьшее возможное количество сыновей, т.е.т/2.
В этом случае будет примерно 2[п/Ъ]/т родителей листьев, 4[п/Ь]/т2 родителейродителей листьев и т.д.Если вдоль пути от корня к листу встречается j узлов, в этом случае 21"\п/Ь\/т''1 > 1;в противном случае на уровне корня окажется меньше одного узла. Таким образом,[п/Ь] > (m/2/"1, a j < 1 + logn/2[n/b]. Например, если п = 106, Ь = 10, а т = 100, тоу < 3,9. Обратите внимание, что Ь является не максимальным количеством записей,которые мы можем поместить в блок, а средним или ожидаемым количеством. Однако, перераспределяя записи между соседними блоками каждый раз, когда один изних опустошается больше чем наполовину, мы можем гарантировать, что Ь будетравняться по крайней мере половине максимального значения.
Обратите также внимание на высказанное нами выше предположение о том, что каждый внутреннийузел имеет минимально возможное количество сыновей. На практике количество сыновей среднего внутреннего узла будет больше минимума, и приведенный выше анализ отражает, таким образом, самый "консервативный" случай.В случае вставки или удаления записи для поиска нужного листа потребуется jобращений к блокам. Точное количество дополнительных обращений к блокам, необходимое для выполнения вставки или удаления записи и распространения воздействия этих операций по дереву, подсчитать весьма затруднительно.
Чаще всего требуется перезаписать только один блок — лист, содержащий интересующую нас запись.Таким образом, в качестве ориентировочного количества обращений к блокам привыполнении вставки или удаления записи можно принять значение 2 + logm/2[ra/6].11.4. ВНЕШНИЕ ДЕРЕВЬЯ ПОИСКА•'.•333Сравнение методовИтак, в качестве возможных методов организации внешних файлов мы обсудилихеширование, разреженные индексы и В-деревья.
Интересно было бы сравнить количество обращений к блокам, связанное с выполнением той или иной операции с файлами, у разных методов.Хеширование зачастую является самым быстрым из трех перечисленных методов;оно требует в среднем двух обращений к блокам по каждой операции (не считая обращений к блокам, которые требуются для просмотра самой таблицы сегментов), если количество сегментов достаточно велико для того, чтобы типичный сегмент использовал только один блок.
Но в случае хеширования не легко обращаться к записям в отсортированной последовательности.Разреженный индекс для файла, состоящего из л записей, позволяет выполнятьоперации с файлами, ограничиваясь использованием примерно 2 + log(n/bb") обращений к блокам в случае двоичного поиска, где Ь — количество записей, помещающихся в один блок, а Ь'— количество пар "ключ-указатель", умещающихся в один блокдля индексного файла.
В-деревья позволяют выполнять операции с файлами с использованием примерно 2 + logm/2[n/6] обращений к блокам, где т — максимальноеколичество сыновей у внутренних узлов, что приблизительно равняется Ъ'. Как разреженные указатели, так и В-деревья допускают обращение к записям в отсортированной последовательности.Все перечисленные методы намного эффективнее обычного последовательногопросмотра файла. Временные различия между ними, однако, невелики и не поддаются точной аналитической оценке, особенно с учетом того, что соответствующие параметры, такие как ожидаемая длина файла и коэффициенты заполненности блоков,трудно прогнозировать заранее.Похоже на то, что В-деревья приобретают все большую популярность каксредство доступа к файлам в системах баз данных. Причина этой популярностичастично заключается в их способности обрабатывать запросы, запрашивая записи с ключами, относящимися к определенному диапазону (при этом используетсяпреимущество упорядоченности записей в основном файле в соответствии с последовательностью сортировки).
Разреженный индекс обрабатывает подобные запросы также достаточно эффективно — хотя, как правило, все же менее эффективно, чем В-деревья. На интуитивном уровне причина предпочтения В-деревьев(в сравнении с разреженным индексом) заключается в том, что В-дерево можнорассматривать как разреженный индекс для разреженного индекса для разреженного индекса и т.д. (Однако ситуации, когда требуется более трех уровнейиндексов, встречаются довольно редко.)В-деревья также зарекомендовали себя относительно неплохо при использовании их в качестве вторичных указателей, когда "ключи" в действительности неопределяют ту или иную уникальную запись.
Даже если записи с заданным значением для указанных полей вторичного индекса охватывают несколько блоков,мы можем прочитать все эти записи, выполнив столько обращений к блокам,сколько существует блоков, содержащих эти записи, плюс число их предшественников в В-дереве. Для сравнения: если бы эти записи плюс еще одна группатакого же размера оказались хешированными в одном и том же сегменте, тогдапоиск любой из этих групп в таблице хеширования потребовал бы такого количества обращений к блокам, которое приблизительно равняется удвоенному числу блоков, требующемуся для размещения любой из этих групп.
Возможно, естьи другие причины популярности В-деревьев, например их высокая эффективность в случае, когда к такой структуре одновременно обращается несколькопроцессов; впрочем, авторы настоящей книги не ставили перед собой задачу освещения подобных вопросов.334ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИУпражнения11.1. Составьте программу concatenate (конкатенация), которая принимает последовательность имен файлов в качестве аргументов и переписывает содержимоеэтих файлов на стандартное устройство вывода, осуществляя таким образомконкатенацию этих файлов.11.2.
Составьте программу include (включить в себя), которая копирует свой вход насвой выход за исключением случая, когда ей встречается строка в форме#include имя_файла; в этом случае программа должна заменить такую строкуна содержимое названного файла. Обратите внимание, что включенные файлытакже могут содержать операторы #include.11.3. Как поведет себя программа, о которой было сказано в упражнении 11.2, когда файл "замыкается" на себя?11.4.
Составьте программу compare (сравнение), которая сравнивает два файла, запись за записью, чтобы выяснить, идентичны ли эти файлы.*11.5. Перепишите программу сравнения, о которой говорилось в упражнении 11.4,воспользовавшись НОП-алгоритмом из раздела 5.6 для поиска самой длиннойобщей последовательности записей в обоих файлах.11.6. Составьте программу find (поиск), которая имеет два аргумента, состоящих изстроки шаблона и имени файла, и распечатывает все строки файла, содержащие указанную строку шаблона в качестве вложенной строки.
Если, например, строкой шаблона является "ufa", а файл представляет собой список слов,тогда find распечатывает все слова, содержащие указанные три буквы.11.7. Составьте программу, которая считывает файл и переписывает записи файла вотсортированной последовательности на свое стандартное устройство вывода.11.8.
Какие примитивы предусмотрены в языке Pascal для работы с внешними файлами? Как бы вы усовершенствовали их?*11.9. Допустим, используется трехфайловая многофазная сортировка, причем на i-мэтапе создается файл с г( сериями длины I/. На n-м этапе требуется одна серияиз одного файла и ни одной из двух других. Поясните, почему должно соблюдаться каждое из приведенных ниже условий.а) k = li-i + li-г Для i 2. 1, где IQ и l.i — длины серий в двух первоначально занятых файлах;б) г, — г1-2 - Гц (или, что эквивалентно, rt.2 = Гц + п) для i fe 1, где г0 и г-г —количество серий в двух первоначальных файлах;в) т„ = rn.i = 1 и, следовательно, ra, rn.i, ..., r t образуют последовательность чисел Фибоначчи.*11.10.Какое дополнительное условие нужно добавить к условиям, перечисленным в упражнении 11.9, чтобы сделать возможным выполнение многофазной сортировкиа) с начальными сериями длиной 1 (т.е.
Jo = l-i — 1)»б) в течение k этапов, но с другими начальными сериями.Совет. Рассмотрите несколько вариантов, например 1„ = 50, ln.i = 31 или1п - 50, 1ал - 32.**11.11. Обобщите упражнения 11.9 и 11.10 на многофазные сортировки с количествомфайлов, большим трех.**11.12. Покажите, чтоа) для сортировки п записей с помощью любого алгоритма внешней сортировки, который использует только одну магнитную ленту в качестве устройства внешней памяти, потребуется времени порядка i2(n2);УПРАЖНЕНИЯ335б) в случае использования двух магнитных лент в качестве устройств внешнейпамяти достаточно будет О(п log л) времени.11.13.
Допустим, имеется внешний файл, содержащий ориентированные дуги х -> у,которые образуют ориентированный ациклический граф. Допустим, что нехватает свободного объема оперативной памяти для одновременного хранениявсей совокупности вершин или дуг.а) Составьте программу внешней топологической сортировки, которая распечатывает такую линейно упорядоченную последовательность вершин, чтоесли х —> у представляет собой дугу, то в данной последовательности вершина х появляется до вершины у.б) Какой будет временная сложность программы как функции от количестваобращений к блокам и сколько ей потребуется пространства оперативнойпамяти?в) Как поведет себя программа, если ориентированный граф окажется циклическим?**г) Каково будет минимальное количество обращений к блокам, необходимоедля выполнения топологической сортировки при внешнем хранении ориентированного ациклического графа?11.14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
