# Efficient data structure for multidimensional searching on intervals and keys

I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (like {'a', 'c'}). I want to be able to do efficient indexing in both ways such as queries like the following are computationally balanced:

• "give me the keys that appear in the interval frame of 1 and 5" or
• "give me the intervals where 'a' exists"

“Computationally balanced” means that there is no 'hierarchy' e.g. from sorting and secondly to be as much redundant as possible.

Also I want to be able to efficiently union/intersect two databases based on intervals (and keys of course).

Here are some notes from approaches I've tried but do not seem to do the trick:

1. Interval-Set/Interval-Map (Boost): Information is not at all redundant:
(1, 5)->'A' and (4, 8)-> 'B', will be stored as
(1, 4)->{'A'}, (4,5)->{'A', 'B'} and (5, 8)->{'B'}.
It is also hierarchical.
2. R-trees (Boost): Everything is geometrical.
On the contrary key '1' is not closer to key '2' than key '3'.
Complicated search queries do not appear feasible.
Things are distinguished between keys and value.
• "Approaches ... do not seem to do the trick". Can you explain how or why they do not do the trick? – Apass.Jack Dec 11 '18 at 19:29