Experto

Árbol B+

1

Á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 unainserció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
sólo contienen claves y punteros.
Todas las hojas se encuentran en el
mismo nivel, que corresponde al más
bajo. Los nodos hoja seencuentran
unidos entre sí como una lista enlazada
para permitir búsqueda secuencial.

Un árbol B+ simple (una variación del árbol B) que enlaza los elementos 1 al 7 a valores
de datos d1-d7. Notela lista enlazada (en rojo) que permite el recorrido de los elementos
en orden.

Características
Las estructuras de árbol B+ reúnen las siguientes características:
• El número máximo de clavesen 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
Dadoun 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):

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

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

Árbol B+

Cantidad de claves
Para un árbol B+ de orden n, con una altura h:
• El número máximode claves es:
• El número mínimo de claves es:

Enlaces externos
• http://www.seanster.com/BplusTree/BplusTree.html

2

Fuentes y contribuyentes del artículo

Fuentes y contribuyentes...