I motsats till föregående poster tror jag inte att du kan få O(log n) komplexitet genom att använda naiv indexering. Låt oss överväga mongodb till exempel. Du kan definiera två index (för start- och slutegenskaper för intervallen), men mongodb kommer bara att använda ett för att lösa en given fråga. Så det kommer inte att fungera. Om du nu använder ett enda sammansatt index som involverar både start- och slutegenskaper för intervallen, kommer komplexiteten att vara logaritmisk för att hitta det första intervallet att kontrollera, men sedan blir det linjärt för att hitta det sista intervallet som matchar frågan. Det värsta fallet är O(n), och du har det när alla lagrade intervall överlappar din inmatning.
Som en sidoanteckning, med Redis sorterad uppsättning kan du emulera ett sorterat index (med O(log n) komplexitet) om du vet vad du gör. Redis är lite mer än ett enkelt nyckel-värdelager. Redis sorterade uppsättningar implementeras med hjälp av en överhoppningslista, och både poängen och värdet används för att jämföra objekt.
För att lösa denna typ av problem behövs en dedikerad indexeringsstruktur. Du kanske vill ta en titt på:
http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree
Om problemet är hastighet över rymden kan det vara intressant att platta till indexet. Låt oss till exempel överväga följande intervall (med enbart heltal för att förenkla diskussionen):
A 2-8
B 4-6
C 2-9
D 7-10
En gles struktur som indexerar icke överlappande segment kan byggas.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Varje post innehåller den nedre gränsen för ett icke-överlappande segment som nyckel, och listan eller uppsättningen av matchande intervall som ett värde. Poster bör indexeras med en sorterad behållare (träd, överhoppningslista, bträd, etc ...)
För att hitta intervallen som matchar 5 letar vi efter den första posten som är lägre eller lika med 5 (det kommer att vara 4 i det här exemplet) och listan med intervall tillhandahålls ( [A C B] )
Med denna datastruktur är frågornas komplexitet verkligen O(log n). Det är dock inte trivialt (och dyrt) att bygga och underhålla det. Det kan implementeras med både mongodb och Redis.
Här är ett exempel med 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"