Инвертированный список

Cтраница 1

Инвертированный список содержит все значения вторичного ключа и хранит вместе с каждым его значением соответствующие идентификаторы записи. На рис. 5.5 представлены два инвертированных списка, полученные на основе файла на рис. 5.3. Для каждого вторичного ключа ЗВАНИЕ и КОД-ПРОФЕССИИ представлен свой список. [1]

Представление отношения многие ко многим.| Пример сетевой логической схемы. [2]

Инвертированный список представляет собой таблицу, в левом столбце которой помещены значения данного признака, а в правом-указатели на соответствующие записи. [3]

Отметим, что инвертированный список является частным случаем мультисписка, так что иногда его можно реализовать, используя имеющееся программное обеспечение для работы о мультисписками. [4]

Если для реализации поиска по вторичным ключам используется какой-нибудь инвертированный список, в нем должны содержаться все значения комбинированных пар элементов данных ВИД-ЖИВОТНОГО СТРАНА-ПРОИСХОЖДЕНИЯ, каждая из которых содержит указатель на запись ЗООПАРК. [5]

Во-вторых, целый класс запросов может быть обработан без обращения к самим данным. Если бы инвертированный список на рис. 26.8 содержал номера изделий, а не адреса записей, запрос мог бы быть обработан просмотром только этого списка. При обработке запросов на записи с несколькими ключами поиск можно ускорить, если в каждом элементе индекса завести счетчик числа записей, соответствующих данному ключу, и начинать поиск с ключа, которому соответствует самый короткий инвертированный список. [6]

Обозначение УК представляет собой изображение указателя па jV - ю запись. Таким образом, инвертированный список как бы заранее хранит ответ на запрос Назвать характеристики узлов, имеющих заданную разрядность. В примере разрядность выступает в качестве признака в запросе. Для каждого признака должен быть построен свой инвертированый список. [7]

Существует несколько способов, с помощью которых данная подсхема могла бы выводиться из общей логической схемы. В одном случае можно было бы использовать инвертированный список королей, в другом - дополнительный ( вторичный) индекс, рассматриваемый ниже, в третьем случае - цепочку, в которую связаны в требуемой последовательности записи о королях. Такая цепочка показана на рис. 10.3. В сложной коммерческой базе данных может быть использовано много цепочек, связывающих элементы данных, между которыми существуют различные отношения. Например, в цепочку, изображенную на рис. 10.4, связаны записи о королях и их родственниках, умерших насильственной смертью. [8]

В этом случае для нахождения одной записи ( как части ответа на запрос) достаточно одного обращения к данным. В предположении, что индекс вторичного ключа просматривается легко, инвертированный список обеспечивает наиболее быстрый ответ на запрос в режиме реального времени, поскольку при этом не требуется поиска в цепях. С другой стороны, индекс может стать большим, и его потребуется хранить во внешней памяти, вследствие чего его организация станет самостоятельной проблемой. Эффективность организации файла в виде инвертированного списка ( или мультисписка с короткими цепями) снижается из-за дополнительных расходов памяти на хранение индексов и расходов времени на их просмотр. Способы организации индексов рассмотрены в гл. [9]

Естественно, что списки указателей для каждого значения вторичного ключа ( инвертированные списки) имеют переменную длину, причем такие списки перемешаны: среди большого числа коротких списков изредка встречаются очень длинные, что обусловливает неравномерность их статистического распределения. Например, среди множества немецких слов, согласно известному экспериментальному закону Зин-фа, примерно 50 % всех слов появляется всего один раз ( длина инвертированного списка равна единице), причем это практически не зависит от мощности множества. Слова, появляющиеся два раза, составляют примерно 1 / 4 всех слов; слова, появляющиеся п раз, будут составлять не более 1 / гс2 всех слов. С другой стороны, наибольшая частота появления всех слов, естественно, пропорциональна величине множества, однако слова с высокой частотностью появляются всего лишь один раз на 10 литературных источников. [10]

Представление отношения многие ко многим.| Пример сетевой логической схемы. [11]

Ознакомление с различными моделями данных показало, что поиск необходимой информации требует значительных затрат времени даже для иерархических СУБД, особенно при больших объемах баз данных. Однако если удается выделить совокупность признаков, по которым формируется запрос, то можно предложить способ организации баз данных, значительно сокращающий время поиска затребованной информации. В основе такого способа лежит понятие инвертированного списка. [12]

Проверка функции Rev покажет, что полное число вызовов:: ( включая и те, что получились от вызовов пропорционально квадрату длины инвертируемого списка. Этот дополнительный параметр ( первоначально равный nil) накапливает требуемый инвертированный список при каждом обращении к функции. [13]

Структура обработки данных. [14]

Сеть связи содержит инвертированные списки, необходимые для эффективной обработки запросов пользователей. Каждое такое поле называется дескрипторным, и для него создается и хранится инвертированный список значений, который содержит для каждого уникального значения дескриптора список записей, содержащих данное значение. [15]

Страницы: 1 2