São grau e ordem a mesma coisa quando se refere a uma árvore B

Eu sei o termo ordem de uma árvore B. Recentemente, ouvi um novo termo: árvore B com grau mínimo de 2.

Sabemos que o grau está relacionado a um nó, mas qual é o grau de uma árvore?
O grau impõe algum tipo de restrição à altura de uma árvore B?

Não acho que o grau de uma árvore seja um termo padrão na teoria dos grafos nem nas estruturas de dados. Um grau é geralmente uma propriedade de um nó / vértice de um gráfico, que indica o número de suas arestas de incidente. Para árvores, às vezes você considera apenas as bordas das crianças.

Suponho que "árvore B com grau mínimo de 2" significa que todo nó tem pelo menos dois filhos. Em outras palavras, é um limite inferior para o número de filhos. Por outro lado, a ordem de uma árvore B indica o grau máximo do nó e, portanto, é um limite superior.

Um nó B-Tree pode conter mais de um valor-chave, enquanto um nó BST contém apenas um. Existem limites inferior e superior no número de chaves que um nó pode conter. Esses limites podem ser expressos em termos de um número inteiro fixo t>=2chamado grau mínimo da árvore B.

• Todo nó que não seja a raiz deve ter pelo menos t-1chaves. Todo nó interno que não seja a raiz tem, portanto, pelo menos tfilhos.
• Cada nó pode conter no máximo 2t-1chaves. Portanto, um nó interno pode ter no máximo 2tfilhos. Dizemos que um nó está cheio se contém exatamente 2t-1chaves.

Clique neste link para obter um excelente básico sobre o B-Tree e este link para um acompanhamento e um algoritmo mais fácil de escrever das operações do B-Tree.

Eu já vi três maneiras de caracterizar a árvore B até agora:

1. Com o grau da árvore B (mínimo, como no livro de algoritmos do CLRS , ou máximo, como no visualizador da árvore B ).$t$

   A árvore B mais simples ocorre quando . Cada nó interno tem 2, 3 ou 4 filhos e temos uma árvore 2-3-4 .$t=2$

   O texto referenciado na resposta de Nasir segue de perto a definição da árvore B, conforme apresentada em Algoritmos, com explicação detalhada das propriedades de graus mínimos.

2. Com os parâmetros e , o limite inferior (superior) do número de filhos do nó interno deve ter (por exemplo, árvore B com é equivalente a árvore B com (ambos permitindo 2 –5 chaves por nó),$L$$U$$L=3, U=6$$t=3$

3. Com a ordem da árvore B , dada por Knuth em TAOCP, vol. 3 tal que qualquer nó interno tenha entre e filhos.$m$$\left\lceil\frac{m}{2}\right\rceil$$m$

Resumindo:

• Com a caracterização do grau, o número permitido de filhos é obrigado a ficar no intervalo ,$[t,2t]$
• enquanto e permitem uma especificação mais precisa do número de filhos (ou seja, número de chaves por nó permitido).$L$$U$

Com relação à segunda parte da pergunta do OP, há o Teorema 18.1 nos algoritmos:

Se , então para qualquer B-tree tecla da altura e mínimo grau , .$n ≥ 1$$n$$T$$h$$t≥2$$h≤\mathrm{log}_t\frac{n+1}{2}$

A ordem (m) da árvore B define (max e min) no. de filhos para um nó específico.

O grau (t) de árvore B define (max e min) no. de chaves para um nó específico. Grau é definido como o grau mínimo de árvore B.

Uma árvore B de ordem m: Todos os nós internos, exceto a raiz, têm no máximo m filhos não vazios e pelo menos ⌈m / 2⌉ filhos não vazios.

Uma árvore B de grau (mínimo) t:

1. cada nó tem no máximo 2t-1 chaves
2. se o nó não for raiz, ele terá pelo menos chaves t-1.

Degreerepresenta o limite inferior do número de filhos que um nó na Árvore B pode ter (exceto a raiz). ou seja, o número mínimo de filhos possível. Considerando que o Orderrepresenta o limite superior do número de filhos. ie o número máximo possível.

B Propriedades da árvore em relação à ordem

NOTE: Wikipedia também afirma estes

B Propriedades da árvore em relação ao grau

B Propriedades da árvore em relação ao grau

NOTE: These can also be found in the CLRS book

Árvore B de ordem 5 OR m = 5

max crianças = 5

min crianças = teto (m / 2) = 3

Árvore B de grau 5 OR t = 5

chaves máximas = 2t-1

chaves mín = t-1

As terminologias das árvores B não são definidas de maneira uniforme onde quer que eu leia , mas a pergunta ambígua é qual é a ordem de uma árvore B? e não muito sobre o grau de uma árvore-B . O grau deriva da teoria dos grafos, que afirma como a soma dos graus dentro e fora desse nó.

Pelo qual se pode inferir que o grau está mais intimamente relacionado ao número de ponteiros / filho que um nó da Árvore B pode ter em vez de valores-chave no nó.

De acordo com Knuth e Michael J. Folk , uma árvore B de ordem m é uma árvore com todos os nós tendo no máximo m filhos. Tão vagamente que podemos dizer que ambos são termos mais ou menos equivalentes no contexto da B-Tree.