Redis eller Mongo for at afgøre, om et tal falder inden for intervaller?

I modsætning til den forrige plakat, tror jeg ikke, man kan få O(log n) kompleksitet ved at bruge naiv indeksering. Lad os overveje mongodb for eksempel. Du kan definere to indekser (for start- og slutegenskaber for områderne), men mongodb vil kun bruge et til at løse en given forespørgsel. Så det vil ikke virke. Hvis du nu bruger et enkelt sammensat indeks, der involverer både start- og slutegenskaber for områderne, vil kompleksiteten være logaritmisk for at finde det første område, der skal kontrolleres, men så bliver det lineært for at finde det sidste område, der matcher forespørgslen. Den værste kompleksitet er O(n), og du har den, når alle de lagrede områder overlapper dit input.

Som en sidebemærkning kan du ved at bruge Redis sorteret sæt efterligne et sorteret indeks (med O(log n) kompleksitet), hvis du ved, hvad du gør. Redis er lidt mere end et simpelt nøgleværdilager. Redis-sorterede sæt implementeres ved hjælp af en overspringsliste, og både score og værdi bruges til at sammenligne varer.

For at løse denne form for problemer er der behov for en dedikeret indekseringsstruktur. Du ønsker måske at se på:

http://en.wikipedia.org/wiki/Segment_treeorhttp://en.wikipedia.org/wiki/Interval_tree

Hvis det drejer sig om hastighed over rummet, kan det være interessant at udjævne indekset. Lad os f.eks. overveje følgende intervaller (bruger kun heltal for at forenkle diskussionen):

A 2-8
B 4-6
C 2-9
D 7-10
 

En sparsom struktur, der indekserer ikke-overlappende segmenter, kan bygges.

0  []
2  [A C]
4  [A C B]
7  [A C D]
9  [C D]
10 [D]
11 []
 

Hver post indeholder den nedre grænse for et ikke-overlappende segment som nøglen og listen eller sættet af matchende områder som en værdi. Indgange skal indekseres ved hjælp af en sorteret beholder (træ, overspringsliste, btræ osv. ...)

For at finde intervallerne, der matcher 5, leder vi efter den første post, som er lavere eller lig med 5 (det vil være 4 i dette eksempel), og listen over intervaller er angivet ( [A C B] )

Med denne datastruktur er kompleksiteten af ​​forespørgslerne virkelig O(log n). Det er dog ikke trivielt (og dyrt) at bygge og vedligeholde det. Det kan implementeres med både mongodb og Redis.

Her er et eksempel med Redis: