ADAPTATION OF RADIX TREES FOR INDEXING SEMISTRUCTURED DATA
In semi-structured data management systems there is acute problem of searching in large data sets. During search implementation, considerable number of disk operations is being performed, which inevitably leads to a rapid depletion of computing resources database with the increase of queries number. To solve this problem, we propose to use Radix tries with a modified multi-layer structure for building the search index. Such structure will allow performing not more than one disk operation for each index layer. The number of layers in the resultant structure will depend on the amount of data and the degree of heterogeneity and only in rare cases will exceed 3. Multi-level structure can be easily cached and allow to reduce the number of disk operations to one per one search query. The resulting structure allows avoiding disadvantages of unbalanced Radix tries and getting a quick and compact search index for use in wide range of semi-structured data management systems.