indices recuperado

27
1 INDICES Introducción Un índice es un archivo usado para agilizar la recuperación de los registros. Es redundante puesto que la información que almacena se encuentra en el archivo al cual indexa. La ventaja, sin duda, viene por la vía de recuperar los registros de manera más rápida. La función de los índices consiste en asignar una clave asociada a un tipo de archivo o dato con la se va a identificar, de ese modo se pueden realizar las búsquedas por los índices y no por los datos, dado que los índices cumplen con un orden la búsqueda será mucho más óptima y rápida que al hacerla sobre los archivos directamente. El índice tiene un funcionamiento similar al índice de un libro, guardando parejas de elementos: el elemento que se desea indexar y su posición en la base de datos. Para buscar un elemento que esté indexado, sólo hay que buscar en el índice dicho elemento para, una vez encontrado, devolver el registro que se encuentre en la posición marcada por el índice. Los índices pueden ser creados usando una o más columnas, proporcionando la base tanto para búsquedas rápidas al azar como de un ordenado acceso a registros eficiente, es

Upload: stiven

Post on 30-Sep-2015

242 views

Category:

Documents


0 download

DESCRIPTION

Descripción sobre indices ciencias de la comutación

TRANSCRIPT

INDICES

Introduccin

Un ndice es un archivo usado para agilizar la recuperacin de los registros. Es redundante puesto que la informacin que almacena se encuentra en el archivo al cual indexa. La ventaja, sin duda, viene por la va de recuperar los registros de manera ms rpida.La funcin de los ndices consiste en asignar una clave asociada a un tipo de archivo o dato con la se va a identificar, de ese modo se pueden realizar las bsquedas por los ndices y no por los datos, dado que los ndices cumplen con un orden la bsqueda ser mucho ms ptima y rpida que al hacerla sobre los archivos directamente.El ndice tiene un funcionamiento similar al ndice de un libro, guardando parejas de elementos: el elemento que se desea indexar y su posicin en la base de datos. Para buscar un elemento que est indexado, slo hay que buscar en el ndice dicho elemento para, una vez encontrado, devolver el registro que se encuentre en la posicin marcada por el ndice.Los ndices pueden ser creados usando una o ms columnas, proporcionando la base tanto para bsquedas rpidas al azar como de un ordenado acceso a registros eficiente, es redundante puesto que la informacin que almacena se encuentra en el archivo al cual indexa.Los catlogos de fichas en las bibliotecas funcionan de manera similar (aunque se usan poco). Para encontrar un libro de un autor en particular, se buscara en el catlogo de autores y una ficha de este catlogo indicara dnde encontrar el libro. Para ayudarnos en la bsqueda en el catlogo, la biblioteca guardara en orden alfabtico las fichas de los autores con una ficha por cada autor de cada libro. Los ndices de los sistemas de bases de datos juegan el mismo papel que los ndices de los libros o los catlogos de fichas de las bibliotecas. Por ejemplo, para recuperar un registro cuenta dado su nmero de cuenta, el sistema de bases de datos buscara en un ndice para encontrar el bloque de disco en que se encuentra el registro correspondiente, y entonces extraera ese bloque de disco para obtener el registro cuenta.

Objetivos

Mediante una consulta investigar los significados de ndices para dar una introduccin al tema que se ha de ver profundizado posteriormente, de tal forma inducir al estudiante a llevar cierta idea acerca de la temtica a la cual se centrara la prxima clase.

Respaldar las temticas investigadas con ejemplos que permitan con mayor facilidad comprender de que se trata cada apartado del documento, de esta forma permitir de manera mas didctica el tema del cual se est tratando.

Mejorar el autoaprendizaje del estudiante e impulsarlo realizar escritos que sigan unas normas especficas las cuales permitan una presentacin correcta de documentos y de esta forma guiarlo para posteriores situaciones que requieran de estas competencias.

