Имеем 4 списка значений по 100 гб. Как получить значения входящие во все списки?

Question

[ruplace]

День добрый.

Возник вопрос касательно инвертированного индекса, задействованного в работе поисковых систем.

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

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

Как базы поисковых систем справляются с такой нетривиальный задачей? Кто-нибудь знает тему настолько хорошо чтобы иметь возможность объяснить ее научно-популярно? Грубо и в общих чертах. Ссылкам буду тоже рад.

Answer 1

[Rsa97]

А в чём проблема? Если индексы уже построены (читай - списки отсортированы), то просто двигаясь параллельно по всем четырём спискам можно находить все пересечения списков за один проход.
Пусть у нас есть четыре отсортированных по возрастанию списка.
0. Добавим в конец каждого списка один и тот же элемент, заведомо больший любого элемента из любого списка.
1. Поставить указатели на первые элементы списков.
2. Найти минимальное значение из текущих элементов, обозначим его через Min.
3. Посчитать количество текущих элементов, равных Min. Если оно равно 4 - вывести элемент.
4. Для каждого списка, пока значение текущего элемента равно Min, передвинуть указатель на следующий элемент.
5. Если ни один указатель не дошёл до конца списка, то перейти к пункту 2.

Для поиска пересечений трёх из четырёх или двух из четырёх списков - подкорректировать пункты 3 и 5.

Comments

[ruplace]

Я просто думал, что существуют более красивые и быстрые решения (учитывая срок развития через который прошли электронные бд и пс).

Можно еще один уточняющий вопрос? Жизнь поисковых баз это постоянные сортировки и частичные дубликации данных? Спасибо

[Rsa97]

ruplace: Зачем постоянные сортировки? Список обратного индекса сам индексируется средствами БД, так что он уже отсортирован для выборки. Да и сама выборка элементов списка может идти через JOIN'ы, то есть алгоритмами СУБД. Сортироваться при этом будет только результирующая таблица, но она в любом случае будет сортироваться после ранжирования.