Предположим, у меня есть обратно связанный список, то есть структура данных, в которой каждый узел указывает на своего предшественника:
A <- B <- C <- D
Это шаблон, который вы можете найти в Git, например, где каждый коммит содержитИдентификатор своего предшественника.
Теперь давайте предположим следующий сценарий: каждый раз, когда новый узел добавляется в список, другой компонент получает уведомление.К сожалению, время от времени некоторые из этих уведомлений теряются, поэтому нет гарантии, что все уведомления будут доставлены.Для приведенного выше списка, уведомления должны быть:
A
B
C
D
Но, как пример, получено следующее:
A
D
Теперь я хотел бы обнаружить «дыры» вполучающий компонент.То есть, когда D получен, компонент может обнаружить, что чего-то не хватает, поскольку предшественник D также не был получен.Поэтому он запрашивает у отправляющего компонента ту часть, которая отсутствует.Можно сказать следующее: последний полученный файл A, а самый новый полученный D.
Итак, теперь компонент, управляющий исходным списком, должен эффективно выяснить, чтоотсутствует подсписок B <- C.
И вот, наконец, мой вопрос вступает в игру: как это сделать эффективно?Я имею в виду, что самый простой подход - двигаться назад от D, пока мы не достигнем A.Все, что между ними, очевидно, отсутствует.
Предполагается, что каждый узел хранится как отдельная запись в таблице в системе реляционной базы данных: каков наиболее эффективный способ выяснить этот подсписок?Очевидно, я мог запускать SELECT в цикле снова и снова и снова.Есть ли лучший способ для этого?
Макет таблицы Nodes в основном выглядит следующим образом:
ID | PredecessorID | Data
-------------------------------------|--------------------------------------|-----------------
43b1e103-d8c6-40f9-b031-e5d9ef18a739 | null | ...
55f6951b-5ed3-46c8-9ad5-64e496cb521a | 43b1e103-d8c6-40f9-b031-e5d9ef18a739 | ...
3eaa0889-31a6-449d-a499-e4beb9e4cad1 | 55f6951b-5ed3-46c8-9ad5-64e496cb521a | ...
Это означает, что идентификаторы не являются числовыми, вы не можетепросто выберите диапазон пропущенных узлов.
PS: Единственное известное мне решение - введение поля position , которое на самом деле равно увеличивающемуся количественному числу.ID, но я явно не хочу иметь что-то подобное, так как тогда мне нужна единственная точка отказа, которая последовательно выдает следующий ID, и я бы хотел этого избежать.