Contrairement à l'affiche précédente, je ne pense pas que vous puissiez obtenir une complexité O (log n) en utilisant une indexation naïve. Considérons mongodb par exemple. Vous pouvez définir deux index (pour les propriétés de début et de fin des plages), mais mongodb n'en utilisera qu'un pour résoudre une requête donnée. Cela ne fonctionnera donc pas. Maintenant, si vous utilisez un seul index composé impliquant à la fois les propriétés de début et de fin des plages, la complexité sera logarithmique pour trouver la première plage à vérifier, mais elle deviendra ensuite linéaire pour trouver la dernière plage correspondant à la requête. La complexité dans le pire des cas est O(n), et vous l'avez lorsque toutes les plages stockées chevauchent votre entrée.
En passant, en utilisant l'ensemble trié Redis, vous pouvez émuler un index trié (avec une complexité O (log n)) si vous savez ce que vous faites. Redis est un peu plus qu'un simple magasin clé-valeur. Les ensembles triés Redis sont implémentés à l'aide d'une liste de sauts, et le score et la valeur sont utilisés pour comparer les éléments.
Pour résoudre ce genre de problème, une structure d'indexation dédiée est nécessaire. Vous voudrez peut-être jeter un œil à :
http://en.wikipedia.org/wiki/Segment_treeouhttp://en.wikipedia.org/wiki/Interval_tree
Si le souci est la vitesse sur l'espace, alors il peut être intéressant d'aplatir l'index. Par exemple, considérons les plages suivantes (en utilisant uniquement des entiers pour simplifier la discussion) :
A 2-8
B 4-6
C 2-9
D 7-10
Une structure clairsemée indexant des segments non superposés peut être construite.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Chaque entrée contient la limite inférieure d'un segment qui ne se chevauche pas comme clé, et la liste ou l'ensemble des plages correspondantes comme valeur. Les entrées doivent être indexées à l'aide d'un conteneur trié (arbre, liste de sauts, btree, etc ...)
Pour trouver les plages correspondant à 5, on cherche la première entrée qui est inférieure ou égale à 5 (ce sera 4 dans cet exemple) et la liste des plages est fournie ( [A C B] )
Avec cette structure de données, la complexité des requêtes est vraiment O(log n). Cependant il n'est pas anodin (et coûteux) de le construire et de l'entretenir. Il peut être implémenté avec mongodb et Redis.
Voici un exemple avec 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"
