PDF de programación - Índices y Ordenamiento

Índices y
Índices y

Ordenamiento
Ordenamiento

Héctor Borges
Héctor Borges

Carmen Camacho
Carmen Camacho

Marina Ramos
Marina Ramos

Gaudy Rodríguez
Gaudy Rodríguez

Agenda
Agenda

• Indices estructurados con arboles:

- Indices.

• Alternativas para Entrada de Datos k* en un Índice
• Alternativas para entrada de datos
- Acceso Secuencial Indexado y Árbol B+
- Indexed Sequential Access Method (ISAM)

• Reglas generales para un índice ISAM
• Creacion del Indice

- Árbol B+: El Índice más usado

• Formato de un Nodo
• Búsqueda de un k* en un árbol
• Insertando entradas de datos en árboles B+
• Borrar una entrada de dato del árbol B+
• Comparación por prefijo de llave
• Bulk Loading

…… Agenda
Agenda

…… Agenda
Agenda

• Hash

- Índices Estructurados con Hash
- Hashing Estático
- Deficiencias del Hashing Estático
- Resumen
- Hashing Dinámico

• Hashing Extensible

• La magia está en el directorio…
• Ejemplos
• Análisis de Casos

• Hashing Lineal
• Ejemplos
• Para terminar…

• Ordenamiento Externo e Interno

– Ordenamiento

• Tipos de Ordenamiento

– Ordenamiento Externo (MergeSort)

• Código en C
• MergeSort de Dos Vias

– Ordenamiento Interno (QuickSort)

– HeapSort

• Código en C
• Ejemplo
• Ventajas y Desventajas
• Condiciones Iniciales

• Código en C
• Ejemplo
• Ventajas y Desventajas
• Condiciones Iniciales

– Bibliografía

Índices Estructurados
Índices Estructurados

con Árboles
con Árboles

Índices

• Un archivo nos permite recuperar registros:

– Especificando rid, ó

– Recorriendo todos los registros secuencialmente

• Algunas veces sera necesario recuperar los registros

especificando el valor de uno o mascampos, Ej,

– Buscar todos los estudiantes del curso “MAT”

– Buscar estudiantes con promedio > 16

• Indices son archivos estructurados que nos permiten

contestar eficientemente consultas basadas en valores.

1

Índices

Índices

• Cada indice tiene asociada una llave.

– Los registros almacenados en un archivo de indices,
llamados entradas, nos permiten encontrar registros
dando un valor de búsqueda para la llave.

• Las técnicas de organizacion o estructuras de datos para

los archivos de indices son llamados metodos de acceso, se
conocen varios, incluyendo Arboles y estructuras hash.

• Un índicesobre un archivo acelera las selecciones que se hacen

sobre los campos llave de búsquedadel índice.

– Cualquier subconjunto de los campos de una relación puede
ser la llave de búsqueda para un índice sobre una relación.

– La llave de búsqueda no es la misma que la llave(mínimo

conjunto de campos que identifican como único un registro en
una relación).

• Un índice contiene una colección de entradas de datos, y permite

una eficiente recuperación de todos los entradas de datos k*
dando un valor k para la llave.

Alternativas para Entrada de

Datos k* en un Índice

• Tres alternativas:

(cid:57) Registro de datos con un valor k para la llave.
(cid:57) <k, rid del registro de datos> con valor k para la llave
(cid:57) <k, lista de rids registros de datos> con valor k para la llave

• Elegir la alternativa para las entradas de datos corresponde a la
técnica de indexamiento usada para localizar la entrada de datos
dando un valor k a la llave.

– Ejemplos de técnicas de indexamiento: Árboles B+,

estructuras hash.

– Comúnmente, los índices contienen información auxiliar que

dirige la búsqueda de una entrada de datos deseada.

Alternativas para entrada de

datos

•• Alternativa 1:
Alternativa 1:

Si se usa ésta, las estructura del índice es una organización
de archivo por registros de datos (Como un archivo Heap o
un archivo ordenado).

En mayoría de las veces un índice sobre una colección de
registros puede usar la Alternativa 1. (Si no, los registros
duplicados, conducen a almacenamiento duplicado y potencial
inconsistencia)

Si los registros de datos son muy grandes, el número de
páginas que contienen las entras de datos es mayor. Esto
implica que el tamaño de la información auxiliar en un el índice
es tan también grande.

Alternativas para entrada de

• Alternativas 2 y 3:

datos

Las entradas de datos son normalmente mas pequeñas que
el registro de datos. Entonces, es mejor que la Alternativa
1 con registros de datos grandes, especialmente si las llaves
de búsqueda son pequeñas (La parte de la estructura del
índice usada para dirigir la búsqueda es mucho mas pequeña
que con la Alternativa 1)

Si se requiere mas de un índice sobre un archivo, la mayoría
de las veces un índice puede usar la Alternativa 1; el resto
debe usar la Alternativa 2 o 3.

La alternativa 3 es más compacta que la 2, pero provoca
tamaño variable de las entradas de datos aunque las llaves de
búsqueda sea de largo fijo.

Acceso Secuencial Indexado

y Árbol B+

Índices para búsquedas y reportes
Índices para búsquedas y reportes

Hasta el momento hemos estudiado 2 tipos de estructuras de
archivos:

• Acceso secuencial:

