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 .
  

Aboles binarios de busqueda PHP Estructuras de Datos

Antes de nada :)

Binary tree (Arboles binarios): In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One common use of binary trees is binary search trees; another is binary heaps.


El codigo fuente para representar cada uno de los nodos es el siguiente

Ahora el codigo que implementa la clase IntBST (Arbol Binario), se muestran las funciones y a continuacion las mismas funciones detalladas



Insert :



Preorder, inorder, postorder :