Los Arboles de Busqueda de M Vias Balanceados ( B-Trees ) son
Arboles de Busqueda de M Vias
con las siguientes propiedades :
Arbol Vacio T -----> F Agrego 30 T -----+ Agrego 20 T -----+ Agrego 40 T -----+
| | |
V V A V
*-------* *-------* | *-------*
| 30 -- | | 20 30 | ( 20 30 40 ) | 30 -- | Nivel 1
*-------* *-------* | | *-------*
| | | | | V V | |
F F F F F +-----+ |
| |
*-------**-------*
| 20 -- || 40 -- | Nivel 2
*-------**-------*
| | | |
F F F F
Agrego 10 T -----+ Agrego 25 T -----+ Agrego 15 T -----+ Agrego 35 T -----+
| | | |
V V V V A
*-------* *-------* *-------* *-------* |
| 30 -- | | 20 30 | | 20 30 | | 20 30 | ( 20 30 40 ) Nivel 1
*-------* *-------* *-------* *-------* | |
| | | | | | | | | | | V V
+-----+ | +-----+ | +-----+ +-----+ | +-----+ +-----+ | +-----+
| | A | | | | | | | | | A
*-------**-------* | *-------**-------**-------* *-------**-------**-------* *-------**-------**-------* |
| 10 20 || 40 -- | ( 10 20 25 ) | 10 -- || 25 -- || 40 -- | | 10 15 || 25 -- || 40 -- | | 10 15 || 25 -- || 35 40 | ( 35 40 45 ) Nivel 2
*-------**-------* | | *-------**-------**-------* *-------**-------**-------* *-------**-------**-------* | |
| | | | | V V | | | | | | | | | | | | | | | | | | | | | V V
F F F F F F F F F F F F F F F F F F F F F F F F F F
Agrego 45 T -----+ Agrego 50 T -----+
| |
V V
*-------* *-------*
| 30 -- | | 30 -- | Nivel 1
*-------* *-------*
| | | |
+-----------------------+ | +-----------------------+ |
| | | |
*-------* *-------* *-------* *-------*
| 20 -- | | 40 -- | | 20 -- | | 40 -- | Nivel 2
*-------* *-------* *-------* *-------*
| | | | | | | |
+-----+ | +-----+ | +-----+ | +-----+ |
| | | | | | | |
*-------**-------* *-------**-------* *-------**-------* *-------**-------*
| 10 15 || 25 -- | | 35 -- || 45 -- | | 10 15 || 25 -- | | 35 -- || 45 50 | Nivel 3
*-------**-------* *-------**-------* *-------**-------* *-------**-------*
| | | | | | | | | | | | | | | | | | |
F F F F F F F F F F F F F F F F F F F
Agrego 38 T -----+ Agrego 55 T -----+
| |
V V
*-------* *-------*
| 30 -- | | 30 -- | Nivel 1
*-------* *-------*
| | | |
+-----------------------+ | +-----------------------+ |
| | | | A
*-------* *-------* *-------* *-------* |
| 20 -- | | 40 -- | | 20 -- | | 40 50 | ( 37 40 50 ) Nivel 2
*-------* *-------* *-------* *-------* | |
| | | | | | | | | V V
+-----+ | +-----+ | +-----+ | +-----+ | +-----+
| | | | A | | | | | A
*-------**-------* *-------**-------* | *-------**-------* *-------**-------**-------* |
| 10 15 || 25 -- | | 35 38 || 45 50 | ( 45 50 55 ) | 10 15 || 25 -- | | 35 38 || 45 -- || 55 -- | ( 35 37 38 ) Nivel 3
*-------**-------* *-------**-------* | | *-------**-------* *-------**-------**-------* | |
| | | | | | | | | | | V V | | | | | | | | | | | | | V V
F F F F F F F F F F F F F F F F F F F F F F F F
Agrego 37 T -----+ Agrego 5 T -----+
| |
V V
*-------* *-------*
| 30 40 | | 30 40 | Nivel 1
*-------* *-------*
| | | | | |
+-----------------------+ | +-----------------------+ +-----------------------+ | +-----------------------+
| | | | | |
*-------* *-------* *-------* *-------* *-------* *-------*
| 20 -- | | 37 -- | | 50 -- | | 10 20 | | 37 -- | | 50 -- | Nivel 2
*-------* *-------* *-------* *-------* *-------* *-------*
| | | | | | | | | | | | |
+-----+ | +-----+ | +-----+ | +-----+ | +-----+ +-----+ | +-----+ |
| | | | | | A | | | | | | |
*-------**-------* *-------**-------* *-------**-------* | *-------**-------**-------**-------**-------* *-------**-------*
| 10 15 || 25 -- | | 35 -- || 38 -- | | 45 -- || 55 -- | ( 5 10 15 ) | 5 -- || 15 -- || 25 -- || 35 -- || 38 -- | | 45 -- || 55 -- | Nivel 3
*-------**-------* *-------**-------* *-------**-------* | | *-------**-------**-------**-------**-------* *-------**-------*
| | | | | | | | | | | | | V V | | | | | | | | | | | | | |
F F F F F F F F F F F F F F F F F F F F F F F F F F F
Agrego 18 T -----+
|
V A
*-------* |
| 30 40 | ( 15 30 40 ) Nivel 1
*-------* | |
| | | V V
+-----------------------+ | +-----------------------+
| | | A
*-------* *-------* *-------* |
| 10 20 | | 37 -- | | 50 -- | ( 10 15 20 ) Nivel 2
*-------* *-------* *-------* | |
| | | | | | | V V
+-----+ | +-----+ +-----+ | +-----+ |
| | | | | | | A
*-------**-------**-------**-------**-------* *-------**-------* |
| 5 -- || 15 18 || 25 -- || 35 -- || 38 -- | | 45 -- || 55 -- | ( 12 15 18 ) Nivel 3
*-------**-------**-------**-------**-------* *-------**-------* | |
| | | | | | | | | | | | | | | V V
F F F F F F F F F F F F F F F
Agrego 12 T -----+ Cantidad Cantidad
| Nodos Entradas
V Maxima Maxima
*-------*
| 30 -- | Nivel 1 1 ( 3*0 ) 2 ( 1x2 )
*-------*
| |
+--------------------------------------------------+ |
| |
*-------* *-------*
| 15 -- | | 40 -- | Nivel 2 3 ( 3*1 ) 6 ( 3x2 )
*-------* *-------*
| | | |
+-----------------------+ | +-----------------------+ |
| | | |
*-------* *-------* *-------* *-------*
| 10 -- | | 20 -- | | 37 -- | | 50 -- | Nivel 3 9 ( 3*2 ) 18 ( 9x2 )
*-------* *-------* *-------* *-------*
| | | | | | | |
+-----+ | +-----+ | +-----+ | +-----+ |
| | | | | | | |
*-------**-------* *-------**-------* *-------**-------* *-------**-------*
| 5 -- || 12 -- | | 18 -- || 25 -- | | 35 -- || 38 -- | | 45 -- || 55 -- | Nivel 4 27 ( 3*3 ) 54 ( 27x2 )
*-------**-------* *-------**-------* *-------**-------* *-------**-------*
| | | | | | | | | | | | | | | |
F F F F F F F F F F F F F F F F
Cantidad Nodos Maxima = 40
Cantidad Entradas Maxima = 80 ( 40x2 )
Cantidad Nodos Actual = 15
Cantidad Entradas Actual = 15 ( 15x2-15 )
Cantidad Nodos Falla = 16 ( 15+1 )
Relacion Nodos / Entradas Actual = 15/15 ( 1,000 )
La Apertura de Nodos en un Arbol de Busqueda de M Vias Balanceado se hace
cuando se pretende
almacenar una nueva Clave en un Nodo que ya esta completo.
Si el Arbol es de M Vias y se determina que la nueva Clave es la Clave M
del Nodo, debera ejecutarse la Apertura del Nodo, ya que solo pueden
almacenarse M-1 Claves en un Nodo, como maximo.
La Apertura del Nodo conlleva el reagrupamiento de las Claves en tres Nodos.
La idea es promocionar la Clave central a un Nodo de nivel superior y
separar las Claves menores y las mayores a la Clave central,
en partes iguales, dentro de lo posible, en dos Nodos del
mismo nivel.
Para ello necesitamos una funcion que nos devuelva el entero siguiente
luego de realizar el cociente de M/2. Llamamos a esta funcion f(M/2).
La reagrupacion de las Claves se hace siguiendo el siguiente algoritmo :
Observar que si sumamos los 3 agrupamientos obtenemos M. En todos los casos
las Claves estan ordenadas creciendo.
Si el nodo pretendido hubiese sido :
Los nodos resultantes son :
donde en todos los casos, Ki < K(i+1) para todo i igual o mayor que 1 hasta i < m.
*--*--*--*--*--*--*--*--*--*--*
M Par |k1|k2|k3|k4|k5|k6|k7|k8|k9|k0|
*--*--*--*--*--*--*--*--*--*--*
M = 10 <------------- M ------------->
n = 9
M/2 = 5
f(M/2) = 5 *--*--*--*--*--*--*--*--*--*--*
f(M/2) - 1 = 4 |k1|k2|k3|k4|k5|k6|k7|k8|k9|k0|
M - f(M/2) = 5 *--*--*--*--*--*--*--*--*--*--*
<-----------><-><------------->
f(M/2) - 1 1 M - f(M/2)
*--*
|k5|
*--*
*--*--*--*--* *--*--*--*--*--*
|k1|k2|k3|k4| |k6|k7|k8|k9|k0|
*--*--*--*--* *--*--*--*--*--*
<-----------><-><------------->
f(M/2) - 1 1 M - f(M/2)
*--*--*--*--*--*--*--*--*--*--*--*--*--*
M Impar |k1|k2|k3|k4|k5|k6|k7|k8|k9|k0|k1|k2|k3|
*--*--*--*--*--*--*--*--*--*--*--*--*--*
M = 13 <------------------ M ----------------->
n = 12
M/2 = 6,5
f(M/2) = 7 *--*--*--*--*--*--*--*--*--*--*--*--*--*
f(M/2) - 1 = 6 |k1|k2|k3|k4|k5|k6|k7|k8|k9|k0|k1|k2|k3|
M - f(M/2) = 6 *--*--*--*--*--*--*--*--*--*--*--*--*--*
<-----------------><-><---------------->
f(M/2) - 1 1 M - f(M/2)
*--*
|k7|
*--*
*--*--*--*--*--*--* *--*--*--*--*--*--*
|k1|k2|k3|k4|k5|k6| |k8|k9|k0|k1|k2|k3|
*--*--*--*--*--*--* *--*--*--*--*--*--*
<-----------------><-><---------------->
f(M/2) - 1 1 M - f(M/2)
T -----+ Elimino 58 T -----+
| |
V V
*-------* *-------*
| 50 -- | | 50 -- | Nivel 1
*-------* *-------*
| | | |
+-----------------------+ | +-----------------------+ |
| | | |
*-------* *-------* *-------* *-------*
| 30 -- | | 60 70 | | 30 -- | | 60 70 | Nivel 2
*-------* *-------* *-------* *-------*
| | | | | | | | | |
+-----+ | +-----+ | +-----+ +-----+ | +-----+ | +-----+
| | | | | | | | | |
*-------**-------* *-------**-------**-------* *-------**-------* *-------**-------**-------*
| 10 -- || 40 -- | | 55 58 || 65 -- || 75 80 | | 10 -- || 40 -- | | 55 -- || 65 -- || 75 80 | Nivel 3
*-------**-------* *-------**-------**-------* *-------**-------* *-------**-------**-------*
| | | | | | | | | | | | | | | | | | | | | | | | |
F F F F F F F F F F F F F F F F F F F F F F F F F
Elimino 65 T -----+ Elimino 55 T -----+
| |
V V
*-------* *-------*
| 50 -- | | 50 -- | Nivel 1
*-------* *-------*
| | | |
+-----------------------+ | +-----------------------+ |
| | | |
*-------* *-------* *-------* *-------*
| 30 -- | | 60 75 | | 30 -- | | 75 -- | Nivel 2
*-------* *-------* *-------* *-------*
| | | | | | | | |
+-----+ | +-----+ | +-----+ +-----+ | +-----+ |
| | | | | | | | |
*-------**-------* *-------**-------**-------* *-------**-------* *-------**-------*
| 10 -- || 40 -- | | 55 -- || 70 -- || 80 -- | | 10 -- || 40 -- | | 60 70 || 80 -- | Nivel 3
*-------**-------* *-------**-------**-------* *-------**-------* *-------**-------*
| | | | | | | | | | | | | | | | | | | | | |
F F F F F F F F F F F F F F F F F F F F F F
Elimino 40 T -----+ Elimino 70 T -----+ Elimino 30 T -----+
| | |
V V V
*-------* *-------* *-------*
| 50 75 | | 50 75 | | 50 75 | Nivel 1
*-------* *-------* *-------*
| | | | | | | | |
+-----+ | +-----+ +-----+ | +-----+ +-----+ | +-----+
| | | | | | | | |
*-------**-------**-------* *-------**-------**-------* *-------**-------**-------*
| 10 30 || 60 70 || 80 -- | | 10 30 || 60 -- || 80 -- | | 10 -- || 60 -- || 80 -- | Nivel 2
*-------**-------**-------* *-------**-------**-------* *-------**-------**-------*
| | | | | | | | | | | | | | | | | | | | |
F F F F F F F F F F F F F F F F F F F F F
package aaa.cursos.javaestr.programas;
public interface B_Tree_Server
{
/**
Crea un Arbol de Busqueda de M Vias Balanceado.
@param client Es el Objeto Cliente que solicito la creacion.
@param vias Es cantidad de vias que debe tener el Arbol que esta siendo creado.
@return void Este Metodo no devuelve valor alguno. En su lugar invoca los siguientes Metodos del Cliente : setFeedback(), setArbol() y setVias().
*/
void Crear_Arbol( Object client, int vias );
/**
Inserta una Clave en un Arbol de Busqueda de M Vias Balanceado.
@param client Es el Objeto Cliente que solicito la insercion.
@param arbol Es el identificador del Arbol donde se insertara la Clave.
@param clave Es la Clave a insertar.
@return void Este Metodo no devuelve valor alguno. En su lugar invoca los siguientes Metodos del Cliente : setFeedback(), setArbol() y setVias().
*/
void Insertar_Clave( Object client, int arbol, int clave );
/**
Elimina una Clave en un Arbol de Busqueda de M Vias Balanceado.
@param client Es el Objeto Cliente que solicito la eliminacion.
@param arbol Es el identificador del Arbol donde se eliminara la Clave.
@param clave Es la Clave a eliminar.
@return void Este Metodo no devuelve valor alguno. En su lugar invoca los siguientes Metodos del Cliente : setFeedback(), setArbol() y setVias().
*/
void Eliminar_Clave( Object client, int arbol, int clave );
/**
Recupera una Clave en un Arbol de Busqueda de M Vias Balanceado.
@param client Es el Objeto Cliente que solicito la recuperacion.
@param arbol Es el identificador del Arbol donde se recuperara la Clave.
@param clave Es la Clave a recuperar.
@return void Este Metodo no devuelve valor alguno. En su lugar invoca los siguientes Metodos del Cliente : setFeedback(), setArbol() y setVias().
*/
void Recuperar_Clave( Object client, int arbol, int clave );
/**
Consulta la existencia de una Clave en un Arbol de Busqueda de M Vias Balanceado.
@param client Es el Objeto Cliente que solicito la consulta.
@param arbol Es el identificador del Arbol donde se hara la consulta por la Clave.
@param clave Es la Clave a consultar.
@return void Este Metodo no devuelve valor alguno. En su lugar invoca los siguientes Metodos del Cliente : setFeedback(), setArbol() y setVias().
*/
void Existe_Clave( Object client, int arbol, int clave );
/**
Recuperar un Arbol de Busqueda de M Vias Balanceado.
@param client Es el Objeto Cliente que solicito la recuperacion.
@param arbol Es el identificador del Arbol a recuperar.
@return void Este Metodo no devuelve valor alguno. En su lugar invoca los siguientes Metodos del Cliente : setFeedback(), setArbol() y setVias().
*/
void Recuperar_Arbol( Object client, int arbol );
}
package aaa.cursos.javaestr.programas;
interface B_Tree_Client
{
/**
Devuelve el Resultado de la Operacion solicitada al Servidor.
@param server Es el Objeto Servidor que atendio la Operacion.
@param feedback Es el Resultado de la Operacion realizada por el Servidor.
@return void Este Metodo no devuelve valor alguno.
*/
void setFeedback( Object server, int feedback );
/**
Devuelve el Identificador del Arbol sobre el cual se realizo la Operacion.
@param server Es el Objeto Servidor que atendio la Operacion.
@param arbol Es el Identificador del Arbol sobre el cual se realizo la Operacion.
@return void Este Metodo no devuelve valor alguno.
*/
void setArbol( Object server, int arbol );
/**
Devuelve el Numero de Vias del Arbol sobre el cual se realizo la Operacion.
@param server Es el Objeto Servidor que atendio la Operacion.
@param arbol Es la Numero de Vias del Arbol sobre el cual se realizo la Operacion.
@return void Este Metodo no devuelve valor alguno.
*/
void setVias( Object server, int vias );
/**
Devuelve la Clave sobre la cual se realizo la Operacion.
@param server Es el Objeto Servidor que atendio la Operacion.
@param clave Es la Clave sobre el cual se realizo la Operacion.
@return void Este Metodo no devuelve valor alguno.
*/
void setClave( Object server, int clave );
/**
Devuelve el Registro sobre el cual se realizo la Operacion.
@param server Es el Objeto Servidor que atendio la Operacion.
@param registro Es el Registro sobre el cual se realizo la Operacion.
@return void Este Metodo no devuelve valor alguno.
*/
void setRegistro( Object server, int registro );
/**
Devuelve las Claves que existen en el Arbol sobre el cual se realizo la Operacion.
@param server Es el Objeto Servidor que atendio la Operacion.
@param claves Son las Claves que existen en el Arbol sobre el cual se realizo la Operacion.
@return void Este Metodo no devuelve valor alguno.
*/
void setClaves( Object server, int[] claves );
/**
Devuelve los Registros existen en el Arbol sobre el cual se realizo la Operacion.
@param server Es el Objeto Servidor que atendio la Operacion.
@param registros Son los Registros que existen en el Arbol sobre el cual se realizo la Operacion.
@return void Este Metodo no devuelve valor alguno.
*/
void setRegistros( Object server, int[] registros );
}