Diferencia clave: en las computadoras, los árboles binarios son estructuras de datos de árbol que almacenan los datos y permiten al usuario acceder, buscar, insertar y eliminar los datos en el momento algorítmico. La diferencia entre un árbol B y B + es que, en un árbol B, las claves y los datos se pueden almacenar tanto en el nodo interno como en el de la hoja, mientras que en un árbol B +, los datos y las claves solo se pueden almacenar en los nodos de la hoja. .
Los árboles binarios son árboles de búsqueda equilibrados que están diseñados para funcionar bien en dispositivos de almacenamiento secundario de acceso directo, como discos magnéticos. Rudolf Bayer y Ed McCreight inventaron el concepto de un árbol B.
Un árbol B es un árbol de búsqueda binario generalizado, en el que cualquier nodo puede tener más de dos hijos. Cada nodo interno en un árbol B contiene una serie de claves. Estas claves separan los valores y forman los subárboles. Los nodos internos en un árbol B pueden tener números variables de nodos secundarios, que están dispuestos dentro de un rango predefinido. En el momento en que se insertan o eliminan datos de cualquier nodo respectivo, hay un cambio en el número de nodos secundarios. Para mantener el rango predefinido, los nodos internos pueden unirse o dividirse. En un árbol B, se permite un rango de nodos secundarios, debido a lo cual se debe mantener el rango predefinido.
Los árboles B no necesitan ser rebalanceados con frecuencia, a diferencia de otros árboles de búsqueda con equilibrio automático. Los nodos en estos árboles no siempre están llenos; Por lo tanto, los espacios se consumen innecesariamente en estos árboles, lo que lleva a un desperdicio de espacio. Solo los límites inferior y superior en el número de nodos secundarios se fijan normalmente para una implementación en particular. Por ejemplo, en un árbol B 2-3 (a menudo llamado simplemente un árbol 2-3), cada nodo interno puede tener solo 2 o 3 nodos hijos.
Además, el árbol B está optimizado para sistemas que leen y escriben grandes bloques de datos. Es comúnmente usado en bases de datos y sistemas de archivos. En el árbol B, todos los nodos se mantienen a las mismas profundidades de balanceo de los nodos raíz. Estas profundidades aumentan lentamente a medida que aumenta el número de elementos; esto hace que todos los nodos de hoja estén uno más lejos de la raíz. Además, los árboles B son más ventajosos en comparación con otras implementaciones en lo que respecta al tiempo de acceso a los datos.
Un árbol B + es un árbol n-array con un nodo, que consiste en un gran número de hijos por nodo. La raíz puede ser una hoja o un nodo que contiene más de dos hijos. Un árbol B + consiste en una raíz, nodos internos y hojas.
Un árbol B + es lo mismo que un árbol B; la única diferencia es que, en el árbol B + hay un nivel adicional agregado en la parte inferior con hojas vinculadas. Además, a diferencia del árbol B, cada nodo en un árbol B + contiene solo claves y no pares clave-valor.
Además, el factor de equilibrio o el orden de un árbol B + mide la capacidad de los nodos internos en un árbol, es decir, la cantidad de nodos que pueden tener. El número real de hijos para un nodo está limitado para los nodos internos. Sin embargo, la raíz es una excepción, ya que se le permite tener más de dos hijos. Por ejemplo, si el orden de un árbol B + es 7, cada nodo interno (excepto la raíz) puede tener entre 4 y 7 hijos; mientras que la raíz puede tener entre 2 y 7. El valor principal del árbol B + es almacenar datos para una recuperación eficiente en un contexto de almacenamiento orientado a bloques y en particular a sistemas de archivos.
El valor primario del árbol B + está en almacenar y mantener los datos, para que no se pierdan los datos. Este enfoque se aplica especialmente en el contexto de almacenamiento orientado a bloques y en algunos sistemas de archivos particulares. Las hojas, que son los bloques de índice más bajos, del árbol B + a menudo están vinculadas entre sí en una lista enlazada; por lo tanto, esto hace que las consultas de rango o una iteración ordenada a través de los bloques sean más simples y eficientes. Además, el factor de espacio no se desperdicia en árboles B +. El árbol B + proporciona un formato eficiente de estructura de datos de alojamiento, que los hace más sencillos de acceder y almacenar. Los árboles B + son particularmente útiles como un índice de sistema de base de datos, donde los datos normalmente residen en un disco.
Comparación entre el árbol B y el árbol B +:
Árbol B | Árbol B + | |
Descripciones cortas de la web | El árbol AB es una estructura organizativa para el almacenamiento y recuperación de información en forma de árbol en el que todos los nodos terminales están a la misma distancia de la base, y todos los nodos no terminales tienen entre n y 2 n subárboles o punteros (donde n es un número entero). | B + tree es un árbol n-array con una variable pero a menudo un gran número de hijos por nodo. Un árbol B + consiste en una raíz, nodos internos y hojas. La raíz puede ser una hoja o un nodo con dos o más hijos. |
También conocido como | Árbol equilibrado. | B más árbol. |
Espacio | En) | En) |
Buscar | O (log n) | O (log b n) |
Insertar | O (log n) | O (log b n) |
Borrar | O (log n) | O (log b n) |
Almacenamiento | En un árbol B, busque claves y datos almacenados en nodos internos u hojas. | En un árbol B +, los datos se almacenan solo en nodos de hoja. |
Datos | Los nodos de hoja de los tres punteros de la tienda a los registros en lugar de los registros reales. | Los nodos de hoja del árbol almacenan el registro real en lugar de los punteros a los registros. |
Espacio | Estos árboles desperdician espacio. | Allí los árboles no desperdician espacio. |
Función de los nudos foliares. | En el árbol B, el nodo de hoja no se puede almacenar utilizando la lista vinculada. | En el árbol B +, los datos del nodo hoja se ordenan en una lista enlazada secuencial. |
buscando | Aquí, la búsqueda se vuelve difícil en el árbol B ya que los datos no se pueden encontrar en el nodo hoja. | Aquí, la búsqueda de cualquier dato en un árbol B + es muy fácil porque todos los datos se encuentran en los nodos de hoja. |
Búsqueda de accesibilidad | Aquí, en el árbol B, la búsqueda no es tan fácil en comparación con un árbol B +. | Aquí en el árbol B + la búsqueda se vuelve fácil. |
Llave redundante | No almacenan clave de búsqueda redundante. | Ellos almacenan la clave de búsqueda redundante. |
Aplicaciones | Son una versión más antigua y no son tan ventajosas en comparación con los árboles B +. | Muchos implementadores de sistemas de bases de datos prefieren la simplicidad estructural de un árbol B +. |