Arboles b virtuales

Arboles B virtuales.

Se ha estudiado que gracias a algunas mejoras en los arboles b pueden ser una estructura de ordenamiento muy eficiente en el proceso de inserción y borrado de elementos y su reacomodo de dichos elementos, sin embargo, el hecho que el árbol tenga una profundidad de 3 niveles no significa que se tengan que hacer los mismos accesos a disco para encontrar la página hoja, esteaspecto se puede mejorar aún más.
Para obtener un mejor desempeño se necesita examinar las características de los índices que son demasiado grandes para cargarlos en memoria principal (RAM). Hasta este punto se enfoca la idea del todo o nada, pero el que no se pueda almacenar todo el índice en memoria principal no quiere decir que no se pueda guardar parte de él.
Por ejemplo, se tiene un índiceque contiene un megabyte de registros y solo nos es posible usar 256k de memoria RAM para almacenar el índice. El árbol b puede estar contenido en tres niveles. Es posible obtener cualquiera de las llaves en no más de 3 accesos a disco, esto es aceptable pero se necesita una forma para reducir lo más posible el número de accesos a la memoria secundaria, llegando incluso a uno o menos.
Se sabe quepara toda búsqueda en árboles se requiere acceder a la página raíz, pero si envés de estar accediendo a esta una y Orta ves al inicio de cada búsqueda, podríamos transferirla a memoria RAM, esta estrategia incrementa el requerimiento de memoria RAM de 4K a 8K, por que se necesitan 4K para la raíz y 4K para cualquier otra página que se lea, pero esto es menor que los 256K disponibles, con estaestrategia tan simple se reducen los accesos a disco en el peor caso en 2 accesos y la búsqueda promedio en menos de dos.
En lugar de almacenar solo la raíz en memoria RAM, se crea un buffer de páginas, para almacenar algunas páginas del árbol B, según sean leídas las páginas del disco se va llenando el buffer. Cuando se solicita una página se lee directamente de la memoria RAM evitando así accederal disco, si las paginas no están en la memoria RAM se transfieren al buffer desde el almacenamiento secundario.
 Muchos de los sistemas de computadores emplean un esquema de gestión de memoria que suministra a cada uno delos usuarios una extensa memoria virtual. El espacio de direcciones de la memoria virtual por usuario está dividido en páginas que son almacenadas en memoria secundaria ycargadas en memoria principal automáticamente cuando son referenciadas. Esta técnica, llamada Página Demandada o Por Falta de Página, multiplex a la cantidad de memoria real de los usuarios y al mismo tiempo proporciona protección para asegurar que cada uno de los usuarios no interferirá con datos de otro. Además el hardware de propósito especial maneja la paginación, así que las transferencias a ydesde memoria son realizadas a alta velocidad. La disponibilidad del hardware de demanda de página sugiere una interesante implementación de árboles-B. A través de una cuidadosa cuota o ración, cada nodo del árbol-B puede ser mapeado en una página del espacio de direcciones virtual. Entonces el usuario trata el árbol-B como si estuviera en memoria. Los accesos a los nodos (páginas) que no están enmemoria, causan al sistema una recuperación de página desde memoria secundaria. 
Muchos algoritmos de paginación eligen sustituir la página menos usada cuando ha de traer una página nueva. En términos del árbol-B, los nodos más activos son esos más próximos a la raíz; estos procuran quedarse en memoria. En realidad Bayer y McCreight [BAYE72] y Knuth [KNUT73] sugieren ambos un mecanismo LRU paraárboles-B cuando no se usa paginación por hardware. Al menos, la raíz debería permanecer en memoria principal ya que es accedida por cada búsqueda. 
Así, los árboles-B virtuales tienen las siguientes ventajas:
1.- El hardware especial realiza transferencias a alta velocidad.
2.- El mecanismo de protección de memoria aísla de otros usuarios, y
3.- Las partes del árbol accedidas frecuentemente,...