Ordem em árvores B

---

A ordem ($M$) de uma árvore B definida pelo número máximo de descendentes que uma página pode possuir.

Ela determina as seguintes propriedades:

1. Máximo de filhos por página: Uma página pode ter até $M$ filhos.
2. Máximo de chaves por página: Cada página pode armazenar no máximo $M-1$ chaves, pois cada chave divide os filhos em dois grupos.
3. Mínimo de chaves por página (exceto a raiz): Cada página deve ter pelo menos $\lceil M/2\rceil -1$ chaves para garantir o balanceamento.

A raiz pode ter de 1 até $M-1$ chaves, pois ela não precisa seguir o mínimo de chaves como os outros nós.

Exemplos

Exemplo 1: Árvore B de ordem $M=4$

• Máximo de filhos por página: $M=4$ (ou seja, cada página pode ter até 4 filhos).
• Máximo de chaves por página: $M-1=4-1=3$.
• Mínimo de chaves por página (exceto a raiz): $\lceil M/2\rceil -1=\lceil 4/2\rceil -1=2-1=1$.

Exemplo 2: Árvore B de ordem $M=5$

• Máximo de filhos por página: $M=5$.
• Máximo de chaves por página: $M-1=5-1=4$.
• Mínimo de chaves por página (exceto a raiz): $\lceil M/2\rceil -1=\lceil 5/2\rceil -1=3-1=2$.

Visão geral

Ordem ($M$)	Máx. Filhos	Máx. Chaves	Mín. Chaves (exceto raiz)
$M=3$	3	2	1
$M=4$	4	3	1
$M=5$	5	4	2

Referências

---

Aula 6 - Árvore B