Al contrario del cartel anterior, no creo que pueda obtener la complejidad O (log n) mediante el uso de una indexación ingenua. Consideremos mongodb por ejemplo. Puede definir dos índices (para las propiedades de inicio y fin de los rangos), pero mongodb solo usará uno para resolver una consulta determinada. Así que no funcionará. Ahora bien, si utiliza un único índice compuesto que incluye las propiedades inicial y final de los rangos, la complejidad será logarítmica para encontrar el primer rango que se va a verificar, pero luego se volverá lineal para encontrar el último rango que coincida con la consulta. La complejidad del peor de los casos es O(n), y la tiene cuando todos los rangos almacenados se superponen con su entrada.
En una nota al margen, al usar el conjunto ordenado de Redis, puede emular un índice ordenado (con complejidad O (log n)) si sabe lo que hace. Redis es un poco más que un simple almacén de clave-valor. Los conjuntos ordenados de Redis se implementan mediante una lista de omisión, y tanto la puntuación como el valor se utilizan para comparar elementos.
Para resolver este tipo de problema, se necesita una estructura de indexación dedicada. Es posible que desee echar un vistazo a:
http://en.wikipedia.org/wiki/Segment_tree o http://en.wikipedia.org/wiki/Interval_tree
Si la preocupación es la velocidad sobre el espacio, entonces puede ser interesante aplanar el índice. Por ejemplo, consideremos los siguientes rangos (usando solo números enteros para simplificar la discusión):
A 2-8
B 4-6
C 2-9
D 7-10
Se puede construir una estructura dispersa que indexe segmentos no superpuestos.
0 []
2 [A C]
4 [A C B]
7 [A C D]
9 [C D]
10 [D]
11 []
Cada entrada contiene el límite inferior de un segmento no superpuesto como clave y la lista o conjunto de rangos coincidentes como valor. Las entradas deben indexarse utilizando un contenedor ordenado (árbol, lista de omisión, btree, etc.)
Para encontrar los rangos que coincidan con 5, buscamos la primera entrada que sea inferior o igual a 5 (será 4 en este ejemplo) y se proporciona la lista de rangos ( [A C B] )
Con esta estructura de datos, la complejidad de las consultas es realmente O(log n). Sin embargo, no es trivial (y costoso) construirlo y mantenerlo. Se puede implementar tanto con mongodb como con Redis.
Aquí hay un ejemplo con 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"
