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

FasterHarder, постановка задачи такова, что БД – это первое, что приходит в голову и альтернатив как-то не особо не видно. Так что я бы не обижался на советы типа "используй СУБД". Другое дело, если целью является написать нечто подобное СУБД самому... но это уже не Алгоритмы, это уже технология, которую следует обсуждать в других разделах. И по-любому начало будет как-то типа "накачать книжек по теории проектирования СУБД и их реализации".

Цитата Qraizer @ 23.06.20, 15:20

постановка задачи такова, что БД – это первое, что приходит в голову и альтернатив как-то не особо не видно. Так что я бы не обижался на советы типа "используй СУБД".

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

и с чего вы взяли, что я обижаюсь? я что, радоваться должен, когда мне какую-ту фигню пишут и читают какие-то морали...
меня бы обидело, если бы ответов было 0 в теме)) это да, обидно, что никто помочь даже не пытается...

Данные подаются из текстового файла. записей может быть много (да хоть миллиард)
Если строить бинарные деревья поиска, то нужно дать идентификатор каждой машине, но так, чтобы при формировании бинарок дерево как бы заполнялось равномерно (стремилось к полному). Если пронумеровать машины с 1 шаг +1, то деревья тупо вырождаются в список, лол, тупо будет очень...
Пока непонятно, что делать с идентификатором. Ну есть какие то мысли, присваивать 1ой машине = 1, 2ой машине = число машин, 3ой машине = 2, 4ой - число машин - 1 и т.д. не знаю...

Также очень важный вопрос ПРО БАЛАНСИРОВКУ деревьев. ДДП ведь не предполагает эту операцию, она ведь производная (типа по ситуации).
нужна балансировка или нет? ответа не будет - вангую)

Добавлено 23.06.20, 15:33

Цитата Qraizer @ 23.06.20, 15:20

Другое дело, если целью является написать нечто подобное СУБД самому

прикалываешься что ли)
делать самописные СУБД нужна минимум твоя квалификация, я и на 5% не потяну...

задача академическая ведь.
вся фишка этой задачи выбрать правильное дерево или список деревьев.
данные по сути состоят только из одной таблицы.
почему у вас всех какие-то мысли масштабные: делать СУБД, сделать конурента MS SQL или даже оракла...вы чего)...задача академическая...

Челу дают советы - а он бычится, вместо того, чтобы попытаться осознать. Тупой как дрова

Показываю вам всем нормальный ответ (отвечать на форумах вас нужно учить очень и очень и очень и очень много и долго, спецы тип Qraizer - исключение, ответы его всегда почти идеальны в разделах "си, плюсах и пр."). Хотя поздно учить - форум скоро уйдет в небытие, к сожалению...Это неизбежно!

Вот вам небольшой пример понятного мне ответа!
---------------------------------------------------------------
Так, FasterHarder, по заданию все понятно. Молодец, тщательно все описал, не поленился.
Ты хочешь 2 варианта дерева: посложнее (профессиольное решение) и попроще (с изъянами).
Сложный вариант: можешь попробовать поразбираться с QT-TREE. Но учти, там важна отсортированность данных.
Простой вариант: семейство бинарных деревьев поиска. Каждое дерево отвечает за конкретное поле сущности "Авто". У тебя вроде 6 полей. Вот и построй 6 деревьев. Кстати, балансировка желательна. Сделай, если справишься. И разберись с идентификатором авто, чтобы их отличать друг друга (по примеру первичного ключа)
Если будут вопросы - задавай! При возможности помогу. Если нужна работа под ключ - пиши в личку, сделаю за деньги)
--------------------------------------------------------------

и никаких гвоздей, по крайней на 1е время!!
и не надо ничо больше...

ЗЫ: 80% отвечающих не слышат спрашивающего) Так всегда и на всех форумах во всех разделах! ФАКТ! да даже прочитать постановку не могут, начинают лепить собственное видение, предлагать какие-то альтернативы и пр., хотя спрашивающему все это даром не сдалось)

ЗЫЗЫ: #18 - весь в тебя)

Так в этом-то и корень, FasterHarder, что твоя задача выглядит как многословное "как написать БД". Потому и пишут в ответ ...э-э-э, "фигню". У меня вот тоже первой мыслью было посоветовать почитать теорию проектирования движков СУБД и вырезать оттуда лишнее. Формально там все ответы должны быть. Но не стал, ибо кто я в этом разделе и кто завсегдатаи.

Цитата FasterHarder @ 23.06.20, 08:05

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

Лично моё мнение будет практически совпадать с уже озвученными. Берём любую подходящую структуру данных, которая имеет амортизируемо константную сложность добавления/удаления элементов и низкие накладные расходы на эти операции и служебную информацию. Из Плюсового stl лучше всего подходит дэк: связный список массивов фиксированного размера. Помещаем в него все структуры в произвольном порядке, почему бы и не в порядке чтения из внешнего источника данных. Индексируем по каждому полю и создаём структуры данных для индексов. Они должны обеспечить логарифмическую сложность поиска и апдейта. Опять же из Плюсового stl тут подходит множества, ибо реализуются через КЧ-деревья, они ещё и балансируются сами... ну, почти сами. На каждое поле, по которому может быть выполнен поиск, свои индексы, т.е. своё множество. Каждый индекс в множестве просто ссылается на конкретный автомобиль в хранящем их дэке. Ключ для сортировки просто определяется методом сравнения автомобилей по соответствующему полю, например, для названий лексикографическое сравнение, для скоростей – простое математическое, итп. При добавлении элемента в нашу БД дописываем его в конец дека и апдейтим множества индексов; при простом поиске выбираем соответствующее критерию множество и отбираем весь удовлетворяющий границам диапазон; при удалении элемента удаляем из дека и опять-же апдейтим индексы; при комплексом поиске можно выбрать один из двух вариантов: либо создаём временный индекс ака множество и пользуем некоторое время, пока актуально, либо разбиваем сложный запрос на простые и применяем последовательно каждый с исключением или объединением, в зависимости от связей простых условий в комплексное, промежуточных результатов.

