ВУЗ:
Составители:
125
Рис. 9.4. Дерево упорядоченной последовательности
Структура сбалансированного двоичного дерева является наиболее гиб-
кой структурой данных. Она обеспечивает наилучшие возможности для ведения
массива (неограниченный рост, быстрая вставка и удаление записей), самые
быстрые сортировку и поиск.
Особенности многоаспектного поиска. Рассмотренные выше методы
поиска обеспечивают одноаспектный поиск по совпадению или по интервалу.
Аргументом
поиска является ключ записи, однозначно ее определяющий, –
первичный ключ.
При многоаспектном поиске аргумент поиска содержит несколько ат-
рибутов записи, не являющихся первичными ключами. Например, в массиве
записей, содержащих сведения обо всех студентах, обучающихся в данном вузе,
могут понадобиться сведения обо всех юношах, обучающихся по определенной
специальности и занимающихся спортом.
В общем
случае при многоаспектном поиске требуется найти все запи-
си с определенными значениями указанных в запросе атрибутов. При реализа-
ции таких запросов часто решающее значение имеет структура хранения дан-
ных в памяти ЭВМ.
Если данные хранятся в виде последовательного списка, то для много-
аспектного поиска можно использовать последовательный метод поиска. Осу-
ществляя последовательный просмотр, в массиве отыскивают все записи,
имеющие заданные значения указанных в запросе атрибутов. Если один из этих
атрибутов ключевой, то на первом этапе можно применить ускоренный поиск
по ключу. Затем в выделенном подмассиве записей следует вновь провести по-
следовательный поиск, в результате которого выявятся записи, характеризую-
щиеся заданными значениями
всех остальных атрибутов. Такой поиск, очевид-
но, займет много времени, поскольку является последовательным. Кроме того, в
процессе поиска для хранения промежуточных подмассивов потребуется до-
полнительная память.
Большой класс методов многоаспектного поиска основан на принципе
использования инверсных массивов. Для данных, хранящихся во внешней памя-
ти, в этом случае используется термин «инвертированные
файлы».
Различие между основным и инверсным массивами состоит в следую-
щем. Каждая запись основного массива соответствует определенному объекту и
содержит перечень признаков, характеризующих этот объект. Каждая запись
инверсного массива соответствует определенному признаку и содержит пере-
чень объектов, характеризующихся этим признаком. Например, телефонный
справочник можно инвертировать так, что каждая запись в нем
будет содержать
название улицы и перечень абонентов АТС, проживающих на этой улице. В
этом случае поиск будет проводиться по адресу абонента.
Страницы
- « первая
- ‹ предыдущая
- …
- 123
- 124
- 125
- 126
- 127
- …
- следующая ›
- последняя »
