Estructura de Datos : Arbol de Busqueda de M Vias ( M-Way Search Tree )

Definiciones

Los Arboles de Busqueda de M Vias ( M-Way Search Trees ) son arboles en los cuales todos los nodos son de grado menor o igual a M, y tienen las siguientes propiedades :

Si T es un Arbol de Busqueda de M Vias y esta vacio :

T tiene el valor de un apuntador nulo

Si T es un Arbol de Busqueda de M Vias y no esta vacio :

T tiene el valor de un apuntador a un nodo del tipo n, A0, ( K1, A1, B1 ), ( K2, A2, B2 ), ..., ( Kn, An, Bn ) donde :
- n, igual o menor a M-1, es el numero de claves que tiene el nodo
- Ki, i variando de 1 a n, son valores de claves
- Ai, i variando de 0 a n, son apuntadores a un subarbol de T
- Bi, i variando de 1 a n, son apuntadores a los registros de clave Ki
- Ki debe ser menor que Ki+1, i variando de 0 a n
- Todos los valores de clave del subarbol Ai deben ser menores que el valor de clave Ki+1 para i variando de 0 a n-1
- Todos los valores de clave en el subarbol An son mayores que el valor de clave Kn
- Los subarboles de T, apuntados por Ai, i variando de 0 a n, son tambien Arboles de Busqueda de M Vias

Ejemplo : Archivo con 9 Registros


r              s              t              u              v              w              x              y              z
|              |              |              |              |              |              |              |              |
V              V              V              V              V              V              V              V              V
*------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------*
| |10|       | | |15|       | | |20|       | | |25|       | | |30|       | | |35|       | | |40|       | | |45|       | | |50|       |
*------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------*

Ejemplo : Claves y Rangos de Claves


*------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------*
| |10|       | | |15|       | | |20|       | | |25|       | | |30|       | | |35|       | | |40|       | | |45|       | | |50|       |
*------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------* *------------*

1 Clave  2 Rangos
                                                              *--*
<-------- Rango  Menor -------------------------------------->|30|<----------------------------------------- Rango  Mayor ----------->
                                                              *--*

2 Claves 3 Rangos
                                *--*                                                        *--*
<-------- Rango  Menor -------->|20|<------------------ Rango Intermedio ------------------>|40|<----------- Rango  Mayor ----------->
                                *--*                                                        *--*

5 Claves 6 Rangos
                 *--*                          *--*           *--*           *--*                          *--*
<--------------->|15|<-------------------------|25|<--------->|30|<--------->|35|<------------------------>|45|<--------------------->
                 *--*                          *--*           *--*           *--*                          *--*
                  K1                            K2             K3             K4                            K5
      Rango                    Rango                  Rango          Rango                 Rango                        Rango
     Ki-->K1                K1-->Ki-->K2           K2-->Ki-->K3   K3-->Ki-->K4          K4-->Ki-->K5                   K5-->Ki

Ejemplo : Arbol de Busqueda de 2 Vias


                                 T ---------------+                                                                                                             Cantidad           Cantidad
                                                  |                                                                                               Niveles       Nodos              Entradas
Orden de Carga                                    V (a)                                                                                                         Maxima             Maxima
20                                       *----------------*
40                                       | 1, b, (20,c,t) |                                                                                          1          1 ( 2*0 )          1 ( 1x1 )
45                                       *----------------*
15                                            |      |
10                                            |      |
25                       +--------------------+      +----------------------+
30                       |                                                  |
50                       V (b)                                              V (c)
35              *----------------*                                  *----------------*
                | 1, d, (15,0,s) |                                  | 1, e, (40,f,x) |                                                               2          2 ( 2*1 )          2 ( 2x1 )
                *----------------*                                  *----------------*
                     |                                                   |      |
                     |                                                   |      |
            +--------+                                          +--------+      +--------+
            |                                                   |                        |
            V (d)                                               V (e)                    V (f)
    *----------------*                                 *----------------*         *----------------*
    | 1, 0, (10,0,r) |                                 | 1, 0, (25,g,u) |         | 1, 0, (45,h,y) |                                                 3          4 ( 2*2 )          4 ( 4x1 )
    *----------------*                                 *----------------*         *----------------*
                                                                   |                          |
                                                                   |                          |
                                                                   +---+                      +---+
                                                                       |                          |
                                                                       V (g)                      V (h)
                                                               *----------------*         *----------------*
                                                               | 1, 0, (30,i,v) |         | 1, 0, (50,0,z) |                                         4          8 ( 2*3 )          8 ( 8x1 )
                                                               *----------------*         *----------------*
                                                                           |
                                                                           |
                                                                           +---+
                                                                               |
                                                                               V (i)
                                                                       *----------------*
                                                                       | 1, 0, (35,0,w) |                                                            5         16 ( 2*4 )         16 ( 16x1 )
                                                                       *----------------*
                                                                                                                                       Cantidad Nodos Maxima = 31
                                                                                                                                    Cantidad Entradas Maxima =                    31 ( 31x1 )
                                                                                                                                       Cantidad Nodos Actual =  9
                                                                                                                                    Cantidad Entradas Actual =                     9 (  9x1 )
                                                                                                                            Relacion Nodos / Entradas Actual =                     9/9 = 1,000

