This presentation goes in depth into some indexing structures but doesn't go into XML indexes (or tree indexes). By tree indexes I don't mean B-trees and the like, which are used for indexing single-dimensional relational data, or even multi-dimensional index structures like R-trees. I mean indexing tree-structured data like XML or other trees.
In my search I have only encountered a few papers:
- Covering Indexes for Branching Path Queries
- Indexing XML Data Stored in a Relational Database
- Efficient Processing of XPath Queries Using Indexes
- Index Structures for Path Expressions
- Indexing techniques for queries on nested objects
- The Lorel Query Language for Semistructured Data
- Indexing Semistructured Data
- Index nesting – an efficient approach to indexing in object-oriented databases
Some stuff seems to be under the category of "semistructured data", but I am looking for trees.
Specifically I would like to see indexes for:
- Exact paths in a tree.
- Exact subtrees in a tree.
- Inexact paths
- Inexact subtrees.
- N-number of branches of a tree.
Examples of these structures include:
1 -- 2 -- 3 -- 4 1 / \ 2 6 | | 3 7 / \ 4 5 1 -- * -- 3 -- (attr != "foo") -- 5 1 / \ 2 * | | * 8 / \ 4 (attr != "foo") | 6 1 / \ 2 6:(0..n of nodes) | | 3 7 / \ 4 5
I have found some stuff on querying for these structures, but not on specifically indexes for speeding up queries on these sorts of structures. I am basically looking for the equivalent of a B-tree or R-tree but for trees, like a T-tree or something.
One of the papers says:
Indexing techniques in relational or object-oriented databases depend on a fixed schema based on a known, strongly typed class hierarchy. Therefore, such techniques are not directly applicable in XML data.
Some papers refer to "traditional XML indexing methods", but I haven't seen those listed out or explained (and not sure if they match the 5 examples above).
Wondering if one could just list the names of such index structures, or perhaps links to a paper that describes them, for further checking.