Definicin 1[footnoteRef:1] [1: FUNDAMENTOS DE BASES DE DATOS - Archivos.pdf, accedido 23 de marzo de 2015, http://bbeltran.cs.buap.mx/Archivos.pdf.]

ndices de un solo nivelPara lograr un acceso directo, rpido a los registros de un archivo se puede usar una estructura de ndice. Cada estructura de ndice est asociada con una clave de bsqueda concreta. Al igual que en el catlogo de una biblioteca, un ndice almacena de manera ordenada los valores de las claves de bsqueda, y asocia a cada clave los registros que contienen esa clave de bsqueda.Los registros en el archivo indexado pueden estar a su vez almacenados siguiendo un orden, semejante a como los libros estn ordenados en una biblioteca por algn atributo como el nmero decimal Dewey. Un archivo puede tener varios ndices segn diferentes claves de bsqueda.ndices primarios:Un ndice primario o simple es aquel que guarda nicamente la llave primaria, identificando de forma nica a un registro almacenado en un fichero. El ndice guarda el campo clave y la direccin fsica del fichero, Se basan principalmente en archivos ordenados secuencialmente.Se denomina ndice primario cuando el archivo de datos asociado se encuentra ordenado en base a la llave de bsqueda, en este apartado se asume que todos los archivos estn ordenados secuencialmente segn alguna clave de bsqueda. Estos archivos con ndice primario segn una clave de bsqueda se llaman archivos secuenciales indexados. Representan uno de los esquemas de ndices ms antiguos usados por los sistemas de bases de datos. Se emplean en aquellas aplicaciones que demandan un procesamiento secuencial del archivo completo as como un acceso directo a sus registros.

En la figura se muestra un archivo secuencial de los registros tomados de ejemplo. En esta figura, los registros estn almacenados segn el orden de la clave de bsqueda de una manera ordenada, siendo el primer ndice a la izq.Un ndice primario es un fichero ordenado cuyos registros son de longitud fija y contienen dos campos. El primero de estos campos tiene el mismo tipo de datos que el campo clave de ordenacin (llamado clave primaria) del fichero de datos, y el segundo campo es un puntero a un bloque de disco (una direccin de bloque). Hay una entrada de ndice (o registro de ndice) en el fichero del ndice por cada bloque del fichero de datos. Cada entrada del ndice contiene, como valores de sus dos campos, la clave primaria del primer registro de un bloque y un puntero a ese bloque.Un problema importante con los ndices primarios as como con cualquier fichero ordenado, es la insercin y eliminacin de registros. El problema se complica en el caso de un ndice primario, porque si intentamos insertar un registro en su posicin correcta dentro del fichero de datos, no solo debemos desplazar registros a fin de abrir espacio para el nuevo registro, sino que tendremos que modificar algunas entradas del ndice, pues el desplazamiento de registros alterara los registros ancla de algunos bloques.Un registro ndice o entrada del ndice consiste en un valor de la clave de bsqueda y punteros a uno o ms registros con ese valor de la clave de bsqueda. 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. Hay dos clases de ndices ordenados que se pueden emplear: ndice denso. Aparece un registro ndice por cada valor de la clave de bsqueda 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 bsqueda. El resto de registros con el mismo valor de la clave de bsqueda se almacenan consecutivamente despus del primer registro, dado que, ya que el ndice es primario, los registros se ordenan sobre la misma clave de bsqueda. Las implementaciones de ndices densos pueden almacenar una lista de punteros a todos los registros con el mismo valor de la clave de bsqueda; esto no es esencial para los ndices primarios.

ndice disperso. Slo 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 bsqueda 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 ms 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 contina con los punteros del archivo hasta encontrar el registro deseado.

Utilizando como ejemplos las figuras a modo de comparacin se supone que se quiere realizar la bsqueda de la sucursal pamplona. Mediante el ndice denso de la primera figura, se sigue el puntero que va directo al primer registro de Pamplona. Se procesa el registro y se sigue el puntero en ese registro hasta localizar el siguiente registro segn el orden de la clave de bsqueda (nombre-sucursal). Se continuara procesando registros hasta encontrar uno cuyo nombre de sucursal fuese distinto de Pamplona. Si se usa un ndice disperso (segunda figura), no se encontrara entrada del ndice para Pamplona. Como la ltima entrada (en orden alfabtico) antes de Pamplona es Madrid, se sigue ese puntero. Entonces se lee el archivo cuenta en orden secuencial hasta encontrar el primer registro Pamplona, y se contina procesando desde este punto. Como se ha visto, generalmente es ms rpido localizar un registro si se usa un ndice denso en vez de un ndice disperso. Sin embargo, los ndices dispersos tienen algunas ventajas sobre los ndices densos, como el utilizar un espacio ms reducido y un mantenimiento adicional menor para las inserciones y borrados.ndices secundarios:Un ndice secundario es tambin un fichero ordenado con dos campos. El primer campo es del mismo tipo de datos que el de cualquier campo que no sea el de ordenacin del fichero de datos, y se denomina campo de indexacin. El segundo campo es o bien un puntero a bloque o bien un puntero a registro. Puede haber varios ndices secundarios (y por lo tanto, campos de indexacin) para el mismo fichero.Los ndices secundarios deben ser densos, con una entrada en el ndice por cada valor de la clave de bsqueda, y un puntero a cada registro del archivo. Un ndice primario puede ser disperso, almacenando slo algunos de los valores de la clave de bsqueda, ya que siempre es posible encontrar registros con valores de la clave de bsqueda intermedios mediante un acceso secuencial a parte del archivo, como se describi antes. Si un ndice secundario almacena slo algunos de los valores de la clave de bsqueda, los registros con los valores de la clave de bsqueda intermedios pueden estar en cualquier lugar del archivo y, en general, no se pueden encontrar sin explorar el archivo completo. Un ndice secundario sobre una clave candidata es como un ndice denso primario, excepto en que los registros apuntados por los sucesivos valores del ndice no estn almacenados secuencialmente. Por lo general, los ndices secundarios estn estructurados de manera diferente a como lo estn los ndices primarios. Si la clave de bsqueda de un ndice primario no es una clave candidata, es suficiente si el valor de cada entrada en el ndice apunta al primer registro con ese valor en la clave de bsqueda, ya que los otros registros podran ser alcanzados por una bsqueda secuencial del archivo. En cambio, si la clave de bsqueda de un ndice secundario no es una clave candidata, no sera suficiente apuntar slo al primer registro de cada valor de la clave. El resto de registros con el mismo valor de la clave de bsqueda podran estar en cualquier otro sitio del archivo, ya que los registros estn ordenados segn la clave de bsqueda del ndice primario, en vez de la clave de bsqueda del ndice secundario. Por tanto, un ndice secundario debe contener punteros a todos los registros. Se puede usar un nivel adicional de indireccin para implementar los ndices secundarios sobre claves de bsqueda que no sean claves candidatas. Los punteros en estos ndices secundarios no apuntan directamente al archivo. En vez de eso, cada puntero apunta a un cajn que contiene punteros al archivo. En la Figura 12.5 se muestra la estructura del archivo cuenta, con un ndice secundario que emplea un nivel de indireccin adicional, y teniendo como clave de bsqueda el saldoSiguiendo el orden de un ndice primario, una bsqueda secuencial es eficiente porque los registros del archivo estn guardados fsicamente de la misma manera a como est ordenado el ndice. Sin embargo, no se puede (salvo en raros casos excepcionales) almacenar el archivo ordenado fsicamente por el orden de la clave de bsqueda del ndice primario y la clave de bsqueda del ndice secundario. Ya que el orden de la clave secundaria y el orden fsico difieren, si se intenta examinar el archivo secuencialmente por el orden de la clave secundaria, es muy probable que la lectura de cada bloque suponga la lectura de un nuevo bloque del disco, lo cual es muy lento

Los ndices secundarios mejoran el rendimiento de las consultas que emplean claves que no son la de bsqueda del ndice primario. Sin embargo, implican un tiempo adicional importante al modificar la base de datos. El diseador de la base de datos debe decidir qu ndices secundarios son deseables, segn una estimacin sobre las frecuencias de las consultas y las modificaciones.ndices de agrupacin:Un ndice de agrupacin es equivalente a un ndice ordenado dado que es tambin un fichero ordenado con dos campos; el primero es del mismo tipo que el campo de agrupacin del fichero de datos, y el segundo es un puntero a un bloque. Hay una entrada en el ndice de agrupacin por cada valor distinto del campo de agrupacin y contiene el valor y un puntero al primer bloque del fichero de datos que tenga un registro con ese valor en el campo de la agrupacin.Si los registros de un fichero estn ordenados fsicamente segn un campo no clave, que no tiene un valor distinto para cada registro, dicho campo e denomina campo de agrupacin. Lo que lo diferencia de un ndice primario, que quiere que el campo de ordenacin del fichero de datos tenga un valor distinto para cada registro.

En la figura se observa que la insercin y la eliminacin pueden seguir causando problemas al manejar ficheros ordenados fsicamente. A fin de aliviar el problema de insercin, se puede reservar un bloque completo (o un grupo de bloques contiguos) por cada valor del campo de agrupacin; todos los registros con ese valor se colocan en el bloque (o grupo de bloques), esto hace relativamente sencillas la insercin y la eliminacin.Los ndices de agrupacin son un ejemplo ms de ndices no densos, porque tienen una entrada por cada valor distinto del campo de indexacin, no por cada registro del fichero. Una diferencia importante es que la bsqueda de un ndice utiliza los valores del propio campo de bsqueda, en tanto que la bsqueda en un directorio de direccionamiento calculado emplea los valores de direccionamiento que se calculan aplicando la funcin de direccionamiento calculado al campo de bsqueda.

ndices multinivelLos ndices multinivel se basan en el planteamiento de varios niveles para la indexacin de ficheros o archivos, inicialmente este considera al fichero del ndice, al que ahora llamaremos primer nivel (o nivel base) del ndice multinivel, como un fichero ordenado con un valor distinto para cada Dato(i), por tanto, podemos crear un ndice primario para este primer nivel; a este ndice del primer nivel se le denomina segundo nivel del ndice multinivel. Como el segundo nivel es un ndice primario, podemos usar anclas de bloques para que el segundo nivel tenga una entrada por cada bloque del primer nivel. El factor de bloques del segundo nivel, y de todos los niveles siguientes, es el mismo que el ndice de primer nivel, porque todas las entradas del ndice tienen el mismo tamao; cada una tiene un valor de campo y una direccin de bloque. Incluso si se usan ndices dispersos, el propio ndice podra ser demasiado grande para un procesamiento eficiente. En la prctica no es excesivo tener un archivo con 100.000 registros, con 10 registros almacenados en cada bloque. Si tenemos un registro ndice por cada bloque, el ndice tendr 10.000 registros. Como los registros ndices son ms pequeos que los registros de datos, podemos suponer que caben 100 registros ndices en un bloque. Por tanto, el ndice ocupara 100 bloques. Estos ndices de mayor tamao se almacenan como archivos secuenciales en disco.Si un ndice es lo bastante pequeo como para guardarlo en la memoria principal, el tiempo de bsqueda para encontrar una entrada ser breve. Sin embargo, si el ndice es tan grande que se debe guardar en disco, buscar una entrada implicar leer varios bloques de disco. Para localizar una entrada en el archivo ndice se puede realizar una bsqueda binaria, pero aun as sta conlleva un gran coste. Si el ndice ocupa b bloques, la bsqueda binaria tendr que leer a lo sumo Llog2(b)J bloques. (LxJ denota al menor entero que es mayor o igual a x; es decir, se redondea hacia abajo.) Para el ndice de 100 bloques, la bsqueda binaria necesitar leer siete bloques. En un disco en el que la lectura de un bloque tarda 30 milisegundos, la bsqueda emplear 210 milisegundos, lo que es mucho. Obsrvese que si se estn usando bloques de desbordamiento, la bsqueda binaria no sera posible. En ese caso, lo normal es una bsqueda secuencial, y eso requiere leer b bloques, lo que podra consumir incluso ms tiempo. As, el proceso de buscar en un ndice grande puede ser muy costosoPara resolver este problema se trata el ndice como si fuese un archivo secuencial y se construye un ndice disperso sobre el ndice primario, como se muestra en la Figura 12.4. Para localizar un registro se usa en primer lugar una bsqueda binaria sobre el ndice ms externo para buscar el registro con el mayor valor de la clave de bsqueda que sea menor o igual al valor deseado. El puntero apunta a un bloque en el ndice ms interno. Hay que examinar este bloque hasta encontrar el registro con el mayor valor de la clave que sea menor o igual que el valor deseado. El puntero de este registro apunta al bloque del archivo que contiene el registro buscado. Usando los dos niveles de indexacin y con el ndice ms externo en memoria principal, tenemos que leer un nico bloque ndice en vez de los siete que se lean con la bsqueda binaria. Si al archivo es extremadamente grande, incluso el ndice exterior podra crecer demasiado para caber en la memoria principal. En este caso se podra crear todava otro nivel ms de indexacin. De hecho, se podra repetir este proceso tantas veces como fuese necesario. Los ndices con dos o ms niveles se llaman ndices multinivel. La bsqueda de registros usando un ndice multinivel necesita claramente menos operaciones de E/S que las que se emplean en la bsqueda de registros con la bsqueda binaria. Cada nivel de ndice se podra corresponder con una unidad del almacenamiento fsico. As, podramos 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 pgina lista la primera palabra en el orden alfabtico en esa pgina. Este ndice es multinivel: las palabras en la parte superior de la pgina del ndice del libro forman un ndice disperso sobre los contenidos de las pginas del diccionario.En la siguiente figura se puede apreciar una estructura implementada con ndices multinivel, la cual como se mencionaba antes parece tener una estructura de tipo rbol, con lo cual se disminuye el gasto de memoria y el tiempo en bsquedas indexadas.El esquema multinivel se puede usar para cualquier tipo de ndice, sea primario, de agrupacin o secundario, siempre que el ndice del primer nivel tenga valores distintos y entradas de longitud fija, en la siguiente se muestra un ndice multinivel construido sobre un ndice primario.

Definicin 2[footnoteRef:2] [2: indices.pdf, accedido 23 de marzo de 2015, http://www.inf.utfsm.cl/~wpalma/ari/indices.pdf.]

ndices de un solo nivel.Los ndices de un solo nivel son ficheros ordenados los cuales tienen registros con dos campos, Los ndices de un solo nivel son los nicos en los cuales se pueden realizar bsquedas binarias, porque un ndice de un solo nivel es un fichero ordenado y sobre un fichero ordenado la bsqueda binaria es, en general, ms rpida que la bsqueda lineal. Cuando el ndice de un nivel es demasiado grande, el ndice cambia si lo hace el fichero de datos al que va asociado y ms concretamente si estos cambios afectan al campo de ordenacin del ndice. En estos casos hay que reorganizar el ndice, lo cual supone un elevado coste y es un problema que se agrava si el ndice es grande. Se puede solucionar utilizando zonas de desborde. De esta forma el ndice slo se reorganiza cada cierto tiempo. ndices Primarios o Principales:Es construido sobre un campo que a su vez se utiliza para ordenar el archivo de datos. Caractersticas: Sobre un fichero ordenado por clave slo puede definirse un ndice primario. Archivo ordenado con registros de longitud fija. Cada entrada del ndice tiene 2 campos: Uno del mismo tipo del campo clave. Un puntero a bloque de disco. El nmero de entradas en el ndice es igual al nmero de bloques de disco. ndice no denso. Ocupa menos bloques que el rea de datos, ya que por cada bloque de datos tiene slo una entrada en el ndice y adems cada entrada es ms pequea que un registro.

Ejemplo:

ndice Secundario:Un ndice que no es un ndice de particionamiento es un ndice secundario. Un ndice puede estar particionado o no particionado. Puede crear un ndice en una tabla para proporcionar vas de acceso a datos para consultas para imponer una restriccin de exclusividad o para agrupar datos en clsteres. En pocas palabras se puede decir que un ndice secundario es cualquier ndice que se define sobre un campo que no es campo de ordenacin; a su vez es un fichero ordenado con registros de longitud (fija o variable).Caractersticas: Cada entrada en el ndice posee dos campos: Uno del mismo tipo de algn campo no ordenado del archivo de datos. Un puntero a bloque de disco. Si el campo de indexacin es clave, entonces se dice que el ndice es denso. Un ndice secundario es un ndice de un solo nivel. Estos ndices son ficheros ordenados y sobre un fichero ordenado podemos realizar bsquedas binarias.Ejemplo:

ndices de Agrupacin:Es un ndice que est definido sobre el campo de ordenacin de un fichero ordenado con registros de longitud fija, siendo ste un campo no clave. Caractersticas: Archivo de datos ordenado, el campo de ordenamiento presenta repeticiones. Cada entrada en el ndice tiene dos campos: Un campo del mismo tipo del campo de ordenamiento. Puntero a bloque de disco. Una entrada en el ndice para cada valor distinto del campo de ordenamiento.Con los ndices de agrupacin se obtienen una serie de ventajas como es la mejora del tiempo de acceso de determinadas consultas. Tambin se tienen inconvenientes como es que empeoran otros accesos (por ejemplo las bsquedas de ventas de un determinado artculo). Otro inconveniente es que se trata de ficheros (de alguna manera) ordenados con todos los inconvenientes que ello conlleva.Ejemplo:

ndices MultinivelPodemos repetir la idea de creacin de ndices tantas veces sea necesario. Es decir, podemos tener muchos niveles de ndices que sencillamente apuntan a otros ndices. Que finalmente apuntan a un registro de la tabla. Con esto ya se reduce aun ms el tiempo. La bsqueda de registros usando un ndice multinivel necesita claramente menos operaciones de E/S que las que se emplean en la bsqueda de registros con la bsqueda binaria, incluso cada nivel de ndice se podra corresponder con una unidad del almacenamiento fsico. As, se podran tener ndices a nivel de pista, cilindro o disco.Caractersticas: Coste de bsqueda de los registros: Logaritmo(base r)b r= numero de registros de ndice que caben en un bloque Se pretende reducir el tamao del trozo del ndice en el que se va a seguir buscando en r Tiempo de acceso: Ventaja que el nivel N quepa en memoria El numero de bloques que se tiene que leer para acceder a los datos es N

Ejemplo:Se parte siempre de un fichero ndice de un nivel (nivel base del ndice ) ordenado y con entradas de tamao fijo. Si este primer nivel ocupa mas de un bloque, se define un ndice de nivel sobre el nivel base (seria el 2 nivel) Se repite el proceso hasta que el ndice de nivel N quepa en un nico bloque de disco El nivel N ser el nivel mximo del ndice multinivel El segundo nivel tiene una entrada por cada bloque del primer nivel El tercer nivel tiene una entrada por cada bloque de segundo nivel As sucesivamente Actualizacin del ndice:Los algoritmos de insercin y borrado para los ndices multinivel se extienden de manera sencilla. Al borrar o al insertar se actualiza el ndice de nivel ms bajo. Por lo que respecta al ndice del segundo nivel, el ndice de nivel ms bajo es simplemente un archivo de registros; as, si hay algn cambio en el ndice de nivel ms bajo, se tendr que actualizarle ndice del segundo nivel. La misma tcnica se aplica al resto de niveles del ndice, si los hubiera.Borrado:Para borrar un registro, primero se busca el ndice a borrar. De nuevo, las acciones que emprende el sistema a continuacin dependen de si el ndice es denso o disperso.

ndices densos: Si el registro borrado era el nico registro con ese valor de la clave de bsqueda, el sistema borra el registro ndice correspondiente del ndice. En caso contrario se emprenden las siguientes acciones: Si el registro ndice almacena punteros a todos los registros con el mismo valor dela clave de bsqueda, el sistema borra del registro ndice el puntero al registro borrado. En caso contrario, el registro ndice almacena un puntero slo al primer registro con el valor de la clave de bsqueda. En este caso, si el registro borrado era el primer registro con el valor de la clave de bsqueda, 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 bsqueda del registro borrado, no hay que hacer nada. En caso contrario se emprenden las siguientes acciones: Si el registro borrado era el nico registro con la clave de bsqueda, el sistema reemplaza el registro ndice correspondiente con un registro ndice para el siguiente valor de la clave de bsqueda (en el orden de la clave de bsqueda). Si el siguiente valor de la clave de bsqueda ya tiene una entrada en el ndice, se borra en lugar de reemplazarla. En caso contrario, si el registro ndice para el valor de la clave de bsqueda 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 bsqueda.

Insercin:Primero se realiza una bsqueda usando el valor de la clave de bsqueda del registro a insertar. Las acciones que emprende el sistema a continuacin dependen de si el ndice es denso o disperso. ndices densos: Si el valor de la clave de bsqueda no aparece en el ndice, el sistema inserta en ste un registro ndice con el valor de la clave de bsqueda en la posicin adecuada. En caso contrario se emprenden las siguientes acciones: Si el registro ndice almacena punteros a todos los registros con el mismo valor dela clave de bsqueda, el sistema aade un puntero al nuevo registro en el registro ndice. En caso contrario, el registro ndice almacena un puntero slo hacia el primer registro con el valor de la clave de bsqueda. El sistema sita el registro insertado despus de los otros con los mismos valores de la clave de bsqueda.

ndices dispersos: 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 bsqueda (en el orden de la clave de bsqueda) que aparezca en el nuevo bloque del ndice. Por otra parte, si el nuevo registro tiene el menor valor de la clave de bsqueda en su bloque, el sistema actualiza la entrada del ndice que apunta al bloque; si no el sistema no realiza ningn cambio sobre el ndice.

Ejemplos propuestosIndices de un solo nivelIndices primariosEn el siguiente caso se tienen bloques con un cdigo y un nombre, ordenados por el nmero de cdigo:

Los indices contienen los atributos del primer elmento de cada bloque.En este caso (1-Mario, 52-Leonardo, 112-Brayan, 151-Stiven, 220-Juan, 257-Lucas) son los primeros atibutos de cada bloque, as estos pasan a formar parte del atributo de los indices.

Indices secundariosEn el siguiente ejemplo se tiene un cdigo y el nombre de cada ciudad, donde el codigo es la clave primaria, y se encuentra ordenada:

El indice esta construido sobre un campo que no es clave primaria., en este caso la clave primara es un cdigo, y se encuentra ordenada, sin embargo el atributo que se encuentra en el ndice es el nombre de la ciudad.Es un indice denso por tanto cada registro debe tener un lugar en el indice.

Indices por agrupamientoPara el siguiente ejemplo los bloques contienen registros de cdigos aereos y de numeros de vuelo:

Los registro se encuentran ordenados por un campo que no es nico, en este caso cdigos de vuelos de 3 letras, estos pasan a ser un atributo del indice, adems del nmero del bloque.

BibliografaBasesdatos_teo8_memoria_secundaria.pdf. Accedido 23 de marzo de 2015. http://www.tejedoresdelweb.com/wiki/images/0/0b/Basesdatos_teo8_memoria_secundaria.pdf.Cair, Osvaldo, Osvaldo Cairo Battistutti, y Silvia Guardati Buemo. Estructuras de datos. McGraw-Hill, 1993.Capitulo6.pdf. Accedido 23 de marzo de 2015. http://changuitos.free.fr/Basesdedatos/Capitulo6.pdf.Conceptos Indices. Accedido 23 de marzo de 2015. http://www.aulaclic.es/sql/b_8_4_1.htm.ESTRUCTURA DE DATOS.- - CAPI5.pdf. Accedido 23 de marzo de 2015. http://robotica.uv.es/pub/Libro/PDFs/CAPI5.pdf.Figueroa, Zenn Jos Hernndez, Jos Daniel Gonzlez Domnguez, Juan Carlos Rodrguez del Pino, Margarita Daz Roca, Jos Rafael Prez Aguilar, y Gustavo Rodrguez Rodrguez. Fundamentos de estructuras de datos: soluciones en Ada, Java y C++. Thomson, 2005.FUNDAMENTOS DE BASES DE DATOS - Archivos.pdf. Accedido 23 de marzo de 2015. http://bbeltran.cs.buap.mx/Archivos.pdf.indices.pdf. Accedido 23 de marzo de 2015. http://www.inf.utfsm.cl/~wpalma/ari/indices.pdf.Oliet, Narciso Mart, Yolanda Ortega Malln, y Jos Alberto Verdejo Lpez. Estructuras de datos y mtodos algortmicos: ejercicios resueltos. Pearson Educacin, 2004.

2