El B+

Un B+ es un árbol balanceado multivías de orden mayor a 2 que tiene las siguientes carácterísticas:

• Los nodos ``rama'' únicamente tienen las llaves y apuntadores a sus subárboles hijos.

• Los nodos ``hoja'' son los únicos que tienen apuntadores a los registros correspondientes a las llaves. Esto es, si un nodo que no es hoja tiene la llave que se busca, entonces este nodo indica que tiene un subárbol-hijo que tiene la hoja con el elemento deseado.

• La altura de cada hoja siempre es la misma o igual a la profundidad² del árbol. Es decir, para accesar a un elemento del árbol siempre hay que recorrer el mismo número de niveles desde la raíz.

• Las hojas tiene ligas entre si, semejantes a las listas ligadas, lo que facilita el recorrido secuencial de los datos.

como se muestra en la figura 2.

  

Figure 2: Estructura de un B+