One of the key issues in information systems is to provide a fast and reliable access to data. This is true for conventional databases and information systems as well as for spatial or multimedia ones. Main tools for such aim are indices, among others. Search and reasoning operations using indices and structured data require a specific support on logical and physical level. A years of research have resulted in a great variety of multidimensional data structures and indices (access methods also). This paper overviews recent trends in the area of multidimensional, spatial, temporal indices and data structures, discusses their principles and implementation issues. The special emphasis is given to research, multimedia and spatial information systems.