Redis oder Mongo zur Bestimmung, ob eine Zahl in Bereiche fällt?

Im Gegensatz zum vorherigen Poster glaube ich nicht, dass Sie mit naiver Indizierung eine O(log n)-Komplexität erreichen können. Betrachten wir zum Beispiel mongodb. Sie könnten zwei Indizes definieren (für Start- und Endeigenschaften der Bereiche), aber mongodb verwendet nur einen, um eine bestimmte Abfrage zu lösen. Es wird also nicht funktionieren. Wenn Sie nun einen einzelnen zusammengesetzten Index verwenden, der sowohl Start- als auch Endeigenschaften der Bereiche enthält, ist die Komplexität logarithmisch, um den ersten zu prüfenden Bereich zu finden, aber dann linear, um den letzten Bereich zu finden, der der Abfrage entspricht. Die Komplexität im schlimmsten Fall ist O(n), und Sie haben sie, wenn alle gespeicherten Bereiche Ihre Eingabe überlappen.

Nebenbei bemerkt, mit Redis Sorted Set können Sie einen sortierten Index (mit O(log n)-Komplexität) emulieren, wenn Sie wissen, was Sie tun. Redis ist etwas mehr als ein einfacher Schlüssel-Wert-Speicher. Redis-sortierte Sätze werden mithilfe einer Skip-Liste implementiert, und sowohl die Punktzahl als auch der Wert werden zum Vergleichen von Elementen verwendet.

Um diese Art von Problem zu lösen, ist eine dedizierte Indizierungsstruktur erforderlich. Vielleicht möchten Sie einen Blick auf:

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

Wenn es um Geschwindigkeit statt Speicherplatz geht, kann es interessant sein, den Index zu glätten. Betrachten wir zum Beispiel die folgenden Bereiche (unter Verwendung nur ganzer Zahlen, um die Diskussion zu vereinfachen):

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

Eine Sparse-Struktur, die nicht überlappende Segmente indiziert, kann aufgebaut werden.

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

Jeder Eintrag enthält die untere Grenze eines nicht überlappenden Segments als Schlüssel und die Liste oder den Satz übereinstimmender Bereiche als Wert. Einträge sollten mithilfe eines sortierten Containers (Baum, Skip-Liste, Btree usw.) indiziert werden.

Um die Bereiche zu finden, die mit 5 übereinstimmen, suchen wir nach dem ersten Eintrag, der kleiner oder gleich 5 ist (in diesem Beispiel ist es 4), und die Liste der Bereiche wird bereitgestellt ( [A C B] )

Bei dieser Datenstruktur ist die Komplexität der Abfragen wirklich O(log n). Es ist jedoch nicht trivial (und teuer), es zu bauen und zu warten. Es kann sowohl mit Mongodb als auch mit Redis implementiert werden.

Hier ist ein Beispiel mit 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"