Please enable JavaScript.

Coggle requires JavaScript to display documents.

INDEXACIÓN Y ASOCIACIÓN (CONCEPTOS BÁSICOS (• Índices ordenados. Estos…

- - - - • Índice denso. Aparece un registro índice por cada valor de la clave de búsqueda en el archivo. El registro índice contiene el valor de la clave y un puntero al primer registro con ese valor de la clave de búsqueda
      - • Índice disperso. Sólo se crea un registro índice para algunos de los valores. Al igual que en los índices densos, cada registro índice contiene un valor de la clave de búsqueda y un puntero al primer registro con ese valor de la clave
  - - - • Inserción. Primero se realiza una búsqueda usando el valor de la clave de búsqueda del registro a insertar. Las acciones que emprende el sistema a continuación dependen de si el índice es denso o disperso.
        
        En caso contrario se emprenden las siguientes acciones:
        
        a. Si el registro índice almacena punteros a todos los registros con el mismo valor de la clave de búsqueda, el sistema añade un puntero al nuevo registro en el registro índice.
        
        b. En caso contrario, el registro índice almacena un puntero sólo hacia el primer registro con el valor de la clave de búsqueda. El sistema sitúa el registro insertado después de los otros con los mismos valores de la clave de búsqueda
        
        Si el valor de la clave de búsqueda no aparece en el índice, el sistema inserta en éste un registro índice con el valor de la clave de búsqueda en la posición adecuada.
    - - Se asume que el índice almacena una entrada por cada bloque. Si el sistema crea un bloque nuevo, inserta el primer valor de la clave de búsqueda (en el orden de la clave de búsqueda) que aparezca en el nuevo bloque del índice
  - - - Índices densos
        
        Si el registro borrado era el único registro con ese valor de la clave de búsqueda, el sistema borra el registro índice correspondiente del índice
        
        En caso contrario se emprenden las siguientes
        acciones
        
        a. Si el registro índice almacena punteros a todos los registros con el mismo valor de la clave de búsqueda, el sistema borra del registro índice el puntero al registro borrado.
        
        b. En caso contrario, el registro índice almacena un puntero sólo al primer registro con el valor de la clave de búsqueda. En este caso, si el registro borrado era el primer registro con el valor de la clave de búsqueda, el sistema actualiza el registro índice para apuntar al siguiente registro
      - Índices dispersos
        
        Si el índice no contiene un registro índice con el valor de la clave de búsqueda del registro borrado, no hay que hacer nada
        
        En caso contrario se emprenden las siguientes
        acciones
        
        a. Si el registro borrado era el único registro con la clave de búsqueda, el sistema reemplaza el registro índice correspondiente con un registro índice para el siguiente valor de la clave de búsqueda (en el orden de la clave de búsqueda). Si el siguiente valor de la clave de búsqueda ya tiene una entrada en el índice, se borra en lugar de reemplazarla
        
        b. En caso contrario, si el registro índice para el valor de la clave de búsqueda apunta al registro a borrar, el sistema actualiza el registro índice para que apunte al siguiente registro con el mismo valor de la clave de búsqueda
- - - - Funciones de asociación
        
        • Distribución uniforme. Esto es, cada cajón tiene asignado el mismo número de valores de la clave de búsqueda dentro del conjunto de todos los valores posibles de la clave de búsqueda
        
        • Distribución aleatoria. Esto es, en el caso promedio, cada cajón tendrá casi el mismo número de valores asignados a él, sin tener en cuenta la distribución actual de los valores de la clave de búsqueda
    - - Los desbordamientos de cajones pueden
        ocurrir por varias razones
        
        • Cajones insuficientes. El número de cajones, que se denota con nB, debe ser escogido tal que nC > nr / fr, donde nr denota el número total de registros que serán almacenados, y fr denota el número de registros que se colocarán en un cajón
        
        • Atasco. Algunos cajones tienen asignados más registros que otros, por lo que un cajón se podría desbordar incluso cuando otros cajones tienen todavía espacio