Организация данных в программировании имеет определяющее значение. Способов организации данных не так уж много. Среди различных структур данных особое место занимает организация данных в виде дерева.
Это наиболее общая организация данных и на ней легко моделируются все остальные структуры данных. Массивы, очереди, стеки легко реализуются на дереве. Многолетний опыт создания информационных систем подтвердил мне универсальность этой структуры данных. Но основное достоинство дерева проявляется при моделировании связей между сущностями. Конечно дерево не единственный и даже не самый распространенный способ это делать. В 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.
Это наиболее общая организация данных и на ней легко моделируются все остальные структуры данных. Массивы, очереди, стеки легко реализуются на дереве. Многолетний опыт создания информационных систем подтвердил мне универсальность этой структуры данных. Но основное достоинство дерева проявляется при моделировании связей между сущностями. Конечно дерево не единственный и даже не самый распространенный способ это делать. В 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.
