Ai sim

Árvore B (B-tree)

Introdução O criador das árvores B, Rudolf Bayer, não definiu claramente de onde veio o B das árvores B. Ao que parece, o B vem de balanceamento onde todos os nós da árvore estão em um mesmo nível. Também é possível que o B tenha vindo de seu sobrenome Bayer, ou ainda do nome da empresa onde trabalhava, a Boeing Scientific Research Labs. Suas principais características são: - Em uma árvore-B cada nó da árvore do pode conter um grande número de chaves (elementos). - O número de sub-árvores de cada nó pode ser muito grande. - A altura da árvore é geralmente muito pequena.
Estrutura do nó da árvore
Considerando X como um nó interno da árvore B e n o número de chaves (elementos) armazenadas em X: - as n chaves (elementos) k1, k2...kn são armazenadas em ordem crescente; - e X possui n+1 ponteiros f1, f2...fn+1 para seus filhos

f1 |K1 |F2 |K2 |f3 |K3 |f4 |K4 |... |... |fn |Kn |fn + 1 | | Em um nó, cada campo chave tem associado a ele um campo ponteiro para um nó filho, esse nó filho é a raiz de uma sub-árvore que contém nós com todos os valores de chave menores ou iguais ao valor da chave em questão no nó pai; e maiores do que o valor da chave anterior no nó pai. Cada nó tem também um campo ponteiro adicional que indica o seu filho mais à direita, esse nó é a raiz de uma subárvore que contém nós com todos os valores de chave maiores do que todas as chaves do nó pai. Exemplo de uma árvore B de ordem 3: • ordem (m) = 3 (número de filhos em cada nó)
[pic]

Exemplo de uma árvore B de ordem 5: • m = 5 (ordem) • n = 4 (elementos)
[pic]
Busca em Árvore B Processo similar à busca em uma árvore binária. Comparação entre os valores da chave de busca e das chaves armazenadas na árvore B. Como as chaves estão ordenadas, pode-se realizar uma busca binária nos elementos de cada nó. Se a chave não for encontrada no nó em questão, continua-se a busca nos filhos deste