sql - dominio - notacion o grande ejercicios resueltos

Índices de base de datos y su notación Big-O (5)

Estoy tratando de entender el rendimiento de los índices de base de datos en términos de notación Big-O. Sin saber mucho al respecto, me imagino que:

La consulta de una clave principal o un índice único le dará un tiempo de búsqueda O (1).
La consulta en un índice no único también dará un O (1) tiempo, aunque quizás el ''1'' sea más lento que para el índice único (?)
La consulta en una columna sin un índice dará un tiempo de búsqueda O (N) (exploración de tabla completa).

¿Es esto generalmente correcto? ¿La consulta en una clave primaria dará un rendimiento peor que O (1)? Mi preocupación específica es para SQLite, pero me gustaría saber hasta qué punto esto varía también entre las diferentes bases de datos.

Depende de cuál sea tu consulta.

Una condición del formulario Column = Value permite el uso de un índice basado en hash, que tiene un tiempo de búsqueda O (1). Sin embargo, muchas bases de datos, incluido SQLite, no las admiten .
Una condición que usa operadores relacionales ( < , > , <= , >= ) puede hacer uso de un índice ordenado, generalmente implementado con un árbol binario, que tiene un tiempo de búsqueda O (log n).
Las expresiones más complicadas que no pueden usar un índice requieren O (n) tiempo.

Dado que lo que más le interesa es SQLite, es posible que desee leer su Descripción general del optimizador de consultas, que explica con más detalle cómo se seleccionan los índices.

La mayoría de las bases de datos relacionales estructuran los índices como árboles-B.

Si una tabla tiene un índice de agrupamiento, las páginas de datos se almacenan como los nodos de hoja del árbol-B. Esencialmente, el índice de agrupamiento se convierte en la tabla.

Para las tablas sin un índice de agrupamiento, las páginas de datos de la tabla se almacenan en un montón. Todos los índices no agrupados son árboles B, donde el nodo hoja del árbol B identifica una página particular en el montón.

La altura del caso más desfavorable de un árbol B es O (log n), y dado que la búsqueda depende de la altura, las búsquedas de árbol B se ejecutan de forma similar (en promedio)

O (log _t n)

donde t es el factor de minimización (cada nodo debe tener al menos las teclas t -1 y como máximo las teclas 2 * t * -1 (por ejemplo, 2 * t * hijos).

Así lo entiendo yo.

Y, por supuesto, diferentes sistemas de bases de datos pueden utilizar diferentes estructuras de datos debajo del capó.

Y si la consulta no utiliza un índice, por supuesto, entonces la búsqueda es una iteración sobre el montón o el árbol B que contiene las páginas de datos.

Las búsquedas son un poco más baratas si el índice utilizado puede satisfacer la consulta; de lo contrario, se requiere un lookaside para recuperar la página de datos correspondiente en la memoria.

Las consultas indexadas (únicas o no) son más típicamente O (log n). De manera muy simple, puede pensar que es similar a una búsqueda binaria en una matriz ordenada. Más exactamente, depende del tipo de índice. Pero una búsqueda de b-tree, por ejemplo, sigue siendo O (log n).

Si no hay índice, entonces sí, es O (N).

Otras respuestas dan un buen punto de partida; pero solo agregaría que para obtener O (1), el índice primario en sí tendría que estar basado en hash (que normalmente no es la opción predeterminada); así que más comúnmente es logarítmico (árbol B).

Es correcto que los índices secundarios suelen tener la misma complejidad, pero un peor rendimiento real, ya que el índice y los datos no están agrupados, por lo que la constante (número de búsquedas de discos) es mayor.

Si selecciona las mismas columnas que busca entonces

Primary o Unqiue será O (log n): es una búsqueda de b-tree
el índice no único también es O (log n) + un bit: es una búsqueda de árbol b
sin índice = O (N)

Si necesita información de otra "fuente" (intersección de índice, marcador / búsqueda de clave, etc.) porque el índice no cubre, entonces podría tener O (n + log n) u O (log n + log n + log n) debido a múltiples resultados de índice + clasificación intermedia.

Si las estadísticas muestran que necesita un alto% de filas (por ejemplo, un índice no muy selectivo), el índice puede ignorarse y convertirse en un escaneo = O (n)