AOP_Tom3 (1021738), страница 142
Текст из файла (страница 142)
Здесь может оказаться небесполезным следующий пример. Предположим, что имеется 1000000 записей па 40 символов и файл хранится на дисках М1ХТЕС (см. раздел 5.4.9). Файл сам по себе заполняет два дисковых модуля, а инвертированные списки, вероятно, займут несколько больший объем. На каждой дорожке содержится 5000 символов = 30000 бит, так что инвертированный список для определенного атрибута займет не более 34 дорожек (это максимальное числа дорожек соответствует самому короткому возможному представлению в виде битовой строки). Предположим, что имеется весьма сложный запрос, представляющий логическую комбинацию из десяти инвертированных списков. В худшем случае придется считать 340 дорожек информации из инвертированного файла с общим временем чтения 340 х 25шз = 8.5з.
Среднее время задержки будет равно пряблизительгю половине времени чтения, но при аккуратном программировании его можно исключить. Сохраняя первьге дорожки каждого битового списка иа одном цилиндре, вторые — на следующем и т. д., можно практически исключить время поиска дорожки на диске, и в результате ожидать, что максимальное время поиска по диску составит окала 34 х 26 шз яв 0.9з (или в два раза больше при использовании двух независимых дисков). Наконец, если запросу удовлетворяют о записей, потребуется около о х (60гпз (паиск по диску) + 12.5 гпз (скрытвя задержка) + 0.2 шз (чтение)) дополнительного времени, чтобы получить их для последующей обработки. Таким образом, грубая оптимистическая оценка общего ожидаемого времени для обработки этого довольно сложнога запроса равна (10+ .0730)з.
Полученное число может быть сопоставлено с примерно 210 з, требующимися для чтения всего файла с максимальной скоростью при тех же предположениях без использования инвертированных списков*. Этот пример показывает, что оптимизация по пространству тесно связана с оптимизацией по времени при работе с дисками; время обрабютки инвертированных списков примерно соответствует времени, необходимому для их поиска на диске и чтения. В приведенном обсуждении в болыпей или меньшей степени полагалось, что файл не растет и не уменыпается во время запроса к нему. Однако чта дечатзч если требуются частые обновления? Во многих приложениях для этого достаточна просто собрать в один пакет некоторое количество запрасан на обновление, которые выполняются в момент, когда нет обрабатынаемых запросов.
Если же, напротив, обновление данных имеет наивысший приоритет, привлекательным представляется использование В-деревьев (см. раздел 6.2.4). Весь набор инвертированных списков может быть представлен в виде одного гигантского В-дерева со специальным соглашением о том, что узлы ветвей содержат значения ключей, а листья — как ключи, так н указатели на записи. Кроме того, обновленные версии файла могут обрабатываться и другими методами, которые будут рассмотрены ниже. Геометрические данные. Огромное количество приложений работает с точками, линиями и прочими фигурами в двух или более измерениях. Одним из первых подходов к запросам, ориентированным на расстояния, было "почтовое дерево" ь Просьбе смотреть нз относительные значения прнводнмых автором велнчнн, абстрагируясь от ебсолюпгнмх значений, которые не соответствуют современной технике.
Твк, без специальной оптимизации в многозадачной ОБ/2 с жестким диском 1ПЕ прн одновременном выполнении других операция для чтения 1 000 000 записей рвзмером по 40 бвят нв компьютере переводчика этого раздела потребовалось 2.3 з. — При.и. нерее. (ровс-ойгсе сгее), предложенное в 1972 году Брюсом Мак-Наттом (Вьчюе МсХпГС). Предположим, например, что необходимо ответить на запрос "Какой город янляется ближайшим к точке х?", имея заданную точку х. Каждый узел дерева Мак-Натта соответствует городу у и "тестовому радиусу" т; левое поддерево узла соответствует всем городам х, последовательно введенным в эту часть дерева, таким, что расстоиние ат у до х < т + б, а правое поддерево точна такое же для расстояний > т — б.
Здесь б — данный допуск; города, находящиеся на расстоянии от т — б до т+ б от у, должны входить в обп поддерева. Поиск в таком дереве позволяет определить все города на расстоянии не более б от заданной точки (рис. 45). Рис. 45. Верхние уровни примера "почтового дерева".
Для поиска всех городов вблизи данной точки х начинаем поиск от корня. Если х находится в пределах 1 800 миль от ЛасВегаса, идем по дереву влево, в противном случае идем вправо, Повторяем этот процесс до тех пор, пока не будет достигнут конечный узел. Метод построения дерева гарантирует, что все деревья в пределах 20 миль от х встретятся в процессе поиска. На основе этой «деи Мак-Натт и Эдвард Принг (Ебшагб Рг1пк) провели несколько экспериментов с использованием в качестве примера базы данных, содержащей 231 наиболее населенный город континентальной части США в случайном порядке. Тестовый радиус уменьшался регулярно, а именно заменой т на 0.67т при перемещении влево, и на О.о7т — при перемещении вправо, за исключением случая, когда последовательно выбирались две правые ветви (при этом т оставался неизменным).
В итоге было получено дерево из 610 узлов при б = 20 миль и из 1600 узлов при б = 35 миль. Верхние уровни меньшего из получившихся деревьев показаны на рис. 45. (В оставшейся части дерева Орландо (штат Флорида) появляется ниже Джексонвилля и Майями. Некоторые города встречаются очень часто. Так, Брактон (штат Массачусетс) встречается в 17 узлах!) Быстрый рост файла при увеличении б указывает на ограниченность применения почтовых деревьев. Пожалуй, лучше работать непосредственно с координатами каждой точки, рассматривая координаты как атрибуты или вторичные ключи; в таком случае можно создать логический запрос, основанный на диапазонах значений ключей. Например, предположим, что записи в файле относятся к городам Северной Америки и что запрос выполняет поиск нсех городов„для которых справедливо (21.49' < ШИРОТА < 37.41') АИО (70.34' < ДОЛГОТА < 75.72 ). Посмотрев на карту, можно увидеть, что множество городов удовлетворяет диапазону параметра ШИРОТА.
Также найдется немало городов, имеющих соответствующий паралсетр ДОЛГОТА, но сложно найти город, отвечающий обоим условиям одновременно. Один из подходов к подобным ортогоиальиы.м запросам диапазонов состоит в разбиении множества всех возможных значений ШИРОТА и ДОЛГОТА таким образом, чтобы на каждый атрибут приходилось небольшое число классов (например, усечением значений до ближайшего меньшего значения, кратного 5'), и построении инвертированного списка по всем комбинированным классам (ШИРОТА, ДОЛГОТА).
Это чем-то напоминает карты, состоящие из страниц длн каждого локального региона. Используя 5-градусные интервалы, рассматриваемый здесь запрос будет обращаться к восьми страницам, а именно — (20',70'), (25',70'), ..., (35',75'). Запрос диапазона в данном случае должен обработать каждую страницу, либо переходя к более мелким частям страницы, либо обращаясь непосредственно к записям— в зависимости от количества записей, соответствующих этой странице. По сути, получается структура дерева с двумерным ветвлением в каждом внутреннем узле. Существенное усовершенствование этого подхода„нвзываегиое сеточным файлом, было разработано Ю.
Нивергельтом (Л. ЛНеуегбе!ь), Г. Гинтербергером (Н. НшсегЬегйег) и К. К. Севчик (К. С. Беис01) [АСМ Тгалз. Вагабаче Вувбетз 9 (1984), 38 — 71). Если каждая точка х имеет гс координат (хы..., ха), они разделяют значения з-й координаты на диапазоны — оо = д'о < яп « ' ' диь = +оо и положение х определяется индексами (уы...,уа), такими, что 0<7;<г;, дО, <х,<дНеП д 1<1<А. (г) Совокупности точек, имеющих данное значение (уы...,уа), называются ячейками. Записи для точек и одной и той же ячейке хранятся в одном блоке внешней памяти. Блоки могут также содержать точки из нескольких смежных ячеек, обеспечивая тем самым соответствие каждого блока (с-мерному прямоугольному региону, нли Ясуперячейке".
Возможно использование различных стратегий для обновления значений границ сетки до и для разделения и комбинирования блоков (смч например, К. Н!ппсЬз, ВУТ 25 (1985), 569 — 592). Характеристики сеточных файлов со случайными данными проанализированы в работах М. Небгйег, В1Т 25 (1985), 335 — 357; Р. Р1аЗо!ег апс1 С. РнесЬ,,7АСМ 33 (1986), 371 — 407, З4.2. При простом способе работы с ортогональными запросами диапазонов, предложенном Дж.
Л. Беитлн (Л. Ь. Вегп!еу) и Р. А. Финкелезг (В.. А. Рш1се1), используются структуры, которые называются четрсвьямие (диасмгеез) (Асга 1пГогтабса 4 (1974), 1-9]. В двумерном случае каждый узел такого дерева представляет прямоугольник и содержит одну из точек в этом прямоугольнике. Имеется четыре поддерева, соответствующих четырем квадрантам исходного прямоугольника относительно координат данной точки. Аналогично для трех измерений существует восьмипутевое ветвление, и деревья соответственно называются восьмиревьями (осбгеез). й-мерные четревья, естественно, порождаются ветвлением по 2а путям.
Математический анализ случайных четревьев является весьма сложным., однако в 1988 году независимо двумя группами исследователей (Ь. Веугоуе апс( Ь. Ьа(огевц * Переводя такие термины, поневоле чувствуешь себя Алисой в Зазеркалье, слушающей объяснение Шалтая-Болтая о словах, похожих на бумажник: открываешь его, а таы два отделении. Надеюсь, читатель простит не слишком научно звучащие, зато оживляющие сухой текст термины. — Прим.
персе. При использовании случайных, а не идеально сбалансированных А-фдеревьев среднее время работы для частичных совпадений по 1 определенным координатам несколько увеличивается до 0(Х' '1ь+У!'1~1). Функция Г неявно определяется уравнением ( Г(х) + 3 — х)* (Г(х) + 2 — х)~ * = 2 (5) и весьма мала: имеем 0 ч Г(х) < 0.06329 33881 23738 85718 14011 2779733590 58170 —.
(6) При этом максимум достигается при х, близком к 0.585371 (см. Р. Р)а1о!ес апг! С. Риес10 .1АСМ ЗЗ (1986), 371-407, з3]. Рост популярности геометрических алгоритмов (и нх эстетическая привлекательность) вызвали ускоренное развитие технологий решения многомерных задач и смежных вопросов разных видов. Фактически в 70-х годах появилось новое направление в математике н информатике, именуемое вичислительной геометрией. Отличным справочным пособием, в котором подробно излагается текущее состояние дел в этой отрасли знаний, является Наш!Боек оГ 01эсгесе апН Согори!айопа1 Сеоьпеггу под редакцией 3.
Е. Сообшав апб 3. О'Ноях!се (Воса На!оп, Р)огЫа: СНС Ргеэв, 1997). Всесторонний обзор структур данных и алгоритмов для важных случаев днухи трехмерных объектов можно найти в двух взаимодополняющих книгах Ханана Самета (Напал Бате!) ТИе Оеэ!Яп апс1 Апа)уэ1э оГ Браг!а! Вага Бсгпс!нгег и Аррйсагюпг оГ $раг1а! Гуаса о!гиссигеэ (Абйяоп-Жеэ!еу, 1990). Самет обратил внимание на то, что исходные четревья Бентли и Финкеля более корректно было бы именовать "точечными четревьями" (рош! Япаг1сгееэ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
