E-book 2 Tópico 2 - Ambientes de Alta Escalabilidade

Prévia do material em texto

Luciano Rossi
BANCO DE DADOS EM 
AMBIENTES DE ALTA 
ESCALABILIDADE
E-book 2
Neste E-Book:
INTRODUÇÃO ����������������������������������������������������������� 3
ARMAZENAMENTO, INDEXAÇÃO E 
GERENCIAMENTO DE TRANSIÇÃO�������������������� 5
MEIOS DE ARMAZENAMENTO FÍSICO ������������������������������������5
INDEXAÇÃO E FUNÇÕES HASHING ���������������������������������������17
Recuperação de falhas �����������������������������������������������������������28
CONSIDERAÇÕES FINAIS ����������������������������������� 35
REFERÊNCIAS BIBLIOGRÁFICAS & 
CONSULTADAS �������������������������������������������������������38
2
INTRODUÇÃO
Os Sistemas Gerenciadores de Banco de Dados 
(SGBD) fornecem ao usuário uma visão de alto nível 
do banco de dados, abstraindo a complexidade do 
hardware, sobretudo em relação ao modo com que 
os dados são armazenados e recuperados� Devemos 
ter em mente que os dados são representados e ar-
mazenados como sequências de bits, em diferentes 
dispositivos de armazenamento�
Existem diferentes dispositivos responsáveis pelo ar-
mazenamento de dados� Podemos utilizar um disco 
magnético ou uma memória flash para o armazena-
mento não volátil de dados�
Os dispositivos de armazenamento não voláteis são 
os que mantêm os dados armazenados mesmo que 
não energizados� Observe que isso não ocorre com a 
memória principal, na qual os dados não persistem 
quando o dispositivo não está energizado� Outros 
dispositivos de armazenamento, comumente utili-
zados para a realização de backup, são os discos 
ópticos e as fitas magnéticas.
Cada tipo de dispositivo de armazenamento tem 
características particulares� Essas características 
são importantes para a determinação da forma 
como os dados são armazenados e, posteriormen-
te, recuperados�
Sendo assim, neste módulo trataremos dos dispo-
sitivos de armazenamento e suas características 
3
principais, como velocidade de acesso aos dados, 
custo por unidade e capacidade de armazenamento�
Além disso, analisaremos as diferentes formas de 
indexação utilizadas em bancos de dados, conside-
rando as estruturas de índices e as funções hashing� 
Por fim, discutiremos os tipos de falhas que podem 
ser um resultado das transações malsucedidas e as 
respectivas formas de recuperação�
4
ARMAZENAMENTO, 
INDEXAÇÃO E 
GERENCIAMENTO DE 
TRANSIÇÃO
O armazenamento de dados nos computadores con-
sidera um contexto binário, ou seja, os dados são 
representados como bits nos diferentes dispositivos� 
Existem vários tipos de dispositivo de armazenamen-
to que utilizam diferentes mecanismos para viabilizar 
a representação dos dados em formato binário�
Alguns desses dispositivos são capazes de arma-
zenar uma grande quantidade de informações, a um 
custo baixo por unidade armazenada, mas não são 
eficientes do ponto de vista da velocidade de acesso. 
Existem dispositivos que são muito rápidos, mas, 
devido ao alto custo por unidade de armazenamento, 
têm capacidade limitada�
Com base nessas premissas, exploraremos os dife-
rentes tipos de dispositivos de armazenamento, evi-
denciando as principais características e aplicações�
Meios de armazenamento físico
A velocidade com que um usuário de computador 
recebe uma resposta, para uma solicitação especí-
fica, depende de vários fatores. Por exemplo, algo-
ritmo implementado, capacidade do processador, 
dispositivo de armazenamento etc� Nesse sentido, os 
5
dispositivos de armazenamento exercem um papel 
importante no desempenho oferecido pelos sistemas 
computacionais� Entre os dispositivos de armazena-
mento comumente disponíveis, podemos destacar o 
cache, memórias, flash, discos magnéticos e ópticos 
e fitas magnéticas.
O cache é um dispositivo de armazenamento que liga 
o processador e a memória principal� Seu objetivo 
é reduzir o tempo gasto para acessar diretamente a 
memória principal� Os blocos de dados são trazidos 
da memória principal para o cache� Note que o aces-
so ao cache é mais rápido assim, por isso, o cache 
acumula momentaneamente os dados que serão 
enviados à memória principal ou que virão dela� A 
estratégia é duplicar os blocos de dados da memó-
ria principal em um dispositivo de armazenamento 
menor e mais rápido�
Podemos ter diferentes níveis de cache, que são 
definidos pela sua localização. O cache pode estar 
presente no próprio chip do processador (nível 1), 
em um chip separado e acoplado ao processador 
(nível 2) e na placa mãe (nível 3)�
Os níveis de cache intermediam o fluxo de dados 
entre a memória principal e o processador� Desse 
modo, quanto mais próximo ao processador está o 
cache, é menor e mais rápido; quanto mais próximo 
à memória principal, o cache é maior e mais lento�
A memória principal armazena os dados disponí-
veis para o processamento, ou seja, as instruções de 
máquina operam sobre ela� Podemos ter diferentes 
6
tamanhos para a memória principal, dependendo 
das características do computador� Porém, nunca 
é suficientemente grande para armazenar o banco 
de dados completo� Tal qual o cache, a memória 
principal é volátil, ou seja, o conteúdo armazenado 
é perdido quando o sistema não está energizado�
A memória flash tem características similares à 
memória principal; as principais diferenças são a 
não volatilidade e a velocidade menor, mas ambas 
são dispositivos eletrônicos, ou seja, não possuem 
partes móveis, o que aumenta o desempenho quando 
comparadas aos dispositivos eletromecânicos com 
partes móveis e são, portanto, mais lentos�
São exemplos de memória flash: pen drives, cartões 
de memória e unidades em estado sólido ou Solid-
State Drive (SSD)�
O SSD tem sido utilizado como substituto para os 
discos magnéticos (Hard Disk – HD), visto que apre-
senta um desempenho superior com um custo por 
unidade de armazenamento reduzido ano a ano�
Discos magnéticos
Os discos magnéticos caracterizam-se pela grande 
capacidade de armazenamento de dados� Assim, o 
banco de dados inteiro pode ser armazenado em um 
disco magnético� Os dados utilizados pelas transa-
ções devem ser movidos do disco magnético para 
a memória principal, onde as operações serão rea-
lizadas e, posteriormente, as alterações devem ser 
atualizadas no disco�
7
O HD é um disco magnético que se caracteriza por 
um prato circular construído a partir de material não 
magnético e que recebe uma camada de material 
magnetizável� Os discos magnéticos são dispositivos 
eletromecânicos; logo, contêm partes móveis, o que 
impacta negativamente no desempenho�
Os grandes servidores de dados utilizam um subsis-
tema de armazenamento na forma de um conjunto 
redundante de discos independentes, os Redundant 
Array of Independent Disks (RAID)� Esse subsistema é 
transparente ao usuário e tem por objetivo aumentar 
a segurança ou o desempenho do sistema�
Dependendo do nível RAID, que é a combinação de 
dois ou mais discos, podemos ter um aumento (i) na 
redundância dos dados, (ii) na taxa de transferência 
e (iii) na taxa de processamento de solicitações�
O nível RAID 0 é constituído de dois ou mais discos, 
em que os blocos de dados se dividem. Essa configu-
ração permite um ganho importante de desempenho, 
pois as operações de leitura e escrita são feitas em 
paralelo nos discos�
Por exemplo, imagine um bloco de dados com o qual 
gastaríamos um tempo t para escrevê-lo no disco� 
Supondo RAID 0 com dois discos, o bloco de da-
dos será dividido em duas partes: a primeira será 
armazenada em um disco; a segunda parte no outro 
disco� Dessa forma, as duas partes do bloco de da-
dos são gravadas em paralelo (ao mesmo tempo), 
propiciando que a operação seja realizada em um 
tempo igual a t/2�
8
O exemplo anterior ilustrou um ganho de desempe-
nho na realização das operações em disco� Neste 
caso, o tempo para a execução da operação foi redu-
zido pela metade, visto que se utilizaram dois discos� 
Caso contássemos com quatro discos em RAID 0, o 
tempo para a realização das operações seria redu-
zido a um quarto do tempo necessário para realizar 
a operaçãoem um único disco�
Para uma melhor compreensão, temos uma analogia 
para o ganho de desempenho propiciado por RAID 
0. Suponha uma fila em um caixa de supermercado 
com 10 pessoas, com as quais o atendente gastará, 
em média, cinco minutos por cliente� Assim, seriam 
necessários 50 minutos para atender todos os clien-
tes� Se adicionarmos um novo caixa, a cada cinco 
minutos, dois clientes seriam atendidos em paralelo, 
e a fila terminaria em 25 minutos.
O RAID 0 utiliza o espalhamento dos dados com vis-
tas a obter um ganho de desempenho� A Figura 1 
apresenta um exemplo de RAID 0 com dois discos� 
Observe que os blocos de dados A, B, C e D são 
segmentados em duas partes, que se armazenam 
em discos diferentes�
9
RAID 0 RAID 1 RAID 5 
RAID 6 RAID 10 
RAID 1 RAID 1 
DISCO 1 DISCO 2 DISCO 3 DISCO 4 DISCO 1 DISCO 2 DISCO 3 DISCO 4 DISCO 4 
DISCO 1 DISCO 2 DISCO 1 DISCO 2 DISCO 1 DISCO 2 DISCO 3 DISCO 4 
RAID 50 
RAID 0
RAID 5 RAID 5
DISCO 1 DISCO 2 DISCO 3 DISCO 4 DISCO 5 DISCO 6 DISCO 7 DISCO 8
A1
B1
C1
D1
A2
B2
C2
D2
A1
B1
C1
D1
A1
B1
C1
D1
A1
B1
C1
P
A2
B2
P
D2
A3
P
C3
D3
P
B4
C4
D4
A1
B1
C1
P
A2
B2
P
P2
A3
P
P2
D3
P
P2
C4
D4
P2
B5
C5
D5
A1
A3
A5
A7
A1
B3
C5
D7
A2
A4
A6
A8
A2
B4
C6
D8
A1
B1
C1
P
A2
B2
P
D2
A3
P
C3
D3
P
B4
C4
D4
A5
B5
C5
P
A6
B6
P
D6
A7
P
C7
D7
P
B8
C8
D8
Figura 1: Conjuntos redundantes de discos independentes� 
Fonte: Elaboração própria�
Em RAID 0, quando um disco é perdido, há perda 
completa de todos os dados, pois o disco íntegro 
contém somente metade de cada bloco de dados, 
o que os torna inviáveis para a utilização� À medida 
que aumentamos o número de discos em RAID 0, 
aumentamos também o risco de perda de todo o 
banco de dados a partir da perda de um único disco�
O nível RAID 1 considera no mínimo dois discos e 
consiste, basicamente, do espelhamento dos da-
dos de um disco em outro, ou seja, esse nível reali-
za a replicação de dados� É uma solução simples 
para a segurança dos dados, visto que, em caso de 
10
perda de um disco, os dados permanecem íntegros 
no outro disco� Na Figura 1, temos um exemplo em 
RAID 1 com dois discos� O principal problema para 
essa solução é o consumo do dobro de discos para 
o armazenamento�
O nível RAID 5 considera dados de paridade dos blo-
cos de dados, criando uma camada de redundância 
sem que seja necessário gastar metade dos discos 
para isso� O RAID 5 utiliza uma estratégia de pari-
dade distribuída e necessita, pelo menos, de três 
discos�
Os blocos de dados são distribuídos entre os discos 
disponíveis� Além disso, um algoritmo é responsável 
por gerar dados de paridade que serão utilizados 
para a recomposição do bloco em caso de perda de 
um dos discos� Assim, RAID 5 integra segurança e 
desempenho em um único arranjo de discos�
É importante notar que os dados de paridade consu-
mirão o equivalente a um disco do arranjo, mesmo 
que haja mais que três discos na composição� Na 
Figura 1, encontra-se um exemplo em RAID 5 com 
quatro discos, os dados de paridade são distribu-
ídos entre os discos, consumindo o equivalente a 
um disco�
O nível RAID 6 é similar ao RAID 5, ou seja, utiliza 
dados de paridade para a recomposição dos blocos 
de dados em caso de perda de discos� A principal 
diferença observada em RAID 6 é a estratégia da 
redundância dupla, pois RAID 6 realiza a duplicação 
dos dados de paridade, de modo que o conjunto de 
11
dados se mantenha íntegro, mesmo com a perda 
de dois discos� Essa solução deve contar com, no 
mínimo, quatro discos, dado que dois discos serão 
consumidos para armazenamento dos dados de 
paridade�
Na busca por mais eficiência das operações e maior 
segura dos dados, é possível considerar a combi-
nação de estratégias de organização dos discos, 
ou seja, podemos utilizar, por exemplo, uma combi-
nação que venha a possibilitar o espelhamento dos 
dados (RAID 1), combinando com uma estratégia 
que considere o espalhamento dos dados (RAID 0)� 
Comumente, esse tipo de combinação é denominado 
RAID 1 + 0 ou RAID 10�
O nível RAID 10 necessita de, pelo menos, quatro 
discos para sua implementação� Assim, os blocos 
de dados são divididos (espalhados) por dois pares 
de discos que, por sua vez, armazenam os dados de 
forma duplicada (espelhada) em cada um dos discos�
Na Figura 1, temos um exemplo de quatro discos em 
RAID 10� Note que os blocos de dados são espelha-
dos em cada par de discos e espalhados em dois 
pares� Desse modo, é possível obter um aumento 
de desempenho e, ao mesmo tempo, manter certo 
nível de segurança dos dados�
Em um arranjo com quatro discos, como é o caso na 
Figura 1, poderíamos ter a perda de até dois discos, 
desde que isso não ocorre em um mesmo par, sem 
que haja a perda dos blocos de dados armazenados�
12
Considerando a Figura 1 como referência, temos um 
último exemplo que considera oito discos, organi-
zados em RAID 50 (ou RAID 5 + 0)� Esse nível RAID 
precisa de, no mínimo, seis discos para a sua imple-
mentação� A estratégia é dividir os blocos de dados 
em dois ou mais segmentos em RAID 5� Com isso, 
teremos um aumento no desempenho das operações 
sobre os discos e, em caso de catástrofe, o sistema 
suporta a perda de até dois discos por arranjo�
Além dos níveis descritos anteriormente, existem 
outras possibilidades de níveis RAID� Por exemplo, o 
nível RAID 60 (ou RAID 6 + 0) considera dois ou mais 
arranjos em RAID 6, os quais receberão os blocos de 
dados espalhados por eles (RAID 0)�
Podemos ter ainda o nível RAID 2, que considera os 
códigos de correção de erros; RAID 3, que utiliza a 
paridade intercalada por bit; e o nível RAID 4, que 
utiliza a paridade intercalada por bloco�
Independentemente do nível RAID utilizado, o obje-
tivo sempre será ou o aumento do desempenho das 
operações ou o aumento do nível de segurança dos 
dados, ou ambos simultaneamente�
Discos ópticos
Os discos ópticos são dispositivos de armazenamen-
to de dados muito populares em um passado recente� 
Os principais tipos de discos ópticos são Compact 
Disk (CD), com capacidade de armazenamento de 
até 700 MB de dados, Digital Video Disk (DVD), que 
pode armazenar de 4,7 a 8,5 GB de dados�
13
Esses dispositivos de armazenamento são fabrica-
dos em policarbonato revestidos com uma camada 
de algum material altamente reflexivo, comumente 
alumínio� A gravação de dados em tais dispositivos 
utiliza sulcos microscópios na superfície reflexiva 
que, após a gravação, se protege com uma cobertura 
translúcida de laca ou verniz�
Os primeiros discos ópticos eram somente para leitu-
ra, utilizados para o armazenamento de áudio e vídeo� 
Um fotossensor percorre a superfície, em intervalos 
regulares, identificando ou não a presença de sulcos. 
Um início ou final de sulco indica o valor binário 1, e 
a ausência de mudança na elevação indica o valor 
0� Outras versões que consideravam apenas uma 
gravação ou múltiplas gravações foram igualmente 
utilizadas no passado�
Fitas magnéticas
As fitas magnéticas foram as precursoras no quesi-
to “dispositivo de armazenamento de dados”� Suas 
principais características são o baixo custo e a alta 
capacidade de armazenamento de dados, princi-
palmente quando utilizadas como dispositivo para 
manter grandes conjuntos de dados� Por exemplo, 
dados de satélites, que podem conter até centenas 
de terabytes (TB)�
A Figura 2 apresenta a hierarquia dos dispositivos 
de armazenamento de dados� Nela, os dispositivos 
localizados na parte superior são os que apresentam 
maior custo por bit armazenado, mas que oferecem 
acesso mais rápido aos dados� Por outro lado, na 
14
parte inferior da figura, localizam-se os dispositivos 
de armazenamento para os quais o custo por bit ar-
mazenado é menor, tal qual a velocidade de acesso:
Cache
Memória
principal
Memória flash
Discos magnéticos
Discos ópticos
Fitas magnéticas
armazenamento
primário
volátil
armazenamento
secundário
ou on-line
não volátil
armazenamento
terciário
ou off-line
não volátil
Rápido
Caro
Lento 
Barato
Figura2: Hierarquia de dispositivos de armazenamento� 
Fonte: Elaboração própria�
O cache, por exemplo, tem maior custo por bit arma-
zenado do que a memória principal� No entanto, ofe-
rece maior velocidade de acesso� Essa observação 
justifica-se, de certo modo, pela quantidade de dados 
que cada dispositivo pode armazenar, ou seja, quanto 
maior o custo de armazenamento por bit, menor a 
disponibilidade de espaço de armazenamento�
As características dos dispositivos de armazena-
mento justificam a forma como são utilizados. O 
15
cache e a memória principal são dispositivos de ar-
mazenamento primário, ou seja, os dados disponíveis 
para utilização devem estar armazenados nesses 
dispositivos�
Outra característica importante nesses dispositivos 
é a volatilidade� Desse modo, os dados só estão dis-
poníveis enquanto houver energia no sistema, uma 
vez a falta de energia, os dados são perdidos�
Comumente, a memória flash e os discos magnéticos 
são considerados dispositivos de armazenamen-
to secundário ou on-line� Nesses casos, os dados 
processados devem ser movidos para a memória 
principal e, sempre que modificados, os dados devem 
ser atualizados nos dispositivos de armazenamento 
secundário�
Esses tipos de dispositivo armazenam os dados de 
forma perene, ou seja, mesmo que não haja energia 
no sistema, os dados permanecem armazenados� 
Nesse sentido, a memória flash e os discos magnéti-
cos são dispositivos de armazenamento não voláteis�
Os discos ópticos e as fitas magnéticas são disposi-
tivos de armazenamento classificados como terciário 
ou off-line� Devido à capacidade que os dispositivos 
têm de armazenar grandes quantidades de dados, 
principalmente as fitas magnéticas, são utilizados 
como dispositivos para back-up�
O custo por bit armazenado é bastante reduzido, tal 
qual a velocidade de acesso aos dados� O termo off-
-line refere-se ao fato de que os dados não estão dis-
16
poníveis diretamente para uso, pois devem ser lidos e 
movidos para os dispositivos secundários e, a partir 
disso, ficam disponíveis a dispositivos primários. 
Indexação e funções hashing
As consultas realizadas sobre o banco de dados re-
ferem-se muitas vezes apenas a poucos registros ou 
a um valor específico. Nesse sentido, não é eficiente 
que várias leituras sejam feitas até que se encontre o 
registro ou valor buscado� O sistema deve ser capaz 
de ler o dado objetivo de maneira direta�
Quando precisamos identificar um assunto específico 
em um livro, por exemplo, não folhamos todas as 
páginas até encontrar o assunto desejado� Para isso, 
utilizamos o índice do livro, no qual encontramos o 
número da página que contém o assunto de interes-
se� Em um sistema de banco de dados, a lógica é 
similar: o sistema utiliza técnicas de indexação para 
facilitar a busca por uma determinada informação 
armazenada no banco de dados�
Os índices utilizados em um sistema de banco de 
dados podem ser de dois tipos básicos: os índices 
ordenados, organizados em uma ordem dos valores, 
e os índices de hash, que realizam o mapeamento 
para uma distribuição uniforme de valores�
A busca por determinados registros em um arquivo 
é feita a partir de uma chave de busca, isto é, um 
índice em um arquivo� Assim, se houver diferentes 
índices, haverá diferentes chaves de busca�
17
Uma estrutura de índices é uma lista ordenada em 
que cada qual é associado a um ponteiro (endereço 
de memória) para o registro� A busca por um de-
terminado registro é feita na estrutura de índices e, 
quando encontrado, o acesso ao registro é feito por 
meio do ponteiro associado ao índice�
Quando os registros no arquivo são armazenados 
em ordem, dizemos que os índices na estrutura são 
índices de agrupamento ou primários� Os índices 
que mapeiam as chaves de busca não ordenadas 
são chamados de índices secundários� Note que, no 
contexto desta unidade, por valores ordenados nos 
referimos à ordem sequencial�
Um registro em uma estrutura de índices é composto 
por um valor da chave de busca e um, ou mais, pon-
teiros para registros que tenham o valor da chave 
de busca�
Na Figura 3ª, temos uma estrutura de índices, na 
qual cada registro é composto pela chave de busca, 
neste caso, consideramos o ID, e um ponteiro para 
o endereço do registro� Perceba que o ponteiro é 
representado por uma circunferência colorida e uma 
seta que aponta para a localização do registro no 
arquivo (Figura 3c)�
18
10101
32343
76543 
10101
12121
15151
22222
32343
33456
45565
 58583
76543
76766
83821
98345
10101
12121
15151
22222
32343
33456
45565
 58583
76543
76766
83821
98345
Srinivasan
WU
Mozart
Einstein
El Said
Gold
Katz
 Califieri
Singh
Crick
Brandt
Kim
Ciência da Computação
Economia
Música
Física
História
Física
Ciência da Computação
 História
Economia
Biologia
Ciência da Computação
Engenharia Elétrica
65000
90000
40000
95000
60000
87000
75000
62000
80000
72000
92000
80000
(a) (b) (c)
/
ID NOME DEPARTAMENTO SALÁRIO
Figura 3: Índice esparso (a), índice denso (b) e arquivo se-
quencial� Fonte: Adaptada de Silberschatz, Sundarshan e 
Korth (2016)�
Para cada registro no arquivo, há um ponteiro indican-
do o próximo registro (Figura 3c)� Nesse exemplo, es-
tamos considerando um arquivo em que os registros 
estão ordenados sequencialmente pelo atributo ID�
O índice denso é composto por um registro na es-
trutura de índices para cada valor-chave no arquivo� 
Na Figura 3, temos uma estrutura de índices (b) para 
cada valor-chave no arquivo (c)�
Nesse caso, o valor-chave é o atributo ID, porém, 
poderíamos ter qualquer outro atributo como valor-
-chave, e outra estrutura de índices correspondente a 
tal atributo� Uma busca pelo valor-chave 22222 seria 
realizada na estrutura de índices de agrupamento 
denso e, quando o valor-chave fosse encontrado, o 
ponteiro associado identificaria o registro completo 
no arquivo�
19
Caso existam vários registros com ID = 22222, o 
valor-chave, na estrutura de índices, deve estar as-
sociado a uma lista de ponteiros, um para cada re-
gistro no arquivo�
No índice esparso, somente alguns valores-chave 
são pertinentes à estrutura de índices� Essa aborda-
gem só pode ser considerada quando os registros 
no arquivo estão ordenados sequencialmente pelo 
valor-chave utilizado� A Figura 3a é um exemplo de 
estrutura de índices de agrupamento esparso�
Nessa abordagem, supondo que queiramos encontrar 
o valor-chave ID = 22222, devemos buscar na estrutu-
ra de índices o valor-chave que seja menor ou igual ao 
valor procurado. Assim, o valor-chave identificado na 
estrutura de índices que corresponde aos critérios é o 
valor 10101. E o registro correspondente é identifica-
do no arquivo por meio do ponteiro associado, visto 
que os registros estão ordenados sequencialmente, 
iniciamos uma busca a partir daquela posição até 
encontrar o valor-chave que buscamos�
A utilização de índices esparsos pode não ser tão efi-
ciente quanto a utilização de índices densos, porém, 
os índices esparsos requerem menor espaço para o 
armazenamento da estrutura de índices, por contar 
de seu número menor de registros�
Não é raro ter tabelas (relações) com um grande 
número de registros em disco� Assim, a estrutura de 
índices, no caso de índices densos, teria o mesmo 
número de registros que a tabela em disco� Note 
que a estrutura de índices deve ser movida para a 
20
memória principal para a identificação do valor-chave 
e do ponteiro associado� Com isso, é possível que a 
estrutura de índices consuma grande parte da me-
mória disponível, tornando as operações lentas�
Mesmo no caso de utilizarmos uma estrutura de ín-
dices esparsa, cada ponteiro na estrutura indicará 
um agrupamento em disco com muitos registros, os 
quais devem ser percorridos sequencialmente até 
que se encontre o valor-chave buscado�
As operações de buscas sequenciais são executa-
das sobre o agrupamento, indicado pelo ponteiro, 
na memória principal, o que também implica mover 
todo o agrupamento para a memória, tornando as 
operações lentas�A solução, neste caso, é a utilização de índices mul-
tiníveis� Podemos utilizar as estruturas de índices 
esparsas em disco como qualquer outro arquivo 
sequencial� Poderíamos compor uma estrutura de 
índices externos para as estruturas de índices inter-
nos em disco, de modo que somente a primeira seria 
movida para a memória e, a partir da identificação do 
intervalo do valor-chave e do correspondente pontei-
ro, a estrutura de índices internos seria movida para 
a memória�
Observe a Figura 4� Imagine que estamos interes-
sados no registro cujo ID = 20856 e contamos com 
uma estrutura de índices esparsos de dois níveis� 
Note que a estrutura de índices externos (a) contém 
ponteiros associados aos valores-chave entre 10�000 
21
e 50�000; inicialmente, apenas esses registros seriam 
movidos para a memória principal�
Em seguida, o endereço da estrutura de índices inter-
nos, correspondente ao valor-chave que se busca, se-
ria identificado por meio do ponteiro associado com 
o valor-chave em (a)� Assim, a estrutura de índices 
internos (b), no intervalo de 20�000 até 20�900, seria 
movida para a memória, e o procedimento se repe-
tiria, ao identificar o bloco de dados que contém o 
valor-chave buscado� Nessa última etapa, uma busca 
sequencial é realizada sobre o bloco de dados obtido�
Note que é possível criar tantos níveis quanto forem 
necessários para a otimização das consultas sobre 
os arquivos da base de dados� A utilização de índices 
multiníveis é mais eficiente na busca por registros 
que a utilização de árvores de busca binária, pois 
executam menos acessos ao disco�
10000
20000
30000
40000
50000
10000
10100
10800
10900
20000
20100
20800
20900
30000
30100
30300
30400
10101
10121
10151
10172
Srinivasan
WU
Mozart
Einstein
Ciência da Computação
Economia
Música
Física
65000
50000
40000
95000
20843
20856
20865
20883
El Said
Gold
Katz
Califieri
História
Física
Ciência da Computação
História
60000
87000
75000
62000
30343
30366
30321
30345
Singh
Crick
Brandt
Kim
Economia
Biologia
Ciência da Computação
Engenharia Elétrica
80000
72000
92000
80000
Figura 4: Índices multiníveis� Fonte: Adaptada de 
Silberschatz, Sundarshan e Korth (2016)�
22
As abordagens de indexação estudadas são aplicá-
veis quando temos os registros no arquivo ordenados 
sequencialmente por algum valor-chave� No entanto, 
quando os registros não apresentam essas caracte-
rísticas, as abordagens anteriores são pouco úteis� 
Nesse contexto, a utilização de índices secundários 
pode ser a solução para tal problema�
A Figura 5 apresenta os registros ordenados pelo 
valor-chave ID. Suponha que queiramos identificar 
o(s) registro(s) que possui(em) o valor do atributo 
SALÁRIO igual a 80�000�
Observe que os registros não estão ordenados pelo 
valor desse atributo, assim, a solução seria percorrer 
todos os registros verificando os que atendem ao 
critério estabelecido�
Percorrer todos os registros em um arquivo não é 
uma boa solução� Em vez disso, podemos utilizar 
uma estrutura de índices secundários, em que cada 
registro da estrutura contém um valor-chave e um 
ou mais ponteiro associado�
Essa estrutura assemelha-se à estrutura de índices 
densos, na qual todos os registros no arquivo têm 
um registro correspondente na estrutura� A principal 
diferença nas estruturas de índices secundários é que 
o endereço associado a cada registro na estrutura 
é um ponteiro para outra estrutura composta pelos 
ponteiros, para os registros no arquivo que atendam 
ao critério de busca estabelecido�
23
Voltemos ao exemplo da busca pelos registros cujo 
atributo SALÁRIO é igual a 80�000� A princípio, re-
alizamos a busca pelo valor-chave na estrutura de 
índices, onde os valores são ordenados linearmente, 
o que viabiliza um processo de busca mais eficiente.
Quando o valor é localizado, o ponteiro associado 
a ele indica a estrutura que contém o(s) ponteiro(s) 
para o(s) registro(s)� Nesse caso, temos dois regis-
tros cujos valores para o atributo SALÁRIO é igual 
a 80�000: ID = ‘76542’ e ID = ‘98345’� Ambos foram 
identificados por meio de seus endereços armaze-
nados na estrutura secundária, de forma direta:
/
ID NOME DEPARTAMENTO SALÁRIO
Ciência da Computação
Economia
Música
Física
História
Física
Ciência da Computação
História
Economia
Biologia
Ciência da Computação
Engenharia Elétrica
40000
60000
62000
65000
72000
75000
80000
87000
90000
92000
95000
10101
12121
15151
22222
32343
33456
45565
58583
76543
76766
83821
98345
Srinivasan
WU
Mozart
Einstein
El Said
Gold
Katz
Califieri
Singh
Crick
Brandt
Kim
65000
90000
40000
95000
60000
87000
75000
62000
80000
72000
92000
80000
Figura 5: Índices secundários� Fonte: Adaptada de 
Silberschatz, Sundarshan e Korth (2016)�
Apesar de aumentar a eficiência das operações em 
disco, o uso de arquivos, organizados sequencialmen-
te, é sempre ligado ao acesso de uma estrutura de 
índices, o que ainda resulta em operação adicional 
sobre o disco�
24
Alternativamente, podemos considerar a utilização 
de técnicas de hashing para evitar o acesso a uma 
estrutura de índices�
Uma função hashing é responsável por mapear um 
valor chave K para um endereço B de um bloco de dis-
co� Com isso, os blocos de disco são denominados 
buckets e podem ser considerados para referenciar 
também às unidades de memória maiores ou meno-
res que um bloco de disco�
Uma função hashing h mapeia um valor-chave para 
um endereço de bucket (h (Ki )=Bi)� Desse modo, os 
endereços dos buckets podem ser obtidos direta-
mente em função do valor da chave, sem consultar 
qualquer tipo de estrutura de índice, o que aumenta 
a eficiência das operações.
As operações de inserção, pesquisa e remoção de 
registros nos buckets é bastante simples� Para inse-
rir um registro cujo valor chave seja Ki, utilizamos a 
função hashing e identificamos o endereço do bucket 
de destino da seguinte forma: h (Ki )=Bi, e o registro 
cujo valor-chave é Ki será inserido no bucket Bi�
A pesquisa segue o mesmo princípio: primeiro iden-
tificamos o bucket por meio da função hashing sobre 
o valor da chave do registro e, no bucket identificado, 
realizamos uma pesquisa sobre todos os valores-
-chave, retornando o registro correspondente. Por fim, 
a remoção segue o mesmo procedimento da pesqui-
sa, apenas depois de o registro ser identificado, ele 
será removido do bucket, ao invés de ser retornado�
25
Em um mundo ideal, a função hashing mapeará os 
valores-chave uniformemente, para todos os buckets 
disponíveis� Caso contrário, se os valores-chave fo-
rem todos mapeados para um mesmo bucket, tería-
mos que realizar uma busca no bucket e, com isso, 
identificar o registro desejado. Verificamos que esse 
tipo de busca é indesejável�
Uma distribuição de valores-chave em buckets deve 
ser uniforme, os buckets devem ter o mesmo número 
de registros, e aleatória, o valor resultante da função 
hashing não deve se associar com qualquer tipo de 
ordenação dos valores de chaves�
Considere que queremos mapear os registros do 
arquivo utilizado nos exemplos anteriores para as 
estruturas de índices� Os registros são mapeados 
por meio do valor do atributo DEPARTAMENTO e de-
senvolvemos uma função hashing que recebe esse 
valor� A partir da primeira letra, indica o endereço de 
um dos 26 buckets considerados para a distribuição�
Nota-se que, neste caso, não teríamos uma distribui-
ção uniforme, visto que os nomes de departamento 
que iniciam com as letras ‘X’ ou ‘Y’ são em número 
menor do que os departamentos que iniciam com 
‘B’ ou ‘R’, por exemplo�
Por outro lado, suponha a utilização do valor do atri-
buto SALÁRIO e uma função hashing que distribua os 
valores em nove buckets da seguinte forma: salário 
entre R$ 10�000,00 e R$ 20�000,00 são mapeados 
para o bucket 1; salários entre R$ 20�001,00 e R$ 
30�000,00 são mapeados para o bucket 2 e assim su-
26
cessivamente até que os salários entre R$ 90�001,00 
e R$ 100�000,00 são mapeados para o bucket 9�
Os valores são distribuídos entre os bucketsunifor-
memente, mas observamos que há determinados 
valores de salário que ocorrem mais frequentemente� 
Assim, alguns buckets terão um maior número de 
registros que outros� Isso ocorre porque os valores 
de salário não ocorrem de modo aleatório, dessa 
maneira, a distribuição dos valores não é uniforme�
Outro problema com as funções hashing é quando 
elas mapeiam um determinado valor para um bucket 
sem espaço para o armazenamento� Nesse caso, 
ocorre o estouro do bucket, que acontece devido 
ao número insuficiente de buckets ou porque um 
bucket recebe um número maior de registros, mes-
mo havendo uma quantidade suficiente de buckets�
Esse motivo para o estouro denomina-se “distorção 
do bucket”, ocorrendo quando vários registros têm 
o mesmo valor-chave ou quando a função hashing 
não atende às propriedades descritas anteriormente�
Um possível tratamento para o estouro de buckets é 
considerar um bucket de estouro, no qual os registros 
que não podem ser alocados no bucket original são 
armazenados no bucket de estouro�
Esse procedimento é repetido quando um bucket 
de estouro também estiver cheio, daí outro bucket 
de estouro é oferecido pelo sistema� Os buckets ori-
ginais e de estouro são interligados por uma lista 
27
ligada, de modo que todos os registros possam ser 
encontrados�
Recuperação de falhas
Estudamos anteriormente que as transações podem 
concorrer pelo mesmo recurso ou, mais especifica-
mente, por um mesmo item de dado� A utilização de 
um mesmo item de dado por transações diferentes 
pode ocasionar inconsistência do banco de dados� 
Nesse sentido, verificamos que o SGBD deve imple-
mentar um controle de concorrência, de modo que as 
transações não utilizem um item de dado de maneira 
concorrente�
Os protocolos de controle de concorrência podem ser 
mais ou menos restritivos, a depender da estratégia 
adotada� Assim, os protocolos mais restritivos po-
dem gerar problemas como deadlock ou starvation�
Os protocolos menos restritivos, como o que conside-
ra a utilização das marcas de tempo, consideram as 
estratégias que previnem a inconsistência do banco 
de dados, sem provocar a ocorrência de deadlock 
ou starvation�
Apesar de podermos contar com diferentes aborda-
gens para o controle de concorrência das transações, 
ainda assim podemos nos deparar com problemas 
de consistência no banco de dados� Nesses casos, 
é necessário que o banco de dados seja recupera-
do e retorne a um estado de consistência anterior à 
execução das transações�
28
Nessa seção, aprofundaremos no processo de recu-
peração de um banco de dados� A recuperação é o 
processo de restauração do banco de dados a um 
estado de consistência, podendo ser aplicado em 
situações de falhas� As falhas podem ser resultantes 
de diferentes fatores, como falha nos discos, queda 
de energia elétrica ou problemas com o software� 
Outra possibilidade é a ocorrência de falhas oriundas 
das transações, por conta da violação de alguma 
restrição de integridade do banco de dados ou por 
impasses, por exemplo�
O processo de recuperação de falhas está intima-
mente ligado ao tipo de armazenamento dos dados� 
Como verificado anteriormente, podemos considerar 
três tipos de armazenamento: volátil, não volátil e 
estável�
O armazenamento estável considera a replicação dos 
dados em diferentes meios de armazenamento não 
voláteis� A implementação de sistemas RAID permite 
que os dados permaneçam íntegros mesmo com a 
ocorrência de perda de disco, porém, esse tipo de 
solução não é imune a desastres como incêndios 
ou inundações�
A utilização de backups pode representar uma solu-
ção para o armazenamento estável de dados� Os da-
dos podem ser armazenados, por exemplo, em fitas 
magnéticas e removidos, fisicamente, para um local 
diferente daquele em que o banco de dados está em 
operação� Nesse caso, temos ainda um problema 
de atualização dos dados, visto que não é possível 
29
realizar a gravação e a remoção física dos dados em 
backup para fora da instalação e, caso ocorra um 
problema, os dados em backup não refletirão o último 
estado do banco de dados, resultando em sua perda�
Um ponto crítico da recuperação de falhas é quando 
ocorrem em meio a uma atualização� As atualizações 
no banco de dados são registradas em um log (lista 
de eventos relevantes) que é mantido em um local 
diferente de onde o banco de dados está operando�
O log é uma lista de registros das atividades de atuali-
zação do banco de dados� Um registro típico em log é 
composto por um identificador da transação que es-
creveu um valor no banco de dados, um identificador 
para o item de dado que foi atualizado, comumente 
esse identificador indica um bloco de dados no disco 
e um deslocamento dentro desse bloco, e pelos valo-
res antigo e novo que descrevem, respectivamente, 
o valor do item de dado antes e depois da escrita�
Considera-se uma transação efetivada somente 
quando seu último registro de log foi transferido para 
armazenamento estável� Os registros em log captu-
ram todos os valores de um item de dado atualizado�
Assim, caso ocorra uma falha e uma transação pre-
cise ser refeita, o último valor em log do item de 
dado é utilizado (redo)� Por outro lado, caso o banco 
de dados precise ser revertido a um estado anterior 
(undo), os valores antigos para os itens de dados 
são utilizados, a depender do ponto para o qual se 
pretenda reverter o estado do banco de dados�
30
Com o objetivo de ilustrar a utilização do log para 
as transações redo e undo, considere o seguinte: 
um sistema bancário cuja transação T0 realiza uma 
transferência de R$ 500,00 da conta A para a conta 
B assim:
T0:
 read(A);
 A A - 50;
 write(A);
 read(B);
 B B + 50;
 write(B)�
Considere, ainda, uma transação T1 que realiza um 
saque de R$ 100,00 da conta C:
T1:
 read(C);
 C C - 100;
 write(C)�
Note que os registros de log referente às transações 
teriam o seguinte:
<T0 start>
<T0,A,1000,950>
<T0,B,2000,2050>
31
<T0 commit>
<T1 start>
<T1,C,700,600>
<T1 commit> 
Para o caso de haver alguma falha, com a utilização 
do log, o sistema pode recuperar um estado consis-
tente do banco de dados� Os procedimentos de recu-
peração redo e undo são aplicados nesse contexto� 
O procedimento redo(Ti) identifica todos os itens de 
dados atualizados pela transação Ti e os define com 
os novos valores disponíveis no log�
Nesse procedimento, a ordem em que as operações 
são refeitas é importante, sob pena de se obter um 
valor incorreto para o item de dado� Por outro lado, o 
procedimento undo(Ti) realiza a restauração de todos 
os valores antigos dos itens de dados que foram 
impactados pela transação Ti�
Desfazer uma transação não implica somente res-
taurar os valores antigos dos itens de dados impac-
tados, mas implica também registrar no log todas 
as informações sobre o processo de undo� Quando 
a operação terminar, insere-se no log um registro do 
tipo: <Ti abort>, indicando a finalização do processo.
Para o caso de haver falhas, a decisão sobre quais 
transações devem ser refeitas e quais devem ser 
desfeitas é tomada a partir da consulta ao log�
Uma transação precisa ser desfeita no caso de ha-
ver o registro de <T start> no log mas não haver o 
32
registro de <T commit> ou <T abort>� Por outro lado, 
se o registro de <T start> estiver presente no log e 
o registro de <T commit> ou o registro de <T abort> 
também estiverem presentes, então a transação de-
verá ser refeita�
Uma alternativa ao registro em log de todos os es-
tados de um item de dado, durante a execução de 
uma transação, é realizar a atualização tardiamente� 
Nesse caso, todas as operações de escrita para o 
item de dado são adiadas até que a transação finali-
ze� O log não precisa conter os valores antigos para 
o item de dado em questão�
As atualizações tardias ou adiadas permitem que, 
havendo falhas, não seja necessário a reversão de 
nenhuma atualização, visto que elas não foram efe-
tivadas em disco� Porém,a abordagem da atualiza-
ção imediata necessita, em caso de falhas, que as 
operações realizadas sejam revertidas�
Quando temos transações muito longas, é possível 
que haja algum problema de desempenho do siste-
ma, visto que o processo de gravação em disco, das 
diferentes alterações promovidas pela transação, é 
lento�
Para evitar ter muitas alterações em disco, após 
a finalização de uma transação longa, utiliza-se o 
conceito de pontos de checagem ou checkpoints� 
Um checkpoint é uma entrada intermediária para as 
atualizações parciais em disco�
33
A utilização de checkpoints prevê a suspensão tem-
porária da execução da transação, a gravação em 
disco dos blocos de dados alterados na memória, 
registrar o checkpoint no log e transferi-lo para o ar-
mazenamento estável e seguir com a execução da 
transação�
Assim, a periodicidade com a qual os checkpoints 
são realizados pode seguir de acordo com critérios 
de tempo ou pelo número de transações efetivadas�
34
CONSIDERAÇÕES FINAIS
Neste módulo, estudamos os tipos de dispositivos 
de armazenamento de dados e em quais característi-
cas eles se diferenciam� Há dispositivos que podem 
armazenar quantidades diferentes de dados, ou seja, 
dispositivos que são adequados para o armazena-
mento massivo de dados, como é o caso das fitas 
magnéticas; e outros que recebem apenas alguns 
blocos de dados, como é o caso do cache�
Pudemos verificar que é diferente a velocidade de 
acesso aos dispositivos de armazenamento� Na me-
mória principal, por exemplo, a velocidade com a qual 
as operações são realizadas é maior do que a velo-
cidade das operações sobre os discos magnéticos�
Os discos magnéticos podem ser organizados de 
modo a possibilitar maior desempenho das opera-
ções e/ou aumentar a segurança dos dados em caso 
de perda de discos� Os níveis de RAID descrevem 
diferentes organizações de discos, visando a oferecer 
maior desempenho ou segurança ou a combinação 
de ambos� 
O desempenho das operações é obtido por meio do 
espalhamento do bloco de dados nos discos, e a 
segurança é o resultado do espelhamento dos dis-
cos� Além disso, podemos contar com a obtenção de 
dados de paridade, a partir da utilização de um algo-
ritmo específico para esse fim. Os dados de paridade 
são utilizados para a recomposição de discos que 
35
foram perdidos e ficam distribuídos entre os discos 
que compõem o sistema de discos�
O desempenho das operações sobre os arquivos de 
dados é relativo ao tipo de indexação que se pode 
utilizar. Verificamos que as estruturas de índices 
disponibilizam os valores-chave ordenados e asso-
ciados ao endereço de armazenamento do registro 
no disco�
Esses índices podem se apresentar na forma densa, 
quando para cada registro no arquivo há um valor-
-chave correspondente na estrutura de índices; ou 
na forma esparsa, que é possibilitada pelo ordena-
mento sequencial dos registros nos arquivos a partir 
do respectivo valor-chave�
Na forma esparsa, a estrutura de índices conta com 
alguns valores-chave que cobrem o intervalo de va-
lores, e a pesquisa por um valor é feita em um de-
terminado bloco de dados, apontado pela estrutura 
de índices�
Quando os registros no arquivo não apresentam uma 
ordenação sequencial a partir de um valor-chave, 
podemos utilizar uma estrutura de índices secun-
dários� Nesse caso, os valores-chave se associam 
a uma estrutura de ponteiros para os endereços de 
disco dos registros, os quais poderão ser acessados 
diretamente�
As funções hashing são uma alternativa ao uso das 
estruturas de índices e têm a vantagem de não ne-
cessitarem de qualquer tipo de busca para o mapea-
36
mento de um valor-chave no seu respectivo endereço 
no disco� 
A obtenção de uma função hashing deve seguir com 
o intuito de haver uma distribuição uniforme entre os 
buckets e de não haver qualquer associação entre os 
valores-chave e algum tipo de ordenação�
Por fim, discutimos diferentes formas de recuperação 
de banco de dados a partir de diferentes tipos de 
falhas� As falhas podem ter sua origem em transa-
ções malsucedidas, que devem ser identificadas e 
desfeitas ou refeitas, a depender do caso�
Assim, a definição das operações para a recuperação 
é feita a partir de um registro de log, que é o registro 
das operações que atualizam, de alguma forma, o 
banco de dados�
37
Referências Bibliográficas 
& Consultadas
BARRETO, J� S� ; ZANIN, A� ; MORAIS, I � S� ; 
VETTORAZZO, A� S� Fundamentos de segurança da 
informação� Porto Alegre: SAGAH, 2018 [Biblioteca 
Virtual]�
ELMASRI, R�; NAVATHE, S� B� Sistema de banco de 
dados� 6� ed� São Paulo: Pearson Addison-Wesley, 
2011 [Biblioteca Virtual]�
HEUSER, C� A� Projeto de banco de dados� 6� ed� 
Porto Alegre: Bookman, 2009� [Biblioteca Virtual]�
MANNINO, M� V� Projeto, desenvolvimento de apli-
cações e administração de banco de dados� 3� ed� 
Porto Alegre: AMGH, 2014 [Biblioteca Virtual]�
MEDEIROS, L� F� Banco de dados: princípios e prática� 
Curitiba: InterSaberes, 2013 [Biblioteca Virtual]�
MOLINARO, L� F� R� Gestão de tecnologia da infor-
mação: governança de TI: arquitetura e alinhamento 
entre sistemas de informação e o negócio� Rio de 
Janeiro: LTC, 2011 [Minha Biblioteca]�
OIKAWA, M� K� Sistemas de Banco de Dados – Notas 
de Aula� Universidade Federal do ABC - UFABC, 2012�
RAMARKRISHNAN, R� Sistemas de gerenciamento 
de banco de dados� 3� ed� Porto Alegre: AMGH, 2001 
[Biblioteca Virtual]�
SILBERSCHATZ, A�; SUNDARSHAN, S�; KORTH, H� F� 
Sistema de Banco de Dados� Elsevier Brasil, 2016�
WANDERLEY, A� R� M� C� Gerenciamento de servido-
res� São Paulo: Érica, 2019 [Biblioteca Virtual]�
	_GoBack
	INTRODUÇÃO
	ARMAZENAMENTO, INDEXAÇÃO E GERENCIAMENTO DE TRANSIÇÃO
	MEIOS DE ARMAZENAMENTO FÍSICO
	INDEXAÇÃO E FUNÇÕES HASHING
	Recuperação de falhas
	CONSIDERAÇÕES FINAIS
	Referências Bibliográficas & Consultadas