Árvore B ou B-Tree
Aldemon Lage Bonifácio
Samuel Belini Defilippo
Mestrado Multidisciplinar em Modelagem Computacional Universidade
21 março 2006
Federal de Juiz de Fora - UFJF
Sumário
Árvore B ou B-tree
 Idéia principal
 Estrutura
 Exemplo
 Algoritmo de inserção
 Exemplo passo a passo
 Outra estrutura de árvore B

Mestrado Multidisciplinar em Modelagem Computacional
2
Árvore B ou B-Tree
Rudolf Bayer [1971]
 Banco de dados e Sistemas de arquivos
 Tempo de leitura na memória secundária

Mestrado Multidisciplinar em Modelagem Computacional
3
Idéia Principal
Cada mudança de nível temos uma nova
leitura ao disco
 Diminuir o número de níveis e aumentar o
número de valores e de filhos

Mestrado Multidisciplinar em Modelagem Computacional
4
Estrutura
Definir a ordem da árvore (número de
valores que cada nó pode armazenar)
 Mínimo de valores = ordem / 2
 Número de filhos = ordem + 1

Mestrado Multidisciplinar em Modelagem Computacional
5
Exemplo
Chave de 4 bytes
 Endereço de 4 bytes
 Ponteiro de 4 bytes para filho
 Cluster de 4kB
 Ordem igual a 341
 Raiz contêm 342 filhos e 116964 netos
 Capacidade para
(1 + 342 + 116964) x 341 = 40.001.674
referências

Mestrado Multidisciplinar em Modelagem Computacional
6
Algoritmo de Inserção
1. Devemos caminhar até o nó onde será
inserido a chave
2. Verificar se o nó irá ultrapassar seus limites.
Caso isso não ocorra, o processo é finalizado.
3. Caso contrário, este será dividido, a chave
central do nó é inserida na posição do pai,
recursivamente até a raiz, se essa estourar,
um novo nó raiz será criado (podendo ter um
único elemento).
Mestrado Multidisciplinar em Modelagem Computacional
7
Exemplo passo a passo
(1) Vamos tentar inserir a chave 12 nessa Árvore
B já construída de ordem três.
Mestrado Multidisciplinar em Modelagem Computacional
8
Exemplo passo a passo
(2) Primeiro ele irá caminhar até encontrar o nó
onde será inserida a chave
Mestrado Multidisciplinar em Modelagem Computacional
9
Exemplo passo a passo
(3) O limite do nó foi ultrapassado, logo ele será
dividido e a chave será inserida em uma das
partes
Mestrado Multidisciplinar em Modelagem Computacional
10
Exemplo passo a passo
(4) Árvore após inserção da chave
Mestrado Multidisciplinar em Modelagem Computacional
11
Outro exemplo de árvore
Mestrado Multidisciplinar em Modelagem Computacional
12
Dúvidas?
Mestrado Multidisciplinar em Modelagem Computacional
13