antes de entender árbol B y árbol B+ diferencias, debemos conocer el árbol B y el árbol B+ por separado.
¿Qué es el árbol B?
árbol B es un árbol autoequilibrado y es un árbol de m vías donde m define el orden del árbol. árbol es una generalización de la Árbol de búsqueda binaria en el que un nodo puede tener más de una clave y más de dos hijos dependiendo del valor de metro . En el árbol B, los datos se especifican en un orden ordenado que tiene valores más bajos en el subárbol izquierdo y valores más altos en el subárbol derecho.
java cómo convertir una cadena a int
Propiedades del árbol B
Las siguientes son las propiedades del árbol B:
- En el árbol B, todos los nodos hoja deben estar en el mismo nivel, mientras que, en el caso de un árbol binario, los nodos hoja pueden estar en diferentes niveles.
Entendamos esta propiedad a través de un ejemplo.
En el árbol de arriba, todos los nodos de hoja no están en el mismo nivel, pero tienen como máximo dos hijos. Por lo tanto, podemos decir que el árbol anterior es un árbol binario pero no un árbol B.
- Si el Btree tiene un orden de m, entonces cada nodo puede tener un máximo de metro En el caso de hijos mínimos, los nodos hoja tienen cero hijos, el nodo raíz tiene dos hijos y los nodos internos tienen un techo de m/2.
- Cada nodo puede tener claves máximas (m-1). Por ejemplo, si el valor de m es 5, entonces el valor máximo de las claves es 4.
- El nodo raíz tiene como mínimo una clave, mientras que todos los demás nodos, excepto el nodo raíz, tienen (techo de m/2 menos - 1) claves mínimas.
- Si realizamos la inserción en el árbol B, entonces el nodo siempre se inserta en el nodo hoja.
Supongamos que queremos crear un árbol B de orden 3 insertando valores del 1 al 10.
Paso 1: Primero, creamos un nodo con 1 valor como se muestra a continuación:
Paso 2: El siguiente elemento es 2, que viene después de 1 como se muestra a continuación:
Paso 3: El siguiente elemento es 3 y se inserta después de 2 como se muestra a continuación:
Como sabemos que cada nodo puede tener 2 claves como máximo, dividiremos este nodo a través del elemento central. El elemento del medio es 2, por lo que se mueve a su padre. El nodo 2 no tiene ningún padre, por lo que se convertirá en el nodo raíz como se muestra a continuación:
Etapa 4: El siguiente elemento es 4. Dado que 4 es mayor que 2 y 3, se agregará después del 3 como se muestra a continuación:
Paso 5: El siguiente elemento es 5. Dado que 5 es mayor que 2, 3 y 4, se agregará después de 4 como se muestra a continuación:
Como sabemos que cada nodo puede tener 2 claves como máximo, dividiremos este nodo a través del elemento central. El elemento del medio es 4, por lo que se mueve a su padre. El padre es el nodo 2; por lo tanto, se agregará 4 después de 2 como se muestra a continuación:
Paso 6: El siguiente elemento es 6. Dado que 6 es mayor que 2, 4 y 5, 6 vendrá después de 5 como se muestra a continuación:
Paso 7: El siguiente elemento es 7. Dado que 7 es mayor que 2, 4, 5 y 6, 7 vendrá después de 6 como se muestra a continuación:
Como sabemos que cada nodo puede tener 2 claves como máximo, dividiremos este nodo a través del elemento central. El elemento del medio es 6, por lo que se mueve a su padre como se muestra a continuación:
Pero no se puede agregar 6 después de 4 porque el nodo puede tener 2 claves como máximo, por lo que dividiremos este nodo por el elemento del medio. El elemento del medio es 4, por lo que se mueve a su padre. Como el nodo 4 no tiene ningún padre, el nodo 4 se convertirá en un nodo raíz como se muestra a continuación:
¿Qué es un árbol B+?
El árbol B+ También se conoce como árbol autoequilibrado avanzado porque cada camino desde la raíz del árbol hasta la hoja del árbol tiene la misma longitud. Aquí, la misma longitud significa que todos los nodos de las hojas se encuentran en el mismo nivel. No sucederá que algunos de los nodos de las hojas ocurran en el tercer nivel y otros en el segundo nivel.
Un índice de árbol B+ se considera un índice multinivel, pero la estructura del árbol B+ no es similar a los archivos secuenciales de índice multinivel.
¿Por qué se utiliza el árbol B+?
Se utiliza un árbol B+ para almacenar los registros de manera muy eficiente al almacenar los registros de manera indexada utilizando la estructura indexada del árbol B+. Gracias a la indexación de varios niveles, el acceso a los datos se vuelve más rápido y sencillo.
Estructura de nodo del árbol B+
La estructura de nodos del árbol B+ contiene punteros y valores clave que se muestran en la siguiente figura:
Como podemos observar en la estructura de nodos del árbol B+ anterior, contiene n-1 valores clave (k1a kn-1) y n punteros (p1arribanorte).
Los valores de la clave de búsqueda que se colocan en el nodo se mantienen ordenados. Así, si yo
Restricción en varios tipos de nodos.
Sea 'b' el orden del árbol B+.
Nodo no hoja
Sea 'm' el número de hijos de un nodo, entonces la relación entre el orden del árbol y el número de hijos se puede representar como:
Sea k representa los valores de la clave de búsqueda. La relación entre el orden del árbol y la clave de búsqueda se puede representar como:
Como sabemos que el número de punteros es igual a los valores de la clave de búsqueda más 1, matemáticamente se puede escribir como:
bash para el bucle 1 al 10
Número de punteros (o hijos) = Número de claves de búsqueda + 1
Por lo tanto, el número máximo de punteros sería 'b' y el número mínimo de punteros sería la función límite de b/2.
Nodo hoja
Un nodo hoja es un nodo que ocurre en el último nivel del árbol B+, y cada nodo hoja usa solo un puntero para conectarse entre sí para proporcionar acceso secuencial en el nivel hoja.
En el nodo hoja, el número máximo de hijos es:
El número máximo de claves de búsqueda es:
Nodo raíz
El número máximo de hijos en el caso del nodo raíz es: b
El número mínimo de niños es: 2
Casos especiales en el árbol B+
Caso 1: Si el nodo raíz es el único nodo del árbol. En este caso, el nodo raíz se convierte en el nodo hoja.
En este caso, el número máximo de hijos es 1, es decir, el nodo raíz en sí, mientras que el número mínimo de hijos es b-1, que es el mismo que el de un nodo hoja.
Representación de un nodo hoja en el árbol B+
En la figura anterior, '.' representa el puntero, mientras que 10, 20 y 30 son los valores clave. El puntero contiene la dirección en la que se almacena el valor de la clave, como se muestra en la figura anterior.
Ejemplo de árbol B+
En la figura anterior, el nodo contiene tres valores clave, es decir, 9, 16 y 25. El puntero que aparece antes de 9 contiene los valores clave menores que 9 representados por ki. El puntero que aparece antes de 16 contiene los valores clave mayores o iguales a 9 pero menores a 16 representados por kj. El puntero que aparece antes de 25 contiene los valores clave mayores o iguales a 16 pero menores a 25 representados por knorte.
Diferencias entre el árbol B y el árbol B+
Las siguientes son las diferencias entre el árbol B y el árbol B+:
| árbol B | árbol B+ |
|---|---|
| En el árbol B, todas las claves y registros se almacenan tanto en el nodo interno como en el nodo hoja. | En el árbol B+, las claves son los índices almacenados en los nodos internos y los registros se almacenan en los nodos hoja. |
| En el árbol B, las claves no se pueden almacenar repetidamente, lo que significa que no hay duplicación de claves o registros. | En el árbol B+, puede haber redundancia en la aparición de claves. En este caso, los registros se almacenan en los nodos hoja, mientras que las claves se almacenan en los nodos internos, por lo que pueden estar presentes claves redundantes en los nodos internos. |
| En Btree, los nodos hoja no están vinculados entre sí. | En el árbol B+, los nodos hoja están vinculados entre sí para proporcionar acceso secuencial. |
| En Btree, la búsqueda no es muy eficiente porque los registros se almacenan en nodos hoja o internos. | En el árbol B+, la búsqueda es muy eficiente o más rápida porque todos los registros se almacenan en los nodos hoja. |
| La eliminación de nodos internos es un proceso muy lento y que requiere mucho tiempo, ya que también debemos considerar al hijo de la clave eliminada. | La eliminación en el árbol B+ es muy rápida porque todos los registros se almacenan en los nodos hoja, por lo que no tenemos que considerar al hijo del nodo. |
| En Btree, el acceso secuencial no es posible. | En el árbol B+, todos los nodos hoja están conectados entre sí mediante un puntero, por lo que es posible el acceso secuencial. |
| En Btree, se realiza una mayor cantidad de operaciones de división debido a que la altura aumenta en comparación con el ancho, | El árbol B+ tiene más ancho que alto. |
| En Btree, cada nodo tiene al menos dos ramas y cada nodo contiene algunos registros, por lo que no necesitamos recorrer hasta los nodos hoja para obtener los datos. | En el árbol B+, los nodos internos contienen solo punteros y los nodos hoja contienen registros. Todos los nodos hoja están al mismo nivel, por lo que debemos recorrer hasta los nodos hoja para obtener los datos. |
| El nodo raíz contiene al menos de 2 a m hijos, donde m es el orden del árbol. | El nodo raíz contiene al menos de 2 a m hijos, donde m es el orden del árbol. |