The integration of heterogeneous systems is still an evolving research area. Due to the complexity of integration processes, there are challenges for the optimization of integration processes. Message-based integration systems, like EAI servers and workflow process engines, are mostly document-oriented, using XML technologies to achieve suitable data independence from the different and particular proprietary data representations of the supported external systems. However, such an approach causes large costs for single-value evaluations within the integration processes. At this point, message indexing, adapting extended database technologies, can be applied in order to achieve better performance. In this paper, we introduce our message indexing structure MIX and discuss and evaluate immediate as well as deferred indexing concepts.