Métodos de Acesso
Indices estruturados por B-TREE
Plano Geral

Método de Acesso Indexado Sequencial (ISAM)




Busca
Inserção
Supressão
B-Tree: uma estrutura dinâmica



Busca
Inserção
Supressão
Dados e Indices

Dados armazenados em arquivo de dados


Arquivos de indice estruturados em árvore



<a1,a2, … , k,…, an> página i, slot j
Folhas : < k, (i,j) >
Nós intermediários : <chave, pagId>
Objetivo : melhorar a busca de registros
Dados e Indices




Inserção e supressões são feitas no arquivo de dados
A cada inserção ou supressão de um registro de
dados, a estrutura do arquivo de indices deve ser
ajustada.
O ajuste implica em inserção ou supressão de
entradas no arquivo de indice.
Como gerenciar inserções e supressões num arquivo
de indice de modo a manter sua estrutura ?
ISAM - Motivação




Quais os empregados com salário > 2000 ?
Busca binária no arquivo de indice até
encontrar o primeiro salário > 2000
Escaneia o arquivo de índice a partir deste
ponto e lê os registros correspondentes.
Se o arquivo de indice é muito grande : busca
binária pode ser dispendiosa.
Idéia

Criar um segundo arquivo com um registro
para cada página do arquivo de indice original


<primeira chave da página, ponteiro da página>
Ordenado por chave
14
2*
5*
7*
12*
14*
17*
19*
22*
Idéia (continuação)
Segundo arquivo menor que arquivo original
Busca binária no segundo arquivo mais rápida
 Se segundo arquivo não cabe numa página
 Repetir o processo : cria-se um terceiro
arquivo com um registro para cada página
do segundo arquivo
… Raiz cabe numa página
Esquema Geral do Método ISAM
Páginas
dos arquivos
de indices
(a partir da
2a camada)
Páginas de overflow
Páginas primárias –
as entradas do arquivo de
índice da primeira
camada
Alocação de Páginas em ISAM


Páginas primárias e de overflow : contém as entradas
primárias k*
ISAM é uma estrutura estática

Na criação do arquivo




Páginas primárias são alocadas
Páginas de índice são alocadas
20% de cada página é livre para posteriores inserções
Manutenção :

Páginas de overflow são alocadas à medida que as páginas de
dados são preenchidas em decorrência de inserções.
Busca de um registro de dados
Procura 27*
Raiz
40
20
10* 15*
51
33
20* 27*
33*
37*
40*
46*
63
51*
55*
63*
97*
Inserção de um registro
Inserção de 23*, 48*, 41*, 42*
Raiz
40
20
10* 15*
51
33
20* 27*
23*
Página de Overflow
33*
37*
40*
46*
48*
41*
42*
63
51*
55*
63*
97*
Supressão de um registro
Supressão de 42*, 51*, 97*
Procura 51*
Raiz
Nunca são
alteradas !!
40
20
10* 15*
51
33
20* 27*
23*
Pagina de Overflow
33*
37*
40*
46*
48*
41*
42*
63
51*
55*
63*
97*
Comparação de Custos

Número de I/O = número de níveis da árvore




Capacidade do nó = F
Total de páginas primárias = N
Número de níveis = logF N
Custo






Arquivo de 1 000 000 registros
10 registros por página de dados : total de páginas = 100 000
100 entradas em cada página de índice
Scan = 1000 000/10 = 100000 I/0
Busca binária = log2 100000 = 17 I/0
ISAM = log100 100000 = entre 2 e 3 I/0, pois

1002 < 100000 < 1003
Vantagens de ISAM


ISAM é estático : inserções e supressões
afetam somente as folhas.
Em alguns casos, ISAM é preferível a B-Trees
Desvantagens de ISAM



Possibilidade de cadeias de páginas overflow
Páginas overflow geralmente não são
ordenadas, a fim de agilizar inserções.
Para aliviar este problema :


Árvore é criada com 20% de cada folha livre
Entretanto, uma vez preenchido este espaço,
cadeias de overflow só podem ser eliminadas
através de uma total reorganização da estrutura.
B-Trees : Método de Acesso Dinâmico




Operações de inserção e supressão são balanceadas de modo
a que cada nó tenha uma ocupação minima e máxima.
Uma ocupação mínima de 50% é garantida em cada nó
(exceto a raiz)
Procura por um registro requer somente uma busca em
profundidade da raiz até uma folha apropriada.
Arvore é balanceada



