Constant on average, worst case linear in the size of the container.

главное дерево построено по айдишникам авто

вот, например, будет такой запрос: "получить кол-во красных машин". ОПА!
на сильноветвящихся деревьях (к чему я тяготею) это будет сделано почти моментально, а тебе придется просмотреть ВСЕ УЗЛЫ главного дерева и проверить

По уникальному коду ты будешь сразу же быстро получать всю инфу по авто.

У тебя справочники это: Цвет, Марка и т.д., которые ты заменил цифровыми ИД.
Основная запись и состоит из кучи ИД и некоторые оставшихся полей, например, вин, год, количество пассажиров, ФИО и т.д.

ГЛАВНОЕ бинарное дерево поиска (ключ у него идентификатор авто)

Структура да.

Б+-деревья используются для хранения данных на жёстких дисках.

В википедии сказано что как правило фиксированное:

Плюс у DOUGLAS COMER так же чётко сказано что ключей в узле 2d.

In general, each node in a B-tree of order d contains at most 2d keys and 2d + 1 pointers, as shown in Figure 4.

i) Each path from tire-root to any leaf has the same length h, also called the
height of T, i.e., h = number of nodes in path.

Ключи там есть К примеру такие ключи как i_size и i_mtime

В ext не используется битовая карта(сегментированный массив блоков)

У B(+)-деревьев количество дочерних узлов может варьироваться. У карты файловых блоков количество элементов в каждом узле (кроме последнего "листа") фиксировано.

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range.

i) Each path from tire-root to any leaf has the same length h, also called the
height of T, i.e., h = number of nodes in path.

Узлы B(+)-дерева содержат как ссылки на дочерние узлы/листья, так и значения ключей. Карта файловых блоков содержит только ссылки, никаких ключей в ней нет.

struct ext2_inode {
__u16 i_mode; /* Тип файла и права доступа (см.ниже) */
__u16 i_uid; /* UserID */
__u32 i_size; /* Размер в байтах */
__u32 i_atime; /* POSIX время последнего обращения к файлу */
__u32 i_ctime; /* POSIX время создания */
__u32 i_mtime; /* POSIX время последней модификации */
__u32 i_dtime; /* POSIX время удаления */
__u16 i_gid; /* GroupID */
__u16 i_links_count; /* Кол-во ссылок на дескриптор */
__u32 i_blocks; /* Кол-во секторов (не блоки!) */
__u32 i_flags; /* Флаг (см.ниже) */
union {
struct {
__u32 l_i_reserved1; /* Зарезервировано */
} linux1;
struct {
__u32 h_i_translator; /* ??? */
} hurd1;
struct {
__u32 m_i_reserved1; /* Зарезервировано */
} masix1;
} osd1;
__u32 i_block[EXT2_N_BLOCKS];/* Указатели на блок */
__u32 i_generation; /* Версия файла (для NFS) */
__u32 i_file_acl; /* Доп. аттрибуты файла */
__u32 i_dir_acl; /* Доп. аттрибуты директории */
__u32 i_faddr; /* Адрес фрагмента */
union {
struct {
__u8 l_i_frag; /* Номер фрагмента */
__u8 l_i_fsize; /* Размер фрагмента */
__u16 i_pad1; /* Зарезервировано */
__u16 l_i_uid_high; /* 16 старших битов UserID */
__u16 l_i_gid_high; /* 16 старших битов GroupID */
__u32 l_i_reserved2; /* Зарезервировано */
} linux2; /* LINUX */
struct {
__u8 h_i_frag; /* Номер фрагмента */
__u8 h_i_fsize; /* Размер фрагмента */
__u16 h_i_mode_high; /* 16 старших битов T&P */
__u16 h_i_uid_high; /* 16 старших битов UserID */
__u16 h_i_gid_high; /* 16 старших битов GroupID */
__u32 h_i_author; /* UserID или автор */
} hurd2; /* GNU HURD */
struct {
__u8 m_i_frag; /* Номер фрагмента */
__u8 m_i_fsize; /* Размер фрагмента */
__u16 m_pad1; /* Зарезервировано */
__u32 m_i_reserved2[2]; /* Зарезервировано */
} masix2; /* MASIX */
} osd2; /* Специфичные значения */
};

