Организация индекса поисковиков на примере Google (по материалам статьи Сергея Брина и Лэрри Пейдж).

Каждый документ в глобальной сети получает свой docID.
Имеется однозначное соотвествие между контрольной суммой url документа и его docID.

Индекс поисковика может состоять из следующих частей: репозитория, индекса документов, словаря, списка вхождений, прямого и обратного индекса.

Репозиторий представляет собой файл, содержащий полный html код для каждого docID.

Индекс документов содержит указатель на код html в файле репозитория, контрольную сумму документа, статус документа и другую статистику. Для документов, которые уже проиндексированы, также записывается их title.

Словарь содержит все различные слова в Вебе, их число равно нескольким миллионам.

В списке вхождений содержится позиция каждого слова в документе, а также ряд характеристик слова. Есть две разновидности вхождений: мнимое (fancy) вхождение и явное (plain).
Мнимое вхождение используется для title, URL, анкоров и мета тегов. Явное во всех остальных случаях. Анкоры представляют собой текст ссылок на наш документ в других документах.
Для явного вхождения указывается позиция слова и начинается ли слово с заглавной буквы, а также относительный размер шрифта. Для мнимого вхождения указывается заглавная буква и позиция. Для вхождения в анкор поле позиции делится и половина используется для указания на документ, в котором стоит ссылка на наш документ.

Мне кажется, что при такой структуре поле позиции явным образом ограничивает как длину индексируемого документа, так длину анкоров и число ссылок на наш документ, содержащее данное слово. В оригинале для документа 12 бит, для анкора по 4 бита на позицию и число ссылок, для просто мнимого вхождения — 8 бит на позицию. В статье говориться, что если слово стоит в документе далее чем на позиции 4096, то используется число 4096. Также говорится, что структура базы будет меняться.

Прямой индекс состоит из записей, включающих для каждого docID, найденные в нем слова со списком вхождений каждого слова в этот документ.

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