Árbol-B+

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

En informática, un árbol-B es un tipo de estructura de datos de árboles. 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+, en contraste respecto 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, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.

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.

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

logMn

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

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

Este caso, es debido 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:

  • Número máximo de claves es: nh
  • Número mínimo de claves es: 2(n / 2)h − 1

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • árbol — (Del lat. arbor, ŏris). 1. m. Planta perenne, de tronco leñoso y elevado, que se ramifica a cierta altura del suelo. 2. Pieza de hierro en la parte superior del husillo de la prensa de imprimir. 3. En los órganos, eje que, movido a voluntad del… …   Diccionario de la lengua española

  • árbol — sustantivo masculino 1. Planta leñosa de tronco elevado que se ramifica a cierta altura del suelo: Han plantado muchos árboles. Este árbol da una sombra deliciosa. árbol del Paraíso Árbol de tronco gris, hojas blanquecinas, estrechas, y flores… …   Diccionario Salamanca de la Lengua Española

  • Arbol — is programming language, primarily developed to serve for Genetic Programming experiments. It is functional programming language inspired by the ideas of other small and esoteric languages. An Arbol program looks like: // Simple I/O ((Z a)b) =… …   Wikipedia

  • Arbol.bb — (Ассемини,Италия) Категория отеля: Адрес: Via Belli 6, 09032 Ассемини, Италия …   Каталог отелей

  • árbol — 1. (en anatomía) estructura anatómica con ramas que se extienden hacia fuera como las de un árbol, como el árbol bronquial. 2. patrón de búsqueda de información en una base de datos de un ordenador, siguiendo una serie de opciones ramificadas a… …   Diccionario médico

  • Árbol — (Del lat. arbor.) ► sustantivo masculino 1 BOTÁNICA Planta de tronco leñoso que se ramifica a mayor o menor altura del suelo, formando una copa. 2 NÁUTICA Madero redondo o cilíndrico fijo en una embarcación que sostiene las vergas a las que se… …   Enciclopedia Universal

  • Árbol-B — Ejemplo de árbol B. En las ciencias de la computación, los árboles B o B árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Son árboles binarios de búsqueda en… …   Wikipedia Español

  • Árbol — Para otros usos de este término, véase Árbol (desambiguación). Un roble en Dinamarca …   Wikipedia Español

  • Árbol kd — Un árbol kd tridimensional. La primera división (rojo) corta la celda raíz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay… …   Wikipedia Español

  • Árbol 2-3 — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de febrero de 2009. También puedes… …   Wikipedia Español

  • Árbol AA — En informática un árbol AA es un tipo de árbol binario de búsqueda auto balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson. Los árboles AA son …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”