Requirements
A supporting structure for indexing of buffer data needs to be created. This structure needs to be able to index elements and provide an easy querying system, that can support current use cases of inspectIT. Furthermore, the indexing structure needs to hold week references to the elements, so that these elements are garbage collected when they are evicted from the buffer. Structure also has to be able to clean it self, meaning that references to weak references have to be destroyed.
Approach
The indexing has a tree structure. It is consisted of several levels, where each level has several branches and indexes the element based on element's properties. On the last level the weak references are mapped, thus from the last level objects are access-able. This would allow fast searching for the elements, especially if a searching query has defined a property for each level. An example is shown in the picture below:
Realization
The model used for realization is same as the Composite design pattern (Composite pattern). ITreeComponent defines operations that are needed for the indexing structure, so that all tree components are able to perform them.
Branch and IBranchIndexer
Branch is a tree component that has references to other tree components (same as Composite in Composite pattern). This means that branch represents one level of indexing. To be able to correctly index elements and perform queries, branch uses functionality of IBranchIndexer. Different implementation of this interface index elements on different properties. Thus, the branch indexer is used when branch needs to determine right "next level" branch for the indexing element. The same stands for the searching of elements.
IBranchIndexer is also responsible to know which indexer has to be used on the next level. This is needed when tree is empty, and new elements should be indexed into branches/leafs that have not yet been created. Currently implemented indexers are:
- Platfrom indexer - creates one tree component for each agent (each platfrom ident)
- Sensor type indexer - creates one tree component for each sensor type (each sensor type ident)
- Method indexer - creates one tree component for each method (each method ident)
- Object type indexer - creates one tree component per class, meaning that all objects of the same class will be in one branch/leaf
- Timestamp indexer - creates one tree component for every minute (only when needed), and indexes the elements by their time stamp
Leaf
Leaf is the element on the deepest level in the tree. All objects that are referenced in one leaf have the same indexing path.
LeafingBranch
LeafingBranch is the special type of branch that has an extended functionality to hold references to all objects that are indexed in this branch. This means that same element can be referenced from one leaf, but also many leafing branches. The advantage is speeding up the queries that need to traverse through whole branch because query does not define property for lower level branching. In this case, leafing brunch can just return results from its own leaf, with no need to look into all tree components below it. The disadvantage is the memory size needed for the indexing structure, because it rises linearly depending on the number of levels that use leaf branch.
During tests it was concluded that the best trade-off between query speed and indexing structure size is achieved by following:
- Normal branches need to be used for branches in the upper indexing levels and in branches that have a small number of referring tree components. A good example would be branch that would use platform indexer.
- Leafing branches need to be used for branches in the lower indexing levels and in branches that have a big number of referring tree components. A good example would be branch that would use time stamp indexer.
Querying the indexing tree
Please refer to Querying the indexed tree for information and specification about indexing tree querying system.
Custom root branch proposal
This root branch proposal should provide the best results when buffer is responsible for holding all inspectIT default data object types.
