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

Question

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

• Consultar en una clave principal o un índice único le dará un O (1) tiempo de búsqueda.
• Consultar en un índice no único también dará un O (1) tiempo, aunque tal vez el '1' es más lento que para el índice único (?)
• Consultar una columna sin índice dará una O (N) tiempo de búsqueda (escaneo completo de la tabla).

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

Answer 1

La mayoría de las bases de datos relacionales estructuran índices como B-trees.

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. Cualquier índice no agrupado es B-trees donde el nodo hoja del árbol B identifica una página particular en el montón.

La altura del peor caso de un árbol B es O (log n), y desde una búsqueda depende de la altura, las búsquedas de árbol B se ejecutan en algo así como (en promedio)

O (log _t n)

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

Así lo entiendo.

Y diferentes sistemas de bases de datos, por supuesto, bien pueden usar diferentes estructuras de datos bajo el capó.

Y si la consulta no usa un índice, por supuesto, la búsqueda es una iteración sobre el montón o B-tree 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 buscar la página de datos correspondiente en la memoria.

Answer 2

Las consultas indexadas (únicas o no) son más típicamente O (log n). Muy simplistamente, puedes 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).

Answer 3

Si selecciona las mismas columnas que la búsqueda de entonces

• Primaria o Unqiue será O (log n): es una búsqueda de árbol B
• índice no único es también O (n log) + un poco: es una búsqueda de árbol B
• ningún índice = O (N)

Si requiere información de otra "fuente" (intersección índice, marcador/clave de búsqueda, etc.) debido a que el índice es no cubriendo, entonces podrías tener O (n + log) n) u O (log n + log n + log n) debido a múltiples hits de índice + clasificación intermedia.

Si las estadísticas muestran que se requiere un alto% de filas (índice por ejemplo, no muy selectivos), entonces el índice puede ser ignorado y se convierte en una exploración = O (n)

Answer 4

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

Tiene razón en que los índices secundarios suelen tener la misma complejidad pero peor rendimiento real, esto porque el índice y los datos no están agrupados, por lo que la constante (número de búsquedas de disco) es mayor.

Answer 5

Depende de lo que sea su consulta.

• Una condición de la forma Column = Value permite el uso de un índice basado en hash, que tiene O (1) de búsqueda de tiempo. Sin embargo, many databases, including SQLite, do not support them.
• Una condición que utiliza operadores relacionales (<, >, <=, >=) puede hacer uso de un índice ordenado, normalmente implementado con un árbol binario, que tiene O (log n) tiempo de búsqueda.
• Las expresiones más complicadas que no pueden usar un índice requieren O (n) tiempo.

Dado que usted está interesado principalmente en SQLite, es posible que desee leer su Query Optimizer Overview que explica con más detalle cómo se seleccionan los índices.