Как правильно организовать базу?

Пошел высоконаучный спор :). Леонид, ты немного не понял как они строят индекс, 50% для Б-дерева это теоретическая худшая плотность, реально всегда намного лучше.

Но в общем, я согласен (хотя Илья на самом деле этот тезис не опровергал), что использовать SQL общего назначения для организации инв. файла - все равно что пытаться минивен доделать до болида формулы 1. С другой стороны, я твердо уверен, что инвертированный индекс поверх B-дерева при правильной организации будет не менее эффективен, чем при "классическом" построении.

Максим, ну пусть 25% в среднем. Все равно там 2 * 1.25 = 2.5 раза. Так что цифры у этих ребят не сходятся в нескольких местах. И это только одно несоответствие. Второе заключается в том, что я не верю, что BDB как object store работает хотя бы примерно с той же скоростью, что и плоский файл. Если авторы верят в это, то это надо доказывать в цифрах. У меня этих цифр нет, но я помню, что когда в моем n-граммном индексе я начал хранить инвертированные списки просто на диске, а не в Беркли, у меня все заметно ускорилось.

А Илья, как раз спорит, не верит, что разница в сто раз возможна. И приводит заборные аргументы. А на заборе как раз всякая фигня может быть написана. Даже если забор такими уважаемыми людьми изготовлен.

PS: Несмотря на то, что в статье много всяких несоответствий там есть и очень правильные мысли на тему блочного кодирования. Что с ним действительно получаются неплохие результаты. У меня вот тоже есть очень положительный опыт использования блочного кодирования, только вот все равно до статического файла это малость не дотягивает, а структуры получаются навороченные.

Да и не нужно для интернет-поисковика нестатический файл, это просто я бы сказал глупо. Интернет поисковик может достаточно быстро "засосать" миллиона два докментов, сделать для них за пару часов индекс. Абсолютно копеечный оверхед по сравнению со временем обхода эти двух млн. документов. А несколько статических файлов можно опросить последовательно. Если их 2-3 на машине, то это всего на несколько процентов медленнее, чем один большой статический индекс в 5 млн. урлов.

Не буду вдаватьс в подробности, чтобы никому не было обидно:

1. Я согласен с Ильей, что на практике (особенно на относительно небольших коллекциях) разница в 100 раз крайне редко возникает, на самом деле может разы-порядки.

2. Я согласен с Леонидом, что при относительно большой коллекции и однословному запросу легко можно разогнать инвертированный файл в 100 раз по сравнению с не очень удачной реализацией поверх СУБД.

Насчет плотности Б-дерева - немного подкрутив алгоритм вставки/удаления можно держать ту плотность, какую хочешь, хоть все время 100%, только обновление будет тогда достаточно дорогое.

Ну ладно, насчет разницы в сто раз. Придется немного сдать знания, полученные во время работы в Яндексе. Специально для представителей Яндекса, которые думаю, что это нереально. Например, примерно такая разница наблюдается между многосёрчем в режиме single payload и одной Яндекс-нодой который стоит в Яндексе.

С большим интересом прочел эту тему.

Если использование реляционных баз накладно, то как все-таки организовывается индекс в large-scale поисковиках? Тут прозвучало, в plain-файлах, но суть все-равно не ясна для меня.

Например, имеется некоторая коллекция документов, собранная crawler'ом. Данная коллекция обрабатывается индексатором, выделяются отдельные слова, строится прямой индекс, на этапе построения прямого индекса считается TF. Далее строится обратный индекс, после инвертирования легко посчитать IDF. А вот как теперь хранить обратный индекс без использования СУБД?

Я бы сделал так:

- Б-дерево для хранения словаря (или все-таки хранить словарь в памяти отсортированным и искать бинарным поиском? но как быть с тем, что словарь будет содержать большое число терминов в силу нелитературности веба?). Планируется взять готовую реализацию б-дерева, например, Berkeley DB (или глупая затея?). В поле value будет хранится адрес начала пост-листа.

