Index tuning as part of database tuning is the task of selecting and creating indexes with the goal of reducing query processing times. However, in dynamic environments with various ad-hoc queries it is difficult to identify potentially useful indexes in advance. In this paper, based on previous research regarding automatic index creation at runtime we point out the need for new indexing schemes suitable for self-tuning. Based on problems with previous approaches we describe the key concepts, which are sparse and partial indexing, usage-balanced instead of data-balanced structures, and dynamic resource assignment. We illustrate the approach by a simple index structure, which provides adaptability as well as improved access characteristics. Furthermore, we will outline key tasks to introduce according concepts in future DBMS.