DBMS - Indexación

Sabemos que los datos se almacenan en forma de registros. Cada registro tiene un campo clave, lo que ayuda a que sea reconocido de forma única.

La indexación es una técnica de estructura de datos para recuperar de manera eficiente registros de los archivos de la base de datos en función de algunos atributos en los que se realizó la indexación. La indexación en los sistemas de bases de datos es similar a lo que vemos en los libros.

La indexación se define en función de sus atributos de indexación. La indexación puede ser de los siguientes tipos:

  • Primary Index- El índice principal se define en un archivo de datos ordenado. El archivo de datos está ordenadokey field. El campo de clave es generalmente la clave principal de la relación.

  • Secondary Index - El índice secundario se puede generar a partir de un campo que es una clave candidata y tiene un valor único en cada registro, o una no clave con valores duplicados.

  • Clustering Index- El índice de agrupamiento se define en un archivo de datos ordenado. El archivo de datos está ordenado en un campo que no es clave.

La indexación ordenada es de dos tipos:

  • Índice denso
  • Índice disperso

Índice denso

En el índice denso, hay un registro de índice para cada valor de clave de búsqueda en la base de datos. Esto hace que la búsqueda sea más rápida pero requiere más espacio para almacenar los registros de índice. Los registros de índice contienen el valor de la clave de búsqueda y un puntero al registro real en el disco.

Índice disperso

En el índice disperso, los registros de índice no se crean para cada clave de búsqueda. Un registro de índice contiene aquí una clave de búsqueda y un puntero real a los datos en el disco. Para buscar un registro, primero procedemos por registro de índice y llegamos a la ubicación real de los datos. Si los datos que estamos buscando no están donde llegamos directamente siguiendo el índice, entonces el sistema inicia la búsqueda secuencial hasta que se encuentran los datos deseados.

Índice multinivel

Los registros de índice comprenden valores de clave de búsqueda e indicadores de datos. El índice multinivel se almacena en el disco junto con los archivos reales de la base de datos. A medida que aumenta el tamaño de la base de datos, también lo hace el tamaño de los índices. Existe una inmensa necesidad de mantener los registros de índice en la memoria principal para acelerar las operaciones de búsqueda. Si se utiliza un índice de un solo nivel, no se puede guardar un índice de gran tamaño en la memoria, lo que da lugar a múltiples accesos al disco.

El índice multinivel ayuda a dividir el índice en varios índices más pequeños para que el nivel más externo sea tan pequeño que se pueda guardar en un solo bloque de disco, que se puede acomodar fácilmente en cualquier lugar de la memoria principal.

B + Árbol

El árbol AB + es un árbol de búsqueda binario equilibrado que sigue un formato de índice de varios niveles. Los nodos de hoja de un árbol B + denotan punteros de datos reales. El árbol B + asegura que todos los nudos de las hojas permanezcan a la misma altura, por lo tanto equilibrados. Además, los nodos hoja están vinculados mediante una lista de vínculos; por lo tanto, un árbol B + puede admitir tanto el acceso aleatorio como el secuencial.

Estructura del árbol B +

Cada nodo hoja está a la misma distancia del nodo raíz. AB + árbol es del ordenn dónde nes fijo para cada árbol B + .

Internal nodes -

  • Los nodos internos (no hoja) contienen al menos ⌈n / 2⌉ punteros, excepto el nodo raíz.
  • Como máximo, un nodo interno puede contener n punteros.

Leaf nodes -

  • Los nodos hoja contienen al menos ⌈n / 2⌉ punteros de registro y valores clave ⌈n / 2⌉.
  • Como máximo, un nodo hoja puede contener n grabar punteros y n valores clave.
  • Cada nodo hoja contiene un puntero de bloque P para apuntar al siguiente nodo de hoja y forma una lista vinculada.

Inserción de árbol B +

  • Los árboles B + se llenan desde la parte inferior y cada entrada se realiza en el nodo de la hoja.

  • Si un nodo hoja se desborda -
    • Divida el nodo en dos partes.

    • Partición en i = ⌊(m+1)/2⌋.

    • primero i las entradas se almacenan en un nodo.

    • El resto de las entradas (i + 1 en adelante) se mueven a un nuevo nodo.

    • ith la clave está duplicada en el padre de la hoja.

  • Si un nodo no hoja se desborda:

    • Divida el nodo en dos partes.

    • Particione el nodo en i = ⌈(m+1)/2.

    • Entradas hasta i se mantienen en un nodo.

    • El resto de las entradas se mueven a un nuevo nodo.

B + Eliminación de árboles

  • Las entradas del árbol B + se eliminan en los nodos hoja.

  • La entrada de destino se busca y se elimina.

    • Si es un nodo interno, elimínelo y reemplácelo con la entrada de la posición izquierda.

  • Después de la eliminación, se prueba el subdesbordamiento,

    • Si se produce un desbordamiento, distribuya las entradas de los nodos que le quedan.

  • Si la distribución no es posible desde la izquierda, entonces

    • Distribuya desde los nodos directamente a él.

  • Si la distribución no es posible desde la izquierda o desde la derecha, entonces

    • Fusiona el nodo con la izquierda y la derecha.