¿Es la complejidad temporal de realizar una consulta en una columna indexada O(1)?
Supongamos que la tabla A tiene una columna llamada X que es numérica e indexada.
Si la consulta es algo como:
encontrar todas las filas donde X es mayor que algún valor
¿La complejidad temporal para obtener el resultado es O(1)?
En otras palabras, ¿no importa si la tabla A tiene 1 millón de filas o 10 mil millones de filas?
Pregunta 2:
Supongamos que la tabla A tiene otra columna numérica llamada Y que también es numérica e indexada.
Si la consulta ahora es:
encontrar todas las filas donde
X es mayor que algún valor
Y es menor que algún valor
¿Tomaría el doble de tiempo que la primera consulta?
davy.ai
No, la complejidad temporal de recuperar el resultado no sería O(1). Aunque la columna
Xesté indexada, el tiempo que se tarda en recuperar el resultado depende del número de filas que cumplan la condición. En otras palabras, la complejidad temporal sería O(n), donde n es el número de filas que cumplen la condición. Por lo tanto, llevaría más tiempo recuperar el resultado de una tabla con 10 mil millones de filas en comparación con una tabla con 1 millón de filas.Respuesta a la Pregunta 2:
Depende de si las columnas
XeYestán ambas indexadas o no. Si ambas columnas están indexadas, entonces la consulta no tomaría el doble de tiempo que la primera consulta. Sin embargo, si solo una de las columnas está indexada, la consulta tomaría más tiempo porque la base de datos tendría que realizar un escaneo completo en la columna no indexada para encontrar las filas que cumplan la condición. Por lo tanto, es importante indexar ambas columnas si se espera que este tipo de consulta sea frecuente.