Son grado y orden lo mismo cuando se refiere a un árbol B

Sé el orden de los términos de un árbol B. Recientemente escuché un nuevo término: árbol B con un grado mínimo de 2.

Sabemos que el grado está relacionado con un nodo, pero ¿cuál es el grado de un árbol?
¿El grado impone algún tipo de restricción en la altura de un árbol B?

No creo que el grado de un árbol sea un término estándar ni en la teoría de grafos ni en las estructuras de datos. Un grado suele ser una propiedad de un nodo / vértice de un gráfico, que denota el número de sus bordes incidentes. Para los árboles, a veces solo se consideran los bordes de los niños.

Supongo que "árbol B con un grado mínimo de 2" significa que cada nodo tiene al menos dos hijos. En otras palabras, es un límite inferior para el número de hijos. Por otro lado, el orden de un árbol B denota el grado máximo de nodo y, por lo tanto, es un límite superior.

Un nodo B-Tree puede contener más de un valor clave, mientras que un nodo BST contiene solo uno. Hay límites inferior y superior en la cantidad de claves que puede contener un nodo. Estos límites se pueden expresar en términos de un número entero fijo t>=2llamado grado mínimo del árbol B.

• Cada nodo que no sea la raíz debe tener al menos t-1claves. Por lo tanto, cada nodo interno que no sea la raíz tiene al menos thijos.
• Cada nodo puede contener como máximo 2t-1claves. Por lo tanto, un nodo interno puede tener como máximo 2thijos. Decimos que un nodo está lleno si contiene exactamente 2t-1claves.

Haga clic en este enlace para tener una excelente base en B-Tree y este enlace para un seguimiento y un algoritmo escrito más fácilmente de las operaciones de B-Tree.

Hasta ahora he visto tres formas de caracterizar el árbol B:

1. Con el grado del árbol B (mínimo, como en el libro de Algoritmos CLRS , o máximo como en el Visualizador de árbol B ).$t$

   El árbol B más simple ocurre cuando . Cada nodo interno tiene 2, 3 o 4 hijos, y tenemos un árbol 2-3-4 .$t=2$

   El texto al que se hace referencia en la respuesta de Nasir sigue de cerca la definición del árbol B como se da en los algoritmos con una explicación detallada de las propiedades de grado mínimo.

2. Con los parámetros y , se supone que tiene un límite inferior (superior) en el número de hijos del nodo interno (por ejemplo, árbol B con es equivalente a árbol B con (ambos permiten 2 –5 teclas por nodo),$L$$U$$L=3, U=6$$t=3$

3. Con el orden del árbol B , dado por Knuth en TAOCP, vol. 3 de tal manera que cualquier nodo interno tiene entre y niños.$m$$\left\lceil\frac{m}{2}\right\rceil$$m$

Para resumirlo:

• Con la caracterización del grado, el número permitido de hijos está en el intervalo ,$[t,2t]$
• mientras que y permiten una especificación más precisa del número de hijos (es decir, número de claves por nodo permitido).$L$$U$

Con respecto a la segunda parte de la pregunta de OP, existe el Teorema 18.1 en Algoritmos:

Si , entonces para cualquier -key B-tree de altura y grado mínimo , .$n ≥ 1$$n$$T$$h$$t≥2$$h≤\mathrm{log}_t\frac{n+1}{2}$

El orden (m) del árbol B define (máx. Y mín.) No. de hijos para un nodo particular.

El grado (t) del árbol B define (máx. Y mín.) No. de claves para un nodo particular. El grado se define como el grado mínimo de B-tree.

Un árbol B de orden m: todos los nodos internos, excepto la raíz, tienen como máximo m hijos no vacíos y al menos ⌈m / 2⌉ hijos no vacíos.

Un árbol B de (mínimo) grado t:

1. cada nodo tiene como máximo 2t-1 claves
2. si el nodo no es root, tiene al menos t-1 claves.

Degreerepresenta el límite inferior del número de hijos que puede tener un nodo en el árbol B (excepto la raíz). es decir, el número mínimo de hijos posible. Mientras que el Orderrepresenta el límite superior en el número de hijos. es decir. El número máximo posible.

B Propiedades del árbol con respecto a la Orden

NOTE: Wikipedia también establece estos

B Propiedades del árbol con respecto al grado

B Propiedades del árbol con respecto al grado

NOTE: These can also be found in the CLRS book

B-árbol de orden 5 OR m = 5

max niños = 5

min niños = techo (m / 2) = 3

B-árbol de grado 5 OR t = 5

teclas max = 2t-1

teclas mín. = t-1

Las terminologías de los árboles B no se definen de manera uniforme dondequiera que leo , sin embargo, la pregunta ambigua es ¿cuál es el orden de un árbol B? y no mucho sobre el grado de un B-Tree . El grado proviene de la teoría de grafos que lo establece como la suma del grado de entrada y salida de ese nodo.

Por el cual se puede inferir que el grado está más estrechamente relacionado con el número de punteros / hijo que puede tener un nodo B-Tree en lugar de valores clave en el nodo.

Según Knuth y Michael J. Folk , un árbol B de orden m es un árbol con cada nodo que tiene como máximo m hijos. Muy vagamente podemos decir que ambos son términos más o menos equivalentes en el contexto de B-Tree.