Árbol B+

En ciencias de la computación, un árbol B+ es un tipo de estructura de datos de árbol, representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Un árbol B+ es una variación de un árbol B.

En un árbol B+, toda la información se guarda en las hojas. Los nodos internos solo contienen claves y punteros. Todas las hojas se encuentran en el mismo nivel, que corresponde al más bajo. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir principalmente recuperación en rango mediante búsqueda secuencial.

Características

Las estructuras de árbol B+ reúnen las siguientes características:

• El número máximo de claves en un registro es llamado el orden del árbol B+.
• El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves.
• El número de claves que pueden ser indexadas usando un árbol B+ está en función del orden del árbol y su altura.

Altura: El mejor y el peor caso

Dado un M, el cual corresponde al número máximo de hijos que un nodo puede contener se define por:

La altura h de un árbol B+ (El peor caso):

${\displaystyle log_{M}n}$

La altura h de un árbol B+ (Mejor caso) :

${\displaystyle log_{\left({\frac {M}{2}}\right)}n}$

Este caso se debe a que si guardamos menos hijos en los nodos, se necesitarán más niveles para almacenar todo.

Cantidad de claves

Para un árbol B+ de orden n, con una altura h:

• El número máximo de claves es: ${\displaystyle n^{h}}$
• El número mínimo de claves es: ${\displaystyle 2(n/2)^{h-1}}$

Véase también

• Estructura de datos

Enlaces externos

• https://sites.google.com/site/tutoriasarboles/arboles-b-y-b
• http://www.seanster.com/BplusTree/BplusTree.html

Esta página se editó por última vez el 30 ene 2021 a las 12:33.