Árvores B+ e B*

Considerações Iniciais

• Alguns autores definem a ordem m de uma árvore B como sendo o número máximo de filhos que um nó interno pode ter.
• O número de filhos de um nó interno, seguindo esta definição, fica limitado por "teto(m/2)" e "m".
• O número de chaves tem limite inferior igual a  "teto(m/2)-1"  e superior igual a "m-1".
• Vantagem: limites máximos não precisam ser números pares.
  
• Desvantagem: algoritmos e provas podem ficar um pouco mais complexas.

Árvores B+

• Ponteiros para registros (ou os próprios registros) e 'chaves' são armazenados apenas nas folhas.
• Nós internos guardam 'chaves' que são usadas apenas para guiar a busca.
• Ordem "m", nas folhas, pode ser diferente da ordem em nós internos.
• Otimização para busca por intervalos de valores: as chaves são armazenadas também em uma lista duplamente encadeada (interligando as folhas da árvore).
  
• Vantagem: Ordem m dos nós internos pode ser aumentada, uma vez que eles podem carregar menos informações. (apenas as chaves).


Base de Dados:
 

	Nome	Endereço	Fone	RA
1	Hemerson	Rua. XXX...	067-1112343	20
2	Julia	Rua. YYY	011-1111111	15
3	Fulano	...	...	10
4	Ciclano	...	...	30
5	Beltrano	...	...	48
6	B1	...	...	60
7	B2	...	...	61
8	Bolao	...	...	31
9	Bolinha	...	...	62
10	Bolota	...	...	22
11	Joao	...	...	40
12	Maria	...	...	23

Árvore B+ de ordem m = 4 (e folhas podendo conter de 2 a 3 chaves) armazenando índice pelo RA