Los Nodos

Los nodos del B+ deben almacenar hasta n-1 llaves³, el tipo de datos de la llave puede variar dependiendo de que campo se desea utilizar como ``campo llave''. Esto es, el campo llave puede ser de tipo entero, flotante, carácter o cadena.

En la implantación que presentamos se incluye un archivo de cabecera auxiliar tipos.h, donde se definen la estructura del registro que manejará el B+ y el tipo de campo llave que utilizará, además de otras definiciones que resulten convenientes para trabajar la estructura de los registros en el árbol⁴.

 
/* tipos.h                               */ 
/* Archivo donde se define la estructura */
/* y llave que maneja el arbol B+        */ 
/* [ABRIL-97]                            */
/* AMILCAR MENESES VIVEROS               */

typedef int Bkey;                        /* Tipo de llave */ 

/* Estructura del registro que se maneja en el arbol B+ */ 
typedef struct s_register {              /* Variable tipo registro */ 
   int edad; 
   char nombre[30]; 
} Bregister;

/* Llave que se maneja en el arbol B+ */
#define Fkey       %d                   /* Formato de la llave             */
#define FFkey      "%d"                 /* Formato de la llave             */
#define BKeyNull   0                    /* Valor nulo de la llave          */
#define KeyNode(p) (p.edad)             /* Campo que se utiliza como llave */
#define PKeyNode(p) ((p)->edad)         /* Campo llave desde un apuntador  */

Debido al tipo de organización de los datos que se debe realizar con el B+, la estructura de un nodo de estos árboles deben tener un arreglo de n apuntadores a los subárboles ``hijo'' (donde n es el orden del árbol); un arreglo de n-1 llaves; un arreglo de n-1 apuntadores a los registros del nodo ``hoja''; un contador para el número de llaves que tenga el nodo; un apuntador al nodo padre; y un apuntador al nodo ``hoja'' subsecuente. De esta forma, la implantación de la estructura node queda de la siguiente forma:

 

typedef struct _node {
   int  nKeys; 	                /* Numero de hojas                        */ 
   Bkey ak[ORDER-1];            /* Arreglo de llaves                      */ 
   Bregister *ap[ORDER-1];      /* Arreglo de apuntadores a los registros */ 
   struct _node *an[ORDER];     /* Arreglo de apuntadores a los hijos     */
   struct _node *nxt;           /* Apuntador a la hoja mas proxima        */
   struct _node *up;            /* Apuntador al nodo padre                */ 
} node;