Criação do Indice B-tree
(ou ISAM)
Carregamento em Massa (Bulk Loading)
AULA 14 – Parte II
Profa. Sandra de Amo
GBC053 – BCC
Construção de uma B-Tree –
Bulk Loading
• Ordena-se as entradas do índice pela
chave de busca
• Aloca-se uma página vazia para a raiz
• Insere nesta página um ponteiro para a
primeira página do arquivo contendo as
entradas.
Exemplo
Ordem da b-tree = 1
3*
4*
6*
9*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
Páginas restantes a alocar
38* 41* 44*
Exemplo
6*
3*
4*
6*
9*
10*
Ordem da b-tree = 1
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
38* 41* 44*
Páginas restantes a alocar
Exemplo
Precisa dividir
6*
3*
4*
6*
9*
10*
12*
20*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
38* 41* 44*
Exemplo
6*
3*
4*
6*
9*
10*
12*
20*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
38* 41* 44*
Páginas restantes a alocar
Exemplo
10*
Precisa dividir
6*
3*
4*
6*
9*
12*
20*
23*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
35*
38* 41* 44*
Exemplo
10* 20*
6*
3*
4*
6*
9*
12*
23*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
35*
38* 41* 44*
Páginas restantes a alocar
Exemplo
10* 20*
Precisa dividir
6*
3*
4*
6*
9*
12*
23*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
35*
38* 41*
38* 44*
44*
Exemplo
Precisa dividir
10* 20*
6*
3*
4*
6*
9*
35*
12*
23*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
38* 44*
38* 41*
44*
Exemplo
20*
10*
6*
3*
4*
6*
9*
35*
12*
23*
10* 11* 12* 13* 20* 22* 23* 31* 35* 36*
38* 44*
38* 41*
44*
Método – Carregamento em Massa
Dados de entrada:
Relação R(A1,...,An)
Chave = Ai1,...,Aik
– Ordena-se a relação R pelos atributos da chave
– Constrói-se o arquivo de índice I com registros (chave,rid)
– Executa rotina Constroi_BTree(I,d,k,x), que retorna uma estrutura
de BTree B de ordem d, contendo nas folhas o arquivo de índice
I, e o número N de níveis da BTree B construída. (O número N é
importante para construir depois a rotina de busca na b-tree B)
Dados de saída:
N = número de níveis da Btree
B = <B0, B1,..., Bn-1> , onde cada Bi = sequência de páginas do nível i
da Btree
Método – Carregamento em Massa
Observações:
– No carregamento em massa, a b-tree B retornada
pela rotina Constroi_BTree(I,d,k,x), respeita as
restrições de ocupação máxima e mínima exceto
nos últimos nós de cada nível. A ocupação de tais
nós pode ser qualquer número de registros entre 1 e
2d.
– Quando a b-tree começar a ser utilizada e sofrer
modificações (inserções e deleções), ela tenderá a
ter seus nós extremos (em cada nível) respeitando as
condições de ocupação mínima e máxima.
Os parâmetros de Constroi_BTree
• I = arquivo de indice ordenado
• d = ocupação mínima (ordem da b-tree)
• 0 ≤ k ≤ d = o quanto a mais queremos de ocupação inicial nas
folhas (as folhas serão construídas com ocupação = d + k), exceto
pela última folha, que terá ocupação entre 1 e 2d.
• 0 ≤ x ≤ d - 1 = o quanto a mais queremos de ocupação inicial nos
nós intermediários (os nós serão construídos com ocupação = d +
x), exceto nos últimos nós de cada nível que terão ocupação entre 1
e 2d
Exemplo:
Entrada: Arquivo de indice de 9 páginas com 4 registros em cada uma.
d = 2, k = 0, x = 1
Saída: (3, <B0,B1,B2>)
B0 = 18 páginas (folhas em amarelo) contendo 2 (= d + k) registros em cada uma
B1 = Nível 1 da Btree = 5 páginas (azuis) de 3 (= d + x) registros cada (exceto a última)
B2 = Nível 2 da Btree (raiz) = 1 página com 4 registros
Exemplo:
Entrada: Arquivo de indice de 9 páginas com 4 registros em cada uma.
d = 2, k = 0, x = 1
Saída: (3, <B0,B1,B2>)
B0 = 18 páginas (folhas em amarelo) contendo 2 (= d + k) registros em cada uma
B1 = Nível 1 da Btree = 5 páginas (azuis) de 3 (= d + x) registros cada (exceto a última)
B2 = Nível 2 da Btree (raiz) = 1 página com 4 registros
Método Controi_Btree
1.
Reestrutura(I,d,k): transforma arquivo I em um arquivo cujas
páginas (P1, P2, ..., Pm) têm no máximo d+k registros. A ordem
dos registros é a mesma do arquivo I original.
2.
M = número de páginas do arquivo de índice reestruturado
3.
Ult_Nivel := 0
4.
Para i = 2, ..., M
1. C = primeiro registro de Pi
2. Insere(C,1,x,d,Pi-1,Pi)
3. Retorna (Ult_Nivel, Btree)
Atenção: Ult_Nível = número de níveis da Btree retornada (variável
global)
Insere(Chave,Nivel,d,x,PgE,PgD)
Insere(C,N,d,x,PgE,PgD)
Input: C = chave, N = nivel da inserção, d = ocupação mínima, x = qte a mais, PgE =
página do nivel N-1 (abaixo de N), à esquerda de C, PgD = página do nível N1(abaixo de N), à direita de C.
1.
2.
3.
Verifica se existe algum nó no nível N
Se não existir:
1.
constrói primeiro nó No_1 no nível N
2.
Incrementa Ult_Nivel
3.
Insere ponteiro Pt1 em No_1 apontando para PgE
4.
Insere C em No_1 após Pt1
5.
Insere ponteiro Pt2 em No_1 após C apontando para PgD
Se existir:
1.
No_Final = último nó do nível N
2.
y = ocupação de No_Final
3.
Se y ≤ d + x
1. Insere C na última posição de No_Final
2. Insere ponteiro Pt à direita de C apontando para PgD
Cont.
4. Se y = d + x + 1
1. Pt = último ponteiro de No_Final
2. Ult_chave = última chave de No_Final
3. Cria novo nó No_New à direita de No_Final no nível N
4. Remove Pt de No_Final e insere em No_New
5. Remove chave Ult_chave de No_Final
6. Insere C em No_New logo após Pt
7. Insere ponteiro Pt_New em No_New logo após C,
apontando para PgD
8. Insere(Ult_chave, N+1,x,d,No_Final, No_New)
Exemplo:
Entrada: Arquivo de indice de 9 páginas com 4 registros em cada uma.
d = 2, k = 0, x = 1
Saída: (3, <B0,B1,B2>)
B0 = 18 páginas (folhas em amarelo) contendo 2 (= d + k) registros em cada uma
B1 = Nível 1 da Btree = 5 páginas (azuis) de 3 (= d + x) registros cada (exceto a última)
B2 = Nível 2 da Btree (raiz) = 1 página com 4 registros