Выбор типа дерева (структура данных) для хранения данных в БД , БД "Гараж из автомобилей"

Цитата Black_Dragon @ 25.06.20, 08:52

Вбиваем в поиск: феррари, красный, двухдверный (трех), с откидным верхом (или с люком), пассажир назвал водителя Миша.

Так это обычный атрибутный поиск, логическое деление. Деревьями тут даже не пахнет.

Цитата Black_Dragon @ 25.06.20, 08:52

Вбиваем в поиск: феррари, красный, двухдверный (трех), с откидным верхом (или с люком), пассажир назвал водителя Миша.

ОФТОП
Типичная прологовская задача на организацию Базы знаний. И мудрить с деревьями не надо, список в прологе стандартно организован в виде дерева(голова - хвост).
Создаём предикат (отношение) owner(имя_владельца, автомобиль), а автомобиль - сложная структура car(марка, цвет, госномер, ...).
Записываем в Базу знаний факты по каждому владельцу и его автомобилю. У владельца может быть несколько автомобилей, для бесхозных автомобилей можно ввести какое-нибудь noname.

Цитата

список в прологе стандартно организован в виде дерева(голова - хвост).

Голова-хвост - это односвязный список. В принципе, можно трактовать его, как абсолютно вырожденное дерево, но зачем?

А у меня тем временем все готово! хехе

По факту получилось:
- 1300+ строк высокопроизводительного кода)
- 50+ функций, выполняющих строго одну операцию
- около 10 структур данных (очень похожих по составляющим)
----------------------------------------------------------
все прекрасно работает, интерфейс предельно дружественный и интуитивно понятный (куча подсказок и пр.).
глобальной обработки ошибок нет, так, местами есть кой какая защита
утечек в памяти не наблюдается (а там есть чему утекать, хехе)
система хорошо поддается расширению, вроде, хотя...может нет!
ход документирован, старался делать по Макконелу) (этого чувака люто уважаю и читаю его книги запоем!)
основная структура данных: двоичное дерево поиска с возможностью хранения дубликатных ключей БЕЗ балансировки

Единственное место, где мне пришлось отойти от бинарок - обработка количества пассажиров, находящихся в машине. Оно варьируется от 1 до 6. Я так чего-то прикинул, ну максимально тупо строить бинарку, хранящую всего 6 различных ключей (с дубликатами, разумеется). Если дано 90 млн. машин, у которых кол-во пассажиров равно 3 и ОДНА машина с кол-вом = 4 и эта машина (с 4мя пассажирами) добавляется последней в дерево, то все вырождается в ЛОС, при этом 4ка висит на хвосте, т е чтобы найти все машины с 4мя пассажирами пришлось бы просканировать 90млн узлов дерева. Нет уж, увольте, требования требованиями, но малейшая логика должна быть! Сделал массив списков, состоящий из 6 элементов и из каждого узла идет подписок на нужное число пассажиров. Дерево ли это? ну издалека похоже) Вообще, нет, ну, если допустить, что у узла может быть один потомок, то да)

Очень плохо, что структуры в СИ не имеют индексацию своих полей (хотя где-то видел пример через добавление указателей и чего то там мутили с объединениями, в общем я там ничего не понял и оч.рад этому) + единственная возможность в коде обращаться к ним - прописывать их название целиком.
В итоге мне нужно было строить СВОЮ отдельную бинарку для каждого поля сущности "авто", а их штук 8. При этом многие из них похожи донельзя(отличие только в названии поля). При этом ведь нужно добавить узел, сделать обход (2 способами) и удалить из памяти, минимум 4ре функции. А т к 8 полей, то РЕЗКО получаем избыточную хрень 8 * 4 = 32 функции, которые крайне похожи по обработке, но там разные поля структуры прописываются. Я хрен знает, как это шаблонизировать в си, вроде как-то делают, но я не выкупаю, да и так неплохо вышло)

Без понятия как оценить производительность работы прожки. Сравнивать не с чем. Данных нет, да и толку от них, все равно даже миллион записей не вывести на экран. Уверен, что можно все организовать эффективные в разы, используя ПРАВИЛЬНЫЕ древовидные структуры (да как бы еще знать их, века не хватит на их фундаментальное изучение), но и так все работает неплохо)

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

