Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Indexación y Asociacion

No description
by

Jorge galvan

on 23 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Indexación y Asociacion

índice de un libro
Un índice para un archivo del sistema funciona como el índice de un libro. Si se va a buscar un tema.
Se puede buscar en el índice al final del libro, encontrar las páginas en las que aparece y después leer esas páginas para encontrar la información que estamos buscando.
Índices
Tipos de índices
* Índices ordenados. Estos índices están basados en una disposición ordenada de los valores.

* Índices asociativos (hash indices). Estos índices están basados en una distribución uniforme de los valores a través de una serie de cajones (buckets). El valor asignado a cada cajón está determinado por una función, llamada función de asociación (hash function).

Se considerarán varias técnicas de indexación y asociación. Ninguna de ellas es la mejor. Sin embargo, cada técnica es la más apropiada para una aplicación específica de bases de datos.
Índices de base de datos
Los índices de los sistemas de bases de datos juegan el mismo papel que los índices de los libros o los catálogos de fichas de las bibliotecas. Por ejemplo, para recuperar un registro cuenta dado su número de cuenta, el sistema de bases de datos buscaría en un índice para encontrar el bloque de disco en que se encuentra el registro correspondiente, y entonces extraería ese bloque de disco para obtener el registro cuenta. Encontrar una cuenta puede consumir mucho tiempo. En su lugar se usan técnicas más sofisticadas de indexación.
12. 1 Conceptos básicos
Indexación y Asociación
Tipos de indexación
Cada técnica debe ser valorada según los siguientes criterios:

• Tipos de acceso. Los tipos de acceso que se soportan eficazmente. Estos tipos podrían incluir la búsqueda de registros con un valor concreto en un atributo, o buscar los registros cuyos atributos contengan valores en un rango especificado.

• Tiempo de acceso.El tiempo que se tarda en buscar un determinado elemento de datos, o conjunto de elementos, usando la técnica en cuestión.

• Tiempo de inserción. El tiempo empleado en insertar un nuevo elemento de datos. Este valor incluye el tiempo utilizado en buscar el lugar apropiado donde insertar el nuevo elemento de datos, así como el tiempo empleado en actualizar la estructura del índice.

• Tiempo de borrado.El tiempo empleado en borrar un elemento de datos. Este valor incluye el tiempo utilizado en buscar el elemento a borrar, así como el tiempo empleado en actualizar la estructura del índice.

Espacio adicional requerido. El espacio adicional ocupado por la estructura del índice. Como normalmente la cantidad necesaria de espacio adicional suele ser moderada, es razonable sacrificar el espacio para alcanzar un rendimiento mejor.
12.2. ÍNDICES ORDENADOS
Un archivo puede tener varios índices según diferentes claves de búsqueda. Si el archivo que contiene los registros está ordenado secuencialmente, el índice cuya clave de búsqueda especifica el orden secuencial del archivo es el índice primario.
12.2.1. Índice primario
Los índices primarios también se llaman índices con agrupación(clustering indices.) La clave de búsqueda de un índice primario es normalmente la clave primaria, aunque no es así necesariamente. Los índices cuyas claves de búsqueda especifican un orden diferente del orden secuencial del archivo se llaman índices secundarios o índices sin agrupación (non clustering indices).

12.2.1.1. Índices densos y dispersos
Un registro índice o entrada del índice consiste en un valor de la clave de búsqueda y punteros a uno o más registros con ese valor de la clave de búsqueda.
El puntero a un registro consiste en el identificador de un bloque de disco y un desplazamiento en el bloque de disco para identificar el registro dentro del bloque.
Í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.
El resto de registros con el mismo valor de la clave de búsqueda se almacenan consecutivamente después del primer registro y se ordenan sobre la misma clave de búsqueda.
Las implementaciones de índices densos pueden almacenar una lista de punteros a todos los registros con el mismo valor de la clave de búsqueda; esto no es esencial para los índices primarios
Í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. Para localizar un registro se busca la entrada del índice con el valor más grande que sea menor o igual que el valor que se está buscando. Se empieza por el registro apuntado por esa entrada del índice y se continúa con los punteros del archivo hasta encontrar el registro deseado.

12.2.1.2. Índices multinivel
Los índices con dos o más niveles se llaman índices multinivel. La búsqueda de registros usando un índice multinivel necesita claramente menos operaciones de E/S que las que se emplean en la búsqueda de registros con la búsqueda binaria.
Cada nivel de índice se podría corresponder con una
unidad del almacenamiento físico. Así, podríamos tener
índices a nivel de pista, cilindro o disco.
Un diccionario normal es un ejemplo de un índice
multinivel en el mundo ajeno a las bases de datos. La
cabecera de cada página lista la primera palabra en el
orden alfabético en esa página. Este índice es multinivel:
las palabras en la parte superior de la página del
índice del libro forman un índice disperso sobre los contenidos
de las páginas del diccionario.
12.2.1.3. Actualización del índice
Sin importar el tipo de índice que se esté usando, los índices se deben actualizar siempre que se inserte o borre un registro del archivo.
*Inserción-. Primero se realiza una búsqueda usando el valor de la clave de búsqueda del registro a insertar.
*Borrado-. Para borrar un registro, primero se busca el índice a borrar.

12.2.2. Índices secundarios
Los índices secundarios deben ser densos, con una entrada en el índice por cada valor de la clave de búsqueda, y un puntero a cada registro del archivo.
Si un índice secundario almacena sólo algunos de los valores de la clave de búsqueda, los registros con los valores de la clave de búsqueda intermedios pueden estar en cualquier lugar del archivo y, en general, no se pueden encontrar sin explorar el archivo completo.
Full transcript