martes, 13 de noviembre de 2007

Indexacion Arboles B Bases de Datos PHP

Existen dos tipos de almacenamiento:
  1. Memoria Principal (RAM)
    • Tiempo de acceso bajo
    • Capacidad de almacenamiento bajo
    • Es volatil
  1. 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
Casos de desequilibrio, rotaciones





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
Su factor de ocupacion
  • MINIMO= 50% , todos los nodos contienen n claves
  • MAXIMO= 100%, todos los nodos contienen 2n claves .