Для 4-х документов (в каждом из которых одна строка детской считалки) 1. Ехал Грека через реку. 2. Видит Грека в реке рак. 3. Сунул в реку руку Грека. 4. Рак за руку Грека - цап.
Получим следующий индекс (игнорируя верхний/нижний регистр) в -- 2, 3 видит -- 2 Грека -- 1, 2, 3, 4 ехал -- 1 за -- 4 рак -- 2, 4 реке -- 2 реку -- 1, 3 руку -- 3, 4 сунул -- 3 цап -- 4 через -- 1
Теперь для поиска по этим документам нам достаточно просмотреть индекс. Ищем "руку" -- находим документ 3,4 Ищем "сунул руку" -- находим по слову "сунул" документ 3, по "руку" -- 3 и 4. Значит оба слова только в документе 3. Хотя бы одно слово в документах 3, 4. Ищем "кукушка" -- нет в индексе, значит нет ни в одном документе.
Даже на таком объёме данных понятно, что поиск по индексу быстрее, чем поиск по всем документам. Если же представить, что мы хотим искать по всем документам в интернете, то только поиск по индексу способен выдать результат за разумное время. Именно такой подход применяют все известные поисковые машины (Яндекс, Мэйл, Гугл и т.д.)
Для хранения огромных индексов используются бинарные деревья или хэши.