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

Цитата FasterHarder @ 26.06.20, 09:02

т е придется просмотреть ВСЕ деревья, чтобы собрать воедино реальные данные

Нет.
У тебя все данные хранятся в одной структуре, которая хранится в главном дереве по уникальном коду.

Добавлено 26.06.20, 09:09

struct Car {
ULONG m_VIN;
ULONG m_Firma;
ULONG m_Model;
ULONG m_Color;
//....
}

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

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

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

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

+зачем тебе хранить дубликаты данных в главном дереве.

не-не, у меня все шикарно)
ну не знаю, может есть какая-то грубая ошибка, но пока не вижу!

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

мне же НЕ придется этого делать!
скажут, хочу все машины ЗЕЛЕНОГО цвета. Я не буду сканировать все узлы данного дерева (если что, их там миллионы может быть). Тупо уйду в дерево, отвечающее за цвет, там найду узел с "зеленым цветом" и через массив ссылок узнаю, все нужные мне машины. Это эффективнее в миллионы раз может быть, чем перебирать все узлы главного дерева...

я пока так это понимаю

Цитата FasterHarder @ 26.06.20, 09:12

ведь у нас в главной таблице обычно хранятся внешние ключи на справочники. а в справочниках реальные данные.

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

Получил ты эту запись и из массивов-справочников вытащил текстовые данные полей.

Добавлено 26.06.20, 09:31
+
Будет избыточность, но это это даст быстродействие.

Добавлено 26.06.20, 09:31
+
Ну и по хожу жизни программы ты можешь просто генерировать любые деревья на ходу.

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

если примерное одинаково, тогда удобнее один раз по главному дереву, выдергивая по одной ссылке нужны данные!

Добавлено 26.06.20, 09:43
Вот, последний момент здесь остался!
Допустим, миллиард авто. (можно взять просто сто).
Из них 150 миллионов красных)

в одном случае чтобы получить все красные авто (+ все остальные поля, разумеется), нужно просканировать все узлы главного дерева). Ведь главное дерево упорядочено НЕ по цвету, а по своему АЙДИ. И это касается любого поиска, кроме поиска по айди!

в другом случае, чтобы получить все красные деревья - идем в цветовое дерево. МОменально определяем цвет и все ссылки на узлы главного дерева. Но этого недостаточно, нужно еще для каждой машины найти другие атрибуты. Всего 150 млн. красных. Значит для каждого другого цвета по 150 млн. раз ищем нужные атрибуты. Если деревьев еще 8 штук, то будет 150 * 8 = 1.2 млрд. узлов нужно просмотреть. Это чуть менее эффективно, чем в случае №1.

Но, если машин красных, всего 15 тысяч, то во втором случае потребуется 15 * 8 = 90 тысяч. Что эффективнее первого варианта в 10 раз.

Считаю, что 2й вариант производительнее в среднем! Но его сложнее кодировать, чем 1й...

Добавлено 26.06.20, 09:44

Цитата Black_Dragon @ 26.06.20, 09:30

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

я это описывал выше!

Цитата FasterHarder @ 26.06.20, 09:32

Но, если машин красных, всего 15 тысяч, то во втором случае потребуется 15 * 8 = 90 тысяч. Что эффективнее первого варианта в 10 раз.

миллиард авто минус 15 тысяч, что с ними будешь делать?
Это твое убыстрение не по цвету в общем, а по конкретному цвету, т.е. по красному, значит остальные цвета в пролете.

Если тебе надо будет добавить еще поле или еще какие-то деревья, код переделывать не нужно.

Цитата Black_Dragon @ 26.06.20, 09:49

миллиард авто минус 15 тысяч, что с ними будешь делать?

в смысле?! они лежат там себе, греются на солнышке, ждут своей обработки)

короче! я определился! нужно делать через сильноветвящиеся деревья.
справочники ТОЛЬКО для строковых данных. Все числа хранятся в узле главного дерева. Какой смысл выносить число в справочник, если код тоже целое число, лол
справочников будет штук 5-6.
там еще есть поле "тип кузова" - вообще будет перечисление - через целое число.

Есть всегда сканировать все узлы главного дерева при поиске, то нет НИКАКОГО прееимущества поиска. Искать нужно начинать через спец.дерево (цветовое, марочное и пр.), а уже потом уточнять информацию через другие деревья.

этот вариант кодировать сложнее! если не получится, то перейду на скан всегда главного дерева, но это менее эффективно, разумеется! Лишь в некоторых случаях будет производительнее. А вообще все это оч. сильно зависит от типа входных данных.

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

ты говоришь про масштабирование системы...хм...ну, допустим появляется НОВОЕ поле у авто (ну, например, степень изношенности, там типа бывает 35 видов ее), новый справочник со степенью изношенности добавили. все вспомогательные деревья перестраиваться не будут.
да, когда полей ооооочень много, штук 200, тогда оч.долго будет доставать всю информацию по кусочкам из каждого справочника - проще просканировать главное дерево.

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

ладно, я понял..
надо еще подумать немного и хватит)

Добавлено 26.06.20, 10:14
можно предельно упростить (за счет памяти дикой)
если включить все данные в узел главного дерева + все деревья построить для нужно поля. это по факту отказаться от связи по кодам!
тогда поиск - почти моментальный, просто сверхбыстрый
сортировка - почти моментальная, тупо обход нужного вспомогательного дерева

