Это наиболее общая организация данных и на ней легко моделируются все остальные структуры данных. Массивы, очереди, стеки легко реализуются на дереве. Многолетний опыт создания информационных систем подтвердил мне универсальность этой структуры данных. Но основное достоинство дерева проявляется при моделировании связей между сущностями. Конечно дерево не единственный и даже не самый распространенный способ это делать. В SQL модели это выполняется в виде таблиц. Способ хоть и самый распространенный, но не самый оптимальный. В этом случае эффективность приносится в жертву языку манипулирования данными. При этом возникают различные нормальные формы для ненормальной организации данных. Дерево в сравнении с набором таблиц сильно выигрывает. Дерево конечно это не столько способ хранения данных, хотя это является определяющим по эффективности при обращении к данным, сколько способ доступа к данным. Дерево должно иметь итератор перебора потомков узла дерева, иметь возможность найти следующего потомка на этом уровне и нахождение родителя данного узла. Любая структура данных, даже простой последовательный файл, имеющая эти способы доступа может трактоваться как дерево. Казалось бы что еще нужно для полного счастья? Но оказалось что в некоторых случаях этой структуры недостаточно, что для меня оказалось откровением. Пришлось придумать расширение дерева. Назовем это расширение деревом Mtree N-го порядка. Это такое дерево каждый узел которого кроме данных и прямых потомков содержит еще N — ветвей. Узел дерева Mtree 2-го порядка содержит 2 ветви, основную и альтернативную. Такая структура необходима, когда основные ветви отражают взаимосвязь сущностей, а сами сущности являются иерархическими объектами.
Mtree дерево может быть построено аналогично Btree дереву. Btree дерево очень эффективная структура широко используемая во многих ИТ проектах. В частности на этой структуре реализованы данные в MUMPS системах, о достоинствах которых я писал в предыдущем посте. Влияние этой организации данных на MUMPS трудно переоценить. Основные свойства этого языка обусловлены именно иерархической организацией данных в виде Btree дерева. И даже наиболее осуждаемое программиским сообществом отсутствием в языке декларирование данных, обусловлено именно деревянной организацией данных. Я плохо представляю как можно декларировать данные в различных узлах дерева. А предполагать, что все узлы дерева будут иметь один и тот же тип весьма странно. Ни в одном другом языке нет такой тесной связи между языком и организацией данных в нем.
Но иерархическая структура оказалась не идеальной. Структуру данных на нее отобразить достаточно удобно, но тогда хранить в узлах такого дерева можно только простые переменные. А если надо хранить свойства объектов? А объекты сами могут быть объектами, что порождает новую иерархию. Значит нужна новая структура данных. Дерево Mtree 2-го порядка.
Попытка расширить MUMPS до хранения объектов привела меня к созданию структуры данных Mtree дерева 2-го порядка. И на базе этого дерева создать язык MSH о котором я писал в другом предыдущем посте.
Такое дерево решает проблему хранения в узле дерева объекта и его свойств. Основная иерархия отражает связи между объектами, а альтернативные ветви содержат свойства объекта. Это не единственное применение многомерных деревьев. На такой структуре легко построить файловую систему. В основной иерархии можно хранить имена каталогов, а в альтернативных ветвях имена файлов и ссылки на занятые блоки. DOM браузеров так же легко ложится на эту структуру. Я думаю, что найдутся и другие способы применения многомерным деревьям.
Придумать структуру и язык еще не все. Нужна реализация этих идей. Первый этап реализации Mtree дерева 2-го порядка я сделал. Программирование в целом завершено и примитивная отладка сделана, но необходимо более всестороннее тестирование базы. Программирование выполнено на языке Си в системе Linux IDE NetBeans. Если кто имеет желание помочь, прошу писать на email.
Комментарии (26)
DAiMor
09.06.2015 10:08+5Михаил, вас уже несколько раз коллеги на форуме просили, выложите в отрытый доступ ваши наработки. И тогда возможно найдутся желающие посмотреть и оценить ваши труды. Раз вы не выкладываете в открытый доступ, полагаю вы планируете на этом заработать, в таком случае, скорее всего вам будет сложно, найти помощников в этом нелегком деле.
misha_shar53 Автор
09.06.2015 11:24-5Ну во первых не просили.
Что вы имеете в виду говоря о наработках? MSH не готов, находится в разработке. База как то сделана и сыро отлажена. Нужно тестирование. Я готов ее предоставить тому кто захочет это сделать. Куда я ее мог выложить. Собираюсь я на этом зарабатывать или нет я еще не знаю. До этого еще далеко. Заработать можно только на готовом продукте с развитой инфраструктурой языка. А до этого еще ой как далеко. Вопрос о заработке пока еще не стоит вообще. А просил помочь я только тебя. Рассчитываю что для тестирования базы кто нибудь найдется. Надежда умирает последней. Если захочешь помочь, пиши вышлю проект для тестирования и описание API обращений к базе данных.DAiMor
09.06.2015 11:29+5Выложить можно как это обычно все делают, например на GitHub, и не важно что оно еще сырое.
lair
09.06.2015 11:22+1Нет уж, давайте разберемся.
Это [дерево] наиболее общая организация данных и на ней легко моделируются все остальные структуры данных.
Нет, на дереве не моделируется граф.
Это такое дерево каждый узел которого кроме данных и прямых потомков содержит еще N — ветвей.
Что такое «ветвь»? Чем она отличается от стандартного ребра (из которых в норме состоит граф)?
Такая структура необходима, когда основные ветви отражают взаимосвязь сущностей, а сами сущности являются иерархическими объектами.
Вы хотите сказать, что у вас между вершинами в дереве могут быть ребра, отличные от условных «вверх-вниз»? Поздравляю вас, это больше не дерево, а обычный граф (скорее всего, направленный).misha_shar53 Автор
09.06.2015 11:43-4Дерево уже есть граф.
|Нет, на дереве не моделируется граф.
Если в узел писать ссылки на другие узлы, то вполне моделируется.
|Что такое «ветвь»? Чем она отличается от стандартного ребра (из которых в норме состоит граф)
Ветвь это не ребро а поддерево узлов. Из каждого узла выходит N- поддеревьев.
|Вы хотите сказать, что у вас между вершинами в дереве могут быть ребра, отличные от условных «вверх-вниз»? Поздравляю вас, это больше не дерево, а обычный граф (скорее всего, направленный).
Ребра всегда имеют связь предок-потомки. Для меня не важно является ли эта структура графом или нет, а вот иерархическим деревом она является.lair
09.06.2015 11:47+2Дерево уже есть граф.
Дерево — это частный случай графа.
Если в узел писать ссылки на другие узлы, то вполне моделируется.
… а если в массив писать ссылки вверх и вниз, то им вполне «моделируется» дерево. Только это не модель, это реализация.
Ветвь это не ребро а поддерево узлов. Из каждого узла выходит N- поддеревьев.
Тогда ваша структура в целом — это обычное дерево, в чем пойнт?
Ребра всегда имеют связь предок-потомки.
Только если это ребро в дереве.
Для меня не важно является ли эта структура графом или нет, а вот иерархическим деревом она является.
Если она является деревом, то она по определению является графом.misha_shar53 Автор
09.06.2015 14:04-1|… а если в массив писать ссылки вверх и вниз, то им вполне «моделируется» дерево. Только это не модель, это реализация.
Дерево можно с помощью ссылок смоделировать как угодно. Но в данном случае речь как раз и идет о конкретной реализации структуры данных необходимой для конкретного языка MSH.
|Тогда ваша структура в целом — это обычное дерево, в чем пойнт?
Именно так. А прикол в обработке такого дерева. При работе со связями объекта, мне не нужны свойства объекта. Это разные сущности и их обработка разделена на уровне структуры данных. Обращение к структуре связных объектов отделено от обращения к свойствам объекта.lair
09.06.2015 14:10Вот только никакого «расширения структуры данных» или «многомерного дерева» вы не придумали или не показали. То, о чем вы пишете — самое обычное дерево (если вы, конечно, не ввели в нем циклы). А критерии обхода — дело совершенно пятнадцатое.
misha_shar53 Автор
09.06.2015 14:42-1|А критерии обхода — дело совершенно пятнадцатое
В разработке языка это имеет первостепенное значение. Я не мог построить язык пока не догадался как разделить в одном дереве разные сущности. И это не пятнадцатое дело эта же проблема стоит и в других случаях о которых я писал в статье. В программировании обработка данных является основой алгоритма и от устройства данных зависит эффективность и надежность программ.lair
09.06.2015 14:53«Устройство данных» у вас — обычное дерево. Никаких «многомерных» деревьев не существует, потому что у дерева вообще нет каких-либо координат, потому нет и многомерности.
Чем ваше дерево отличается от обычного, описанного во всех учебниках?
эта же проблема стоит и в других случаях о которых я писал в статье
Какая именно проблема?
Mrrl
09.06.2015 15:05Совсем недавно я пытался разобраться в структуре 2-3-кучи, так там автор использовал именно многомерные деревья. Дерево размерности N у него — массив деревьев размерности N-1 (организованный, как список), и в итоге каждый узел N-мерного дерева содержит и ссылку на деревья-сёстры той же размерности (с которыми он вместе составляет N+1-мерное дерево), и список детей меньших размерностей (точнее, сестёр самого себя, интерпретируемого, как дерево меньшей размерности). Хранить структуру как обычное N-уровневое дерево там нельзя, поскольку нужен быстрый доступ к «угловому» элементу, в итоге получается что-то совершенно страшное — главным образом, из-за того, что поддерево с индексом 0 выглядит не так, как поддеревья с ненулевыми индексами. Но дерево действительно N-мерное. С координатами и направлениями.
misha_shar53 Автор
09.06.2015 15:41|«Устройство данных» у вас — обычное дерево. Никаких «многомерных» деревьев не существует, потому что у дерева вообще нет каких-либо координат, потому нет и многомерности.
У вас в голове координат может и нет. А у меня в реализации очень даже есть. В данном случае у меня построено 2-х мерное дерево. В каждой вершине 2 координаты в которых находятся потомки данного узла.
|Чем ваше дерево отличается от обычного, описанного во всех учебниках?
Отличается структурой узла.
4dmonster
09.06.2015 15:59В каждой вершине 2 координаты в которых находятся потомки данного узла.
А можете пояснить рисунком?
lair
09.06.2015 16:02В каждой вершине 2 координаты в которых находятся потомки данного узла.
… и чем это отличается от «обычного» дерева с помеченными ребрами? (а все это вместе — частный случай графоориентированной БД)lair
09.06.2015 16:10Даже, собственно, помеченные ребра не нужны, можно сразу вершины размечать (поскольку это дерево, ребро+вершину можно схлопнуть до ссылки на вершину).
Mrrl
09.06.2015 16:22Так ведь разметка вершин и обсуждается в следующем комментарии (про типы узлов).
lair
09.06.2015 16:24Тогда это обычное дерево, про что я с начала и говорил.
Mrrl
09.06.2015 16:37Я так понял, что автору эта идея не нравится. И могу согласиться: если у нас есть ровно два типа — узел дерева и свойство, то свойства неплохо сгруппировать в отдельные списки, привязанные к узлу. Уйдёт проблема динамического определения типов, прохода по списку в поисках того, что нужно (только детей или только свойств) — ведь перебирать детей и свойства вперемешку приходится очень редко.
Вот только называть это двумерным деревом (и вообще заострять на этой структуре внимание) что-то не хочется. Действительно, обычное дерево, в узлах или листьях которого лежат объекты+их свойства.
Mrrl
09.06.2015 16:31+2Мне это дерево не кажется двумерным. Если у «свойств» нет своих потомков, образующих поддеревья, то оно просто двуслойное — есть слой дерева объектов, и из каждого объекта ссылка во второй слой, где лежат свойства. Это если свойства нельзя загнать внутрь объектов.
Если же свойства могут иметь потомков, которые могли бы быть как свойствами, так и объектами, то получилось бы дерево с размеченными рёбрами или вершинами.
Честное двумерное дерево — это не больше и не меньше, чем дерево деревьев. Например, его можно использовать, когда объект индексируется двумя ключами. Вполне нормальная структура, но, увы, ничего нового.misha_shar53 Автор
10.06.2015 04:31Любая вершина может иметь N-поддеревьев, значит свойство может быть само объектом.
|Честное двумерное дерево — это не больше и не меньше, чем дерево деревьев. Например, его можно использовать, когда объект индексируется двумя ключами. Вполне нормальная структура, но, увы, ничего нового.
Причем тут ключи? Ключ один.
4dmonster
09.06.2015 12:49Я плохо представляю как можно декларировать данные в различных узлах дерева.
А можно в глобале метаданных описать типы а у узла указывать его тип?misha_shar53 Автор
09.06.2015 14:11|А можно в глобале метаданных описать типы а у узла указывать его тип?
Можно, но зачем? Что это даст? В MUMPS загоняют огромные массивы данных различной структуры и типов, и что на каждое значение хранить его тип? Для чего? Проверяй корректность данных на входе и будет тебе счастье, тем более что тип данных мало что говорит о его корректности.
Zibx
09.06.2015 13:30+1Однажды я b+tree скрестил с b-tree когда в первый раз реализовывал. Такая хрень получилась.
valemak
Увидев название публикации, обрадовался, думал — сейчас зайду и пополню сокровищницу своих знаний об алгоритмах.
Абзацы будут отделены друг от друга пустой строкой, текст проиллюстрирован парой-тройкой «многомерно-древообразных» разноцветных диаграммок, смысловые блоки разбиты с помощью подзаголовков и в качестве бонуса автор ключевые слова выделит жирным шрифтом. Будет, где взгляду зацепиться.
В общем, по тексту статьи можно будет бегло (но результативно) пробежаться «по диагонали», занести в закладки и вернуться к теме многомерных деревьев через час-два, дамы вдумчиво впитать в себя полезный материал. В предвкушении профита, захожу, а тут — шиш. Пичалька.