Ao contrário do pôster anterior, não acho que você possa obter complexidade O(log n) usando indexação ingênua. Vamos considerar o mongodb, por exemplo. Você pode definir dois índices (para propriedades de início e fim dos intervalos), mas o mongodb usará apenas um para resolver uma determinada consulta. Então não vai funcionar. Agora, se você usar um único índice composto envolvendo as propriedades inicial e final dos intervalos, a complexidade será logarítmica para encontrar o primeiro intervalo a ser verificado, mas ficará linear para encontrar o último intervalo correspondente à consulta. A complexidade do pior caso é O(n), e você a tem quando todos os intervalos armazenados se sobrepõem à sua entrada.
Em uma nota lateral, usando o conjunto classificado do Redis, você pode emular um índice classificado (com complexidade O(log n)) se souber o que faz. O Redis é um pouco mais do que um simples armazenamento de chave-valor. Os conjuntos classificados do Redis são implementados usando uma lista de pular, e tanto a pontuação quanto o valor são usados para comparar itens.
Para resolver esse tipo de problema, é necessária uma estrutura de indexação dedicada. Você pode querer dar uma olhada em:
http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree
Se a preocupação é a velocidade sobre o espaço, então pode ser interessante achatar o índice. Por exemplo, vamos considerar os seguintes intervalos (usando apenas inteiros para simplificar a discussão):
A 2-8
B 4-6
C 2-9
D 7-10
Uma estrutura esparsa indexando segmentos não sobrepostos pode ser construída.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Cada entrada contém o limite inferior de um segmento não sobreposto como chave e a lista ou conjunto de intervalos correspondentes como valor. As entradas devem ser indexadas usando um contêiner classificado (árvore, lista de pulos, btree, etc...)
Para encontrar os intervalos correspondentes a 5, procuramos a primeira entrada que é menor ou igual a 5 (será 4 neste exemplo) e a lista de intervalos é fornecida ( [A C B] )
Com essa estrutura de dados, a complexidade das consultas é realmente O(log n). No entanto, não é trivial (e caro) construí-lo e mantê-lo. Ele pode ser implementado com mongodb e Redis.
Aqui está um exemplo com Redis:
> rpush range:2 2-8 2-9
(integer) 2
> rpush range:4 2-8 2-9 4-6
(integer) 3
> rpush range:7 2-8 2-9 7-10
(integer) 3
> rpush range:9 2-9 7-10
(integer) 2
> rpush range:10 7-10
(integer) 1
> zadd range_index 0 range:0 2 range:2 4 range:4 7 range:7 9 range:9 10 range:10
(integer) 6
> zrevrangebyscore range_index 5 0 LIMIT 0 1
1) "range:4"
> lrange range:4 0 -1
1) "2-8"
2) "2-9"
3) "4-6"
