W przeciwieństwie do poprzedniego plakatu, nie sądzę, że można uzyskać złożoność O(log n) za pomocą naiwnego indeksowania. Rozważmy na przykład mongodb. Możesz zdefiniować dwa indeksy (dla właściwości początkowych i końcowych zakresów), ale mongodb użyje tylko jednego do rozwiązania danego zapytania. Więc to nie zadziała. Teraz, jeśli użyjesz pojedynczego indeksu złożonego obejmującego zarówno właściwości początkowe, jak i końcowe zakresów, złożoność będzie logarytmiczna, aby znaleźć pierwszy zakres do sprawdzenia, ale wtedy uzyska się liniową, aby znaleźć ostatni zakres pasujący do zapytania. Najgorsza złożoność to O(n) i masz ją, gdy wszystkie przechowywane zakresy nakładają się na dane wejściowe.
Na marginesie, używając posortowanego zestawu Redis, możesz emulować posortowany indeks (ze złożonością O(log n)) jeśli wiesz, co robisz. Redis to coś więcej niż zwykły magazyn klucz-wartość. Posortowane zestawy Redis są implementowane przy użyciu listy pomijania, a zarówno wynik, jak i wartość są używane do porównywania elementów.
Aby rozwiązać ten problem, potrzebna jest dedykowana struktura indeksowania. Możesz rzucić okiem na:
http://en.wikipedia.org/wiki/Drzewo_segmentulubhttp://en.wikipedia.org/wiki/Drzewo_przedziałów
Jeśli problemem jest prędkość w przestrzeni, może być interesujące spłaszczenie indeksu. Rozważmy na przykład następujące zakresy (używając tylko liczb całkowitych, aby uprościć dyskusję):
A 2-8
B 4-6
C 2-9
D 7-10
Można zbudować rzadką strukturę indeksującą nienakładające się segmenty.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Każdy wpis zawiera dolną granicę nienakładającego się segmentu jako klucz oraz listę lub zestaw pasujących zakresów jako wartość. Wpisy powinny być indeksowane za pomocą posortowanego kontenera (drzewo, lista pomijanych, btree, itp.)
Aby znaleźć zakresy pasujące do 5, szukamy pierwszego wpisu, który jest niższy lub równy 5 (w tym przykładzie będzie to 4) i podana jest lista zakresów ( [A C B] )
Przy takiej strukturze danych złożoność zapytań wynosi w rzeczywistości O(log n). Jednak zbudowanie i utrzymanie go nie jest trywialne (i drogie). Można go zaimplementować zarówno z mongodb, jak i Redis.
Oto przykład z 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"