- Пост-листы хранить в отдельном файле. Если индекс некоординатный, то все просто - хранить номера документов, для сжатия - дельта-кодирование (или другие методы разностного кодирования). А вот как быть с координатным? Хранить все в виде пар (документ, позиция) или в виде подчиненных списков? Здесь есть какие-то "правильные" решения? Кстати, релевантность idf*tf думаю хранить в пост-листе для каждого документа.

З.Ы. Еще хотелось бы узнать, где можно почитать насчет способов построения инвертированного индекса, когда нет возможности сделать это целиком в памяти.

Ну, в общем-то, Eugen, Вы все сами написали. ИФ индекс получается из прямого фактически сортировкой (и последующим сжатием). Сортировка файла, который не влезает в память целиком можно делать так: разбить на N кусков, каждый отсортировать в памяти, записать на диск. Потом нужно сделать то, что кажется называется сортировкой с многопутевым слиянием. То есть идем по всем файлам одновременно, храним в памяти большой отсортированный буфер, как только он заполняется сбрасываем его на диск. Из какого куска считывать очередную запись решаем по правилу: если в текущем буфере сама "маленькая" запись считалась из куска i, то из него и считываем. Вставляем в отсортированный буфер, чтобы он оставался отсортированным.

По поводу правильного кодирования инв. списков с координатами. Все примерно тоже самое, что и без координат. Ситуация, конечно несколько осложняется тем, что если номера документов монотонно растут, то номера позиций растут только для записей из дного документа, пример

(0, 1) (0, 4) (0, 7) (1, 24) (1, 25) (3, 48) (4, 1)

в скобках первое число номер документа, второе - позиция. Можно, например, просто хранить две последовательные дельты: одну для документа, другую для позиции. Разумеется, если начинается новая "серия" позиций внутри документа, то первое значение - абсолютное, не относительное.

Только, надо иметь в виду, что битовые схемы кодирования не очень быстрые. Байтовые и словные и полусловные могут быть гораздо быстрее. С моей реализацией дельты и байтового кодирования разница чуть не в 10 раз была.

У зобеля есть много интересных и полезных статей на тему ИФ

(гляньте на его страничке)

, например,

"Efficient single-pass index construction for text databases"

"Compression of Inverted Indexes For Fast Query Evaluation" (это на тему byte-aligned методов)

itman, спасибо за ответы ;)

Скажите, касательно способа хранения словаря, какие варианты возможны? Или способ б-дерева и есть самый правильный для большого словаря? Как я уже писал выше, я остановился на таком хранении, т.к. подозреваю, что словарь будет очень большим для коллекция в несколько десятков миллионов документов. Но я могу и ошибаться насчет размеров (есть какая-та статистика?). Какие существуют эффективные схемы хранения словаря в памяти?

Кстати, Максим Голубев в одной из тем объяснял необходимость наличия 2х индексов: поисковый (небольшой) и рабочий (полный). При этом критерием включения документа в поисковый индекс является его значимость. Интересно, как можно определить значимость и насколько релевантным будет выдача, сформированная только лишь на основе данных поискового индекса?

Максим, наверное, рассказывал про pruning. Да, действительно, неплохая штука для больших баз данных, только эвристики отбора значимых и незначимых документов должны быть "хорошие". Причем я сразу не готов сказать, какие хорошие, а какие плохие, да и опыта соответствующего нет.

Насчет хранения словаря: по-моему это ИМХО практически без разницы, для коллекции в несколько десятков миллионов документов словарь не будет больше 5-10 млн словоформ (это по опыту). В память влезет. Для слов, про которые известно, как они склоняются и спрягаются, лучше и дуобнее хранить словарь ИМХО в виде trie-дерева.

Где можно почитать про такой способ хранения?

А насчет эвристики разделения на 2 индекса, то тут, наверное, надо ждать комментариев самого Максима Голубева :)

Кстати, Максим недавно как-раз анонсировал, что может несколько десятков млн документов индексировать на одной машине. Видимо, это как раз с помощью прунинга. Но, с прунингом надо поосторожнее :-)

Здесь про trie http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic7/

и вооще погулить лучше, наверное, в гугль-скаляр