Database systems are increasingly being used to manage semistructured
data, which may not have a fixed structure or set of relationships
between data items. Indexes which use tree structures to manage
semistructured data become unbalanced and difficult to parallelize due
to the complex nature of the data. We propose a mechanism by which an
unbalanced vertical tree is managed in a balanced way by additional
layers of horizontal index. Then, the vertical tree can be partitioned
among parallel computing nodes in a balanced fashion. We discuss how
to construct, search and update such a horizontal structure using the
example of a Patricia trie index. We also present simulation results
that demonstrate the speedup offered by such parallelism; for
three-way parallelism, our techniques can provide almost a factor of
three speedup.