зациями таблиц символов из рассмотренными в главах 12-15. Будучи таковыми, они вообще не являются внешними методами. Тем не менее, они построены в соответствии с простой абстрактной моделью, что превращает их в подробное описание того, как строить методы поиска для конкретных внешних устройств.

Подробные абстрактные модели менее полезны, чем применительно к сортировке, поскольку связанные с ними затраты весьма невелики для многих важных приложений. В основном нас будут интересовать методы поиска в очень больших файлах, хранящихся на внешних устройствах наподобие дисков, которые обеспечивают быстрый доступ к произвольным блокам данных. Для устройств типа ленточных накопителей, где допускается только последовательный доступ (похожая модель рассматривалась в главе И), поиск вырождается до тривиального (и медленного) метода считывания с начала файла до тех пор, пока поиск не будет завершен. Для дисковых устройств можно воспользоваться гораздо более эффективным подходом: как ни удивительно, методы, которые мы изучим, могут поддерживать операции search и insert в таблицах символов, содержащих миллиарды и триллионы элементов, при использовании всего трех-четырех ссылок на блоки данных на диске. Такие системные параметры, как размер блока и отношение затрат на доступ к новому блоку к затратам на доступ к элементам внутри блока, влияют на производительность, но методы можно считать относительно не зависящими от этих параметров (в пределах значений, которые, скорее всего, будут встречаться на практике). Более того, большинство важных шагов, которые необходимо предпринимать для подгонки методов под конкретные реальные ситуации, вполне очевидны.

Поиск - это фундаментальная операция для дисковых устройств. Как правило, файлы организованы так, чтобы можно было воспользоваться преимуществами конкретного устройства с целью максимально эффективного доступа к информации. Короче говоря, вполне можно предположить, что устройства, используемые для хранения очень больших объемов информации, построены именно для поддержки эффективных и простых реализаций операции search. В этой главе рассматриваются алгоритмы, которые построены на несколько более высоком уровне абстракции, нежели базовые операции, обеспечиваемые дисковыми устройствами, и которые могут поддерживать операцию insert и другие динамические операции для таблиц символов. Эти методы по сравнению с прямыми методами предоставляют такие же преимущества, какие деревья бинарного поиска и хеш-таблицы предоставляют по сравнению с бинарным и последовательным поиском.

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

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

ветствия, который может включать несколько ключей и возвращать большое количество элементов. Методы этого типа затрагиваются в частях 5 и 6. В общем случае запросы на поиск достаточно сложны, чтобы зачастую приходилось выполнять последовательный поиск по всей базе данных, проверяя каждый элемент на соответствие критерию. Тем не менее, быстрый поиск крошечных фрагментов данных, соответствующих конкретному критерию, в офомном файле - основная возможность в любой системе баз данных, и многие современные базы данных строятся на основе описанных в этой главе механизмов.

16.1 Правила игры

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

Определение 16.1 Страница - это непрерывный блок данных. Зондирование - это первое обращение к странице.

Нас интересуют реализации таблиц символов, в которых используется небольшое количество зондирований. Мы будем избегать конкретных предположений касательно размеров страницы и отношения времени, требуемого для зондирования, ко времени, которое впоследствии потребуется для доступа к элементам внуфи блока. Ожидается, что эти значения должны быть порядка 100-1000; большая точность не требуется, поскольку алгоритмы не особо чувствительны к этим значениям.

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

Эта модель непосредственно применима и к системе виртуальной памяти, где мы просто ссылаемся на огромный объем памяти и предоставляем системе самой сохранять часто используемую информацию в хранилище с бысфым доступом (таком, как внутренняя память), а редко используемую информацию - в хранилище с медленным доступом (таком, как диск). Многие компьютерные системы располагают слож-

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

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

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

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

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