Ejemplo : Arbol de Busqueda de 3 Vias


                                                     T -----+                                                                                                   Cantidad           Cantidad
                                                            |                                                                                     Niveles       Nodos              Entrdas
Orden de Carga                                              V (a)                                                                                               Maxima             Maxima
20                                              *--------------------------*
40                                              | 2, b, (20,c,t), (40,d,x) |                                                                         1          1 ( 3*0 )          2 ( 1x2 )
10                                              *--------------------------*
15                                                   |      |         |
25                                                   |      |         |
30                                                   |      |         |
35         +-----------------------------------------+      |         +-----------------------------------------+
45         |                                                |                                                   |
50         |                                                |                                                   |
           V (b)                                            V (c)                                               V (d)
*--------------------------*                    *--------------------------*                        *--------------------------*
| 2, 0, (10,0,r), (15,0,s) |                    | 2, 0, (25,0,u), (30,e,v) |                        | 2, 0, (45,0,y), (50,0,z) |                     2          3 ( 3*1 )          6 ( 3x2 )
*--------------------------*                    *--------------------------*                        *--------------------------*
                                                                      |
                                                                      |
                                                                      |
                                                                      +-----------------------------------------+
                                                                                                                |
                                                                                                                |
                                                                                                                V (e)
                                                                                                    *------------------------*
                                                                                                    | 1, 0, (35,0,w)         |                       3          9 ( 3*2 )         18 ( 9x2 )
                                                                                                    *------------------------*
                                                                                                                                       Cantidad Nodos Maxima = 13
                                                                                                                                    Cantidad Entradas Maxima =                    26 ( 13x2 )
                                                                                                                                       Cantidad Nodos Actual =  5
                                                                                                                                    Cantidad Entradas Actual =                     9 ( 5x2-1 )
                                                                                                                            Relacion Nodos / Entradas Actual =                     5/9 = 0,555

Ejemplo : Arbol de Busqueda de 5 Vias


                                                     T -----+                                                                                                   Cantidad           Cantidad
                                                            |                                                                                     Niveles       Nodos              Entradas
Orden de Carga                                              V (a)                                                                                               Maxima             Maxima
10                                  *---------------------------------------------*
15                                  | 4, 0, (10,0,r), (15,0,s) (20,0,t), (25,b,u) |                                                                  1          1 ( 5*0 )          4 ( 1x4 )
20                                  *---------------------------------------------*
25                                                                           |
30                                                                           |
35                                                                           |
40                                                                           +-----------+
45                                                                                       |
50                                                                                       |
                                                                                         V (b)
                                                               *---------------------------------------------*
                                                               | 4, 0, (30,0,v), (35,0,w) (40,0,x), (45,c,y) |                                       2          5 ( 5*1 )         20 ( 5x4 )
                                                               *---------------------------------------------*
                                                                                                        |
                                                                                                        |
                                                                                                        |
                                                                                                        +-----------+
                                                                                                                    |
                                                                                                                    |
                                                                                                                    V (c)
                                                                                          *---------------------------------------------*
                                                                                          | 1, 0, (50,0,z)                              |            3         25 ( 5*2 )        100 ( 25x4 )
                                                                                          *---------------------------------------------*
                                                                                                                                       Cantidad Nodos Maxima = 31
                                                                                                                                    Cantidad Entradas Maxima =                   124 ( 31x4 )
                                                                                                                                       Cantidad Nodos Actual =  3
                                                                                                                                    Cantidad Entradas Actual =                     9 ( 3x4-3 )
                                                                                                                            Relacion Nodos / Entradas Actual =                     3/9 = 0,333

Ejemplo : Arbol de Busqueda de 10 Vias


                                                          T -----+                                                                                              Cantidad           Cantidad
                                                                 |                                                                                Niveles       Nodos              Entradas
Orden de Carga                                                   V (a)                                                                                          Maxima             Maxima
10                  *------------------------------------------------------------------------------------------------*
15                  | 9, 0, (10,0,r), (15,0,s), (20,0,t), (25,0,u), (30,0,v), (35,0,w), (40,0,x), (45,0,y), (50,0,z) |                               1          1 ( 10*0 )         9 ( 1x9 )
20                  *------------------------------------------------------------------------------------------------*
25
30
35
40
45
50
                                                                                                                                       Cantidad Nodos Maxima =  1
                                                                                                                                    Cantidad Entradas Maxima =                     9 ( 1x9 )
                                                                                                                                       Cantidad Nodos Actual =  1
                                                                                                                                    Cantidad Entradas Actual =                     9 ( 1x9 )
                                                                                                                            Relacion Nodos / Entradas Actual =                     1/9 = 0,111

