Что такое поисковый индекс?

Поисковые технологии давно и прочно вошли в нашу повседневную жизнь, однако многие до сих пор слабо представляют себе значения некоторых терминов, связанных с ними. Собственно, именно для решения подобных проблем и заведена в "Компьютерных вестях" рубрика FAQ, в рамках которой мы с вами сегодня обратимся к поисковым технологиям.

Поисковый индекс - это некоторая структура данных, позволяющая уменьшить время, необходимое для поиска в каком-то хранилище данных заданной последовательности символов. Говорят, что индекс, в отличие от самого хранилища данных, обеспечивает сублинейное время поиска, в то время как время поиска по хранилищу является линейным. Что это означает? Что для поиска некоторого элемента в хранилище данных по заданному запросу вам потребуется время, пропорциональное количеству элементов в данном хранилище. Индекс, представляя собой структурированный, а не хаотический набор данных, позволяет осуществлять доступ к ним уже быстрее. Чтобы легче понять, о чем именно идёт речь, представьте себе набор визиток с адресами и телефонами, расположенных в совершенно случайном порядке, и телефонный справочник, куда внесены данные из этих визиток, упорядоченные по фамилии их обладателя или по названию организации. Очевидно, что поиск по упорядоченному справочнику займёт куда меньше времени, чем по хаотическому набору визиток. Таким образом, телефонный справочник можно считать некоторым подобием или, наверное, даже прообразом поисковых индексов, используемых сегодня при поиске данных в их неструктурированных хранилищах.

На самом деле, конечно, поисковые индексы устроены несколько сложнее, чем простой телефонный справочник. Большинство структур данных, применяемых в современных поисковых системах, позволяют добиться скорости поиска, пропорциональной логарифму количества элементов в наборе данных, по которому ведётся поиск. При достаточно большом числе элементов в наборе выигрыш в скорости получается очень даже заметным. Впрочем, есть и более быстрые структуры, позволяющие добиваться скорости поиска, практически не зависящей от количества данных.

Одним из наиболее распространённых типов поисковых индексов в наши дни является полнотекстовый индекс, используемый, как несложно догадаться, при полнотекстовом поиске. Полнотекстовый поисковый индекс включает в себя перечень всех слов, встречающихся в проиндексированных документах, и указание мест, в которых данные слова встречаются. Такой подход позволяет быстро искать в данных практически любые фразы.

Вадим СТАНКЕВИЧ,
[email protected]

Версия для печатиВерсия для печати

Номер: 

45 за 2009 год

Рубрика: 

Software
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!