единственынй минус - хранить избыточные данные в колоссальном кол-ве! хм...
но быстродействие будет дичайшим!!!!

Цитата FasterHarder @ 26.06.20, 10:05

Есть всегда сканировать все узлы главного дерева при поиске, то нет НИКАКОГО прееимущества поиска.

Как это нет? Оно в дереве лежит, где поиск быстрее линейного перебора.
И не забывай, тебе на экран надо выводить по каждому авто всю инфу, когда человек будет листать список... По уникальному коду ты будешь сразу же быстро получать всю инфу по авто.

Цитата Black_Dragon @ 26.06.20, 10:24

Как это нет? Оно в дереве лежит, где поиск быстрее линейного перебора.

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

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

Цитата Black_Dragon @ 26.06.20, 10:24

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

я нигде выше этого и НЕ отрицал) ну опять-таки, если под кодом понимается айдишник


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

короче, ладно! точно знаю, что сейчас уже знаю, как можно значительно улучшить все по сравнению с 1-ой версией. Кстати, она неплохая, когда данных мало, на десятках миллионов авто система умрет)) и по памяти и по скорости...ладно, а что сделать-то, а ничего...только переписывать!

ЗЫ: по-разному делать можно, но самый эффективный вариант (особенно по памяти требуемой) самый сложный в реализации. ладно!

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

Цитата Black_Dragon @ 26.06.20, 09:01

std::unordered_map

Хотя я в этой теме persona non grata, но выскажусь ... ты частично не прав! Все зависит от "режима" использования! Если де-факто редкие модификации и частый поиск - следует наоборот использовать упорядоченную карту std::map (т.к. ее порядок по поиску = O(lgN)). Строго экономим на поиске. А у std::unordered_map он равен O(N). Но если модификация данных происходит значительно чаще поиска - ты на 117% прав! Тогда важнее успеть "занести" данные. И std::unordered_map будет идеален.

JoeUser
Цель была в другом: типа используй готовые наработки.

У меня раньше быль файлик , шаблон простого списка с минимум функций (кода на два экрана), кочевал из проекта в проект.
Потом в какой-то дискуссии натолкнулся на набор из std, плюнул на свой файлик....

Но тут смотря какая цель, тебе просто нужен функционал и ты используешь готовое, или хочешь поковыряться под капотом этого функционала сам.

Цитата FasterHarder @ 26.06.20, 10:36

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

Да, и оно же является основным хранилищем всех данных.

Если поиск идет больше 10с и там есть главный цикл, то используй OpenMP или изобретай ухищрения....

Геометрическая обработка

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.4973356
--- Создаем базу линий ---
Затраченное время: 00:00:00.1499118
--- Обработка ---
Количество обработанных полигонов - 45832
Затраченное время: 00:04:34.3432271
Общее время: 00:04:35.9934664
--- Конец ---

Тоже, но с ухищрениями

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.5067219
--- Создаем базу линий ---
Затраченное время: 00:00:00.1795199
--- Обработка ---
Количество обработанных полигонов - 45832
Затраченное время: 00:00:03.1831981
Общее время: 00:00:04.8764213
--- Конец ---

OpenMP (6C/12T)

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.6982313
--- Создаем базу линий ---
Затраченное время: 00:00:00.1680519
--- Обработка ---
Количество потоков: 12
Количество обработанных полигонов - 45832
Затраченное время: 00:00:32.8862290
Общее время: 00:00:34.7565014
--- Конец ---

Ухищрения + OpenMP

Скрытый текст

--- Загрузка ---
Количество прочтенных строк файла - 676537
Количество загруженных полилиний - 12094
Количество созданных линий - 124421
Затраченное время: 00:00:01.4844383
--- Создаем базу линий ---
Затраченное время: 00:00:00.1695467
--- Обработка ---
Количество потоков: 12
Количество обработанных полигонов - 45832
Затраченное время: 00:00:01.6181071
Общее время: 00:00:03.2770786
--- Конец ---

Цитата JoeUser @ 26.06.20, 14:24

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

Я же писал, главное дерево с данными и деревья по основным поисковым запросам с ссылками на основе данные.

Black_Dragon, в твоем предыдущем сообщении - цитата не моя. Я и так знаю количество красных машин в мире!

Все, проблема решена! 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. сложно проводить тесты на больших объемах данных, нужен супермощный комп с дичайшим объемом ОЗУ...

Цитата FasterHarder @ 27.06.20, 23:32

нужен супермощный комп с дичайшим объемом ОЗУ

На мощном компе ты не оценишь быстродействие...
А сколько памяти было?
При загрузке где узкое место? Диск был загружен или проц?
На моем компе с обычного HDD 10Гб читались (в nul) 1 минуту.
Имхо, оптимизируй добавлений данных...

Цитата JoeUser @ 26.06.20, 14:24

Строго экономим на поиске. А у std::unordered_map он равен O(N).

Цитата

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

В принципе, если не умничать и не писать хеши самому, либо не ломать специально хеш-функцию специально подобранными данными (на реальных данных это 100% не произойдёт), то можно надеяться на average.

Цитата OpenGL @ 28.06.20, 18:42

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

Надеясь на лучшее - готовься к ужасному (С)