Сообщение отредактировано: Qraizer - 23.06.20, 16:32

Qraizer, вот чорт меня дернул упомянуть термин БД...у меня просто ДАННЫЕ, ну, тупо 1на таблица...

спс, конечно, но я еще даже не дочитал твой монолог, как сразу 2 момента:
1. язык СИ (который чистейший)
2. структура "дек". Это ведь вставка и в начало и в конец + такие же удаления. Но это ведь НЕ древовидная структура. А др.структуры использовать нельзя. Ну, как минимум обработка дерева начинается с корня (точка входа в дерево), а дек нарушает это требование.

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

Цитата

Так, FasterHarder, по заданию все понятно. Молодец, тщательно все описал, не поленился.

Не обманывайте себе. У вас описание всегда не годное куча лишней информации и 0 нужной. Во вторых вы все равно не слушаете других и делаете все по своему.

Qraizer, я оценил твои попытки решения - но, уверяю, это пока не твое Когда речь идет о выборках данных - решают две вещи: само проектирование данных и набор запросов ним. Обвязка в виде ЯП - это гораздо вторичнее.

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

Цитата Pavia @ 23.06.20, 16:38

Не обманывайте себе

+1

Добавлено 23.06.20, 16:46

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

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

Цитата

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

Нет БД это и есть деревья все современные БД используют B+ деревья
http://citforum.ru/programming/theory/sort...ng2.shtml#5_1_2
http://citforum.ru/database/osbd/glava_39.shtml#_4_1_2_1

У крутых СУБД можно ещё другие структуры использовать.

Сообщение отредактировано: Pavia - 23.06.20, 17:18

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

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

Цитата FasterHarder @ 23.06.20, 16:37

1. язык СИ (который чистейший)

Не проблема. Я не призывал использовать Плюсы и stl, я лишь, см. начало поста, описал свои мысли. И тем не менее, упоминание языка и библиотеки дают хороший старт к поиску инфы для самореализации описанных в посте идей.

Цитата FasterHarder @ 23.06.20, 16:37

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

Не проблема. Можно хранить деревом. Только зачем? Поиск всё равно всегда выполняется по индексам, так что выгода от дерева в самом хранилище полезной информации никак не востребована, тогда как дерево имеет бо́льшие накладные на служебную инфу и производительность. Иными словами запрет на использование других структур данных ухудшает ТЗ.

Цитата FasterHarder @ 23.06.20, 16:37

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

Предположим, данные исходно лежат на диске в файлике. Вопрос: «можно вообще не хранить инфу, а индексы пусть ссылаются на смещения от начала файла» нарушает ТЗ?

Добавлено 23.06.20, 17:27
Повторю: индексы древовидны.

вот, придумал хороший вариант!
не нужно никакое семейство бинарных деревьев! Как минимум нерациональное использование дин.памяти.

1. индексируем исходные данные (добавляем первичный ключ). Можно рандомом пройти. Общее число записей ведь известно.
2. строим бинарное дерево поиска (без балансировки) по КЛЮЧАМ, второе поле узла дерево - информационная часть об авто. Все в одном месте хранится!
3. операция удаления происходит по ключу, поэтому выполняется за логарифмическое время (или какое-то там, не знаю, в общем быстро)
4. операция вставки - аналогично.
5. сортировка! Допустим, хотим отсортировать данные по названию авто. СТРОИМ вспомогательное дерево (также ДДП), но лексикографическое по названию. Для этого достаточно один раз просмотреть исходное дерево, вынимая от туда узлы и добавлять в вспомогательное. Затем элементарно делаем обход по дереву названий и выводим либо ASC, либо DESC. Это касается всех полей. Да, будет 6 различных функций, делающих примерно одно и то же. Шаблонов в СИ нету. После печати по названий - дерево вспомогательное уничтожаем и получаем исходное состояние.
6. при поиске делаем п№5, а затем запускаем бинарный поиск нужной информацию по конкретному полю.
7. с редактированием. По ключу - поэтому нет проблем.


Все, думаю, меня это устроит! Реализовать еще нужно грамотно - тоже дело непростое ведь)
В итоге сам со всем разобрался. Ну, как и обычно в принципе...)
Насчет балансировки: ну, желательна, конечно...хм...надо подумать...

P.S. вот так и думаешь, ну, канет форум в небытие, много ли я потеряю...сложный вопрос...Иногда на форуме выручают очень круто, но это лишь очень и очень иногда...

Добавлено 23.06.20, 17:34

Цитата AVA12 @ 23.06.20, 17:23

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

, если бы все было так просто
эта задача взята с бесконечных просторов инета...

Добавлено 23.06.20, 17:37
Qraizer, спс за конструктивный материал (сложноватый местами для понимания)

Цитата FasterHarder @ 23.06.20, 17:32

не нужно никакое семейство бинарных деревьев! Как минимум нерациональное использование дин.памяти.

B+ это не бинарные деревья.