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 .