Na rozdíl od předchozího plakátu si nemyslím, že můžete získat složitost O(log n) pomocí naivního indexování. Vezměme si například mongodb. Můžete definovat dva indexy (pro počáteční a koncové vlastnosti rozsahů), ale mongodb použije k vyřešení daného dotazu pouze jeden. Takže to nepůjde. Pokud nyní použijete jeden složený index zahrnující počáteční i koncové vlastnosti rozsahů, bude složitost hledání prvního rozsahu ke kontrole logaritmická, ale pak bude lineární při nalezení posledního rozsahu vyhovujícího dotazu. Nejhorší případ složitosti je O(n) a máte ho, když se všechny uložené rozsahy překrývají s vaším zadáním.
Na okraj, pomocí seřazené sady Redis můžete emulovat seřazený index (se složitostí O(log n)), pokud víte, co děláte. Redis je trochu víc než jen jednoduchý obchod s páry klíč–hodnota. Seřazené sady Redis jsou implementovány pomocí seznamu přeskočení a k porovnání položek se používá skóre i hodnota.
K vyřešení tohoto druhu problému je zapotřebí specializovaná struktura indexování. Možná se budete chtít podívat na:
http://cs.wikipedia.org/wiki/Segment_treeorhttp://cs.wikipedia.org/wiki/Interval_tree
Pokud jde o rychlost v prostoru, pak může být zajímavé index zploštit. Uvažujme například následující rozsahy (pro zjednodušení diskuse použijte pouze celá čísla):
A 2-8
B 4-6
C 2-9
D 7-10
Lze vytvořit řídkou strukturu indexující nepřekrývající se segmenty.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Každý záznam obsahuje spodní hranici nepřekrývajícího se segmentu jako klíč a seznam nebo sadu odpovídajících rozsahů jako hodnotu. Položky by měly být indexovány pomocí setříděného kontejneru (strom, seznam přeskočení, bstrom atd...)
Abychom našli rozsahy odpovídající 5, hledáme první položku, která je nižší nebo rovna 5 (v tomto příkladu to bude 4) a poskytneme seznam rozsahů ( [A C B] )
S touto datovou strukturou je složitost dotazů skutečně O(log n). Není však triviální (a nákladné) jej postavit a udržovat. Lze jej implementovat s mongodb i Redis.
Zde je příklad s 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"