Как сделать большой обратный индекс?

Йоу... вы о чем?

Я говорю про создание поисковика не средствами СУБД.

По кусочкам. Считываешь первые 64Кб прямого индекса. Строишь куски обратного, сбрасываешь на диск. Считываешь следующий кусок прямого индекса. Строить куски обратного, сбрасываешь на диск. И так до конца прямого индекса.

А как просто большой индекс делать:

допустим есть такие поля

int id //ключ

int offset //смещение в файле

void *gt, *lt; int bf; // для организации сбалансированного бинарного дерева

5*4 байта = 20 байт

Хотелось бы чтобы вся эта структура хранилась в памяти для быстрого определения смещения в файле по заданному ключу.

Но как это можно хранить в памяти если id несколько десятков миллионов (хотябы) - 20*50 000 000 = 1Гб

Или в таких ситуациях индекс раниться частично на диске ?

Разбиваете обратный индекс по словам. Для каждого слова свой файл с обратным индексом. Файлы хранятся на диске. Если требуется большая производительность и время чтения с диска критично, то кидаете часто используемые файлы в memcached.

Соответственно, при построении обратного индекса Вы берёте базу документов и создаёте прямой индекс, сбрасывая его постепенно на диск (незачем ему хранится в памяти целиком). Затем для каждого уникального слова по очереди проходитесь по прямому индексу, составляете обратный индекс для этого слова, файл сбрасываете на диск. Таким образом, Вы можете индексировать базы любого размера. Правда количество проходов по прямому индексу получается равно количеству уникальных слов. Но это можно оптимизировать 🙄 Самое узкое место - дисковая подсистема. Это уже лечится только добавлением памяти.

Тут я делаю проход по прямому индексу не для одного уникального слова а для определенного интервала - так меньше проходов требуется.

Тут я делаю не так. Если для каждого слова использовать файл то время доступа к списку вхождений увеличивается из-за дополнительного поиска по файловой системе, не говоря уже про то что миллионы файлов в каталоге это многовато. Я весь обратный индекс храню в одном файле, а списки вхождения для слов нахожу по смещению в нем.

Но это мелочи - проблема не здесь.

Проблема в том что индекс "имен файлов" в оперативной памяти не умещается.

Кстати нету случайно статьи "J. Jobel, A. Moffat. Inverted Files for Text Search Engines, ACM Computing Surveys, Vol. 38, No. 2. (2006)"

скачать не получается ?

Я так же делаю. ;)

Миллионы файлов это многовато. Но если использовать стемку, то их количество сильно уменьшается. Тысяч до ста, а с этим линуксы уже справляются. Можно ещё посмотреть в сторону BerkeleyDb - я пока не тестировал на необходимость беркли, но должно быть лучш. Если Вы храните индекс в одном файле, то там есть маленькая проблема. Добавление/удаление/изменение документа приводит к значительным операциям с этим файлом. Даже если он весь хранится в памяти, то сдвиги сотен мегабайт данных в памяти не сказка. Если кусочек оказывается на диске, то вообще получаются ужасы. С кучей маленьких файлов таких проблем нет.

Самый простой способ в Вашем случае хранить файл на диске, а смещения и часть индекса держать в памяти (кешь).

Интересно, а раззиповка индексных файлов из памяти работает быстрее, чем чтение с диска?

Да, и требует больше памяти.