Главная Промышленная автоматика.

сына, а у правого "брата" этого родителя имеется минимальное количество сыновей - три. Таким образом, мы объединяем родителя с его "братом" и получаем один узел с пятью сыновьями. □

[18jj28[» I»

»12

4 6 8

12 14 16

1820

22 23 J24 2б

t 38

28 30 32

34 Зб

38 40 42

Рис. 11 я. В-дерево после вставки записи


Рис. 11.9. В-дерево после удаления записи

Время выполнения операций с В-дереволл

Допустим, есть файл с и записями, организованный в виде В-дерева порядка т. Если кавдый лист содержит в среднем Ь записей, тогда дерево содержит примерно [п/6] листьев. Самые длинные пути в таком дереве образуются в том случае, если каждый внутренний узел имеет наименьшее возмокное количество сыновей, т.е. т/2. В этом случае будет примерно 2[п/Ь]/тродителей листьев, 4[п/й]/тодителей родителей листьев и т.д.

Если вдоль пути от корня к листу встречается j узлов, в этом случае 2\п/Ь]/т~> 1; в противном случае на уровне корня окажется меньше одного узла. Таким образом, [n/bj > (т/гу S а j < 1 -Ь 1/2[л/Ь]-Например, если и = 10 Ь = 10, а м = 100, то J < 3,9. Обратите внимание, что Ь является не максимальным количеством записей, которые мы можем поместить в блок, а средним или ожидаемым количеством. Однако, перераспределяя записи мевду соседними блоками каждый раз, когда один из них опустошается больше чем наполовину, мы можем гарантировать, что Ь будет равняться по крайней мере половине максимального значения. Обратите таюке внимание на высказанное нами выше предположение о том, что каждый внутренний узел имеет минимально возможное количество сьшовей. На практике количество сыновей среднего внутреннего узла будет больше минимума, и приведенный выше анализ отражает, таким образом, самый "консервативный" случай.

В случае вставки или удаления записи для поиска нркного листа потребуется j обрашений к блокам. Точное количество дополнительных обрашений к блокам, необходимое для выполнения вставки или удаления записи и распространения воздействия этих операций по дереву, подсчитать весьма затруднительно. Чаше всего требуется перезаписать только один блок - лист, содержащий интересующую нас запись. Таким образом, в качестве ориентировочного количества обрашений к блокам при выполнении вставки или удаления записи мокно принять значение 2 -Ь log„/2[w/b].

11.4. ВНЕШНИЕ ДЕРЕВЬЯ ПОИСКА



Сравнение методов

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

Хеширование зачастую является самым быстрым из трех перечисленных методов; оно требует в среднем двух обрашений к блокам по каждой операции (не считая обрашений к блокам, которые требуются для просмотра самой таблицы сегментов), если количество сегментов достаточно велико для того, чтобы типичный сегмент использовал только один блок. Но в случае хеширования не легко обрашаться к записям в отсортированной последовательности.

Разреженный индекс для файла, состояшего из л записей, позволяет выполнять операции с файлами, ограничиваясь использованием примерно 2 + 1о§(п/Ьй)обраше-ний к блокам в случае двоичного поиска, где Ь - количество записей, помешаюших-ся в один блок, а fc- количество пар "ключ-указатель", умешаюшихся в один блок для индексного файла. В-деревья позволяют выполнять операции с файлами с использованием примерно 2 + logm/2[n/b] обрашений к блокам, где т - максимальное количество сыновей у внутренних узлов, что приблизительно равняется Ъ. Как разреженные указатели, так и В-деревья допускают обрашение к записям в отсортированной последовательности.

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

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

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



Упражнения

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,-. На л-м этапе требуется одна серия из одного файла и ни одной из двух других. Поясните, почему должно соблюдаться каждое из приведенных ниже условий.

) k м+ li2i > 1,где loVL l-i- длины серий в двух первоначально занятых файлах;

б) г, - г,.2 - Гц (или, что эквивалентно, г,.2 = Ец -Ь г,) для i fe 1, где го и r.i - количество серий в двух первоначальных файлах;

в) г„ = г„1 = 1 и, следовательно, г„, r„.i, ri образуют последовательность чисел Фибоначчи.

*11.10.Какое дополнительное условие нужно добавить к условиям, перечисленным в упражнении 11.9, чтобы сделать возможным выполнение многофазной сортировки

а) с начальными сериями длиной 1 (т.е. 1о = Ц- 1);

б) в течение к этапов, но с другими начальными сериями.

Совет. Рассмотрите несколько вариантов, например 1„ = 50, 1пл = 31 или /„ - 50, /„, - 32.

** 11.11. Обобщите упражнения 11.9 и 11.10 на многофазные сортировки с количеством файлов, большим трех.

** 11.12. Покажите, что

а) для сортировки и записей с помошью любого алгоритма внешней сортировки, который использует только одну магнитную ленту в качестве устройства внешней памяти, потребуется времени порядка Д(л);





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 [107] 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0045