В общем я доволен результатом! Нет, даже ОЧЕНЬ ДОВОЛЕН!!! Пойду съем мороженку)

И самое главный императив: и тай сойдет (с)

Цитата FasterHarder @ 25.06.20, 14:54

Без понятия как оценить производительность работы прожки. Сравнивать не с чем. Данных нет, да и толку от них, все равно даже миллион записей не вывести на экран.

В чем проблема?
База есть, делаем разные алгоритмы, а потом для каждого запускаем идентичные операции и мерим время.

а это вот такая архитектура должна быть на уровне структур данных??

Прикреплённая картинка

Цитата AVA12 @ 25.06.20, 13:59

Цитата

список в прологе стандартно организован в виде дерева(голова - хвост).

Голова-хвост - это односвязный список. В принципе, можно трактовать его, как абсолютно вырожденное дерево, но зачем?

Бинарное дерево

Сообщение отредактировано: swf - 25.06.20, 17:23

FasterHarder
Кроме ФИО, все остальные поля - это справочники, по ним тупо отдельный массив с индексами (число), которые и будут использоваться.
По этому, структура для всех случаев будет идентична.

Цитата Black_Dragon @ 26.06.20, 02:55

ФИО

ягуар Сергей Иванович
опель Виктор Сергеевич
ты об этом ведать...

прочитал два раз твой ответ - ничего не понял, вот ничего не понял
прочитал еще раз - ничего не понял
какие справочники (под справочником в теории БД обычно понимают таблицы, содержащие редкоизменяемую инфу, еще ее называют статической инфой), какие еще массивы (мне деревья нужны) и т.д.

я приложил картинку, и спросил "да или нет?". так и не понял, так "да или нет"

FasterHarder
Ягуар, Опель, ВАЗ и т.д. Красный, Зеленый и т.д. и многие другие поля, это справочники, они кодируются 1, 2, 3 и т.д.

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

Цитата Black_Dragon @ 26.06.20, 07:56

Ягуар, Опель, ВАЗ и т.д. Красный, Зеленый и т.д. и многие другие поля, это справочники, они кодируются 1, 2, 3 и т.д.

как минимум это не поля, а значения полей конкретных объектов структуры, но пока на мой взгляд это не важно вообще. Называть можно как угодно.
а, я понял, ты хочешь создать для марок ОДТЕЛЬНУЮ таблицу с целочисленным первичным ключом и сделать связь не через строки, а через целые числа (по айдишнику). И так для каждого поля. Понятно, вот почему был призыв к нормализации. В итоге получаем солнцеобразную структуру БД: в центре данные и лучики исходят к 8 справочникам. Что характерно справочники между собой НЕ имеют ни одной связи. Такое оч.редко бывает в норм. БД)

Цитата Black_Dragon @ 26.06.20, 07:56

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

так, ясно. У меня реализовано не так, ну частично так. На миллиарды процентов Макконел прав, когда говорит, что оптимальное решение проблемы приходит только тогда, когда сделана минимум одна попытка решить эту проблему неэффективно. Как правило это приводит к ПОЛНОМУ переписыванию проекта (иногда больше 1го раза, хехе).

И тут есть такой важный момент с точки зрения памяти и эффективности.
Вот мы прочитали данные (ну, пусть из файла или с клавиатуры или еще как-нибудь - не важно вообще) и построили ГЛАВНОЕ бинарное дерево поиска (ключ у него идентификатор авто). Это как бы главное дерево для хранения данных.

Можно СРАЗУ построить все бинарки вспомогательные для всех полей сущности "Авто", их там штук 8. Т е обязательно строим главное дерево и можно построить 8 дополнительных (для каждого поля, по которому будет идти поиск, сортировка и пр.)
Минус первый - нужно много памяти. Хотя, если в узлах будут храниться целые числа, то sizeof(long) * 8 * <количество машин> + на указатели что-то там по мелочевке.
Во-вторых, если есть поля, по которым редко происходит обработка, ну, например, малое число запросов по полю "страна-производитель", то в таких случаях эту бинарку можно строить по мере необходимости? имеет смысл? (с др.стороны я уже писал раньше, что обращение к любому полю авто равновероятно)
в-третьих, когда меняются данные (удаление, вставка, апдейт), то сразу перестраиваем ГЛАВНОЕ дерево + нужно отследить все ссылки из всех бинарок на эти изменения. Чем больше вспомогательных деревьев, тем больше работы по этим указателям.

