Contrariamente al poster precedente, non penso che tu possa ottenere la complessità O (log n) usando l'indicizzazione ingenua. Consideriamo mongodb per esempio. Puoi definire due indici (per le proprietà di inizio e fine degli intervalli), ma mongodb ne utilizzerà solo uno per risolvere una determinata query. Quindi non funzionerà. Ora se usi un singolo indice composto che coinvolge sia le proprietà di inizio che di fine degli intervalli, la complessità sarà logaritmica per trovare il primo intervallo da controllare, ma poi diventerà lineare per trovare l'ultimo intervallo che corrisponde alla query. La complessità del caso peggiore è O(n) e ce l'hai quando tutti gli intervalli memorizzati si sovrappongono al tuo input.
In una nota a margine, usando il set ordinato di Redis puoi emulare un indice ordinato (con complessità O (log n)) se sai cosa fai. Redis è un po' più di un semplice negozio di valori-chiave. Gli insiemi ordinati Redis vengono implementati utilizzando una lista di salto e sia il punteggio che il valore vengono utilizzati per confrontare gli elementi.
Per risolvere questo tipo di problema è necessaria una struttura di indicizzazione dedicata. Potresti voler dare un'occhiata a:
http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree
Se il problema è la velocità nello spazio, potrebbe essere interessante appiattire l'indice. Ad esempio, consideriamo i seguenti intervalli (usando solo numeri interi per semplificare la discussione):
A 2-8
B 4-6
C 2-9
D 7-10
È possibile creare una struttura sparsa che indicizza segmenti non sovrapposti.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Ciascuna voce contiene il limite inferiore di un segmento non sovrapposto come chiave e l'elenco o l'insieme di intervalli corrispondenti come valore. Le voci devono essere indicizzate utilizzando un contenitore ordinato (albero, lista da saltare, btree, ecc...)
Per trovare gli intervalli corrispondenti a 5, cerchiamo la prima voce che è inferiore o uguale a 5 (sarà 4 in questo esempio) e viene fornito l'elenco degli intervalli ( [A C B] )
Con questa struttura dati, la complessità delle query è realmente O(log n). Tuttavia non è banale (e costoso) costruirlo e mantenerlo. Può essere implementato sia con mongodb che con Redis.
Ecco un esempio con 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"
