This article describes strategies devised to improve the efficiency of two classical index data structures for parallel textual databases. The design and cost evaluation is effected on top of the bulk-synchronous model of parallel computing. This allows us to compare different alternative sunder the same framework in a way which is independent of programming details and architecture of the parallel machine. Our interest is on query processing upon cluster of PCs, and thereby we focus on communication and synchronization optimization