AOP_Tom3 (1021738), страница 141
Текст из файла (страница 141)
Более того, он способен обрабатывать вычислительные запросы наподобие рассмотренного нами ранее (с использованием понятия "расстояние от Сизтлап), Другой простой путь облегчить получение информации по вторичному ключу состоит в делегировании части работы человеку, который снабжен подходящими печатными указателями. Этот метод зачастую является наиболее разумным и зкономичньгм способом работы (ес и, конечно, старая бумага перерабатывается при издании нового указателя), в особенности потому, что люди обычно отмечают интересные запросы при обеспечении удобного доступа к данным большого об"ьема"'. Приложения, для которых пе подходят приведенные простые схемы, иклизчают в себя очень большие файлы, критичные ко времени ответа на запрос. Такая ситуация, например.
нозникает при одновременной выдаче запросов от множесгна пользователей нли при машинной генерации запросов. Назначение данного раздела — рассмотреть способы обеспечения выборки информации при различных предположениях о структуре файла. К счастью, методы, которые будут обсуждаться, становятся все более и более пригодными для практического применения, а цена вычислений продолжает ~тезке снижаться. Существует немало хороших способов решения поставленных задач., однако (как читатель должен был понять из всех предварительных примечаний) все зти алгоритмы не так хороши, как алгоритм поиска информации по первичному ключу. Изза огромного разнообразия файлов и приложений мы не в состоянии сколь-нибудь полно обсудить все возможности или проанализировать поведение каждого алгоритма в типичных угловиях.
В оставшейся части этого раздела представлены основные предлагаемые подходы, н дело читателя — решать, какая комбинация описанных технологий лучше всего подходит для решения той или иной конкретной задачи. " Пожалуй, автор несколько недооценивает тенденции развития вычислительной техники и технологий бвз денных. Твк, наприиер, опорвтор службы "09", конечно же, держит в гачове сотни телефонов н нв свиые часто звдвввеиые вопросы способен ответить мгновенно. Но кто иешеет испояьзоватьч нвцрииер, кэширование запрпсов, которое не подвержено той же усталости к концу смены? Вычислительная техника и информационные технологии — очень быстро развивающаяся облвсть, и то, что еще вчера квзвлось недостижииыы, сегодня ствновнтся обыденным.
Общая тенденция такова, что думать и принимать решения — эта работа человека, и механически искать информацию — удел коипьютерв. — - Лрцзь ггерее. Инвертированные файлы. Первый важный класс технологий поиска по вторичному ключу основан на идее инвертированных фвььлвв. Данный термин не означает, что файл перевернут вверх ногами; это означает изменение ролей атрибутов записей (вместо списка атрибутов записи приводится список записей с данныль атрибутом). Мы часто сталкиваемся с инвертированными файлами (пусть и под другими названиями) в нашей повседневной жизни. Например, инверсией англо-русского словаря будет словарь русско-английский; инвертированным файлом, соответствующем какай-нибудь книге, является ее предметный или авторский указатель.
Бухгалтеры традиционно используют в работе "двойную бухгалтерикэ" (ь!оьэуэ)е-епггу !эааЫьеершЕ), в которой все сделки фиксируются как в кассовых книгах, так и в счетах клиентов, чтобы иметь возможность быстро получить информацию как по кассе, так и по клиентам. В общем случае инвертированный файл ие самодостаточен и должен использоваться совместно с 'прямым", неинвертированным файлом. В инвертированном файле содержится избыточная информация — — цена, которую приходится платить за ускорение поиска по вторичному ключу. Компоненты инвертированного файла называются инвертированными списками, т.
е. списками всех записей с данным значением некоторого атрибута. Подобно прочим спискам, инвертированные списки могут быть представлены в компьютере самыми разными способами, причем для каждого приложения и данных может быть выбран свой, наиболее подходящий способ представления. Одни вторичные ключи могут иметь только два значения (например, графа анкеты ПОЛ (хотя, как говорят, находятся уникумы, пишущие в этой графе что-то вроде 'паркетный, а в англоязычной анкете на вопрос ЕЕХ отвечающие ггебп!аг"; впрочем, эти замечания больше относятся к вопросу о проверке корректности вводимых данных. При.м, перев,))ь и соответствующие списки могут оказаться весьма длинными; другие же, наподобие НОМЕР ТЕЛЕФОНА, как правило, коротки и с малым количеством дубликатов. Предсдавим, что хранить информацию в телефонной книге нужно так.
чтобы все записи могли быть получены на основе имени, телефонного номера нли адреса абонента. Одно из релэеиий — создать трн различных файла, ориентированных на поиск по своему типу ключа. Вторая идея состоит в комбинировании всех трех файлов, например, в три хеш-таблицы, служаьцие в качестве заголовков списков для метода цепочек. В последней схеме каждая запись файла должна быть элементом трех списков и, таким образом, должна иметь три поля ссылок. Этот так называемый мььвгосписвчяма (тийбйгг) метод проиллюстрирован на рис.
13 раздела 2.2.б и обсуждается нияье. Третья вазможность состоит в комбинировании трех файлов в один суперфайл по аналогии с каталогом библиотеки, в котором карточки авторов, названий книг и их тем располагаются вместе в алфавитном порядке. После рассмотрения формата, использованного в предметном указателе этой книги„возникают новые идеи по представлению инвертированных списков. Для полей вторичного ключа, когда имеется около пяти элементов на одно значение атрибута, можно просто создать короткий последовательный список позиций записей (по аналогии с номерами страниц в указателе книги), следующих за значением ключа.
В случае кластеризации записей может оказаться удобным указание диапазонов позиций (как, например, указание диапазона страниц 559 — 582). Если записи в файле часто перемещаются, то лучше вместо позиций записей использовать первичные ключи — при этом не требуется обновление при перемещении записей. Например, ссылки в Библии всегда даются на главу и стих; во многих книгах ссылки основываются на номерах параграфов, а не страниц. Ни одна из рассмотренных идей не подходит для атрибута с двумя значениями, например ПОЛ.
В таком случае, конечно, достаточно только одного инвертированного списка, так как все не мужчины являются женщинами и наоборот. Если каждое значение соответствует примерно полонине элементов файла, инвертированный список может быть ужасно длинным, но существует возможность получить очень изящное решение на бинарном компьютере с помощью представления в виде битовой строки, в которой каждый бит определяет значение конкретной записи. Так„ битовая строка 01001011101... может означать, что первая запись в файле относится к мужчине, вторая — к женщине, следующие две — к мужчинам и т. д. Таких методов достаточно для обработки простых запросов по определенным значениям атрибутов.
Немного расширив эти методы, можно работать с запросами диапазонов, но вместо хеширования следует использовать схемы поиска, основанные на сравнениях (см. раздел 6.2). Для логических запросов наподобие ТСПЕЦИАЛИЗАЦИЯ = МАТЕМАТИКА) АМО (МЕСТОЖИТЕЛЬСТВО. ШТАТ = ОГАЙО)" необходимо найти пересечение двух инвертированных списков. Это можно сделать несколькими путями; например, если оба списка упорядочены, два прохода (по каждому из них) дадут все общие элементы. С другой стороны, можно выбрать более короткий список и просмотреть каждую из его записей, проверяя, соответствуют ли запросу прочие атрибуты.
Однако этот метод работает только с запросами типа АМР, но не ОВ и не очень хорош для внешних файлов, поскольку требует множества обращений к записям, не удовлетворяющим критериям запроса. Такое же рассмотрение вопроса показывает, что организация в виде множества списков, описанная ранее, неэффективна для логических запросов к внешним файлам в связи с выполнением больпюго количества ненужных обращений. Например, представим, что указатель этой книги организован с помощью множества списков: каждый его элемент указывает только на последнюю страницу, на которой встречается соответствующий термин.
Соответственно для каждого термина на этой странице имеется ссылка на предыдущую страницу с тем же термином и т. д, В таком случае для поиска всего материала, соответствующего запросу наподобие "ТАналиэ алгоритмов) АМР ([Внешняя сортировка) ОЯ [Внешний поиск])",придетсяперелистать очень много страниц. С другой стороны, ту же задачу люжно решить, взгляну.в на две страницы имеющегося указателя и выполнив несложные операции над инвертированными списками для получения минимального подмножества страниц, которое удовлетворяет запросу. Когда инвертированный список представлен в виде битовой строки, выполнение логических комбинаций простых запросов не вызывает трудностей, так как компьютеры раГютают с битовыми строками с относительно высокой скоростью. Для смешанных запросов, одни атрибуты которых представлены в виде последовательных списков записей, а другие — в виде битовых строк, несложно конвертировать последовательные списки в битовые строки, а затем выполнить над ними необходимые логические операции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
