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

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

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

Хакими за счёт использования 2-3 деревьев понизил сложность своего алгоритма с O(n^3) до O(nlogn).
Мне даже смотреть противно на эти 2-3 деревья.
У меня честные двумерные массивы и двойной цикл крутится.
Чтобы догнать Хакими, мне нужно всего-то с O(n^2) понизить до O(nlogn). Вот только не пойму как.
Кнута что ли почитать...

Добавлено 24.06.20, 07:25
На топикстартёра не наезжайте, на нём одном весь раздел держится

Цитата swf @ 24.06.20, 07:23

на нём одном весь раздел держится

шаришь)

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

Цитата FasterHarder @ 24.06.20, 07:32

создай отдельную тему и там разбирайся

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

А что за задача-то?

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

ОФТОП!
Я забыла поверх своего сообщения написать одно слово - ОФТОП
Так что сорри, рейдерский захват темы не предполагался.
to amk

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

Задачу я непременно тут запощу в отдельной теме, только сейчас не могу, статья ещё не вышла.
Может кто помнит, 5 лет назад я тут на сорцах мучалась с алгоритмом размещения абсолютного 1-центра неориентированного графа, даже тема старая есть.
Вот эту задачу я сделала, алгоритм простой, прямыми вычислениями в двойном цикле за квадратичное время все эквивалентные центры находятся для одного ребра.
Эту задачу и некоторые обобщения.

Теперь нужно использовать специальные деревья и понизить выч. сложность до nlogn.
Пока я этого не сделала, у Хакими алгоритм быстрее.
Вначале, конечно, сама попробую сделать, всё равно летом никуда не поедешь.

Цитата swf @ 24.06.20, 08:40

Теперь нужно использовать специальные деревья и понизить выч. сложность до nlogn.

OpenMP?

Pavia:

Цитата

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

Не-а.

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

AVA12
1)

Цитата

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

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

Цитата

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

Плюс у DOUGLAS COMER так же чётко сказано что ключей в узле 2d.
https://dl.acm.org/doi/pdf/10.1145/356770.356776

Цитата

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.

https://www.inf.fu-berlin.de/lehre/SS10/DBS...yerBTree-72.pdf

3.

Цитата

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

Ещё скажите что файлов не существует. Ключи там есть К примеру такие ключи как i_size и i_mtime используются для синхронизации файлов.

Цитата

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; /* Специфичные значения */
};

4.

Цитата

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

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

2)

Цитата

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

Б+-деревья используются для хранения данных на жёстких дисках. Если Если использовать сегментированный массив и поверх положить Б+ дерево, то да.
Это будет быстрее, поэтому NFTS и выигрывает у EXT в скорости. Но тут палка о двух концах либо вы сразу занимаетесь балансировкой дерева либо потом делаете дефргаментацию массива.

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

Pavia
У меня складывается впечатление, что кто-то из нас бредит.

Цитата

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

Цитата

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

Как ты думаешь, как переводится процитированная тобой фраза? В моем мире это переводится как "В B-деревьях внутренний узел (не лист) может содержать различное/переменное количество дочерних узлов, в рамках некоторого определенного диапазона." А как она переводится в твоем мире?

Цитата

Плюс у 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.

В моем мире это переводится как "Вообще, каждый узел B-дерева порядка d содержит максимум 2d ключей и 2d + 1 указателей, как показано на рис. 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

Во-первых, указанные поля inode ни к какому дереву не принадлежат, ни B-, ни C-, ни D-. Во-вторых, ты показал на картинке только часть inode - карту размещения файловых блоков. Т. е. структуру, хранящую номера всех блоков (в мире [Win]do[w]s их называют кластерами) с полезной нагрузкой конкретного файла.

Цитата

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

При чем тут битовые карты? (В ext они, кстати, используются - для поиска свободных inode и блоков). Слово "сегментированный" (синоним - "фрагментированный") означает "разбитый на части, возможно, хранящиеся в разных местах". Карта блоков в ext - это, по сути, массив, i-тый элемент которого (начиная с 0) является номером блока, который хранит байты [i*s .. (i+1)*s-1] конкретного файла (где s - это фиксированный размер блока). Поскольку разместить этот массив одним куском не всегда возможно (файлы растут, блоки добавляются), то приходится массив разбивать.

Цитата Pavia @ 24.06.20, 19:33

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

И сам тут же цитируешь: "variable number of child nodes" - переменное число дочерних узлов. А то, что выделено означает "в фикмрованных границах"

Цитата Pavia @ 24.06.20, 19:33

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

Ты уверен, что именно данных, а не структуры файлов? То бишь дерева каталогов. Просто вставка данных в середину файла ни в одной файловой системе не реализуется системой, и возможности B+-деревьев оказываются сильно избыточными.

Насколько помню, в файловых системах ext, как и в UNIX (именно эту ФС использовала упомянутая в википедии Minix), используются иерархические списки блоков. Только размеры записей другие, что позволяет создавать очень большие файлы на просто огромных "дисках".

Про Minix я дописал после того, как проверил, что в вики написано.

Всё прочитал, ничего не понял.

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

Есть у нас автомобиль А в состоянии Ах. Мы что-то с ним делаем (любая операция корректировки), получаем автомобиль А в состоянии Ау, а родителем состояния Ау является состояние Ах. Делаем вторую операцию, получаем состояние Аz. Так вот - родителем состояния Az может быть только и исключительно состояние Ау, и ни при каких обстоятельствах родителем не будет Ах. Так что мы получаем не дерево, а его частный случай, прозываемый односвязным списком.

Уже проще.

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

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

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

Комбинация первых двух полей образует естественный ПК. Для ускорения описанных операций используются соответствующие индексы. А вот когда заходит речь о том, как именно оптимизировать конкретную отдельную операцию - необходимо сначала определиться с конкретной СУБД и конкретной структурой, а потом мыслить об оптимизации.

Формально это, конечно, дерево, хотя реально - лес, где совокупность записей для отдельного автомобиля образует самостоятельное и независимое дерево.

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

---

А дальше практически по всей теме идёт мысль, что никакой БД нет и в помине, что все данные загружены в память приложения, и там оно с этими данными и работает. Поневоле
хочется изречь нечто типа "Батюшка, вы уж определитесь, ...".

Проблема в том, что все очень умные, и задачу 3 класса пытаются решать интегралами и другими вузовскими приемами...
Задача академическая.

Я понял так.
В памяти есть большой объеме информации, как туда она попала не интересует, рандомный генератор делает...
Надо эмулировать работу с этой информацией как с БД: поиск, добавление и т.д.
Использовать деревья, определить эффективные (из какого-то набора) методом тестирования.

Цитата Black_Dragon @ 25.06.20, 05:55

Я понял так.
В памяти есть большой объеме информации, как туда она попала не интересует, рандомный генератор делает...
Надо эмулировать работу с этой информацией как с БД: поиск, добавление и т.д.
Использовать деревья, определить эффективные (из какого-то набора) методом тестирования.

Гм... рождается очередная резидентная БД? тогда мои соболезнования.

Цитата Akina @ 25.06.20, 06:07

Гм... рождается очередная резидентная БД? тогда мои соболезнования.

Дело не в БД, а применить деревья на чем-нибудь, сравнить их.

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

Дело не в БД, а применить деревья на чем-нибудь, сравнить их.

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

Автомобиль тут формальность. Разноплановый набор данных, не более.
Например, ВИН или Госномер полностью уникальный ИД, не особо интересен. Кроме случая Госномера для поиска частичного соответствия.
Другие парамметры менее уникальные.

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

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