Multidimensional Mtree Tree
The organization of data in programming is of decisive importance. There are not so many ways to organize data. Among the various data structures, a special place is occupied by the organization of data in the form of a tree.
This is the most common organization of data and all other data structures are easily modeled on it. Arrays, queues, stacks are easily implemented on the tree. Many years of experience in creating information systems have confirmed to me the universality of this data structure. But the main advantage of the tree is manifested in the modeling of connections between entities. Of course the tree is not the only or even the most common way to do it. In the SQL model, this is done in the form of tables. The method, though the most common, but not the most optimal. In this case, efficiency is sacrificed to the data manipulation language. In this case, there are various normal forms for the abnormal organization of data. A tree is a big winner compared to a set of tables. The tree of course is not so much a way to store data, although it is decisive in terms of efficiency in accessing data, as it is a way to access data. The tree must have an iterator iterating over the descendants of the tree node, be able to find the next descendant at this level and find the parent of this node. Any data structure, even a simple sequential file, that has these access methods can be treated as a tree. It would seem that still need to complete happiness? But it turned out that in some cases this structure is not enough, which turned out to be a revelation for me. I had to come up with an extension of the tree. We call this extension the tree of the Nth order Mtree. This is such a tree, each node of which, in addition to data and direct descendants, also contains N - branches. The 2nd order Mtree tree node contains 2 branches, primary and alternative. Such a structure is necessary when the main branches reflect the relationship of entities, and the entities themselves are hierarchical objects.
A mtree tree can be constructed similarly to a btree tree. Btree tree is a very effective structure widely used in many IT projects. In particular, this structure implements data in MUMPS systems, the merits of which I wrote in a previous post . The impact of this data organization on MUMPS is hard to overestimate. The main properties of this language are determined precisely by the hierarchical organization of data in the form of a Btree tree. And even the most deprecated by the programming community is the lack of data declaring in the language, due precisely to the wooden organization of data. I have little idea how to declare data in different nodes of the tree. And to assume that all the nodes of the tree will have the same type is very strange. No other language has such a close connection between a language and the organization of data in it.
But the hierarchical structure was not perfect. The data structure on it is quite convenient to display, but then only simple variables can be stored in the nodes of such a tree. And if you need to store the properties of objects? And objects themselves can be objects, which creates a new hierarchy. So need a new data structure. Mtree tree of the 2nd order.
')
Attempting to extend MUMPS to object storage led me to create a second-order Mtree data structure. And on the basis of this tree to create the MSH language about which I wrote in another previous post .
Such a tree solves the problem of storing the object and its properties in the tree node. The main hierarchy reflects relations between objects, and alternative branches contain object properties. This is not the only application of multidimensional trees. On such a structure it is easy to build a file system. You can store directory names in the main hierarchy, and file names and links to busy blocks in alternative branches. DOM browsers just as easily falls on this structure. I think there are other ways to use multidimensional trees.
To invent a structure and language is not all. Need implementation of these ideas. The first stage of the implementation of the Mtree tree of the 2nd order I did. Programming as a whole is complete and primitive debugging is done, but more comprehensive base testing is needed. Programming is done in the C language in the Linux system NetBeans IDE. If anyone has a desire to help, please write to the email.
This is the most common organization of data and all other data structures are easily modeled on it. Arrays, queues, stacks are easily implemented on the tree. Many years of experience in creating information systems have confirmed to me the universality of this data structure. But the main advantage of the tree is manifested in the modeling of connections between entities. Of course the tree is not the only or even the most common way to do it. In the SQL model, this is done in the form of tables. The method, though the most common, but not the most optimal. In this case, efficiency is sacrificed to the data manipulation language. In this case, there are various normal forms for the abnormal organization of data. A tree is a big winner compared to a set of tables. The tree of course is not so much a way to store data, although it is decisive in terms of efficiency in accessing data, as it is a way to access data. The tree must have an iterator iterating over the descendants of the tree node, be able to find the next descendant at this level and find the parent of this node. Any data structure, even a simple sequential file, that has these access methods can be treated as a tree. It would seem that still need to complete happiness? But it turned out that in some cases this structure is not enough, which turned out to be a revelation for me. I had to come up with an extension of the tree. We call this extension the tree of the Nth order Mtree. This is such a tree, each node of which, in addition to data and direct descendants, also contains N - branches. The 2nd order Mtree tree node contains 2 branches, primary and alternative. Such a structure is necessary when the main branches reflect the relationship of entities, and the entities themselves are hierarchical objects.
A mtree tree can be constructed similarly to a btree tree. Btree tree is a very effective structure widely used in many IT projects. In particular, this structure implements data in MUMPS systems, the merits of which I wrote in a previous post . The impact of this data organization on MUMPS is hard to overestimate. The main properties of this language are determined precisely by the hierarchical organization of data in the form of a Btree tree. And even the most deprecated by the programming community is the lack of data declaring in the language, due precisely to the wooden organization of data. I have little idea how to declare data in different nodes of the tree. And to assume that all the nodes of the tree will have the same type is very strange. No other language has such a close connection between a language and the organization of data in it.
But the hierarchical structure was not perfect. The data structure on it is quite convenient to display, but then only simple variables can be stored in the nodes of such a tree. And if you need to store the properties of objects? And objects themselves can be objects, which creates a new hierarchy. So need a new data structure. Mtree tree of the 2nd order.
')
Attempting to extend MUMPS to object storage led me to create a second-order Mtree data structure. And on the basis of this tree to create the MSH language about which I wrote in another previous post .
Such a tree solves the problem of storing the object and its properties in the tree node. The main hierarchy reflects relations between objects, and alternative branches contain object properties. This is not the only application of multidimensional trees. On such a structure it is easy to build a file system. You can store directory names in the main hierarchy, and file names and links to busy blocks in alternative branches. DOM browsers just as easily falls on this structure. I think there are other ways to use multidimensional trees.
To invent a structure and language is not all. Need implementation of these ideas. The first stage of the implementation of the Mtree tree of the 2nd order I did. Programming as a whole is complete and primitive debugging is done, but more comprehensive base testing is needed. Programming is done in the C language in the Linux system NetBeans IDE. If anyone has a desire to help, please write to the email.
Source: https://habr.com/ru/post/259855/
All Articles