In tegenstelling tot de vorige poster, denk ik niet dat je O(log n)-complexiteit kunt krijgen door naïeve indexering te gebruiken. Laten we bijvoorbeeld eens kijken naar mongodb. Je zou twee indexen kunnen definiëren (voor begin- en eindeigenschappen van de bereiken), maar mongodb zal er maar één gebruiken om een bepaalde vraag op te lossen. Het zal dus niet werken. Als u nu een enkele samengestelde index gebruikt met zowel begin- als eindeigenschappen van de bereiken, zal de complexiteit logaritmisch zijn om het eerste bereik te vinden dat moet worden gecontroleerd, maar dan wordt het lineair om het laatste bereik te vinden dat overeenkomt met de zoekopdracht. De complexiteit in het slechtste geval is O(n), en je hebt het wanneer alle opgeslagen bereiken je invoer overlappen.
Even terzijde, met behulp van Redis gesorteerde set kun je een gesorteerde index emuleren (met O (log n) complexiteit) als je weet wat je doet. Redis is iets meer dan een eenvoudige sleutel-waardeopslag. Redis-gesorteerde sets worden geïmplementeerd met behulp van een lijst die kan worden overgeslagen, en zowel de score als de waarde worden gebruikt om items te vergelijken.
Om dit soort problemen op te lossen, is een speciale indexeringsstructuur nodig. Misschien wil je eens kijken naar:
http://en.wikipedia.org/wiki/Segment_treeofhttp://en.wikipedia.org/wiki/Interval_tree
Als het gaat om snelheid over ruimte, kan het interessant zijn om de index af te vlakken. Laten we bijvoorbeeld de volgende bereiken bekijken (alleen gehele getallen gebruiken om de discussie te vereenvoudigen):
A 2-8
B 4-6
C 2-9
D 7-10
Er kan een dunne structuur worden gebouwd die niet-overlappende segmenten indexeert.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Elk item bevat de ondergrens van een niet-overlappend segment als de sleutel, en de lijst of reeks overeenkomende bereiken als een waarde. Invoer moet worden geïndexeerd met behulp van een gesorteerde container (boom, lijst overslaan, btree, enz ...)
Om de bereiken te vinden die overeenkomen met 5, zoeken we naar de eerste invoer die lager is dan of gelijk is aan 5 (in dit voorbeeld is dit 4) en de lijst met bereiken wordt gegeven ( [A C B] )
Met deze datastructuur is de complexiteit van de queries eigenlijk O(log n). Het is echter niet triviaal (en duur) om het te bouwen en te onderhouden. Het kan worden geïmplementeerd met zowel mongodb als Redis.
Hier is een voorbeeld met 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"