MTREE DATA STRUCTURE FOR STORAGE, INDEXING AND RETRIEVAL OF INFORMATION

Data storage space and data access time are significantly decreased by utilizing a tree structure to store data in memory. Only one copy of each data element common to different data units is stored. Each data element is stored in a node that has a next pointer and an alternate pointer. The next pointer points to a list of alternatives for the next sequential element of the data unit. The alternate pointer defines that list of alternatives. Thus, a progression of next pointers and alternate pointers corresponds to a unique data unit. Associated with each data unit is one or more identifiers, which tie the data unit to data units in another trees or to external objects. The last alternate pointer in an alternative list points back to the preceding element of the data unit in order to reconstruct a data unit from the identifier. Nodes in memory that are not currently being used in the tree are linked together to form a list of free nodes.