¿cómo se ve un índice B-tree en más de 1 columna?

Question

así que estaba leyendo sobre índices y su aplicación, y me encontré con este sitio web que contiene una breve explicación de los índices de árbol B:

http://20bits.com/articles/interview-questions-database-indexes/

El índice de árbol B 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 puedo crear un índice en: (id, nombre, ciudad)

y luego ejecute 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?

Answer 1

Imagínese que la clave está representado por una tupla de Python (col1, col2, col3) ... la operación de indexación consiste en comparar tuple_a con tuple_b ... si usted tiene no sé qué valor de col1 y col2 que están interesados ​​en, pero solo col3, entonces tendrían 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, col3 en la cláusula WHERE), el RDBMS no usará ese índice (por ejemplo, SQLite) o realizará un análisis de índice completo (por ejemplo, Oracle) [si ningún otro índice es mejor].

En su ejemplo específico, suponiendo que la identificación 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 anotada como ÚNICA)

Answer 2

En 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 ;-)

En su ejemplo los valores clave podía ve algo 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 del árbol intermedios se pueden utilizar en algunos casos "cubrir" la consulta.

Por ejemplo, si la consulta es para encontrar el nombre y la ciudad dada la identificación, ya que la identificación es primera 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, la lógica seguiría la hoja cuando se encuentre el registro completo.

Answer 3

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.

He aquí una pregunta relacionada escribí la semana pasada:

Does SQL Server jump leaves when using a composite clustered index?

Answer 4

Aparte del mecanismo de "clave compuesta" ya se ha descrito, una posibilidad es una kdtree que funciona como un árbol binario, pero a medida que atraviesan cada uno nivel de ciclo a través de 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 nivel k+1 divide nuevamente la primera dimensión, etc. Esto permite la partición eficiente de datos en cualquier cantidad de dimensiones . Este enfoque es común en las bases de datos "espaciales" (por ejemplo, Oracle Spatial, PostGIS, etc.), pero probablemente no sea tan útil en las tablas "multi-indexadas" "regulares".

http://en.wikipedia.org/wiki/Kd-tree

Answer 5

Se puede utilizar el (id, nombre, ciudad) Índice de satisfacer una "Ciudad =?" Predicado, pero muy, muy inefficently.

Para usar el índice para satisfacer esta consulta, necesitarí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.

Answer 6

En Oracle, se puede usar un índice de clave compuesta aunque las columnas iniciales no se filtran. Esto se hace a través de tres mecanismos:

1. Escaneo de índice rápido completo, en el que se utilizan lecturas de varios bloques para recorrer todo el segmento de índice.
2. Un análisis completo de índice, en el que el índice se lee en el orden lógico de los bloques (creo que he leído que en versiones recientes Oracle puede usar lecturas de varios bloques para esto, pero realmente debe contar con lecturas de bloque único)
3. Una exploración de salto 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 las partes internas del índice de Oracle.