Ejemplo : Ordenamiento de las Claves dentro de un Nodo


                                                     T -----+
                                                            |
Orden de Carga                                              V (a)
                                    *---------------------------------------------*
20                                  | 1, 0, (20,0,t)                              |
                                    *---------------------------------------------*

                                    *---------------------------------------------*
35                                  | 2, 0, (20,0,t), (35,0,w)                    |
                                    *---------------------------------------------*

                                    *---------------------------------------------*
30                                  | 3, 0, (20,0,t), (30,0,v), (35,0,w)          |
                                    *---------------------------------------------*

Siempre que haya lugar para incorporar una clave en un nodo, ese nodo no tiene subarboles.

Secuencia de Busqueda del Registro de una Clave Determinada

Secuencia de Busqueda del Registro cuya Clave es de valor 35 en el Arbol de Busqueda de 3 Vias

Determino Nodo Raiz

Recupero el Nodo (a)

Busco en el Nodo (a)

Determino seguir en (c)

Recupero el Nodo (c)

Busco en el Nodo (c)

Determino seguir en (e)

Recupero el Nodo (e)

Busco en el Nodo (e)

Encuentro la Clave en el Nodo(e)

Recupero el Registro (w)

Observaciones

Los Arboles de Busqueda de M Vias son indices densos, ya que todas las claves estan en el indice

El maximo numero de accesos a disco en un Arbol de Busqueda de M Vias para hallar una clave es igual a la altura del arbol

Minimizar el numero de accesos a disco en un Arbol de Busqueda de M Vias es equivalente a minimizar la altura del arbol

El maximo numero de nodos de un Arbol de Busqueda de M Vias y altura h es igual a m*0+m*1+m*2+...+m*(h-1), lo que es igual a ((m*h)-1)/(m-1)

El maximo numero de entradas de un Arbol de Busqueda de M Vias y altura h es igual a (((m*h)-1)/(m-1))x(m-1), o sea, (m*h)-1

Por ejemplo, para un Arbol de Busqueda de 2 Vias, con altura h=3, el maximo numero de entradas que se pueden disponer son (2*3)-1 = 7

Por ejemplo, para un Arbol de Busqueda de 20 Vias, con altura h=3, el maximo numero de entradas que se pueden disponer son (20*3)-1 = 7999

Por ejemplo, para un Arbol de Busqueda de 200 Vias, con altura h=3, el maximo numero de entradas que se pueden disponer son (200*3)-1 = 7999999

Metodo para Recuperar Registros a partir del Valor de una Clave


        Direccion_Disco nodo_nulo;
        Direccion_Disco nodo_padre;
        Direccion_Disco nodo_actual;

        Direccion_Disco registro_nulo;
        Direccion_Disco registro_hallado;

        boolean Clave_Hallada                 // ( true = Clave Existe en el Arbol )  ( false = Clave No Existe en el Arbol )

        Buscar_M_Way( Direccion_Disco t, Clave x )
        {
                nodo_actual = t;
                while ( !nodo_actual.equals(nodo_nulo) )
                {
                        // Recupero el Nodo

                        // Busco en el Nodo

                                // Clave No Hallada

                                        // Nodo Actual a Nodo Padre
                                        // Nodo Posible a Nodo Actual

                                // Clave Hallada

                                        // Recupero Registro
                                        // Seteo Variables Salida
                                        // Nodo Nulo a Nodo Actual
                }
        }

Ejemplo : Arbol de Busqueda de 3 Vias - Diagrama Simplificado


Orden de Carga          T -----+                                          Agrego 38               T -----+
20                             |                                                                         |
40                             V                                                                         V
10                         *-------*                                                                 *-------*
15                         | 20 40 |                                                                 | 20 40 |
25                         *-------*                                                                 *-------*
30                          |  |  |                                                                   |  |  |
35           +--------------+  |  +--------------+                                     +--------------+  |  +--------------+
45           |                 |                 |                                     |                 |                 |
50       *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
         | 10 15 |         | 25 30 |         | 45 50 |                             | 10 15 |         | 25 30 |         | 45 50 |
         *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
                                  |                                                                         |
                                  +-----+                                                                   +-----+
                                        |                                                                         |
                                    *-------*                                                                 *-------*
                                    | 35 -- |                                                                 | 35 38 |
                                    *-------*                                                                 *-------*