B(+)-дерево - это дерево поиска. Карта файловых блоков - это, в общем-то, и не дерево, это сегментированный массив.

2. B(+)-деревья позволяют вставку и удаления узла/листа, при этом затрагивается максимум log(n) узлов. Чтобы вставить или удалить узел в карту файловых блоков, нужно перетряхнуть все последующие узлы (в худшем случае - вообще все).

На это картинке изображено B+ дерево.

"Описание" - просто текстовое поле.

Неужели еще никто не понял, что данная задача обладает лютейшей сложностью, т к для выбора правильного дерева нужно знать все ныне существующие деревья, знать их лучшие худшие/случаи производительности и кучу др.характеристик. Этих деревьев изобретено свыше 1000, наверное. Там есть такая жесть. Иногда вижу какие-то закольцованные деревья, со связями к корню, к предку или на какой-то другой уровень и пр. Это все очень сложно. Это все очень сложно. Это все очень сложно. +сами по себе деревья имеют рекурсивную природу, а рекурсия один из сложнейших разделов информатики. На каком-то уровне рекурсию не сможет понимать ни один разработчик (самый великий даже) в мире (это со слов Макконела).

1. Количество записей будет штучек 30. Ну, максимум 100. Отображение в консоли через псевдографику (красивый каркас таблицы) происходит ооооочень медленно. Даже 20 записей отображаются НЕ мгновенно. миллион, например, записей отобразиться через несколько часов (может суток) - смысла в этом ноль все равно, т к их не просмотреть будет. Делать перелистывание данных в консоли - не вариант, даже думать об этом не буду. Поэтому на ограничение про память забываем. Тут проблемы нет.

Бурный у вас вечер.

Как сделано у меня в реале.

Есть класс Устройство с кучей полей... храниться в памяти.
делаем std::map или std::unordered_map
Где первичным ключем будет какое-то нужное поле (строка/число), а значением - ссылка на этот класс в оперативной памяти.
Сколько полей для поиска, столько и мап-ов.
Вообщем по аналогии: ключ/ссылка.

Если надо сделать тестовое исследование, то делаешь на ООП обвертку с базовым классом и нужным набором функций и наследуешь для разных вариантов реализации.
Создаешь массив (обычный) объектов нужного класса.
И потом пихаешь в нужное дерево, через обвертку, значения полей и ссылку на объект.

И что для построения индекса нужно просмотреть все записи?

Ты не объяснил, как (и с какой целью) ты будешь индексировать поле "описание".

Сортировка по любому из полей (кроме краткого описания)

Ты не обосновал оптимальность (и даже применимость) двоичных деревьев поиска.

B⁺-дерево — структура данных на основе B-дерева, сбалансированное {\displaystyle n}n-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B⁺-дерево состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками.

Во-вторых где Вы там inode разглядели?

ТС вам написал, что для него это задача академическая, а не практическая.

Ты не рассмотрел проблему большого количества записей (подсказка: в память индекс целиком не влезет, и это только верхний пласт проблемы).

1. индексируем исходные данные (добавляем первичный ключ).

2. строим бинарное дерево поиска (без балансировки) по КЛЮЧАМ, второе поле узла дерево - информационная часть об авто. Все в одном месте хранится!

3. операция удаления происходит по ключу, поэтому выполняется за логарифмическое время (или какое-то там, не знаю, в общем быстро)

5. сортировка! Допустим, хотим отсортировать данные по названию авто. СТРОИМ вспомогательное дерево (также ДДП), но лексикографическое по названию. [...] После печати по названий - дерево вспомогательное уничтожаем

7. с редактированием. По ключу - поэтому нет проблем.

Если нужен полезный совет: FasterHarder, готовь бутылку хорошего коньяка (или что там препод любит)

2. структура "дек". Это ведь вставка и в начало и в конец + такие же удаления. Но это ведь НЕ древовидная структура. А др.структуры использовать нельзя. ...

... Ну, как минимум обработка дерева начинается с корня (точка входа в дерево), а дек нарушает это требование.