FasterHarder: Все, проблема решена! 1800+ строк кода, функций стало еще больше + они стали сложнее местами гораздо (где-то 450 строк взял из 1ой версии).
Все реализовал на чистейшей динамике. Все статические строковые массивы (марка и пр.) заменил на char * с выделением дин. памяти. Кол-во указателей какое-то дичайшее получилось.

Сделал тесты на 10 авто, 100, 1000, 10 000, 100 000, 1 000 000, 5 000 000, 25 000 000 (файлик текстовый весит 2.5+ Гигов). Во всех случаях поиск МГНОВЕННЫЙ. Как я понимаю, замеряем время до нахождения первого блока искомых данных (а потом они идут все последовательно, благодаря списку ссылок из узла дерева). От 5млн. комп начинает терять сознание, на 25млн. завис наглушняк (оперативку забрал всю теор.возможную) - ребут пришлось делать.

Самая тяжелая операция: загрузка данных в память. Для 1млн. длится несколько минут(даже вроде больше 10 длилось). При очистке памяти аналогично.
Производительность по сравнению с 1ой версии увеличена в +бесконечность (особенно при увеличении объема входных данных).

Если добавить балансировку главного дерева (вспомогательных бессмысленно, вроде), можно еще ускорить поиск, например (по коду, хотя на 1млн. авто поиск коду был ПОЧТИ мгновенным, правда не тестировал вырожденные случаи), но балансировать дерево даже на 1млн. авто - жесть.

Как я понимаю, ускорить импорт данных не представляется возможным. Фундаментально структуру входных файлов не изменить.
Вижу лишь единственный полуминус - данные как бы пришлось закачивать в двойном экземпляре в память (всего лишь в двойном!!). С другой стороны, ну, вот, например, марка машины "Jaguar", занимаем 7байт информации. Если заменить на целое число, то будет 4байта (или 2 байта). Благодаря указателям (char*) на каждое строковое данное было использовано минимально требуемое число памяти, не сильно превышающее числовой код (раньше была константа = 100 символам для всех строк, кроме краткого описания, там было под 500). Тут все как бы оптимально!

Кардинально программу уже менять стопудова не придется, т к:
и тай сойдет (с) - и реально сойдет!

P.S. сложно проводить тесты на больших объемах данных, нужен супермощный комп с дичайшим объемом ОЗУ...

https://forum.sources.ru/index.php?showtopic=419028&view=findpost&p=3833343