Efficient access to data is an attractive topic because of the huge volume of nowadays information. In case of uncertain data, the issue becomes more challenging, since such data are more complex. A main technique for efficient data access is to use indexes. In this paper, we tackle the problem of indexing imperfect structured data where imperfection is managed through the Evidence theory; a generalization of the Bayesian theory. Existing data structures are presented and improved and new structures are introduced. In addition, the methods for constructing and searching data using these structured are presented. To evaluate the efficiency of the presented indexes, we implemented them and conducted extensive experiments on both synthetic and real evidential databases. A final discussion on the results shows on which criteria indexing performances depend.
