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

Определение 16.1. Страница — это непрерывный блок данных. Проба — это первое обращение к странице.
Нас интересуют реализации таблиц символов, использующие небольшое количество проб. Мы будем избегать конкретных предположений по поводу размеров страницы и отношения времени, необходимого для пробы, ко времени, которое впоследствии потребуется для доступа к элементам внутри блока. Ожидается, что эти значения должны быть порядка 100—1000; большая точность не требуется, поскольку алгоритмы не очень чувствительны к этим значениям.
Эта модель непосредственно применима, например, к файловой системе, в которой файлы состоят из блоков с уникальными идентификаторами, и назначение которой состоит в поддержке эффективных операций чтения, вставки и удаления на основе этих идентификаторов. Блок содержит определенное количество элементов, и затратами на обработку элементов внутри блока можно пренебречь по сравнению с затратами на считывание блока.
Эта модель непосредственно применима и к системе виртуальной памяти, где мы просто работаем с огромным объемом памяти и предоставляем системе самой сохранять часто используемую информацию в запоминающем устройстве с быстрым доступом (таком, как внутренняя память), а редко используемую информацию — в медленном запоминающем устройстве (таком, как диск). Многие компьютерные системы имеют сложные механизмы страничной обработки, которые реализуют виртуальную память, храня недавно использовавшиеся страницы в кэше (cash), который допускает быстрое обращение. Системы страничной организации памяти основаны на той же рассматриваемой абстракции: они делят диск на блоки и считают, что затраты на первое обращение к блоку существенно превышают затраты на доступ к данным внутри блока.
Обычно такое абстрактное представление страницы в точности соответствует блоку в файловой системе или странице в системе виртуальной памяти. Для простоты при рассмотрении алгоритмов мы всегда будем предполагать такое соответствие. В конкретных ситуациях, в зависимости от системы или приложения, блок может состоять из нескольких страниц, либо несколько блоков могут образовывать одну страницу; подобные нюансы не снижают эффективность алгоритмов, тем самым лишь подчеркивая удобство работы на абстрактном уровне.
Мы работаем со страницами, ссылками на страницы и элементами с ключами. Для большой базы данных наиболее важная для рассмотрения задача заключается в поддержке индексов данных. То есть, как было кратко упомянуто в "Таблицы символов и деревья бинарного поиска" , мы предполагаем, что элементы, образующие нашу таблицу символов, хранятся где-то отдельно, а наша задача состоит в построении структуры данных с ключами и ссылками на элементы, которая позволяет быстро получить ссылку на заданный элемент. Например, телефонная компания может хранить информацию о клиентах в огромной статической базе данных и использовать несколько индексов, возможно, использующих различные ключи, для ежемесячных оплат счетов, обработки ежедневных транзакций, периодических запросов и т.п. Для очень больших наборов данных индексы имеют первостепенное значение: обычно копии основных данных не создаются не только потому, что невозможно выделить дополнительный объем памяти, но и потому, что желательно избежать проблем, связанных с поддержкой целостности данных при использовании нескольких копий.
Соответственно, мы обычно предполагаем, что каждый элемент представляет собой ссылку на фактические данные, которая может быть адресом страницы или каким-либо более сложным интерфейсом для базы данных. Для простоты будем хранить в своих структурах данных не копии элементов, а копии ключей — часто такой подход оказывается наиболее практичным. Кроме того, для простоты описания алгоритмов мы не будем использовать абстрактный интерфейс для ссылок на элементы и страницы — вместо этого будем использовать только указатели. Таким образом мы сможем использовать наши реализации непосредственно в среде виртуальной памяти, но нам придется преобразовать ссылки и обращения к объектам в более сложные механизмы, чтобы сделать их действительно методами внешней сортировки.
Мы рассмотрим алгоритмы, которые для широкого диапазона значений двух основных параметров (размера блока и относительного времени доступа) реализуют операции найти, вставить и другие в полностью динамической таблице символов, используя для каждой операции лишь несколько проб. В типичном случае, когда выполняется огромное количество операций, может очень помочь тщательная настройка. Например, если типичные затраты на поиск удастся снизить с трех проб до двух, производительность системы может повыситься на 33%! Однако в этой главе подобная настройка не рассматривается; ее эффективность в очень большой степени зависит от используемой системы и приложения.
В первых компьютерах внешние запоминающие устройства были сложными аппаратами, которые не только были большими и медленно работающими, но и не могли хранить большие объемы информации. Поэтому было важно обойти их ограничения, и фольклор начала эпохи программирования полон историями о программах доступа к внешним файлам, которые обеспечивали прекрасную синхронизацию при чтении данных с вращающегося диска или барабана, или как-либо иначе минимизировали физические перемещения, необходимые для доступа к данным. Но фольклор полон и историями о сокрушительных провалах подобных попыток, когда малейшие просчеты существенно замедляли процесс по сравнению с простейшими реализациями. В отличие от тех монстров, современные устройства хранения информации не только очень малы по размерам и исключительно быстро работают, но и способны хранить огромные объемы информации, поэтому обычно такие проблемы решать не приходится. Вообще-то в современных средах программирования мы стремимся избегать зависимости от свойств конкретных физических устройств — чаще гораздо важнее эффективная работа программ на различных компьютерах (включая и будущие разработки), чем их максимальная производительность на конкретном устройстве.
Для баз данных с длительным сроком использования существует множество вопросов реализации, связанных с основными целями обеспечения целостности данных и гибкого и надежного доступа к ним. Здесь эти вопросы не рассматриваются. Для таких приложений рассматриваемые методы можно считать базовыми алгоритмами с гарантированно высокой производительностью и отправной точкой при разработке систем.