|
|
Главная » 2010 » Декабрь » 21 » Просмотр информации и индексы
21:04 Просмотр информации и индексы |
Рассмотрим вторую задачу отбора данных — быстрый поиск в таблицах.
Чтобы система могла достаточно быстро найти нужные записи, таблицу следует упорядочить по значениям ключа поиска (по возрастанию или убыванию). Что это значит?
Рассмотрим простейший случай: таблица упорядочена по возрастанию значения первичного ключа, например, телефонный справочник — по номеру телефона. Пример такого упорядочивания показан на рис. 14.1.
У В главе 2 вы узнали, что упорядочить можно и символьные поля: система точно знает, какая буква (точнее — символ) больше, а какая меньше.
Допустим, вы хотите найти данные об абоненте с номером 357-14-18 в таблице из 526 строк. Система знает: (1) значения ключа (т. е. номера) — уникальны; (2) всего в справочнике 526 записей. Прежде всего система заглядывает в середину таблицы
и читает 263-ю запись. Возможны три случая: (1) номер телефона этой записи равен искомому — запись найдена сразу; (2) номер меньше искомого (например, 214-14-52, — значит, искомый телефон находится в верхней половине таблицы); (3) номер больше искомого (например, 425-17-25, значит, искомый номер находится в нижней половине таблицы). Таким образом, с первого захода система исключает из области поиска сразу половину таблицы. Следующая запись берется из середины нижней или верхней половины (например, 141-я запись). В зависимости от результата сравнения, исключается половина новой группы записей и т. д. Выполнив всего несколько шагов (в нашем случае прочитав максимум 9-10 записей вместо 526), система либо найдет искомый номер, либо удостоверится, что его в таблице нет. Это самый простой метод поиска, и называется он двоичным (или бинарным, от слова «binary» — двоичный).
В ряде случаев значения ключа поиска в таблице не уникальны. Например, в электронном каталоге библиотеки может оказаться несколько книг Чейза, которые мы хотим отыскать (см. п. 14.13.1). В этом случае система сначала найдет первую попавшуюся запись, а затем, сместившись назад, определит положение первой записи в искомой группе и будет читать карточки, пока автор книги — Чейз. Примерно так же действовали и вы, подходя сразу к ящику на букву «Ч» и не обращая внимания на остальные ящики.
Вы уже догадались, что в этом примере каталог библиотеки должен быть упорядочен по алфавиту (а точнее — по фамилии автора). Если мы хотим найти книги по определенной тематике, каталог следует упорядочить по коду этой тематики (можно и по названию темы), и некоторые книги одного автора попадут в разные концы каталога. В этом случае быстрый поиск по фамилии автора станет невозможным.
Списки сотрудников фирмы, например, упорядочивают (сортируют) по разным ключам — по табельному номеру, по зарплате, по году рождения, по образованию, полу и т. д.
Ключ сортировки (ключ поиска) может составляться из не-скольких данных, — например, вы можете упорядочить свою видеотеку по коду рубрики и длительности. В этом случае ключ сортировки можно записать как сумму имен данных RUB+DLIT.
От ключа сортировки зависит не только время поиска по определенному запросу, но и сама возможность ответить на запрос, не перебирая все записи.
Как упорядочивают записи таблиц в информационных системах? Как правило, таблицу не трогают, но создают для нее специальный массив данных, который называется индексом.
Индекс — это набор указателей на строки таблицы, упорядоченный по значениям ключа. Каждый элемент этого набора состоит из двух частей: порядкового номера записи в таблице и значения ключа сортировки.
Например, индекс для таблицы TELEFON (сортировка по возрастанию номеров) может выглядеть так:
272 123-14-25 192 145-28-99 314 151-12-17
Слева указан номер записи в таблице (272, 192, 314, ...), а справа — номер телефона в данной записи (номера следуют по возрастанию). Принцип поиска описан выше: сначала система находит нужный элемент индекса (по номеру телефона), а затем
— по номеру записи — сразу читает искомую запись таблицы. Ес¬
ли вернуться к аналогии с Чейзом, то можно сказать, что ящик с
карточками — это и есть индекс. Мы находим карточку методом
двоичного поиска, читаем на ней «адрес» стеллажа (шкафа) с
книгами и сразу направляемся к нему.
В разных системах индексы формируются по-разному. На-пример, в старых СУБД типа dBASE индекс — это отдельный индексный файл (например, с расширением .IDX), а в совре¬менных системах индекс обычно является частью файла базы данных.
В этой главе мы рассмотрели частный случай индексирования
— применительно к структурированным базам данных. Однако
индексирование широко применяется для поиска информации и
в неструктурированных документах, например, в глобальной се¬
ти Internet. В этом случае в качестве значений ключа индекса
используются так называемые ключевые слова, т. е. фрагменты
текста, каким-то образом отражающие содержание документа.
Вместо номера записи указывается адрес документа, в котором
обнаружено данное ключевое слово (подробнее см. п. 17.7). |
|
Просмотров: 196 |
Добавил: sergei4
| Рейтинг: 0.0/0 |
| Всего комментариев: 1 | |
0   1
diurdyDup (23.12.2011 03:06)
да, что-то на подобии этого
|
|
|
|
|
|
