Diseñando indices en SQL Server

Recuerde, la función principal de un índice, es que Ud. pueda encontrar la información que busca con la menor cantidad de lecturas posibles.

SQL utiliza B-tree "Balanced tree" para crear y mantener sus indices. Una definición bien detallada la podemos en contrar en: http://en.wikipedia.org/wiki/B-tree

En resumen podemos decir que un arbol b, contiene un nodo root, el cual consta de una única página, una o mas niveles de páginas intermedias y uno o mas páginas leaf (su traducción seria hoja).

El leaf-level contiene las todas las entredas ordenadas como se ha definido el indice. Obviamente que el nro. de filas almacenada por página dependera del tamaño de las columnas especificadas en el indice.

Tip: Cada página en sql ocupa 8060 bytes, por lo que si solo definimos como idx una columna de tipo int, se podran almacenar 2015 valores por página. (ver tablas de tipos de datos para derterminar cuantas filas por página pueden almacenarce).

Como se construye un arbol-b? veamos la siguiente imagen:

(ya se que la imagen esta bastante chota, pero, es muy ilustrativa).

Volvieldo a la pregunta original, la raíz y los niveles intermedios del índice se construye tomando la primera entrada de la cada página en el nivel inferior, junto con un puntero a la página donde el valor de los datos procedían de, como se muestra en la figura anterior.

Por lo contrario una consulta, lo que hace es escanear el root hasta encontrar en que pagina (de nivel inferior) se encuentra el valor buscado, y así sucesivamente hasta llegar al left-level, en este punto se ha encontrado el valor buscado.

ra

Cálculo de un arbol-b

El número de paginas y niveles de un idx es calcula por simples cálculos matemáticos.

Si recordamos una página solo puede contener 8060 bytes (8192, pero solo 8060 de datos), conociendo el/los tipos de datos del idx podemos calcular cuantos registros pueden almacenarce por página. Por ejemplo si el idx es de tipo int, cada int ocupa 4 bytes entonces podemos decir que en cada página se pueden almacenar 2015 entradas (8060/4).

Siguiente con el ejemplo, supongamos que la tabla contiene 1200 filas, traducida al índice, son 1200 entradas que se pueden almacenar en una única página (que en este caso sera tanto root como leaf).

Ahora bien cuando en la tabla se inserta el registro nro. 2016, se inicia un proceso que se denomia table-split, lo que hace es insertar dos páginas en de nivel inferior (en este caso leaft-level y nuestra página root/leaft ahora es solamente root) y a su vez sql toma la mitad de los datos y los coloca en cada una de las páginas. El último paso de este proceso es tomar la primera entrada de las dos páginas de datos y escribirlas en el root, en este caso no se necesitan niveles intermedios debido a que las entradas mismas pueden ser contenidas por el root.

En este punto se requiere leer dos páginas de índice para localizar cualquier registro en la tabla.

Ahora bien, podemos seguir insertando registros en la tabla sin cambiar la cantidad de niveles hasta llegar al registro 4.060.225, ya que vamos a tener 2015 entradas en el root-page, o sea 2015 paginas leaf que a su vez contienen 2015 entradas (2015 * 2015 = 4060225).

Cuando se inserta el registro nro. 4060226, sql tiene que iniciar nuevamente un proceso de split, y lo que hace es nuevamente tomar la mitad de las entradas del root y escribirlas en dos páginas que en este caso seran de nivel intermedio, luego toma la primera entrada de las paginas recién creadas y las escribe en el root.

Nota: En la vida real esto es un poco mas compejo, debido a que las páginas de índices simpre estan ordenadas, con lo cual ademas de producirse splits, también podemos encontrarnos con movimiento de datos entre páginas.