sql server - usar - ¿Cómo se ve un índice B-tree en más de 1 columna?
usar indices en consulta sql (6)
Así que estaba leyendo sobre los índices y su implementación, y me encontré con este sitio web que tiene una breve explicación de los índices de b-tree:
http://20bits.com/articles/interview-questions-database-indexes/
El índice b-tree tiene mucho sentido para los índices que están solo en una sola columna, pero digamos que creo un índice con múltiples columnas, ¿cómo funciona el árbol b? ¿Cuál es el valor de cada nodo en el árbol b?
Por ejemplo, si tengo esta tabla:
table customer:
id number
name varchar
phone_number varchar
city varchar
y creo un índice en: (id, nombre, ciudad)
y luego ejecuta la siguiente consulta:
SELECT id, name
FROM customer
WHERE city = ''My City'';
¿Cómo utiliza esta consulta el índice de columna múltiple, o no lo utiliza a menos que el índice se cree como (ciudad, identificación, nombre) o (ciudad, nombre, id) en su lugar?
Aparte del mecanismo de "clave compuesta" ya descrito, una posibilidad es un kdtree que funciona como un árbol binario, pero a medida que atraviesas cada nivel, kdtree k dimensiones. Es decir, el primer nivel del árbol separa la primera dimensión en dos partes, el segundo nivel divide la segunda dimensión, el k+1 nivel divide nuevamente la primera dimensión, etc. Esto permite la partición eficiente de datos en cualquier número de dimensiones Este enfoque es común en las bases de datos "espaciales" (p. Ej., Oracle Spatial, PostGIS, etc.), pero probablemente no sea tan útil en las tablas "multi-indexadas" "regulares".
En Oracle, se puede usar un índice de clave compuesta aunque las columnas principales no se filtran. Esto se hace a través de tres mecanismos:
- Un análisis de índice completo rápido, en el que se utilizan lecturas de varios bloques para recorrer todo el segmento de índice.
- Un análisis completo de índice, en el que el índice se lee en el orden lógico de los bloques (creo que leí que en versiones recientes Oracle puede usar lecturas de varios bloques para esto, pero realmente debe contar con lecturas de bloque único)
- Una exploración de omisión inddex, donde una cardinalidad muy baja para las columnas principales sin predicados permite a Oracle realizar múltiples escaneos de rango de índice, uno para cada valor único de la (s) columna (s) principal (es). Estos son bastante raros en mi experiencia.
Busque artículos de Richard Foote o Jonathan Lewis para obtener más información sobre los componentes internos del índice Oracle.
Imagine que la clave está representada por una tupla de Python (col1, col2, col3) ... la operación de indexación implica comparar tuple_a con tuple_b ... si no sabe qué valor de col1 y col2 le interesa, pero solo col3, entonces tendría que leer todo el índice ("análisis de índice completo"), que no es tan eficiente.
Si tiene un índice en (col1, col2, col3), entonces puede esperar que cualquier RDBMS use el índice (de manera directa) cuando la cláusula WHERE contiene referencia a (1) las 3 columnas (2) col1 y col2 (3) solo col1.
De lo contrario (por ejemplo, solo col3 en la cláusula WHERE), el RDBMS no usará ese índice en absoluto (por ejemplo, SQLite) o realizará un escaneo de índice completo (por ejemplo, Oracle) [si ningún otro índice es mejor].
En su ejemplo específico, presumiendo que el ID es un identificador único de un cliente, no tiene sentido que aparezca en un índice (que no sea el índice que su DBMS debe configurar para una clave o columna principal que se indique como ÚNICA).
Puede usar el índice (id, name, city) para satisfacer un predicado "City =?", Pero muy muy ineficientemente.
Para usar el índice para satisfacer esta consulta, debería caminar la mayor parte de la estructura de árbol buscando entradas con la ciudad deseada. ¡Este sigue siendo probablemente un orden de magnitud más rápido que escanear la tabla!
Un índice de (ciudad, nombre, id) sería el mejor índice para su consulta. Encontraría todas las entradas de ciudad deseadas fácilmente y no necesitaría acceder a la tabla subyacente para obtener los valores de identificación y nombre.
Con la mayoría de las implementaciones, la clave es simplemente una clave más larga que incluye todos los valores clave, con un separador. No hay magia allí ;-)
En su ejemplo, los valores clave podrían ser algo así como
"123499|John Doe|Conway, NH" "32144|Bill Gates| Seattle, WA"
Una de las características de estos índices con claves compuestas es que los nodos intermedios de árbol se pueden usar en algunos casos para "cubrir" la consulta.
Por ejemplo, si la consulta es para encontrar el nombre y la ciudad dado el ID, dado que el ID está primero en el índice, el índice puede buscar de esta manera de manera eficiente. Una vez en el nodo intermedio, puede "analizar" el Nombre y la Ciudad, desde la clave, y no necesita ir al nodo hoja para leer el mismo.
Sin embargo, si la consulta también quería mostrar el número de teléfono, entonces la lógica seguiría la hoja cuando se encuentre el registro completo.
Algunas implementaciones simplemente concatenan los valores en el orden de las columnas, con delimitadores.
Otra solución es simplemente tener un b-tree dentro de un b-tree. Cuando tocas una hoja en la primera columna, obtienes una lista de registros coincidentes y un mini b árbol de la columna siguiente, y así sucesivamente. Por lo tanto, el orden de las columnas especificadas en el índice hace una gran diferencia en cuanto a si ese índice será útil para consultas particulares.
Aquí hay una pregunta relacionada que escribí la semana pasada: