Aula 22 - Controle de concorrência

Prévia do material em texto

Controle de concorrência
Disciplina: Banco de Dados
Professor: Wandré Nunes de 
Pinho Veloso
2
Controle de Concorrência
• Técnicas voltadas para garantir a propriedade 
de isolamento das transações (I do ACID)
• A maioria das técnicas envolve garantir que o 
escalonamento de operações internas às 
transações seja serializável, usando protocolos
• Um grupo importante de protocolos usa a 
técnica de provocar o travamento de um registro 
ou grupo de registros
• Outros protocolos:
– técnicas baseadas em rótulos de tempo (timestamps)
– multiversão
– validação ou certificação (protocolos otimistas)
3
Controle de Concorrência
• A granularidade dos itens de dados 
também afeta o controle de concorrência
– Granularidade: a porção/parte do Banco de 
Dados que um item de dado representa
– Pode ser um único atributo, um bloco de disco 
inteiro, um arquivo (tabela) inteiro, ou mesmo 
todo o BD
– Este problema ocorre em transações longas, 
típicas de bancos de dados espaciais e SIG
4
Técnicas de Travamento em
Duas Fases
• Two-phase locking
• Uma trava ou bloqueio (lock) é uma variável 
associada a um item de dados e que descreve a 
situação do item quanto a possíveis operações 
que possam ser aplicadas a ele
• Geralmente existe uma trava para cada item de 
dados possível no BD, de atributos ao Banco 
inteiro
• As travas são um recurso para forçar a 
sincronização correta das operações 
concorrentes
5
Tipos de Travas
• Travas binárias
– Dois estados: travado (1) ou destravado (0)
– Se o valor da trava for 1, o item não pode ser 
acessado por nenhuma operação que o 
requisite
– Apenas duas operações são exigidas: 
lock_item(X) e unlock_item(X)
• Essas operações devem ser indivisíveis, ou seja, 
nenhum entrelaçamento de operações é permitido 
até que a operação termine ou a transação seja 
colocada em modo de espera
6
Algoritmos
lock_item(X):
B: if LOCK(X)=0 (item está 
desbloqueado)
 then LOCK(X)<-1 (bloquear o 
item)
 else begin
 wait (until lock(X) = 0
 e o gerenciador de bloqueio 
reinicia a transação);
 go to B
 end;
7
Algoritmos
unlock_item(x):
LOCK(X)<-0; (desbloquear o item)
 se alguma transação estiver 
esperando
 então acorda uma das transações 
em espera;
8
Travas Binárias
• No exemplo, a operação wait é em geral 
implementada sob a forma de uma fila de 
espera pelo item X, até que o mesmo esteja 
disponível e a transação possa finalmente 
acessá-lo
• As filas de espera podem também ser 
organizadas como uma tabela (lock table) ou 
como um arquivo hash
• Se o item não estiver na tabela ou no arquivo, é 
considerado destravado
9
Travas Binárias
• Regras aplicáveis a travas binárias:
1. A transação deve disparar a operação lock_item(X) 
antes de qualquer read_item(X) ou write_item(X)
2. A transação deve executar a operação unlock_item(X) 
depois que todas as operações read_item(X) ou 
write_item(X) tenham sido completadas com sucesso
3. A transação não executará um lock_item(X) se ela já for 
a responsável pelo travamento de X
4. A transação não executará um unlock_item(X) a menos 
que ela tenha sido a responsável pelo travamento de X
• Apenas uma operação pode estar mantendo o 
travamento do item X
10
Tipos de Travas
• Travas compartilhado/exclusivo (ou 
read/write)
– O travamento binário é muito restritivo, pois 
apenas uma operação pode ser a responsável 
pelo travamento
– É possível permitir que várias transações 
acessem o mesmo item se for apenas para 
leitura
– Se uma transação precisar gravar o item, deverá 
obter acesso exclusivo ao mesmo
– Travamento multimodo
11
Travas Compartilhado/Exclusivo
• A trava tem três estados possíveis
– Read-locked (compartilhado): travado para leitura
• Outras transações podem ler o item
– Write-locked (exclusivo): travado para gravação
• Apenas o dono do travamento pode ler ou gravar o item
– Unlocked: destravado
• Operações: read_lock(X), write_lock(X), 
unlock(X)
• A tabela de travamento terá quatro entradas
– Nome do item de dados; Valor da trava; Número de 
leituras simultâneas; Transações responsáveis pelo 
travamento
12
Travas Compartilhado/Exclusivo
• Na tabela, o valor da trava é sempre 
read_locked ou write_locked (itens destravados 
não são mantidos na tabela)
• Se o valor for write_locked, então o número de 
transações envolvidas terá que ser 1 e a lista 
terá apenas a transação responsável pelo 
travamento
• Se o valor for read_locked, haverá um número 
qualquer > 0 de transações e suas 
identificações formarão uma lista
13
Algoritmos
read_lock(X):
 B: if LOCK(X)=“unlocked”
 then begin LOCK(X)<-“read-locked”;
 no_of_reads(X)<-1
 end
 else if LOCK(X)=“read-locked”
 then no_of_reads(X)<-no_reads(X)+1
 else begin wait(until LOCK(X)=“unlocked”
e o gerenciador de bloqueio reinicia a transação);
 go to B
 end
14
Algoritmos
write_lock(X):
 B: if LOCK(X)=“unlocked”
 then LOCK(X)=“write-locked”;
 else begin
 wait(until LOCK(X)=“unlocked” e o 
gerenciador de bloqueio reinicia a 
transação);
 go to B
 end;
15
Algoritmos
unlock(x):
if LOCK(X)=“write-locked”
 then begin LOCK(X)<-”unlocked”;
 desperta uma das transações aguardando, se houver
 end
 else if LOCK(X)=“read-locked”
 when begin
 no_of_reads(X)<-no_of_reads(X)-1;
 if no_of_reads(X)=0
 then begin LOCK(X)=“unlocked”;
 desperta uma das transações aguardando, se 
houver
 end
 end;
16
Travas Compartilhado/Exclusivo
•Regras aplicáveis a travas compartilhado/exclusivo
1. A transação deve executar read_lock(X) ou 
write_lock(X) antes que qualquer operação 
read_item(X) seja executada
2. A transação deve executar write_lock(X) antes que 
qualquer operação write_item(X) seja executada
3. A transação deve executar unlock(X) depois que todas as 
operações read_item(X) e write_item(X) tenham 
terminado
4. A transação não pode executar read_lock(X) se ela já 
estiver mantendo um travamento compartilhado ou exclusivo 
sobre X
5. A transação não pode executar write_lock(X) se ela já 
estiver mantendo um travamento compartilhado ou exclusivo 
sobre X
6. A transação não pode executar unlock(X) se ela não estiver 
mantendo um travamento compartilhado ou exclusivo sobre X
17
Conversão de Travas (lock 
upgrading)
• Os algoritmos anteriores não permitem que o 
estado da trava seja passado de compartilhado 
para exclusivo
– Regras 4 e 5
• Essas regras podem ser relaxadas em certas 
condições:
– Permitindo que uma transação que tem um 
read_lock(X) possa emitir um write_lock(X), 
solicitando assim um travamento exclusivo (upgrade)
– Permitindo que uma transação que tem um 
write_lock(X) possa recuar (downgrade) para 
um estado de read_lock sobre X
18
Tipos de Travas
• Apenas o uso de travas binárias ou 
compartilhado/exclusivo não garante a 
seriabilidade
• No exemplo a seguir: os itens X em T2 e Y 
em T1 foram destravados cedo demais, 
não evitando o problema
• Para assegurar a seriabilidade, é 
necessário contar com mais um protocolo: 
travamento em duas fases
19
Exemplo
(b) Valores iniciais: 
X=20, Y=30
Resultado do plano 
de execução serial 
T1, seguido por T2: 
X=50, Y=80
Resultado do plano 
serial T2 seguido 
por T1: X=70, Y=50
T1 T2
read_lock(Y); read_lock(X);
read_item(Y); read_item(X);
unlock(Y); unlock(X);
write_lock(X); write_lock(Y);
read_item(X); read_item(Y);
X:=X+Y; Y:=X+Y;
write_item(X); write_item(Y);
unlock(X); unlock(Y);
(a)
20
Exemplo
Resultado do 
plano S X=50, 
Y=50 (não 
serializável)
T1 T2
read_lock(Y);
read_item(Y);
unlock(Y);
EXECUÇÃO
DE T2write_lock(X);
read_item(X);
X:= X + Y;
write_item(X);
unlock(X);
(c)
21
Two-Phase Locking
• Travamento/bloqueio em duas fases (2PL)
• Diz-se que uma transação segue o protocolo de 
travamento em duas fases se todas as operações de 
travamento (read_lock, write_lock) precederem a 
primeira operação de destravamento (unlock) na 
transação
• Se isso acontece, a transação pode ser dividida em 
duas fases:
– Expansão: novos travamentos são adquiridos, mas nenhum é 
liberado
– Contração: travamentos existentes são liberados, mas nenhum 
travamento novo é adquirido
• Upgrades só podem ocorrer na fase de expansão, e 
downgrades só podem ocorrer na fase de contração
22
Two-Phase Locking
• As transações T1 e T2 do exemplo anterior não seguem 
o travamento em duas fases
– Em T1, um write_lock(X) vem depois de um unlock(Y)
– Em T2, um write_lock(Y) vem depois de um unlock(X)
• O exemplo a seguir mostra uma nova versão de cada 
transação; nessa nova versão, o escalonamento do 
exemplo anterior não se aplica
• Foi provado que, se todas as transações em um 
escalonamento cumprirem o protocolo de travamento 
em duas fases, o escalonamento é garantidamente 
serializável
– Mas o protocolo pode limitar o desempenho concorrente
23
Two-Phase Locking
T1’ T2’
read_lock(Y); read_lock(X);
read_item(Y); read_item(X);
write_lock(X); write_lock(Y);
unlock(Y); unlock(X);
read_item(X); read_item(Y);
X:= X + Y; Y:= X + Y;
write_item(X); write_item(Y);
unlock(X); unlock(Y);
24
Two-Phase Locking
• Variações
– Básico: conforme apresentado anteriormente
– Conservador ou estático: exige que a transação 
trave todos os itens de que necessita antes de 
iniciar sua execução
– Estrito: a transação não libera nenhum 
write_lock até depois do commit ou abort
• Garante escalonamento estrito (nenhuma transação 
pode ler ou gravar um item até que a última transação 
que a gravou o item seja committed), favorecendo a 
recuperação
– Rigoroso: a transação não liberta nenhum 
travamento (read_lock ou write_lock) até 
depois do commit ou abort
25
Two-Phase Locking
• O travamento em duas fases garante a 
seriabilidade, mas pode provocar dois outros 
problemas
– Deadlocks
• Ocorre quando cada transação em um escalonamento 
(contendo pelo menos duas transações) é mantida em 
espera por um item travado por uma das outras
– Starvation
• Ocorre quando uma transação não pode prosseguir por um 
longo período de tempo, enquanto outras transações são 
processadas normalmente (“morre de fome”)
26
Deadlock ou Starvation?
27
Deadlock ou Starvation?
28
Deadlock
• Uma solução para deadlocks é usar um 
protocolo de prevenção contra deadlocks
– Uma maneira é usar o 2PL conservador, travando 
todos os itens antes de iniciar o processamento 
(porém, se algum item não puder ser bloqueado, 
nenhum será)
– Outra maneira é determinar uma ordem para a 
obtenção dos travamentos
– Nenhuma das duas é prática
• Outra solução proposta inclui o uso de 
timestamps associados às transações
29
Deadlock
• Usando timestamps, duas estratégias de 
prevenção de deadlocks são possíveis:
– Esperar-morrer: se TS(Ti) < TS(Tj), então (Ti 
mais antigo que Tj) Ti tem permissão para 
esperar; caso contrário (Ti mais novo que Tj) 
aborta Ti (Ti morre) e reinicia mais tarde com 
o mesmo timestamp
– Ferir-esperar: se TS(Ti) < TS(Tj), então (Ti 
mais antigo que Tj) aborta Tj (Ti fere Tj) e 
reinicia mais tarde com o mesmo timestamp; 
caso contrário (Ti mais novo que Tj), Ti tem 
permissão para esperar
30
Deadlock
• Em esperar-morrer, uma transação mais 
antiga tem permissão para esperar por uma 
transação mais nova, enquanto uma 
transação mais nova que solicita um item 
mantido por uma transação mais antiga é 
abortada e reiniciada
• A técnica ferir-esperar faz o contrário: uma 
transação mais nova tem permissão para 
esperar por uma mais antiga, enquanto uma 
transação mais antiga que solicita um item 
mantido por uma transação mais nova 
apodera-se da transação mais nova ao 
abortá-la
31
Deadlock
• Em ambos casos, a transação mais 
“jovem” dentre as duas, e que pode estar 
envolvida em um deadlock, é abortada
– Nem sempre o deadlock acontecerá de fato, 
portanto essas estratégias podem causar 
aborts desnecessários
• Foi demonstrado que em ambas as 
estratégias os deadlocks são evitados
32
Deadlock
• Algoritmo sem espera: se uma 
transação for incapaz de obter um 
bloqueio, ela é imediatamente abortada e, 
depois, reiniciada após certo atraso de 
tempo sem verificar se um deadlock 
realmente ocorrerá ou não
• Nesse caso, nenhuma transação espera, 
de modo que nenhum deadlock ocorrerá
– Esse esquema pode fazer que as transações 
abortem e reiniciem sem necessidade
33
Deadlock
• Algoritmo espera cuidadosa: proposto 
para reduzir o número de aborts 
desnecessários
– Se Tj não estiver bloqueada (não esperando por outro item bloqueado), então Ti está bloqueada e tem permissão para esperar; 
caso contrário, aborte Ti
• Nenhuma transação esperará por outra 
transação bloqueada
34
Deadlock
• Detecção de deadlocks
– Interessante quando se sabe que haverá pouca 
interferência entre transações; caso contrário, é 
preferível usar técnicas de prevenção
• Transações pequenas/curtas
• Cada transação trava poucos itens
• Carga de trabalho baixa
– Construir e manter um grafo de espera
• Um nó para cada transação que está em execução
• Um arco direcionado da transação em espera para a 
transação que mantém a trava em um item
• Quando a trava e liberada, deletar o arco
• Existe deadlock apenas se o grafo contiver ciclos
35
Deadlock
• Um problema é determinar com que frequência o 
sistema deve checar a existência de ciclos no grafo
– Número de transações concorrentes
– Período de tempo em espera para que uma transação bloqueie 
um item
• Se o sistema entrar em deadlock, algumas das 
transações envolvidas devem ser abortadas
– Victim selection
• Escolha das transações a abortar; evitar transações que estão 
executando a mais tempo e que realizaram mais atualizações; o 
custo de recuperação será maior se estas forem escolhidas
– Timeout
• Aborta a transação se um limite de tempo tiver sido excedido, 
mesmo que o deadlock não tenha sido detectado
36
Starvation
• Também chamado de inanição
• Ocorre quando uma transação é impedida de prosseguir por 
um longo período de tempo, enquanto outras transações são 
executadas normalmente (“morre de fome”)
• Pode ocorrer
– se o esquema de espera por itens travados for injusto, ou seja, 
privilegiar certas condições que não são atendidas por alguma 
transação, que então tende a entrar em starvation
– se o victim selection sempre escolhe a(s) mesma(s) vítima(s)
• Uma solução é montar uma fila (FIFO) na espera por itens
• Outra solução permite que certas transações tenham 
prioridade, mas o critério considera também o tempo de 
espera
• Esperar-morrer e Ferir-esperar evitam a ocorrência de 
starvation
37
Controle de Concorrência por
Ordenação de Timestamps
• O uso de travamento, combinado com o protocolo 
two-phase locking, garante a seriabilidade
• Os escalonamentos seriais correspondentes 
poderiam ser obtidos com base na ordem dos 
travamentos
– Se uma transação precisa de um item que está travado, 
terá que esperar a liberação
• Um enfoque diferente para garantir a seriabilidade 
envolve a ordenação da execução das operações 
com base nos timestamps das transações
• O two-phase locking é mais usado
38
Controle de Concorrência por
Ordenação de Timestamps
• Timestamps são atribuídos na ordem em que as 
transações são submetidas
– Não é possível ter timestamps iguais
• Esta técnica não usatravamento, portanto deadlocks 
são impossíveis
• O algoritmo básico garante que, caso ocorram conflitos, 
a ordem de execução não afeta a seriabilidade
• Cada item é associado a dois valores:
– read_TS(X): o maior timestamp dentre os das transações que 
leram X com sucesso
– write_TS(X): o maior timestamp dentre os das transações 
que gravaram X com sucesso
39
Controle de Concorrência por
Ordenação de Timestamps
• Ordenação básica de timestamps
– A transação T executa um write_item(X):
• Se read_TS(X) > TS(T) ou se write_TS(X) > TS(T), 
abortar e executar rollback: alguma transação mais “jovem” 
acessou o item
• Caso contrário, executar o write_item(X) e fazer 
write_TS(X) = TS(T)
– A transação T executa um read_item(X):
• Se write_TS(X) > TS(T) , abortar e executar rollback: 
alguma transação mais “jovem” alterou o item
• Caso contrário, executar o write_item(X) e fazer 
read_TS(X) = max(read_TS(X), TS(T))
– É possível que ocorra starvation
40
Controle de Concorrência por
Ordenação de Timestamps
• Ordenação de timestamps (TO) estrita
– Garante que os schedules sejam tanto estritos 
(para maior facilidade de recuperação) quanto 
serializáveis (conflito)
– Uma transação T emite um read_item(X) ou 
write_item(X), tal que TS(T) > write_TS(X) 
tenha sua operação de leitura ou gravação 
adiada até que a transação T’ que gravou o valor 
de X (portanto, TS(T’) = write_TS(X)) tenha 
sido confirmada ou abortada
– É necessário simular o bloqueio de um item X 
que foi gravado pela transação T’ até que T’ seja 
confirmada ou abortada
41
Controle de Concorrência por
Ordenação de Timestamps
• Regra da gravação de Thomas
– Não impõe a serialização por conflito, mas rejeita 
menos operações de gravação ao modificar as 
verificações para a operação write_item(X) 
da seguinte forma:
1. Se read_TS(X) > TS(T), então aborte e reverta T, e 
rejeite a operação
2. Se write_TS(X) > TS(T), então não execute a 
operação de gravação, mas continue processando
3. Se nem a condição na parte (1) nem a condição na 
parte (2) acontecer, então execute a operação 
write_item(X) de T e defina write_TS(X) para 
TS(T)
42
Controle de Concorrência por
Multiversão
• São protocolos que mantêm os valores anteriores de um 
item de dados quando o item é atualizado
• Potencialmente, várias versões (valores) são mantidas
• Quando uma transação precisa ter acesso ao valor de 
um item, a versão apropriada é escolhida, de modo a 
manter a seriabilidade
• A idéia é evitar o rollback em transações que poderiam 
ser aceitas se a leitura do dado fosse feita com o valor 
antigo
• A limitação desta alternativa está na necessidade de 
espaço de armazenamento para essas versões 
adicionais
– Mas versões anteriores podem ter que ser mantidas de qualquer 
forma, pelo log ou para as operações de recuperação
– No caso extremo, estaríamos lidando com um BD temporal
43
Controle de Concorrência por
Validação
• Também chamado de controle de concorrência 
otimista
– aka técnicas de validação ou certificação
• Nenhuma verificação é realizada enquanto a 
transação está executando
• Existem vários métodos
– Aplicar as atualizações ao BD apenas ao final do 
processamento da transação
– Durante a execução, as atualizações são realizadas 
sobre cópias locais dos itens
– Ao final do processamento, uma fase de validação 
verifica se alguma atualização viola a seriabilidade
44
Controle de Concorrência por
Validação
• Fases do protocolo
1. Leitura: a transação pode ler itens committed, mas aplica 
updates apenas sobre cópias locais (versões) dos dados, 
mantidos em um espaço reservado para a transação
2. Validação: uma verificação é executada para garantir que não 
haja nenhuma violação da seriabilidade
3. Gravação: se não houver violação, as atualizações são 
efetivadas; caso contrário, as atualizações (espaço temporário) 
são descartadas e a transação é reinicializada
• A ideia é concentrar as verificações, para interferir pouco 
com a execução
– Funciona bem apenas se existe uma tendência a haver pouca 
interferência entre transações
45
Granularidade dos Itens de Dados
• As técnicas de controle de concorrência 
consideram que o BD é formado de diversos 
itens de dados
• Um item pode ser:
– Um registro (linha)
– Um atributo em um registro
– Um bloco do disco
– Um arquivo (tabela) inteiro
– Todo o BD
• Evidentemente, a granularidade pode afetar o 
desempenho do controle de concorrência
46
Granularidade e Travamento
• Granularidade fina: itens pequenos
• Granularidade grossa: itens grandes
• Quanto maior a granularidade, menor a 
concorrência permitida
• Por outro lado, quanto menor a granularidade, 
maior o número de itens no BD
– Mais travamentos, maiores tabelas de travamentos
– Mais espaço adicional para timestamps
• A escolha da granularidade ideal depende dos 
tipos de transações típicas
47
Granularidade múltipla
48
Travamento em Múltiplos Níveis
de Granularidade
• Para possibilitar o travamento em múltiplos níveis 
simultâneos de granularidade, são necessárias travas 
de intenção, em adição aos travamentos compartilhado 
(S, de shared) e exclusivo (X, de exclusive)
– Intention-shared (IS)
• Indicam que um ou mais travamentos compartilhados serão 
solicitados sobre algum item/nó descendente
– Intention-exclusive (IX)
• Indicam que um ou mais travamento exclusivos serão solicitados 
sobre algum item/nó descendente
– Shared-intention-exclusive (SIX)
• Indicam que o nó atual está travado em modo compartilhado, mas 
que um ou mais travamentos exclusivos serão solicitados sobre 
algum item/nó descendente
49
IS IX S SIX X
IS Sim Sim Sim Sim Não
IX Sim Sim Não Não Não
S Sim Não Sim Não Não
SIX Sim Não Não Não Não
X Não Não Não Não Não
50
Travamento em Múltiplos Níveis
de Granularidade
• Novo protocolo: Multiple Granularity Locking (MGL)
1. É necessário atender à matriz de compatibilidade entre 
travamentos (tabela anterior)
2. A raiz da árvore deve ser travada primeiro, em qualquer modo
3. Um nó N pode ser travado por uma transação T em modo S 
ou IS apenas se o nó pai de N já estiver travado por T em 
modo IS ou IX
4. Um nó N pode ser travado por uma transação T em modo X, 
IX ou SIX apenas se o nó pai de N já estiver travado por T em 
modo IX ou SIX
5. Uma transação T pode travar um nó apenas se não houver 
destravado nenhum nó (protocolo two-phase locking)
6. Uma transação T pode destravar um nó N apenas se nenhum 
dos nós descendentes de N estiverem atualmente travados 
por T
51
Travamento em Múltiplos Níveis
de Granularidade
• A regra 1 apenas diz que travamentos em 
conflito não podem ser concedidos
• As regras 2, 3 e 4 estabelecem as condições 
nas quais uma transação pode requisitar um 
travamento
• As regras 5 e 6 estabelecem o comportamento 
esperado pelo protocolo two-phase locking
• Exemplo:
– T1 quer atualizar o registro r111 e o registro r211
– T2 quer atualizar todos os registros na página p12
– T3 quer ler os registros r11j e o arquivo f2 inteiro
52
T1 T2 T3
IX(db); IX(f1)
IX(db)
IS(db); IS(f1); IS(p11)
IX(p11); X(r111) 
IX(f1); X(p12)
S(r11j)
IX(f1); IX(p21)
X(r211)
unlock(r211); unlock(p21) 
unlock(f2)
S(f2)
unlock(p12); unlock(f1) 
unlock(db)
unlock(r111); unlock(p11) 
unlock(f1); unlock(db)
unlock(r11j); unlock(p11) 
unlock(f1); unlock(f2) 
unlock(db)
53
Travamento em Múltiplos Níveis
de Granularidade
• O protocolo MGL é adequado para situações em 
que se tem um mix de tipos de transações, 
incluindo
– Transações curtas, que acessam poucos itens 
pequenos (registros ou atributos)
– Transações grandes/longas, que acessam arquivos 
inteiros
• Esse protocolo tende a causar menosbloqueios 
e menos overhead por travamento do que 
protocolos que só consideram um nível de 
granularidade
54
Tópicos Adicionais
• Uso de travamento em índices (páginas de disco)
– Se for usado o 2PL, o nó que contém a raiz do índice se 
tornará um gargalo
• O 2PL estabelece que o travamento deve permanecer até a 
fase de contração
– Os blocos do índice podem ser travados, mas em caso de 
simples busca eles devem ser liberados assim que nós 
filhos sejam alcançados
– Em caso de gravação, nós ao longo da árvore podem ser 
liberados assim que for constatado que o bloco folha tem 
espaço para mais chaves
– Existem estruturas de dados específicas para lidar com 
esse problema: B-link tree
55
Tópicos Adicionais
• Inserção, exclusão e registros-fantasma
– Vide subseção 22.7 de Elsmari Ramez; 
Navathe Shamkant B. Sistemas de Banco de 
Dados – Fundamentos e Aplicações. 6 ed. 
Pearson, São Paulo, 2011.
56
Bibliografia
• Capítulo 22: Elsmari Ramez; Navathe 
Shamkant B. Sistemas de Banco de 
Dados – Fundamentos e Aplicações. 6 ed. 
Pearson, São Paulo, 2011.