Todos os caminhos da raiz até a folha têm o mesmo comprimento.
Cada nó intermediário contém m entradas, onde d ≤ m ≤ 2d,
d = ordem da B-tree
Páginas das folhas são ligadas em sequência através de
ponteiros – podem ser percorridas em sequência nas duas
direções.
Busca
Ordem = 2 : cada nó contém K entradas, 2 <= K <= 4
Chave contém chave candidata (não há duplicatas)
13
5* 7*
24
30
15 ?
5?
2* 3*
17
14*16*
19* 20* 22*
24* 27* 29*
33* 34* 38*39*
Inserção
Inserindo 8*
Cheia !
13
2*
3* 5* 7*
Cheia !
7* 8*
14* 16*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Inserção



Variante 1 : Se nó está cheio divida e ajuste os nós
ancestrais.
Variante 2 : Testa primeiro se pode redistrisbuir
num nó vizinho. Em caso negativo, divide.
Ideal


Não redistribuir nós intermediários – sempre dividir o
nó.
Se uma folha está cheia, procure um vizinho.


Se tiver espaço, redistribua.
Caso contrário, divida a folha cheia.
Inserção - Variante 1
Inserindo 8*
Cheia !
13
2*
3* 5* 7*
Cheia !
7* 8*
14* 16*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Inserção : Variante 1
Inserindo 8*
5
2* 3*
135
5* 7* 8*
17
13
14* 16*
17
24 24
19* 20* 22*
30 30
24* 27* 29*
33* 34* 38*39*
Inserção : Variante 2
Inserindo 8*
8*
13
2* 3* 5* 7*
814** 14*
16* 16*
8*
17
24
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Resumo: Metodologia de Inserção
1. Busca a página onde deve ser inserida a entrada.
2. Caso a página suporte a inserção (sem ultrapassar o max)

Insere a tupla no final da página e pára.
3. Caso a página P não suporte a inserção
3.1 Verifica se um dos vizinhos suporta a inserção
3.2 Caso positivo

Vizinho à direita VD: a entrada é inserida na 1a posição de VD: o
elemento da camada imediatamente superior que tem um ponteiro à
direita apontando para VD é substituido pela chave da entrada inserida.

Vizinho à esquerda VE

Insere-se a nova entrada na posição adequada em P, obtendo-se P’ (P’
tem d+1 elementos agora)

primeira chave X da página P’ passa para a última posição de VE,

o elemento da camada imediatamente superior que tem um ponteiro
apontando à esquerda para VE é substituido pela chave X.
Resumo: Metodologia de Inserção
3.2 Caso negativo: número de elementos de P = d

Considera-se a página P’ = P + nova entrada X

Quebra-se a P’ em duas páginas P1, P2 de tamanho d. Considera-se o
elemento X do meio das duas páginas.

Insere-se o elemento X na camada imediatamente acima, à esquerda do
ponteiro que apontava para P.

Ajusta-se os ponteiros desta camada: o da esquerda de X aponta para P1,
o da direita de X aponta para P2. O restante permanece como estava.

Caso após a inserção de X na camada acima, a página fique cheia, repetese o mesmo processo (testa se é possível distribuir entre os vizinhos e em
caso negativo, quebra-se a página e modifica-se a camada imediatamente
acima).
Supressão


Se ocupação não fica abaixo do mínimo,
suprime, não altera ponteiros, nem nós
ancestrais
Se ocupação fica abaixo do mínimo


