Внешний поиск a

Перспективы

Наиболее важное применение рассмотренных в этой главе методов — это построение индексов для очень больших баз данных, хранимых во внешней памяти, например, в дисковых файлах. Хотя рассмотренные фундаментальные алгоритмы обладают большими возможностями, разработка реализации файловой системы, основанной на использовании B-деревьев или расширяемого хеширования, представляет собой сложную задачу. Во-первых, приведенные в этом разделе С++-программы нельзя использовать непосредственно — они должны быть модифицированы для считывания и обращения к дисковым файлам. Во-вторых, необходимо быть уверенным, что параметры алгоритма (например, размеры страницы и каталога) подобраны с учетом характеристик конкретного используемого аппаратного обеспечения. В-третьих, следует уделить внимание надежности, а также выявлению и исправлению ошибок. Например, необходимо иметь возможность убедиться в целостности структуры данных и принять решение о том, как исправить любую из множества возможных ошибок. Подобные системные факторы являются критичными и выходят за рамки этой книги.
С другой стороны, при наличии среды программирования, которая поддерживает виртуальную память, рассмотренные реализации на языке C++ можно непосредственно использовать в ситуации, когда необходимо выполнять очень большое количество операций в очень большой таблице символов. В первом приближении можно сказать, что при каждом обращении к странице такая система будет помещать эту страницу в кэш, в котором ссылки на данные этой страницы обрабатываются более эффективно. При обращении к странице, отсутствующей в кэше, система должна считать страницу из внешней памяти, поэтому случаи отсутствия страницы в кэше можно считать приблизительным эквивалентом используемой нами меры затрат на пробу.
При использовании B-деревьев каждый поиск или вставка обращается к корню, поэтому корень будет присутствовать в кэше всегда. В противном случае, если M достаточно велико, типичные случаи поиска или вставки максимум два раза обращаются к страницам вне кэша. При достаточно большом объеме кэш-памяти велика вероятность того, что первая страница, к которой происходит обращение при поиске (дочерняя страница корня), уже присутствует в кэше, поэтому средние затраты на один поиск, скорее всего, будут значительно меньше двух проб.
При использовании расширяемого хеширования маловероятно, что весь каталог будет храниться в кэше, поэтому можно ожидать, что обращения и к каталогу, и к странице не будут попадать в кэш (худший случай). То есть для выполнения поиска в очень большой таблице требуются две пробы: одна для обращения к соответствующей части каталога, а другая для обращения к соответствующей странице.
Эти алгоритмы завершают наше знакомство с поиском, поскольку для их эффективного использования требуется понимание базовых свойств бинарного поиска, деревьев бинарного поиска, сбалансированных деревьев, хеширования и trie-деревьев — базовых алгоритмов поиска, которые были изучены в лекциях 12—15. Все вместе эти алгоритмы предоставляют решения для задачи реализации таблицы символов во множестве ситуаций и представляют собой прекрасный пример возможностей технологии алгоритмов.
Упражнения
16.46. Разработайте реализацию таблицы символов с использованием B-деревьев, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить и объединить для АТД таблицы символов с поддержкой клиентских дескрипторов (см. упражнения 12.6 и 12.7).
16.47. Разработайте реализацию таблицы символов с использованием расширяемого хеширования, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить и объединить для АТД таблицы символов с поддержкой клиентских дескрипторов (см. упражнения 12.6 и 12.7).
16.48. Измените реализацию B-дерева, приведенную в разделе 16.3 (программы 16.1—16.3), чтобы в ней для обращений к страницам использовался абстрактный тип данных.
16.49. Измените реализацию расширяемого хеширования, приведенную в разделе 16.4 (программы 16.5—16.8), чтобы в ней для обращений к страницам использовался абстрактный тип данных.
16.50. Оцените среднее количество проб, затрачиваемое на каждый поиск в B-дереве, при выполнении S случайных поисков в типичной кэш-системе, хранящей в памяти T страниц, к которым выполнялись последние обращения (т.е. они не увеличивают значение счетчика проб). Считайте, что S значительно больше T.
16.51. Оцените среднее количество проб на каждый поиск в расширяемой хеш-таблице для модели кэш-памяти, описанной в упражнении 16.50.
16.52. Если используемая вами система поддерживает виртуальную память, разработайте и проведите эксперименты для сравнения производительности B-деревьев с производительностью бинарного поиска при выполнении случайных поисков в очень большой таблице символов.
16.53. Реализуйте АТД очереди с приоритетами, поддерживающий операцию создать для очень большого количества элементов, вслед за которой выполняется очень много операций вставить и удалить наибольший (см. "Очереди с приоритетами и пирамидальная сортировка"
16.54. Разработайте АТД внешней таблицы символов, основанной на представлении B-деревьев в виде слоеного списка (см. упражнение 13.80).
16.55. Если используемая вами система поддерживает виртуальную память, определите экспериментально значение M, которое обеспечивает наименьшее время выполнения для реализации B-дерева, поддерживающей случайные операции вставить в очень большой таблице символов. (Прежде чем выполнять подобные эксперименты, которые могут потребовать больших затрат, стоит ознакомиться с основными характеристиками системы.)
16.56. Измените реализацию B-дерева, приведенную в разделе 16.3 (программы 16.1—16.3), чтобы она работала в среде, в которой таблица размещается на внешнем запоминающем устройстве. Если применяемая файловая система допускает произвольный доступ к файлам, поместите всю таблицу в один (очень большой) файл, и в структуре данных вместо ссылок используйте смещения внутри файла. Если система допускает непосредственное обращение к страницам на внешних устройствах, то в структуре данных вместо ссылок используйте адреса страниц. Если система допускает оба вида доступа, выберите подход, который, по вашему мнению, наиболее подходит для реализации очень большой таблицы символов.
16.57. Измените реализацию таблицы расширяемого хеширования, приведенную в разделе 16.4 (программы 16.5—16.8), чтобы она работала в среде, в которой таблица размещается на внешнем запоминающем устройстве. Объясните причины выбранного вами способа распределения каталога и страниц по файлам (см. упражнение 16.56).