Agrego 55               T -----+                                          Agrego 37               T -----+
                               |                                                                         |
                               V                                                                         V
                           *-------*                                                                 *-------*
                           | 20 40 |                                                                 | 20 40 |
                           *-------*                                                                 *-------*
                            |  |  |                                                                   |  |  |
             +--------------+  |  +--------------+                                     +--------------+  |  +--------------+
             |                 |                 |                                     |                 |                 |
         *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
         | 10 15 |         | 25 30 |         | 45 50 |                             | 10 15 |         | 25 30 |         | 45 50 |
         *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
                                  |                 |                                                       |                 |
                                  +-----+           +-----+                                                 +-----+           +-----+
                                        |                 |                                                       |                 |
                                    *-------*         *-------*                                               *-------*         *-------*
                                    | 35 38 |         | 55 -- |                                               | 35 38 |         | 55 -- |
                                    *-------*         *-------*                                               *-------*         *-------*
                                                                                                                  |
                                                                                                                  |
                                                                                                                  |
                                                                                                              *-------*
                                                                                                              | 37 -- |
                                                                                                              *-------*


Agrego 5                T -----+                                          Agrego 18               T -----+
                               |                                                                         |
                               V                                                                         V
                           *-------*                                                                 *-------*
                           | 20 40 |                                                                 | 20 40 |
                           *-------*                                                                 *-------*
                            |  |  |                                                                   |  |  |
             +--------------+  |  +--------------+                                     +--------------+  |  +--------------+
             |                 |                 |                                     |                 |                 |
         *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
         | 10 15 |         | 25 30 |         | 45 50 |                             | 10 15 |         | 25 30 |         | 45 50 |
         *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
          |                       |                 |                               |     |                 |                 |
    +-----+                       +-----+           +-----+                   +-----+     +-----+           +-----+           +-----+
    |                                   |                 |                   |                 |                 |                 |
*-------*                           *-------*         *-------*           *-------*         *-------*         *-------*         *-------*
|  5 -- |                           | 35 38 |         | 55 -- |           |  5 -- |         | 18 -- |         | 35 38 |         | 55 -- |
*-------*                           *-------*         *-------*           *-------*         *-------*         *-------*         *-------*
                                        |                                                                         |
                                        |                                                                         |
                                        |                                                                         |
                                    *-------*                                                                 *-------*
                                    | 37 -- |                                                                 | 37 -- |
                                    *-------*                                                                 *-------*


Agrego 12               T -----+                                          Agrego Nodos de Falla   T -----+                                                      Cantidad           Cantidad
                               |                                                                         |                                        Niveles       Nodos              Entrdas
                               V                                                                         V                                                      Maxima             Maxima
                           *-------*                                                                 *-------*
                           | 20 40 |                                                                 | 20 40 |                                       1          1 ( 3*0 )          2 ( 1x2 )
                           *-------*                                                                 *-------*
                            |  |  |                                                                   |  |  |
             +--------------+  |  +--------------+                                     +--------------+  |  +--------------+
             |                 |                 |                                     |                 |                 |
         *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
         | 10 15 |         | 25 30 |         | 45 50 |                             | 10 15 |         | 25 30 |         | 45 50 |                     2          3 ( 3*1 )          6 ( 3x2 )
         *-------*         *-------*         *-------*                             *-------*         *-------*         *-------*
          |  |  |                 |                 |                               |  |  |           |  |  |           |  |  |
    +-----+  |  +-----+           +-----+           +-----+                   +-----+  |  +-----+     F  F  +-----+     F  F  +-----+
    |        |        |                 |                 |                   |        |        |                 |                 |
*-------**-------**-------*         *-------*         *-------*           *-------**-------**-------*         *-------*         *-------*
|  5 -- || 12 -- || 18 -- |         | 35 38 |         | 55 -- |           |  5 -- || 12 -- || 18 -- |         | 35 38 |         | 55 -- |            3          9 ( 3*2 )         18 ( 9x2 )
*-------**-------**-------*         *-------*         *-------*           *-------**-------**-------*         *-------*         *-------*
                                        |                                  |  |     |  |     |  |              |  |  |           |  |
                                        |                                  F  F     F  F     F  F              F  |  F           F  F
                                        |                                                                         |
                                    *-------*                                                                 *-------*
                                    | 37 -- |                                                                 | 37 -- |                              4         27 ( 3*3 )         54 ( 27x2 )
                                    *-------*                                                                 *-------*
                                                                                                               |  |
                                                                                                               F  F
                                                                                                                                       Cantidad Nodos Maxima = 40
                                                                                                                                    Cantidad Entradas Maxima =                    80 ( 40x2 )
                                                                                                                                       Cantidad Nodos Actual = 10
                                                                                                                                    Cantidad Entradas Actual =                    15 ( 10x2-5 )
                                                                                                                                        Cantidad Nodos Falla =                    16 ( 15+1 )

La cantidad de nodos de falla es siempre uno mas que la cantidad de entradas. Los nodos de falla son la materializacion de los rangos de claves no presentes en el indice