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

[AVA12]

Цитата

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

Верно. Но при чем тут inode? Это совсем из другой оперы.

[FasterHarder]

AVA12, если есть желание, то плз чекни алгоритм из поста №29 (я там постарался упросить насколько возможно).
там еще можно провести оптимизацию, не удалять из памяти отсортированное дерево, если не было удаления/вставки новых данных.

[AVA12]

Пожалуйста, навскидку:

Цитата

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

Индексирование данных - это не добавление первичного ключа. Это построение индекса (т. е. структуры поиска) по какому-то ключу.

Цитата

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

Что такое "дерево поиска по КЛЮЧАМ"? Имеется в виду дерево с составным ключом? Несколько деревьев по разным ключам? Что-то еще?

Цитата

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

"или какое-то там, не знаю" - преподу так же отвечать будешь?

Цитата

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

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

Цитата

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

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

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

Короче, садись, неуд.

[Pavia]

Цитата AVA12 @ 23.06.20, 18:09

Верно. Но при чем тут inode? Это совсем из другой оперы.

Опера та же самая. ФС и БД не отличимы друг от дружки. Решают одни и тежи задачи.
Во-вторых где Вы там inode разглядели? Ext - хороша тем, что изначально не требует сложной реализации и может реализована в упрощенном виде.
И самое главное она реализована чисто на дереве без использования прочих структур, что и просил ТС.

Цитата

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

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

inode в этом плане одна из самых экономичных структур так как часть данные может хранятся непосредственно в ней.

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

[AVA12]

Цитата

ФС и БД не отличимы друг от дружки. Решают одни и тежи задачи.

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

Цитата

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

Так ведь карта блоков - это часть inode, разве нет?

Цитата

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

Гм. Если задача теоретическая, то зачем упоминать миллиарды записей?

[Pavia]

Цитата AVA12 @ 23.06.20, 22:28

Ты пояснил, что B+ это не бинарные деревья, и привел картинку - зачем? Человек, не знакомый с темой, может решить, что это пример B+ деревьев (что на самом деле не так).

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


https://ru.wikipedia.org/wiki/B⁺-дерево

Цитата

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

Сообщение отредактировано: Pavia - 24.06.20, 05:08

[FasterHarder]

Цитата AVA12 @ 23.06.20, 19:44

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

Короче, садись, неуд.

не не не! Двоек у меня никогда не было за последнюю тысячу лет) да и сдавать я буду ее сам себе, хехе.

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

2. Идентификатор принято сразу добавить во входной файл с данными. Иначе там будет не стыковка. Это тупо целое натуральное УНИКАЛЬНОЕ число из отрезка [1 ... общее кол-во машин]. Проблемы тут нет! Добавляет по sizeof(int) памяти к каждой записи таблицы. Думаю, памяти хватит. Тут проблемы нет.

3.

Цитата AVA12 @ 23.06.20, 19:44

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

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

4.

Цитата AVA12 @ 23.06.20, 19:44

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

, из поста №1:

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

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

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

Цитата AVA12 @ 23.06.20, 19:44

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

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

Какое бы дерево не взять за основу нет возможности за разумное время доказать, что оно является оптимальным в данном случае.
Бинарные деревья относительно простые. Но лишь относительно. На самом деле, ИМХО, это достаточно сложная структура данных. Простая структура, ну, например, массив одномерный (статический), да и то, там тоже полно тонкостей.

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

ЗЫ: мне больше ничего не нужно) ничего не нужно) хватит, пожалейте свое время) ничего мне не надо в рамках этой задачи, ну по крайней мере пока) т к любые ваши ответы (ну большинства) никогда не приближали меня к решению поставленной проблемы (речь не только про эту проблему, а про ЛЮБУЮ в целом)...это факт! ничего не надо, все хватит! Оставьте эту задачку в покое. Не мучайте ее, ей становится только хуже после ответов большинства, ахаха. Закрываем тему. Тему закрываем.

всем спс, кто писал конструктив. Мне это чуть-чуть помогло)

[Black_Dragon]

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

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

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

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

[Pavia]

FasterHarder

Цитата

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

Вопрос в том фиксированного размера или это Blobs? И нужен по нему полнотекстовый поиск с обратным индексом.

Цитата

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

Как Вам сказать? Просто молчат из вежливости. Сложности нету, если бы вы критерий сравнения озвучили, а Вы не озвучили и решили заняться анализом. Но профессор не читает книжек по анализу алгоритмов. А дедушка Кнут в своем 3-х томнике уже проанализировал кучу деревьев. Многие его тут читали, в отличии от вас поэтому уже знают что B+ деревья оптимальны по большинству параметров. Есть и деревья и по круче которые были разработаны позже и не вошли в эти книги.

У меня проблем не было. После решения 10 учебных задач на деревья и рекурсию и динамическое программирование. Самое сложное что делал это обход AST дерева для определения типа переменной.
https://gitlab.com/pavia00/pop/-/blob/maste...nticCheking.pas

