Akina: Всё прочитал, ничего не понял.
Если исходить из полной постановки задачи, включая весьма странное требование "а подать сюда дерево", то первый вывод, который вылезает - а не будет тут дерева как такового.
Есть у нас автомобиль А в состоянии Ах. Мы что-то с ним делаем (любая операция корректировки), получаем автомобиль А в состоянии Ау, а родителем состояния Ау является состояние Ах. Делаем вторую операцию, получаем состояние Аz. Так вот - родителем состояния Az может быть только и исключительно состояние Ау, и ни при каких обстоятельствах родителем не будет Ах. Так что мы получаем не дерево, а его частный случай, прозываемый односвязным списком.
Уже проще.
Далее - условие задачи, озвученное в инит-посте, однозначно говорит о том, что этот односвязный список должен храниться в БД. Что опять же практически однозначно порождает структуру
- Уникальный идентификатор автомобиля (разумнее использовать естественный уникальный признак, а именно VIN);
- Уникальный автоинкрементный номер состояния (или штамп времени перехода в это состояние);
- Прочие атрибуты, в том числе FK.
Забавно, что постановка задачи такова, что исключает удаление записей, что в свою очередь делает ненужным наличие ссылки на запись-родитель, достаточно последовательной нумерации.
Комбинация первых двух полей образует естественный ПК. Для ускорения описанных операций используются соответствующие индексы. А вот когда заходит речь о том, как именно оптимизировать конкретную отдельную операцию - необходимо сначала определиться с конкретной СУБД и конкретной структурой, а потом мыслить об оптимизации.
Формально это, конечно, дерево, хотя реально - лес, где совокупность записей для отдельного автомобиля образует самостоятельное и независимое дерево.
Не, можно пробовать любую истинно "древесную" структуру - но смысл-то? то, что эффективно работает с деревом, скорее всего не будет самым эффективным в случае односвязного списка. Я уж не говорю о том, что некоторые структуры не работают с лесом, им одно дерево подавай (хотя на уровне СУБД это пофиг, просто ещё одно условие в запросе).
А дальше практически по всей теме идёт мысль, что никакой БД нет и в помине, что все данные загружены в память приложения, и там оно с этими данными и работает. Поневоле
хочется изречь нечто типа "Батюшка, вы уж определитесь, ...".
https://forum.sources.ru/index.php?showtopic=419028&view=findpost&p=3833117
