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

Лекция 16: 
Внешний поиск
A
| 
версия для печати
< Лекция 15 || Лекция 16: 1234567 || Лекция 17 >
Ключевые слова: значение, поиск, механизмы, множества, доступ, операции, отношение, производительность, определение, массив, database, равенство, базы данных
Алгоритмы поиска, которые могут выбирать элементы из больших файлов, имеют огромное практическое значение. Поиск — это основная операция для больших наборов данных, которая, безусловно, задействует значительную часть ресурсов, используемых во многих вычислительных средах. С появлением глобальных сетей появилась возможность выбирать практически любую информацию, хоть как-то относящуюся к какой-либо задаче — проблема заключается только в возможности эффективного поиска. В этой главе рассматриваются базовые механизмы, которые могут поддерживать эффективный поиск в настолько больших таблицах символов, насколько можно себе представить.
Подобно алгоритмам из "Специальные методы сортировки" , алгоритмы, рассматриваемые в этой главе, пригодны для множества различных типов аппаратных и программных сред. Поэтому мы будем стремиться к формулировке алгоритмов на более абстрактном уровне, чем программы на языке C++. Однако приведенные далее алгоритмы также непосредственно обобщают знакомые методы поиска, и их удобно записывать в виде С++-программ, полезных во многих ситуациях. Эта глава будет не похожа на "Специальные методы сортировки" : мы тщательно разработаем конкретные реализации, рассмотрим их основные характеристики производительности, а затем обсудим способы применения базовых алгоритмов в реальных ситуациях. Вообще-то название этой главы не совсем верно, поскольку в ней алгоритмы будут представлены в виде С++-программ, взаимозаменяемых с другими реализациями таблиц символов, которые были рассмотрены в лекциях 12—15. В таком виде они вообще не являются " внешними " методами. Тем не менее, они построены в соответствии с простой абстрактной моделью, что превращает их в подробное описание того, как можно строить методы поиска для конкретных внешних устройств.
В основном нас будут интересовать методы поиска в очень больших файлах, хранящихся на внешних устройствах наподобие дисков, которые обеспечивают быстрый доступ к произвольным блокам данных. Для устройств типа ленточных накопителей, где возможен только последовательный доступ (такая модель была рассмотрена в "Специальные методы сортировки" ), поиск вырождается до тривиального (и медленного) метода считывания от начала файла до завершения поиска. С дисковыми устройствами дело обстоит намного лучше: как ни удивительно, методы, которые мы изучим, могут поддерживать операции найти и вставить в таблицах символов, содержащих миллиарды и триллионы элементов, используя всего три-четыре обращения к блокам данных на диске. Такие системные параметры, как размер блока и отношение затрат на доступ к новому блоку к затратам на доступ к элементам внутри блока, влияют на производительность, но методы можно считать относительно не зависящими от значений этих параметров (в тех пределах, которые, скорее всего, будут встречаться на практике). А большинство важных шагов, необходимых для подгонки этих методов под конкретные реальные ситуации, достаточно просты.
Поиск — это фундаментальная операция для дисковых устройств. Как правило, файлы организованы так, чтобы можно было воспользоваться преимуществами конкретного устройства для максимально эффективного доступа к информации. Короче говоря, вполне можно предположить, что устройства, используемые для хранения очень больших объемов информации, построены именно для поддержки простых и эффективных реализаций операции найти. В этой главе мы рассмотрим алгоритмы, которые построены на несколько более высоком уровне абстракции, нежели базовые операции, обеспечиваемые дисковыми устройствами, и которые могут поддерживать операцию вставить и другие динамические операции для таблиц символов. Эти методы дают такие же преимущества по сравнению с прямыми методами поиска, как и деревья бинарного поиска и хеш-таблицы по сравнению с бинарным и последовательным поиском.
Во многих вычислительных средах возможна непосредственная работа в очень большой виртуальной памяти, и мы можем предоставить системе определение эффективных способов обработки запросов данных любой программы. Рассматриваемые алгоритмы также могут служить эффективными решениями задачи реализации таблицы символов в таких средах.
Массив информации, которая должна обрабатываться компьютером, называется базой данных (database). Методам построения, сопровождения и использования баз данных посвящены многочисленные исследования. Большая часть этой работы проводится в области разработки абстрактных моделей и реализаций для поддержки операций найти с более сложным критерием, чем рассмотренное простое " равенство отдельному ключу " . В базе данных поиски могут основываться на критерии частичного соответствия, который может содержать несколько ключей и возвращать большое количество элементов. Методы этого типа будут рассмотрены в частях V и VI. Запросы на поиск общего вида достаточно сложны, поэтому зачастую приходится выполнять последовательный поиск по всей базе данных, проверяя каждый элемент на соответствие критерию. И все же быстрый поиск в огромном файле крошечных фрагментов данных, удовлетворяющих заданному критерию — основная возможность в любой системе управления базами данных, и многие современные базы данных построены на основе описанных в этой главе механизмов.
Правила игры
Как и в "Специальные методы сортировки" , мы будем считать, что последовательный доступ к данным требует значительно меньших затрат, чем не последовательный. Рабочей моделью будет любое запоминающее устройство, которое можно применить для реализации таблицы символов, разбитой на страницы (page) — непрерывные блоки информации, к которым возможен эффективный доступ дисковых устройств. Каждая страница обычно содержит множество элементов, и задача заключается в организации элементов внутри страниц таким образом, чтобы к любому элементу можно было обратиться, прочитав всего нескольких страниц. Мы будем предполагать, что время ввода/вывода, требуемое для считывания страницы, значительно больше времени, требуемого для доступа к конкретным элементам или для выполнения любых других вычислений в пределах этой страницы. Во многих отношениях эта модель слишком упрощена, но она сохраняет характеристики внешних запоминающих устройств, необходимые для рассмотрения фундаментальных методов.