Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 52
Текст из файла (страница 52)
С другой стороны, можно выбрать более короткий список и просмотреть каждую из его записей, проверяя, соответствуют ли запросу прочие атрибуты. Однако этот метод работает только с запросами типа АИО. но не ОИ и не очень хорош для внешних файлов, поскольку требует множества обращений к записям, не удовлетворяющим критериям запроса. Такое же рассмотрение вопроса показывает, что организация в виде множества списков, описанная ранее, неэффективна для логических запросов к внешнил~ файлам в связи с выполнением болыпого количества ненужных обращений.
Например, представим, что указатель этой книги организован с помощью множества списков: каждый его элемент указывает только на последнюю страницу, на которой встречается соответствующий термин. Ссютветственно для каждого термина на этой странице имеется ссылка на предыдущую страницу с тем же термином н т. д. В таком случае для поиска всего материала, соответствующего запросу наподобие "~Анализ алгоритмов) АИО (ГЗиеиняя сортировка) ОИ Юнеиний поиск))'~придется перелистать очень много страниц.
С другой стороны, ту же задачу можно реи(нть, взглянув на две страницы имеющегося указателя и выполнив несложные операции над инвертированными списками для получения минималыюго подмножества страниц, которое удовлетворяет запросу. Когда инвертированный список представлен в виде битовой строки, выполнение логических комбинаций простых запросов не вызывает трудностей. так как компьютеры работают с битовыми строками с относительно высокой скоростью. Для смешанных запросов, одни атрибуты которых представлены в виде последовательных списков записей, а другие -- в виде битовых строк, несложно конвертировать последовательные списки в битовые строки, а затем выполнить нэд ними необходимые логические операции.
Здесь может оказаться небесполезным следующий пример. Предположим, что имеется 1000000 записей по 40 символов и файл хранится иа дисках И1ХТЕС (см. раздел 5.4.9). Файл сам па себе заполняет два дисковых модуля, а инвертированные списки, вероятно, займут несколько болыпий объем. На каждой дорожке содержится 5 000 символов = 30 000 бнт, так что инвертированный список для определенного атрибута займет не более 34 дорожек (это максимальное число дорожек соответствует самому короткому возможному представлению в виде битовой строки). Предположим, чта имеется весьма сложный запрос, представляющий логическую комбинацию из десяти инвертированных списков. В худшем случае придется считать 340 дорожек информации из инвертированного файла с общим временем чтения 340 х 25пзэ = 8.5э.
Среднее время задержки будет равно приблизительно половине времени чтения, но при аккуратном программировании ега можно исключить. Сохраняя первые дорожки каждого бнтовога списка на одном цилиндре, вторые — на следующем и т. д., можно практически исключить время поиска дорожки на диске, и в результате ожидать, что максимальное время поиска па диску составит около 34 х 26 шя св 0.9 в (или в два раза больше при использовании двух независимых дисков). Наконец, если запросу удовлетворяют 7 записей, потребуется около о х (60 шэ (поиск па диску) + 12.5шя (скрытая задержка) + 0.2 шз (чтение)) дополнительного времени, чтобы получить их для последующей обработки. Таким образом, грубая оптимистическая оценка общего ожидаемога времени для обработки этого довольно сложного запроса равна (10 + .0730)э. Полученное число может быть сопоставлено с примерна 210 э, требующимися для чтения всего файла с максимальной скоростью при тех же предположениях без использования инвертированных спискове.
Этот пример показывает, что оптимизация па пространству тесно связана с оптимизацией па времени при работе с дисками; время обработки инвертированных списков примерно соответствует времени, необходимому ддя их поиска на диске и чтения. В приведенном обсуждении в большей нли меньшей степени полагалось, что файл не растет и не уменьшается во время запроса к нему. Однако что делать, если требуются частые обновления? Ва многих приложениях для этого достаточна просто собрать в один пакет некоторое количество запросов на обновление, которые выполняются в момент, когда нет обрабатываемых запросов.
Если же, напротив, обновление данных имеет наивысший приоритет, привлекательным представляется использование В-деревьев (см. раздел 6,2.4). Весь набор инвертированных списков может быть представлен в виде одного гигантского В-дерева са специальным соглашением а том, что узлы ветвей содержат значения ключей, а, листья — как ключи, так и указатели на записи. Кроме тога, обновленные версии файла могут обрабатываться и другими методамн, которые будут рассмотрены ниже. Геометряческие данные.
Огромное количество приложений работает с точками, линиями и прочими фигурами в двух или более измерениях. Одним из первых подходов к запросам, ориентированным на расстояния, бьща епочтовое дерево" * Просьба смотреть ня оягнесигяеяьнме знвчення приводимых автором величин, абстрагируясь от ебселюягнмя знвчеинй, которые ие соответствуют современной технике. Так, без спецяедьной оптин язяпин в мвогозвдвчной ОБА с жестким диском ! ПЕ при одновременном выпачненин других операций дяя чтения 1000000 записей размером по 40 байт ие компьютере переводчика этого раздела потребоввдось 2.2 е.
— Прим. персе. (ревью(Все Атее), предложенное в 1972 году Брюсом Мак-Наттом (Вгпсе Мс%йь). Предположим, например, что необходимо ответить на запрос "Какой город является ближайшим к точке х7", имея заданную точку х. Каждый узел дерева Мак-Натта соответствует городу у и "тестовому радиусу" г; левое поддерево узла соответствует всем городам з, последовательно введенным в эту часть дерева, таким, что расстояние от у до - < г + 6, а правое поддерево точно такое же для расстояний > г — Ю. Здесь 5 — данный допуск; города, находящиеся на расстоянии от г — 6 до г+ 6 от у, должны входить в оба полдерева, Поиск в таком дереве позволяет определить все города на расстоянии не более 6 от заданной точки (рис.
45). Рис. 45. Верхние уровни примера "почтового дерева". Для поиска всех городов вблизи данной точки х начинаем поиск от корня, Если я находится в пределах 1800 миль от УуасВегаса, идем по дереву влево, в противном случае идем вправо. Повторяем этот процесс до тех пор, пока не будет достигнут конечный узел. Метод построения дерева гарантирует, что все деревья в пределах 20 миль от я встретятся в процессе поиска, На основе этой идеи Мак-Натт и Эдвард Принг (Е~Ьчагс( Рг1пк) провели несколько экспериментов с использованием в качестве примера базы данных, содержащей 231 наиболее населенный город континентальной части США в случайном порядке. 'Тестовый радиус уменьшался регулярно, а именно заменой т на 0.67г при перемещении влево, и на 0.57г — прн перемещении впршю, за псключением случая, когда последовательно выбирались две правые ветви (при этом г оставался неизменным).
В итоге было получено дерево нз 610 узлов при 6 = 20 миль и из 1600 узлов при 6 = 35 миль. Верхние уровни меньшего нз получившихся деревьев показаны на рис. 45. (В оставшейся части дерева Орландо (штат Флорида) появляется ниже Джексонвилля и Майями. Некоторые города встречаются очень часто. Так, Броктон (штат Массачусетс) встречается в 17 узлах!) Быстрый рост файла при увеличении б указывает на ограниченность применения почтовых деревьев, Пожалуй, лучше работать непосредственно с координатамп каждой точки, рассматривая координаты как атрибуты илв вторичные ключи; в таком случае можно создать логический запрос, основанный на диапазонах значений ключей. Например, предположим, что записи в файле относятся к городам Северной Америки и что запрос выполняет поиск всех городов, для которых справедливо (21.49' < ШИРОТА < 37.41') АИО (70.34' < ДОЛГОТА < 75.72').
Посмотрев на карту, можно увидеть, что множество городов удовлетворяет диапазону параметра ШИРОТА. Также найдется немало городов, имеющих соответствующий параметр ДОЛГОТА, но сложно найти город, отвечающий обоим условиям одновре. менно. Один из подходов к подобным оргдогомадьньсм запросам диапазонов состоит в разбиении множества всех возможных значений ШИРОТА и ДОЛГОТА таким образом, чтобы на каждый атрибут приходилось небольшое число классов (например, усечением значений до ближайшего меньшего значения, кратного 5'), н построении инвертированного списка по всем комбинированным классам (ШИРОТА, ДОЛГОТА). Это чем-то напоминает карты, состоящие из страниц для каждого локального региона.
Используя 5-градусные интервалы, рассматриваемый здесь запрос будет обращатьс» к восьми страницам, а именно — (20',?О'), (25',70'), ..., (35',75'). Запрос диапазона в данном случае должен обработать каждую страницу, либо переходя к более мелким частям страницы, либо обращаясь непосредственно к записям— в зависимости от количества записей, соответствующих этой странице. По сути, получается структура дерева с двумерным ветвлением в каждом внутреннем узле, Существенное усовершенствование этого подхода, называемое ссепочммм файдолс, было разработано Ю.
Ннвергельтом (1. Н(еуегйе!ь), Г, Гвнтербергером (Н. Н1птегЬегйег) и К. К. Севчик (К. С. Бетой) [АСМ 2?апй. ВаГабаяе Луйсеще 9 (1984), 38 — 71). Если каждая точка х имеет (с координат (хм..., хе), они разделяют значения й-й координаты на диапазоны — оо = Лсо ь. ап ь. ь. амь = +со н положение х определяется индексами Цы...,?е), такими, что 0<,уе ~ум ЛО,, С я~ С йцу,ч.1! для 1 С 1 С ?с. (2) Совокупности точек, имеющих данное значение (~ы...,уе), называются ячейками. Записи для точек в одной и той же ячейке хранятся в одном блоке внешней памяти. Блоки могут также содержать точки нз нескольких смежных ячеек, обеспечивая тем самым соответствие каждого блока !с-мерному прямоугольному региону, или есуперячейке'! Возможно использование различных стратегий для обновления значений границ сетки дб и для разделения и комбинирования блоков (см., например, К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
