Semistructured data contains many complex relationships between data
items; morever, the structure of these relationships is irregular and
can frequently change. Queries over such data navigate these
relationships via path expressions. Our solution is based on encoding
paths as strings, and inserting those strings into a special index
that is highly optimized for long and complex keys. This provides the
flexibility needed to query and manage semistructured data without
sacrificing high performance. We describe the Index Fabric, an
indexing structure that provides the efficiency and flexibility we
need. The Index Fabric contains "raw paths," paths that can be used to
optimize ad hoc queries over semistructured sources, and "refined
paths," indexing paths optimized for particular queries.  Although we
can use knowledge about the queries and structure of the data to
create refined paths, no such a priori knowledge is needed for raw
paths. A performance study shows that our techniques, when implemented
on top of a commercial relational database system, outperform the more
traditional approach of using the commercial system's native indexing
mechanism to query the XML.