Tenta redistribuição com nó vizinho, se possível
Caso contrário junta com vizinho
Nem junta nem redistribui
Suprimindo 19*
5
2* 3*
17
13
5* 7* 8*
24
14* 16*
19* 20* 22*
30
24* 27* 29*
33* 34* 38*39*
Redistribuição nas folhas
Suprimindo 20*
5
2* 3*
17
13
5* 7* 8*
24
27
14* 16*
22* 20*
24* 22*
30
24* 29*
27* 29*
27*
33* 34* 38*39*
Juntando folhas
Suprimindo 24*
17
Quase vazia !
5
2* 3*
13
5* 7* 8*
27
30
14* 16*
22*
2422*
*
27*
30
29* 27* 29*
33* 34* 38*39*
Junção de dois nós intermediários
17
5
2* 3*
13
5* 7* 8*
5
14* 16*
13
27
30
2422*
*
27*
30
29* 27*
São necessários 5 ponteiros
33* 34* 38*39*
Junção de dois nós intermediarios
17
5
2* 3*
5* 7* 8*
14* 16*
13
30
27
2422*
*
27*
30
30
29* 27*
33* 34* 38*39*
Redistribuição em nós intermediários
22
5
2* 3*
5* 7* 8*
135
14*16*
17
13
20
17
17* 18*
27
20* 21*
22* 24*
30
27*29*
33* 34* 38* 39*
Redistribuição em nós intermediários
22
Quase vazia
5
2* 3*
5* 7* 8*
135
14*16*
17
13
20
17
17* 18*
30
20* 21*
22* 27* 29*
33* 34* 38* 39*
Redistribuição em nós intermediários
22
5
135
17
13
20
17
30
??
2* 3*
5* 7* 8*
14*16*
17* 18*
20* 21*
22* 27* 29*
??
33* 34* 38* 39*
Redistribuição em nós intermediários
22
5
2* 3*
5* 7* 8*
135
14*16*
13
17
17
17* 18*
20
20* 21*
305
22*27* 29*
??
13
17
33* 34* 38* 39*
Resumo: Metodologia de Supressão
1.
2.
3.
Busca a página onde está a tupla a ser removida.
Caso após a remoção da tupla, a ocupação não fica abaixo do mínimo, a
tupla é removida e nenhum ajuste suplementar é feito nos outros níveis.
Caso após a remoção da tupla, a ocupação fica abaixo do mínimo:

Há possibilidade de redistrisbuir com um dos vizinhos.



Primeiro elemento do vizinho à direita passa para a folha à esquerdaelimina-se o primeiro elemento do pai do vizinho à direita
Exercicio : Último elemento do vizinho à esquerda passa para a
folha- ?
Não há possibilidade de redistribuição com os vizinhos


Junta-se com o vizinho à direita
Remove do pai do ex-vizinho o elemento cujo ponteiro à direita
apontava para o ex-vizinho da direita.
Resumo: Metodologia de Supressão

Junção de nós intermediários




Caso o nó à esquerda tenha no máximo d elementos
Remove-se do pai do ex-nó à direita o elemento cujo ponteiro à
direita apontava para este ex-nó. Insere-se este elemento no nó
juntado.
Ajusta-se os ponteiros.
Redistribuição de nós intermediários

Caso o nó à esquerda tenha mais de d elementos

Ultimo elemento do nó à esquerda passa para o nó à direita.

Remove-se do pai do nó à direita o elemento cujo ponteiro à
direita apontava para este nó. Insere-se este elemento no nó
juntado.

Transfere-se para o lugar que ocupava o elemento removido, o
ultimo elemento do nó à esquerda.
Exercicio
Como tratar o caso em que o nó que ficou abaixo
da ocupação minima é o primeiro nó (não tem
nó vizinho à esquerda) ?
Gerenciando Duplicatas


Quando a chave do índice não é chave candidata da
relação
Em sistemas comerciais:


Sybase: dados são ordenados pela chave – páginas são
ordenadas sequencialmente – acrescenta-se páginas de
overflow
DB2, Oracle, MS SQL Server: considera-se um
identificador de tuplas, eliminando-se as duplicatas.
Exemplo: (k,*) (k,*) ...  (k,id1,*) (k,id2,*),...
Método Geral para Gerenciamento de Duplicatas
17
7
2* 3* 5*
7* 8*
95
9* 10*
13
17
13*17* 23*
-
23* 23*
Primeiro Filho
375
17
43
13
23* 37* 41*
43* 47*
Segundo Filho não contém
nenhuma nova chave
Primeira nova
Chave é 37*
Duplicatas : chave não contém chave candidata
Busca 17*
7
2* 3* 5*
7* 8*
17
95
9* 10*
13
17
13*17* 23*
-
23* 23*
375
23* 37* 41*
43
13
17
43* 47*
Duplicatas : chave não contém chave candidata
Busca 24*
7
2* 3* 5*
7* 8*
17
95
9* 13*
13
17
-
13*17* 23*
?
23* 23*
375
23* 37*41*
Não precisa ir mais adiante !
43
13
17
43* 47*
Duplicatas : chave não contém chave candidata
Busca 13*
7
2* 3* 5*
7* 8*
17
95
9* 13*
13
17
13*17*23*
-
23* 23*
375
23* 37*41*
43
13
17
43* 47*