У меня в исходном проекте происходит некое дублирование всех данных об авто в памяти + деревья строятся по мере необходимости, т е в памяти висит ТОЛЬКО главное дерево с данными, а когда, например, нужно получить список авто отсортированных по марке, то я строию эту бинарку и вывожу ее на экран, после этого дропаю из памяти. это проблема...

Цитата FasterHarder @ 26.06.20, 08:18

сделать связь не через строки, а через целые числа (по айдишнику)

Да. Упрощает код, так как везде ИД. Ну и быстрее будет работать.

Цитата FasterHarder @ 26.06.20, 08:18

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

Да. И оно отвечает за сохранность данных.
Во всех остальных деревьях хранятся ссылки на эти данные.

Дальше я вижу так: деревья по главным полям.
Но размер этих деревьев будет очень мал, сколько у нас фирм? сколько у нас моделей у фирмы? Даже если взять года, то 100 всего будет.
Толку ноль...
Достраивать деревья во время поиска. Первичный Фирма, а там уже по годам и будет проще потом двигаться по разным годам.

Но если ключи сделать комбинацией полей... Фирма+Модель+Цвет (ID1*1000000 + ID2*1000 + ID3), Фирма+Цвет (ID1*1000 + ID2) и т.п.

Вообщем, все упирается в поиск

еще такой момент!
если в наличии у нас 50 млн. машин, то это НЕ означает, что у них уникальные атрибуты. Стран-производителей, ну 100, ну макс. 200 (ну не миллионы, однозначно ). Аналогично по цвету, по макс. скорости, по кол-ву пассажиров и т.д.

В итоге, нужно все нормализовать (как правильно заметил Black_Dragon), создать для каждого поля справочники со своими айдишниками и уникальными значениями.
исходные данные заменить на соот-щие коды из этих справочников. В итоге исходные данные превратятся В ЦЕЛЫЕ ЧИСЛА - крайне эффективно хранить в памяти.

Возьмем цвет для примера. В наличии 1200 машин зеленых и 1700 красных и 500 черных. По факту в справочнике цветов 3 записи с кодами (1 - зеленые, 2 - красный, 3 - черный). Получаем дерево из ТРЕХ узлов, но ключом выступает цвет при построении (а не код, т к если брать код, то все вырождается в список). И у каждого узла есть поле - массив указателей на все машины в главном дереве соот-щего цвета. Т е у корня (там зеленый цвет) будет массив указателей на 1200 узлов в главное дерево и т.д.

Это дает предельно быстрый поиск. Сортировать НЕ нужно, просто сделать ЛКП обход, т к информация в деревьях уже упорядочена при построении.
Можно сразу все грузить в память, т к это ничтожно мало занимает.

Единственная проблема, чисто техническая, правильно обрабатывать сильноветвящиеся деревья при удалении, вставке, апдейте.

Вот она, идеальная структура, только сейчас стало понятно, что должно быть) Да уж...нужно ВСЕ перекраивать (ну кроме импорта / экспорта данных). Эх, ну и ладно)

Цитата FasterHarder @ 26.06.20, 08:49

Единственная проблема, чисто техническая, правильно обрабатывать сильноветвящиеся деревья при удалении, вставке, апдейте.

Юзай готовые решения.
std::unordered_map

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

10. вывод данных на экран

т е придется просмотреть ВСЕ деревья, чтобы собрать воедино реальные данные, а не их числовые айдишники. Учитывая то, что эти деревья небольшие, то все будет мгновенно.

это ладно, когда уникальных атрибутов не много. А если было бы какое-то поле типа данных float (дробное) с большим разбросом. В этом случае это дерево было бы по объему не меньше главного дерева. В этом случае это поле можно включить в главное дерево и не создавать для него справочника отдельного.

т е в справочники выносим частоповторяющуюся информацию, а редкую включаем в главное дерево.
понятно...