Эффективный запрос на членство в группе на определенный момент времени

Question

У нас есть такой сценарий:

• Миллионы записей (Запись 1, Запись 2, Запись 3...)
• Разделенный на миллионы маленьких непересекающихся групп (Группа A, Группа B, Группа C...)
• Со временем членство постепенно меняется, т.е. запись может быть переназначена другой группе.

Мы переделываем схему данных, и в одном случае использования, который нам нужно поддержать, дается конкретная запись, находим все другие записи, которые принадлежали к той же группе в данный момент времени. Кроме того, это можно рассматривать как два отдельных запроса, например:

1. К какой группе принадлежал Record 15544 три года назад? (Назовите эту группу g).
2. Какие записи принадлежали Группе g три года назад?

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

1. Найдите строку для Записи 15544 с самой последней отметкой времени до указанной даты. Это говорит нам о группе g.
2. Найти все записи, которые когда- либо принадлежали группе g.
3. Для каждой из этих записей найдите строку с самой последней отметкой времени до указанной даты. Если это указывает на то, что запись в то время находилась в группе g, добавьте ее в набор результатов.

Это не так уж плохо (при условии, что таблица индексируется отдельно как по идентификатору записи, так и по идентификатору группы), и даже может быть оптимальным алгоритмом для только что описанной структуры наивной таблицы, но это стоит поиска индекса для каждой записи, найденной на шаге 2. Есть ли альтернативная структура данных, которая бы отвечала на запрос более эффективно?

---

ETA: это только один из нескольких вариантов использования системы, поэтому мы не хотим ускорять этот запрос за счет замедления запросов о текущих группировках, а также не хотим платить огромную цену за использование пространства и т. Д.,

Answer 1

Как насчет создания двух таблиц:

1. (recordID, time-> groupID) - ключ является recordID, время - отсортировано по recordID и вторично по времени (пусть это будет map1)
2. (groupID, time-> List) - ключ является groupID, время - отсортировано по recordID и вторично по времени (пусть это будет map2)

При каждом изменении записи:

• Получить текущий идентификатор группы записи, которую вы изменяете
• задавать t <- current time
• создать новую запись для map1 для старой группы: (oldGroupID,t,list') - where list '- это тот же список, но без записи, которую вы только что переместили оттуда.
• Добавить новую запись в map1 для новой группы: (newGroupId,t,list'') - где list'' - старый список для новой группы, с добавленной в него измененной записью.
• Добавить новую запись (recordId, t, newGroupId) на map1

Во время запроса:

• Вам нужно найти запись в map2 это "ближайший" и меньше, чем(recordId,desired_time) - это классика O(logN) работа в отсортированной структуре данных.
• Это даст вам группу g элемент принадлежал в нужное время.
• Теперь посмотрите на map1 аналогично для записи с ключом ближе всего, но меньше, чем (g,desired_time), Значение - это список всех записей, которые находятся в группе в нужное время.

Это требует немного больше места (хотя с постоянным коэффициентом...), но каждая операция O(logN) - где N количество изменений записи.

Эффективным отсортированным DS для записей, которые в основном хранятся на диске, является дерево B +, которое также реализуется многими реляционными реализациями DS.