Archivos que pueden recorrerse secuencialmente
(registros contiguos) regresando los registros en algún
orden específico

•

Indexamiento:

Archivos de datos que poseen archivos de índices por
diferentes llaves que permiten acceder los datos de
distintas maneras, el archivo de datos se encuentra sin
ningún orden.

2

Alternativas para Entrada de

Datos k* en un Índice

Los árboles B y los árboles B+ son casos especiales de árboles
de búsqueda. Un árbol de búsqueda es un tipo de árbol que
sirve para guiar la búsqueda de un registro, dado el valor de
uno de sus campos.

En estructuras ISAM y árboles B+, las páginas que están en
las hojas contienen las entradas de datos.

Denotaremos una entrada de datos con el valor k para una
llave de búsqueda k*.

Las páginas que no están en las hojas contienen entradas de
índice de la forma <valor de llave, id de página> y son usadas
para dirigir la búsqueda de la entrada de datos deseada
(almacenada en una hoja).

Índices Tipo Árbol.
Índices Tipo Árbol.

• Estático

-> ISAM es una estructura estática

• Dinámico

-> B-Tree, estructura dinámica.

Acceso Secuencial Indexado

y Árbol B+

Problemas:

• Desafortunadamente el archivo secuencial es difícil de

mantener.

• Los índices nos permiten hacer búsquedas rápidamente pero

...nos permiten recorrer el archivo secuencialmente ??

En realidad el B-Tree sí nos permite recorrer el archivo en
orden, pero no en una manera sencilla ya que debemos hacer
demasiados "seeks" para poder hacerlo.

Acceso Secuencial Indexado

y Árbol B+

En la práctica en muchas situaciones se requieren de ambas cosas

(búsquedas y accesos secuenciales), por ejemplo:

• En la universidad

– Búsquedas: horarios
– Secuenciales: Reportes de calificaciones que se imprimen

• En una empresa

– Búsquedas: agenda telefónica, vacaciones
– Secuenciales: cheques de nómina

• Las 2 soluciones existentes:

- ISAM
- B+ Tree

Indexed Sequential Access

Method (ISAM)

Básicamente es la idea de tener un índice
esparcido, de manera que el archivo de
datos lo agrupamos por bloques y en cada
bloque existe un "rango" ordenado de los
Datos, como vemos en la figura:

ISAM

• Lo importante a resaltar aquí

es que los bloques no
necesariamente están
formando una secuencia en el
archivo, es decir, dentro del
archivo de datos los bloques
pueden estar desordenados,
aquí el detalle es mantener
un apuntador a cada bloque
subsecuente como se
muestra en la figura

3

Reglas generales para un

índice ISAM

• Podemos iniciar el archivo con un bloque o varios (definiendo

previamente los rangos y dejando bloques vacíos reutilizables).

• Cuando agregamos datos ubicamos el bloque correspondiente en
base al índice en memoria y procedemos a agregar la información.

• Si al insertar notamos que el bloque ya esta lleno entonces

tenemos que partirlo en 2, muy similar al btree solo que aqui no
necesitamos un separador de ramas, simplemente creamos otro
bloque, dividimos equitativamente los datos y ajustamos los
apuntadores entre los bloques

• Para eliminar, ubicamos el bloque y eliminamos el registro

Si al eliminar notamos que se pueden mezclar o unir dos bloques
con pocos registros entonces lo podemos hacer y el bloque libre
lo marcamos para reutilización

Creación del Índice

Puede ser muy
simple como el que
se muestra en la
tabla.

Key

BERNE
CAGE
DUTTON
EVANS
FOLK
GADDIS

Block
number

1
2
3
4
5
6

Donde sólo se guardan los
máximos valores de cada
bloque; quizás si las llaves
fueran numéricas todo sería
muy simple y podría quedar
bien este esquema, pero en
especial para cadenas
(aunque también aplica para
números) lo que en realidad
se busca es tener
separadores que sirvan para
varios casos ya que si
eliminamos el máximo valor
de un bloque entonces
tendremos que alterar el
índice.

Creación del Índice

Creación del Índice

La figura muestra una primera solución de separadores basándose
en los prefijos de las palabras. De esta manera nos evitamos el
tener que estar actualizando constantemente el índice. Estos
separadores de rangos nos son únicos, dependerá del programador
el definirlos.

Muestra una lista de opciones para el caso de los

bloques 3 y 4.

Árbol B+: El Índice más

usado

• F = fan-out*, N = # páginas en las hojas.
• Cada nodo contiene d <= m <= 2d entradas.

Entradas de Índices

(Búsqueda directa)

Entrada de Datos

(“Conjunto de secuencias")

Formato de un Nodo

KiKi son los valores de claves de búsqueda.

PiPi son punteros a los hijos para nodos no hojas o

punteros a registros o cajones de punteros a registros

para nodos hojas.

4

Ejemplo de árbol B+

Búsqueda de un k* en un árbol

raíz

13

17

24

30

2* 3* 5* 7*

14* 16*

19* 20* 22*

24* 27* 29*

33* 34* 38* 39*

Insertando entradas de

datos en árboles B+

• Se busca la hoja correcta L.

• Se coloca la entrada de dato sobre L.

• Esto puede suceder recursivamente.

• Las divisiones “agrandan” al árbol; las divisiones de la
raíz incrementan la altura del árbol.

Insertar dentro del árbol B+
Insert