Métodos de indexación y acceso

Los índices y los métodos de acceso son las estructuras de datos auxiliares —principalmente árboles B+ e índices hash— que permiten a una base de datos localizar tuplas coincidentes sin escanear una tabla completa, proporcionando las rutas de acceso rápidas en las que se basa el optimizador.

Definition

Un índice es una estructura de datos auxiliar sobre uno o más atributos de una relación que mapea valores clave a las ubicaciones de las tuplas coincidentes, permitiendo la recuperación en un tiempo sublineal con respecto al tamaño de la tabla; un método de acceso es el mecanismo que utiliza una consulta para leer datos, como un escaneo completo o un escaneo de índice.

Scope

Este tema abarca las estructuras y conceptos detrás de las rutas de acceso a los datos: la distinción entre índices agrupados y no agrupados, primarios y secundarios; el árbol B+ como el índice ordenado principal que soporta búsquedas de igualdad y de rango; los índices basados en hash para búsquedas de igualdad; y el papel de los índices en la selección, la unión y la evitación de la ordenación. Se trata cómo la elección del índice afecta el costo de la consulta y la sobrecarga de actualización. Excluye la selección general del plan del optimizador basado en costos, que es un tema aparte.

Core questions

• ¿Cómo soporta un árbol B+ de manera eficiente tanto las consultas de igualdad como las de rango?
• ¿Cuál es la diferencia entre índices agrupados y no agrupados, primarios y secundarios?
• ¿Cuándo es preferible un índice hash a un índice de árbol?
• ¿Cómo aceleran los índices las selecciones, las uniones y la recuperación ordenada?
• ¿Cuál es el costo de mantener los índices bajo inserciones, actualizaciones y eliminaciones?

Key concepts

• índice de árbol B+
• índice hash
• índice agrupado versus no agrupado
• índices primarios y secundarios
• índices densos y dispersos
• búsqueda de rango y de igualdad
• hashing extensible y lineal
• costo de mantenimiento del índice

Key theories

Índices de árbol B+

El árbol B+ es un árbol de búsqueda equilibrado y de alto factor de ramificación que almacena claves en orden ascendente con todas las referencias de datos en las hojas; soporta consultas de igualdad y de rango y escaneos ordenados con E/S logarítmica y se mantiene equilibrado bajo inserciones y eliminaciones.

Índices agrupados versus no agrupados

Un índice agrupado mantiene las filas de la tabla físicamente ordenadas por la clave del índice, lo que hace que los escaneos de rango sean muy eficientes, mientras que un índice no agrupado (secundario) apunta a un archivo no ordenado, por lo que la recuperación de muchas filas coincidentes puede costar una E/S por fila.

Índices hash

Los índices basados en hash mapean claves a cubos para búsquedas de igualdad en tiempo constante esperado, pero no soportan consultas de rango; los esquemas dinámicos como el hashing extensible y lineal les permiten crecer de manera gradual con los datos.

Clinical relevance

La indexación es la palanca práctica más común para el rendimiento de las bases de datos: elegir los índices correctos puede convertir los escaneos de tabla completa en búsquedas de milisegundos para consultas transaccionales y analíticas, mientras que la sobreindexación ralentiza las actualizaciones, por lo que el diseño de índices es una decisión recurrente en la operación de sistemas reales.

History

Bayer y McCreight introdujeron el árbol B en 1972 para mantener grandes índices ordenados en disco; la variante del árbol B+, que mantiene todos los datos en las hojas, se convirtió en el índice de base de datos estándar, como se revisó en el 'Ubiquitous B-tree' de Comer de 1979. Los métodos de acceso basados en hash y los esquemas de hashing dinámico se desarrollaron en paralelo, y ambas familias siguen siendo fundamentales para cada motor relacional.

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

¿Por qué se utilizan árboles B+ en lugar de árboles de búsqueda binaria en las bases de datos?

Las bases de datos almacenan datos en disco, donde el costo está dominado por el número de lecturas de página. Los árboles B+ tienen un alto factor de ramificación, por lo que cada nodo llena una página de disco y el árbol es muy poco profundo, requiriendo solo unas pocas operaciones de E/S para alcanzar cualquier registro. Un árbol binario sería mucho más profundo e incurriría en muchos más accesos a disco.

¿Cuándo debo usar un índice hash en lugar de un árbol B+?

Utilice un índice hash cuando solo necesite búsquedas de igualdad (por ejemplo, encontrar la fila con un ID dado) y desee un acceso en tiempo constante esperado. Utilice un árbol B+ cuando también necesite consultas de rango, escaneos ordenados o coincidencia de prefijos, ya que los índices hash no conservan el orden de las claves y no pueden responder a las condiciones de rango de manera eficiente.