б) в случае использования двух магнитных лент в качестве устройств внешней памяти достаточно будет 0(п logл) времени.

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

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

б) Какой будет временная сложность программы как функции от количества обрашений к блокам и сколько ей потребуется пространства оперативной памяти?

в) Как поведет себя программа, если ориентированный граф окажется циклическим?

**г) Каково будет минимальное количество обрашений к блокам, необходимое для выполнения топологической сортировки при внешнем хранении ориентированного ациклического графа?

11.14.Допустим, имеется файл, состояший из одного миллиона записей, причем каждая запись занимает 100 байт. Блоки имеют длину 1000 байт, а указатель на блок занимает 4 байта. Придумайте вариант организации этого файла с помошью хеширования. Сколько блоков потребуется для хранения таблицы сегментов и самих сегментов?

11.15.Придумайте вариант организации файла, описанного в упражнении 11.14, в виде В-дерева.

11.16.Напишите программы, реализующие операторы RETRIEVE, INSERT, DEEETE и MODIFY ддя

а) хешированных файлов;

б) индексированных файлов;

в) файлов в виде В-дерева.

11.17.Составьте программу, выполняюшую поискй-го наибольшего элемента

а) в файле с разреженным индексом;

б) в файле в виде В-дерева.

*11.18. Допустим, что на считывание блока, содержащего узел т-арного дерева поиска, уходит а. + Ьт миллисекунд. Допустим также, что на обработку кавдого узла во внутренней памяти уходит с + dloggm миллисекунд. Если на таком дереве имеется и узлов, то потребуется считать приблизительно log„n узлов, чтобы обнарркить нужную запись. Таким образом, обшее время, которое потребуется, чтобы найти на дереве нркную запись, составит

(log,,, n){a + bm + с + d logj т) - (log п)((а + с + bm)/ logm + d)

миллисекунд. Сделайте обоснованные оценки значений а, Ь, с и и постройте график зависимости этой величины от т. При каком значении т удается достичь минимума?

*11.19.В*-дерево представляет собой В-дерево, в котором каждый внутренний узел заполнен не на половину, а по крайней мере на две третьих. Придумайте схему вставки записи для В*-деревьев, которая позволяет отложить расщепление внутренних узлов до того момента, пока не окакутся заполненными два узла-"брата". Затем два этих заполненных узла можно разделить на три, каждый из которых будет заполнен на две третьих. Каковы преимущества и недостатки В*-деревьев в сравнении с В-деревьями?

* 11.20. Когда ключ записи представляет собой строку символов, можно сэкономить место в памяти, сохраняя в каждом внутреннем узле В-дерева в качестве разделителя ключей только префикс ключа. Например, слова "cat" и "dog" можно разделить префиксом "d", или "do", или "dog". Придумайте такой алгоритм вставки для В-дерева, который использует как можно более короткие префиксные разделители ключей.

*11.21. Допустим, что р-ю часть времени при выполнении операций с определенным файлом занимают вставки и удаления, а оставшуюся (1 - р)-ю часть времени занимают операции поиска информации, в которых указывается только одно поле. В записях файла имеются k полей, а i-e поле в операциях поиска указывается с вероятностью qt- Допустим, что выполнение операции поиска занимает а миллисекунд, если для указанного поля не предусмотрен вторичный индекс, и Ь миллисекунд, если для этого поля предусмотрен вторичный индекс. Допустим такясе, что выполнение операций вставки и удаления занимает с + sd миллисекунд, где s - количество вторичных индексов. Определите среднее время выполнение операций как функцию от а, Ь, с, d, р я д,- и минимизируйте его.

**11.22. Предположим, что используемый тип ключей допускает возможность их линейного упорядочения (например, ключи являются действительными числами) и известно вероятностное распределение в данном файле ключей с заданными значениями. Па основании этих сведений постройте алгоритм поиска ключа в разреженном индексе, превосходящий по эффективности двоичный поиск. Эта статистическая информация используется в одной из схем (которая называется интерполяционным поиском) для прогнозирования, в каком именно месте диапазона индексных блоков Bi, ... ,В, вероятность появления ключах является наибольшей. Докажите, что для поиска ключа в среднем было бы достаточно 0(]og logn) обращений к блокам.

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

а) Напишите программу построения остовного дерева минимальной стоимостью для графа G, полагая, что объем основной памяти достаточен для хранения всех вершин графа, но не достаточен для хранения всех его ребер.

б) Какова временная сложность этой программы как функции от количества вершин и ребер?

Совет. Один из подходов к решению этой задачи заключается в сохранении леса связных компонентов в основной памяти. Каждое ребро считывается и обрабатывается следующим образом. Если концы очередного ребра находятся в двух разных компонентах, добавить это ребро и объединить данные компоненты. Если это ребро создает цикл в каком-то из существующих компонентов, добавить это ребро и удалить ребро с наивысшей стоимостью из соответствующего цикла (это ребро может быть текущим). Такой подход подобен алгоритму Крускала, но в нем не требуется сортировки ребер, что весьма существенно для решения данной задачи.

11.24. Допустим, что имеется файл, содержащий последовательность положительных и отрицательных чисел «1, Ог, ... ,а„. Напишите программу с временем выполнения 0(п), которая находила бы непрерывную вложенную подпоследовательность Oi, а,+1, ... которая имела бы наибольшую сумму а, + щ+х + ... + Oj среди всех вложенных подпоследовательностей такого рода.

Библиографические примечания

Дополнительный материал по внешней сортировке можно найти в книге [65], по структурам внешних данных и их использованию в системах баз данных - там же, а также в [112] и [118]. Многофазная сортировка обсуждается в работе [102]. Схема слияния с шестью буферами, описанная в разделе 11.2, заимствована из [39], а схема с четырьмя буферами - из [65].

Выбор вторичного индекса, упрошенным вариантом которого является упражнение 11.21, обсуждается в работах [72] и [95]. Ссылка на В-деревья впервые встречается в [6]. В [20] приведен обзор различных вариантов В-деревьев, а в [45] обсуждается их практическое применение.

Информацию, касаюшуюся упражнения 11.12 (сортировка с помошью одной и двух магнитных лент), можно найти в [35]. Тема упражнения 11.22, посвяшенного интерполяционному поиску, подробно обсуждается в [84] и [124].

Весьма элегантная реализация подхода, предложенного в упражнении 11.23 для решения задачи построения остовного дерева минимальной стоимости, принадлежит В. А. Высоцкому (1960 г., не опубликовано).