Противно на предишния плакат, не мисля, че можете да получите O(log n) сложност, като използвате наивно индексиране. Нека разгледаме mongodb например. Можете да дефинирате два индекса (за начални и крайни свойства на диапазоните), но mongodb ще използва само един за решаване на дадена заявка. Така че няма да работи. Сега, ако използвате единичен съставен индекс, включващ както началните, така и крайните свойства на диапазоните, сложността ще бъде логаритмична за намиране на първия диапазон за проверка, но след това ще стане линеен за намиране на последния диапазон, съответстващ на заявката. Сложността в най-лошия случай е O(n) и я имате, когато всички съхранени диапазони се припокриват във вашия вход.
От друга страна, с помощта на сортиран набор на Redis можете да емулирате сортиран индекс (с O(log n) сложност), ако знаете какво правите. Redis е малко повече от просто хранилище на ключ-стойност. Сортираните набори на Redis се реализират с помощта на списък за пропускане и както резултатът, така и стойността се използват за сравняване на елементи.
За решаването на този вид проблем е необходима специална структура за индексиране. Може да искате да разгледате:
http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree
Ако проблемът е скоростта над пространството, тогава може да е интересно да изравним индекса. Например, нека разгледаме следните диапазони (използвайки само цели числа, за да опростим дискусията):
A 2-8
B 4-6
C 2-9
D 7-10
Може да се изгради рядка структура, индексираща неприпокриващи се сегменти.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Всеки запис съдържа долната граница на незастъпващ се сегмент като ключ и списъка или набора от съвпадащи диапазони като стойност. Записите трябва да бъдат индексирани с помощта на сортиран контейнер (дърво, списък за пропускане, btree и т.н. ...)
За да намерим диапазоните, съответстващи на 5, търсим първия запис, който е по-нисък или равен на 5 (в този пример ще бъде 4) и се предоставя списък с диапазони ( [A C B] )
С тази структура от данни сложността на заявките наистина е O(log n). Въпреки това не е тривиално (и скъпо) да го изградите и поддържате. Може да се реализира както с mongodb, така и с Redis.
Ето пример с 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"
