- Memoria Principal (RAM)
- Tiempo de acceso bajo
- Capacidad de almacenamiento bajo
- Es volatil
- Memoria Secundaria (HDD,DVD,..)
- Tiempo de acceso elevado (movimiento del cabezal)
- Capacidad de almacenamiento alto
- No es volatil
La idea basica, es almacenar los datos en memoria secundaria, pero acceder directamente a ellos a traves de un indice que estara soportado por una estructura de datos, y no de forma secuencial.
El 80% del tiempo se pieder en el movimiento del cabezal. Se lee y se escribe Uble a Uble.
INDICE:
- Estructura de acceso que se utiliza para acelerar el acceso a los registros; en respuesta a ciertas condiciones de busqueda.
- Ordenacion virtual del fichero que permite encontrar la informacion mas facilmente
Tipos de indice
- VECTORES
- Ventajas: Acceso a memoria, busquedas binarioas o dicotomicas.
- Inconvenientes: Limitacion de memoria, tamaño del vector (no son dinamicos), inserccion o borrado costosas
- LISTAS ENLAZADAS
- Ventajas: Acceso a memoria, no esta limitada de tamaño, actualizar una lista es menos costosa que un vector
- Inconvenientes: Limitacion de la memoria, la busqueda de los indices es secuencial
- ABB - BST (Arboles Binarios de Busqueda - Binary Search Tree)
- Ventajas: Acceso a memoria, el tamaño no esta limitado, busqeudas binarias
- Inconvenientes: Limitacion de la memoria, pueden degenerar en una lista (sumando asi los inconvenientes anteriores)
- APE (Arboles Perfectamente Equilibrados)
- Ventajas: Acceso a memoria, no tiene limitaciones de tamaño, busquedas binarias, no degeneran el una lista.
- Desventajas: Operaciones de reequilibrio muy costosas, mantenimiento de la informacion de equilibrio constantemente
- AVL
El patron o esquema general para el restablecimiento del equilibrio es el siguiente :
ROTACIONES SIMPLES
(I-I)
(D-D)
ROTACIONES DOBLES
(D-I)
(I-D)
- Ventajas: Acceso a Memoria, el tamaño del arbol no esta limitado, busquedas dicotomicas, actualizar este arbol es menos costoso, no degeneran en una lista, rotaciones menos costosas que el reequiibrio de APE
- Inconvenientes: Limitacion de la memoria, las rotaciones siguen siendo costosas, mantenimiento del factor de reequilibrio
A viendo visto todas estas estructuras de datos, pasaremos a estudiar los arboles B, indicando su ventajas mas importantes respecto a las estructuras anteriores.
ARBOLES B
Caracteristicas :
- Multicamino
- De busqueda (esta rodenado)
- Todas las hojas estan a la misma altura
- Crece hacia arriba, no necesita rotaciones
- MINIMO= 50% , todos los nodos contienen n claves
- MAXIMO= 100%, todos los nodos contienen 2n claves .