Term for index-like data structures
These are sometimes called (static) online data structures or online query data structures. It's actually rather hard to find a definition written down and the notion is "soft", in the sense that you can reasonably argue that almost anything would qualify especially if you allow updating. Here's one definition and mini-taxonomy:


  Online data structures support query operations in a continous manner. When the data items do not change and the data strucuture can be preprocessed before any queries are made, the data structure is known as static. When the data structure supports insertions and deletions of items, intermixed with the queries, the data structure is called dynamic.


The term online algorithm is used with a related meaning. It seems to be more widespread (as a term) than its counterpart for data structures. Since the query is the stuff/input that's online in your case, "data structure for online query" is more explicit; searching this as an entire phrase doesn't find much, but as nearby terms you'll get relevant hits e.g. from books [1] [2] [3] [4] etc. Likewise one can speak of "data structure" for "online updating".