Índices multinivel

Los índices que se han descrito hasta ahora son ficheros ordenados en los que una búsqueda requiere aproximadamente $\log_{2}b$ accesos a bloques de disco, siendo $b$ el número de bloques que tiene el índice. Es el logaritmo en base dos porque en cada paso del algoritmo se reduce a la mitad el trozo del índice en el que se va a seguir buscando. Mediante los índices multinivel se pretende reducir mucho más el trozo del índice sobre el que seguir buscando, en concreto, se quiere dividir el tamaño no entre dos, sino entre el número de registros del índice que caben en un bloque. De este modo, se reduce el espacio de búsqueda mucho más rápidamente. Si el número de registros del índice que caben en un bloque es $r$, entonces el buscar en un índice multinivel requiere aproximadamente $\log_{r}b$, que es mucho menor si $r>2$.

Un índice multinivel está formado por un fichero índice, al que se denomina primer nivel o nivel base del índice. Este primer nivel es un fichero ordenado con un valor distinto del campo de indexación en cada entrada. Por tanto, se puede crear un índice primario sobre el primer nivel; este índice constituye el segundo nivel del índice multinivel. Ya que el segundo nivel es un índice primario, en él se tiene una entrada por cada bloque del primer nivel. Como todas las entradas de ambos niveles tienen el mismo tamaño (son registros de tamaño fijo siempre iguales), en un bloque caben siempre el mismo número de entradas: $r$. Si el primer nivel tiene $i_{1}$ entradas, ocupa $\lceil i_{1}/r \rceil$ bloques, que es el número de entradas $i_{2}$ que se necesitan en el segundo nivel. El proceso se puede repetir sobre este nivel, si es necesario. El tercer nivel, que es un índice primario sobre el segundo nivel, tiene una entrada por cada bloque del segundo nivel, por lo tanto, el número de entradas del tercer nivel será $i_{3}=\lceil i_{2}/r \rceil$. Nótese que se necesita un tercer nivel sólo si el segundo nivel ocupa más de un bloque. Este proceso se puede repetir hasta que todas las entradas de algún nivel $n$ quepan en un solo bloque. Cada bloque reduce el número de entradas del nivel anterior por un factor de $r$, por tanto, un índice multinivel con $i_{1}$ entradas en el primer nivel tiene aproximadamente $n$ niveles, donde $n = \lceil \log_{r}i_{1} \rceil$.

Este esquema multinivel se puede utilizar sobre cualquier tipo de índice, sea primario, de agrupamiento o secundario, siempre que el primer nivel tenga valores distintos en el campo de indexación y entradas de tamaño fijo.

Cuando el índice del primer nivel es denso, se puede saber si existe un registro con un valor dado en el campo de indexación (test de existencia) sin tener que acceder al fichero de datos, cosa que hay que hacer siempre en un índice no denso. Por lo tanto los índices multinivel reducen el número de accesos a bloque cuando se busca un registro a partir del valor de su campo de indexación. Pero todavía siguen los problemas en inserciones y borrados sobre los índices, ya que todos ellos (todos los niveles) son ficheros ordenados. Para mantener las ventajas que presentan los índices multinivel y reducir los problemas de las inserciones y borrados, los diseñadores adoptan a menudo un índice multinivel que deja espacio en cada uno de sus bloques para insertar nuevas entradas. Esto es lo que se denomina un índice multinivel dinámico y se suele implementar mediante estructuras de datos denominadas árboles B y árboles B+.