Организация данных в программировании имеет решающее значение.
Способов организации данных не так много.
Среди различных структур данных особое место занимает организация данных в виде дерева.
Это наиболее распространенная организация данных, и на ее основе можно легко смоделировать все остальные структуры данных.
Массивы, очереди, стеки легко реализуются в дереве.
Многолетний опыт создания информационных систем подтвердил мне универсальность этой структуры данных.
Но основное преимущество дерева проявляется при моделировании связей между сущностями.
Конечно, дерево – не единственный и даже не самый распространенный способ сделать это.
В модели SQL это делается в виде таблиц.
Способ хоть и самый распространенный, но не самый оптимальный.
В этом случае эффективность приносится в жертву языку манипулирования данными.
При этом возникают различные нормальные формы ненормальной организации данных.
Дерево намного лучше по сравнению с набором таблиц.
Дерево, конечно, не столько способ хранения данных, хотя это и имеет решающее значение с точки зрения эффективности при доступе к данным, сколько способ доступа к данным.
Дерево должно иметь итератор для перебора дочерних элементов узла дерева, иметь возможность найти следующего дочернего элемента на этом уровне и найти родителя данного узла.
Любую структуру данных, даже простой последовательный файл, имеющую эти методы доступа, можно рассматривать как дерево.
Казалось бы, что еще нужно для полного счастья? Но оказалось, что в некоторых случаях этой структуры недостаточно, что оказалось для меня откровением.
Пришлось придумать продолжение к дереву.
Назовем это расширение Mtree N-го порядка.
Это дерево, в котором каждый узел помимо данных и прямых потомков содержит еще N ветвей.
Узел Mtree 2-го порядка содержит две ветви: основную и альтернативную.
Такая структура необходима, когда основные ветви отражают взаимоотношения сущностей, а сами сущности являются иерархическими объектами.
Дерево Mtree может быть построено аналогично дереву Btree. Дерево Btree — очень эффективная структура, широко используемая во многих ИТ-проектах.
В частности, эта структура используется для реализации данных в MUMPS-системах, о преимуществах которых я писал в разделе предыдущий пост .
Влияние такой организации данных на MUMPS невозможно переоценить.
Основные свойства этого языка определяются именно иерархической организацией данных в виде Btree-дерева.
И даже отсутствие объявления данных в языке, которое больше всего осуждается сообществом программистов, связано именно с деревянной организацией данных.
Мне трудно понять, как данные могут быть объявлены в разных узлах дерева.
И очень странно предполагать, что все узлы дерева будут одного типа.
Ни один другой язык не имеет такой тесной связи между языком и организацией данных внутри него.
Но иерархическая структура оказалась не идеальной.
На нем довольно удобно отображать структуру данных, но тогда в узлах такого дерева можно хранить только простые переменные.
Что делать, если вам нужно сохранить свойства объекта? А сами объекты могут быть объектами, что порождает новую иерархию.
Это означает, что необходима новая структура данных.
Мдерево 2-го порядка.
Попытка расширить MUMPS до объектного хранилища привела меня к созданию структуры данных Mtree 2-го порядка.
И на основе этого дерева создать язык MSH, о котором я писал в другом предыдущий пост .
Такое дерево решает проблему хранения объекта и его свойств в узле дерева.
Основная иерархия отражает связи между объектами, а альтернативные ветви содержат свойства объекта.
Это не единственное применение многомерных деревьев.
На такой структуре легко построить файловую систему.
Основная иерархия может хранить имена каталогов, а альтернативные ветви могут хранить имена файлов и ссылки на занятые блоки.
DOM браузеров так же легко соответствует этой структуре.
Я думаю, что многомерным деревьям найдутся и другие применения.
Придумать структуру и язык – это еще не все.
Эти идеи необходимо реализовать.
Я выполнил первый этап реализации дерева Mtree 2-го порядка.
Программирование в целом завершено и примитивная отладка проведена, но требуется более комплексное тестирование базы.
Программирование выполнялось на языке C с использованием Linux IDE NetBeans. Если кто-то хочет помочь, напишите мне на почту.
Теги: #структуры данных #языки программирования #MUMPS #базы данных #разработка веб-сайтов #компиляторы #ООП #большие данные
-
Orkut Станет Ближе К «Офлайну»
19 Oct, 24 -
Проекционное Моделирование
19 Oct, 24 -
Для Поиска Теперь Требуется Авторизация
19 Oct, 24