Цитата

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

У человека время реакции рук ног не превышает 100 мс. Так что такие задержки он переносит комфортно. Последний дебиа поставил так он теперь летает. Там 1000 мгновенно выводиться.
Для виртуальных компонентов отображать миллионы записей мгновенно не проблема.
https://yadi.sk/d/CLV_V2lVPqyZDA

Добавлено 24.06.20, 06:01

Black_Dragon

Цитата Black_Dragon @ 24.06.20, 05:30

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

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

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

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

А есть пример? Мне вот интересно как в Си++ такое делается. И насколько Delphi в этом плане убог.

Сообщение отредактировано: Pavia - 24.06.20, 06:02

[FasterHarder]

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

не утруждай себя в будущем больше, я не оценю)
вот чего ты вообще прицепился к этой задаче? заняться больше не чем)) ты желаешь мне помочь - не смеши мои тапочки) У тебя единственная цель: понтануться своими знаниями и унизить спрашивающего) ВСЕ! другого не дано!

ЗЫ: господи, вот какие ты убогие сравнения приводишь, типа не читал и пр. Читать - не значить понимать! Время жалко на тебя, чтобы написать, что 90% из тобою написанного не помогает мне абсолютно...

N.B. поиск по описанию нужно исключать, т к нет четких правил этого поиска. Не нужно мне писать про LIKE и мета символы. Про полнотекстовый поиск, который реализован в промышленных СУРБД. Речь про то, что в задании нет четких инструкций поиска. Все будет упрощаться, все предельно будет упрощаться! Буду упрощать настолько, пока не останется то, что мне будет понятно на 100%. Все упрощу, донельзя, до копейки...до грамма...

[OpenGL]

Цитата Pavia @ 24.06.20, 05:59

Мне вот интересно как в Си++ такое делается.

Я бы просто с помощью boost::multi_index_container сделал это.

[Black_Dragon]

Цитата Pavia @ 24.06.20, 05:59

А есть пример?

класса обвертки?

[Pavia]

Цитата Black_Dragon @ 24.06.20, 06:43

класса обвертки?

Да.

[FasterHarder]

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

В общем нужно соорудить архитектуру похожую на архитектуру современных СУРБД (sql server, oracle).
не-не-не! я не готов! нет, конечно, конечно же нет! Это нереально абсолютно! Нереально. Ни за что на свете.

Во-первых, нужно досконально понимать внутреннее устройство хранения данных в БД. Там всякие В+, самоперестраюивающиеся деревья. Там чего-то данные хранятся по 8Кб или по 32, вообще не важно мне все это. За разумное время с этим мне не разобраться (если вы можете за 10 минут, ну, ладно, я вот не могу).
Во-вторых, нужно досконально знать все эти структуры данных. Тоже сложно. В+ какое-нибудь навороченное + нету как всегда НОРМАЛЬНОГО описания в инете. Спрашивать на форуме про В+-деревья - это сразу смерть понимания процесса. Этот этап можно поднять, но уйдет оч.много времени.

нет, не готов, конечно, строить такую архитектуру. нереал, без вариантов, ответ ОТРИЦАТЕЛЬНЫЙ, ни за что! нет нет нет...
все сделаю на бинарках) это еще сделать надо! на словах то все легко, а тут проектировать нужно еще все корректно, что тоже не просто...

все оказалось достаточно серьезно в плане постановки. тут за пару часов и не закодировать. хм...
ладно, упрощу донельзя, сделаю НЕОПТИМАЛЬНО на бинарках (понятно, что реализовано будет ужасно, алгоритмы будут несовершенные и пр.).
и тай сойдет (с)

подчеркиваю еще раз: и так сойдет (с)
если я добьюсь тупо работоспособности - буду считать, что я молодец и справился с задачей!
ВСЕ!!!

[Black_Dragon]

// Класс автомобиль
class Car {
string m_Name;
string m_Firma;
}
typedef Car* PtrCar;
 
// Базовый класс
class Wrap {
public:
virtual void Add(string key, PtrCar val) = 0;
virtual void Del(string key) = 0;
virtual PtrCar Find(string key) = 0;
virtual void DelAll() = 0;
}
// Класс по конкретному дереву
class WrapBTree : public Wrap {
protected:
// Внутренняя реализация
std::map<string, PtrCar> m_Tree;
public:
virtual void Add(string key, PtrCar val) { m_Tree[key] = val; };
virtual void Del(string key);
virtual PtrCar Find(string key)
virtual void DelAll();
}
 
Wrap *ptrName = new WrapBTree;
Wrap *ptrFirma = new WrapBTree;
PtrCar c = new Car;
c->m_Name = "Копейка"
c->m_Firma = "ВАЗ"
ptrName->Add(c->m_Name, c);
ptrFirma->Add(c->m_Firma, c);

Тестовый набор действий можно загнать в функцию, и только менять враперы под разные деревья и замерять нужные временные интервалы

Сообщение отредактировано: Black_Dragon - 24.06.20, 07:21