tisbd_aguiar_2spp_2013.1

Prévia do material em texto

José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 1 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 1 
Técnicas de Implementação de 
Sistemas de Bancos de Dados 
José de Aguiar 
Moraes Filho, Dr.-Ing. 
Universidade de Fortaleza – UNIFOR 
Departamento de Computação 
jaguiar@unifor.br 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 2 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- TÓPICOS- 
1. Sistema de Bancos de Dados (SBD ou DBS) - Revisão 
2. Armazenamento de Dados 
3. Gerenciamento de Buffer (Memória) 
4. Indexação 
5. Processamento de Consultas 
6. Processamento de Transações 
7. Controle de Concorrência 
8. Recuperação e Logging 
9. Performance (Tuning) em BDs 
10.Distribuição de BDs - Conceitos 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 2 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 3 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Bibliografia Recomendada- 
1. Silberschatz, A., Korth, H., Sudarshan, S. “Sistemas de 
Banco de Dados”, 3ª Edição, Makron Books 
2. Garcia-Molina, H., Ullman, Jeffrey D., Widom, Jennifer. 
“Implementação de Sistemas de Bancos de Dados”. 
Editora Campus, 2001 
3. O’Neil, Patrick., O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. Second 
Edition, Morgan Kaufmann 
4. Elsmari, R., Navathe, Shamkant B. “Fundamentals of 
Database Systems”. Third Edition, Addison-Wesley. 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 4 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
1. Sistema de 
Bancos de 
Dados (SBD ou 
DBS) 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
1, 2, 3, 4, 7,16 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
1 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
1, 2, 3 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
2, 7, 8, 14 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 3 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 5 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
2. 
Armazenamento 
de Dados 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
10 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
2, 3 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
Nenhum capítulo 
específico para o 
tópico 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
5 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 6 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
3. 
Gerenciamento 
de Buffer 
(memória) 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
Nenhum capítulo 
específico para o 
tópico 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
6.8 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
Nenhum capítulo 
específico para o 
tópico 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
Nenhum capítulo 
específico para o 
tópico 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 4 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 7 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
4. Indexação Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
11 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
4, 5 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
8 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
6 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 8 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
5. 
Processamento 
de Consultas 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
12 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
6, 7 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
9 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
18 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 5 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 9 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
6. Processamento 
de Transações 
7. Controle de 
concorrência 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
13, 14 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
9, 10 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
10.1, 10.2, 10.3, 
10.4, 10.5 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
19, 20 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 10 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
8. Recuperação 
e Logging 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
15 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
8 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
10.6, 10.7, 10.8, 
10.9 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
21 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 6 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 11 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
9. Performance 
(Tuning) em BD 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
19.3, 19.4Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
Nenhum 
capítulo 
específico para 
o tópico 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
10.10 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
16 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 12 
Técnicas de Implementação de Sistemas de 
Banco de Dados 
- Guia Bibliográfico por Tópicos - 
Tópico Livro Capítulo/Seção 
10. Distribuição 
em BD – 
Conceitos 
Silberschatz, A., Korth, H., Sudarshan, S. 
“Sistemas de Banco de Dados”, 3ª Edição, 
Makron Books 
18 
Garcia-Molina, H., Ullman, Jeffrey D., 
Widom, Jennifer. “Implementação de 
Sistemas de Bancos de Dados”. Editora 
Campus, 2001 
10.4 
O’Neil, Patrick, O’Neil, Elizabeth. “Database: 
Principles, Programming and Performance”. 
Second Edition, Morgan Kaufmann 
11 
Elsmari, R., Navathe, Shamkant B. 
“Fundamentals of Database Systems”. Third 
Edition, Addison-Wesley 
24 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 7 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 13 
1. Sistemas de Bancos de Dados 
 - Conceitos Básicos - 
q Sistema de Bancos de Dados (SBD ou DBS) 
Banco de Dados (BD ou DB) 
+Conjunto de dados relacionados 
Sistema Gerenciador de Bancos de Dados 
 (SGBD ou DBMS) 
+Componente de software 
Acesso 
Controle de Concorrência 
Recuperação 
Armazenamento 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 14 
1. Sistemas de Bancos de Dados 
 - Arquitetura de Três Camadas - 
Esquema 
Externo 1 
Esquema 
Externo 2 
Esquema 
Externo n 
Esquema Conceitual 
Esquema Interno 
(Banco de Dados armazenado) 
DBMS 
Camada 
Conceitual 
Camada 
Interna 
Camada 
Externa 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 8 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 15 
1. Sistemas de Bancos de Dados 
 - Arquitetura - 
Gerenciador 
de Transações 
Mecanismo 
de Consultas 
Gerenciador 
de Buffer 
Gerenciador 
de Arquivo 
Compilador 
DML 
Pre-compilador 
DML 
Sistema de 
Armazenamento 
Processador 
de Consultas 
DBMS 
DBS 
Código Objeto 
aplicativos 
Arquivos 
de dados 
índices Catálogo 
DB 
Esquema Consulta Programa Aplicativo 
DBA Usuário experiente Programadores 
Interpretador 
DDL 
Fragmentos 
de código 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 16 
1. Sistemas de Banco de Dados 
 - Componentes da Arquitetura - 
*SGBD 
Processador de Consultas + Sistema de Armazenamento 
Processador de Consultas 
 
Compilador DML 
Analisa sintaticamente e semanticamente comandos DML 
expressos em uma linguagem de consulta (ex. SQL) 
Traduz estes comandos para uma das formas de representação 
interna de consultas (ex. álgebra relacional) 
Pré-Compilador DML 
Traduz comandos DML em chamadas a procedimentos (rotinas) 
na linguagem hospedeira 
Interpretador DDL 
Interpreta comandos DDL e os armazena no catálogo 
Tabelas contendo meta-dados 
Descrição do banco de dados Esquema 
Mecanismo de Consultas 
Responsável pela otimização e geração de planos de execução 
de consultas 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 9 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 17 
*SGBD (cont.) 
Sistema de Armazenamento 
Gerenciador de Transações 
Controle de concorrência 
Recuperação do banco de dados após falhas 
Gerenciador de Buffer 
Responsável para recuperar objetos em disco e carregá-los na 
memória principal em forma de páginas 
SGBD possui uma área de buffer em memória principal 
Mapeamento: Bloco 
 (disco) (buffer do SGBD) 
Definição da política de alocação do buffer 
MRU, LRU, FIFO, etc 
1. Sistemas de Banco de Dados 
 - Componentes da Arquitetura - 
Página 
Gerenciador de Arquivo (File System) 
Responsável pelo armazenamento físico em disco 
Gerencia a alocação de espaço em disco 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 18 
1. Sistemas de Banco de Dados 
 - Componentes da Arquitetura - 
*BD 
Arquivos de dados + Índices + Catálogo + 
 Fragmentos de código 
Arquivos de dados 
Armazena os dados 
Índices 
Estruturas de índices para os arquivos de dados 
Índices ordenados 
Árvores B+ 
Arquivos grade 
Árvores R 
Árvores quadrantes 
Índices não ordenados 
Indice hash 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 10 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 19 
1. Sistemas de Banco de Dados 
 - Componentes da Arquitetura - 
*BD (cont.) 
Catálogo 
Armazena esquema do banco de dados (meta-dados) 
Nomes das tabelas 
Atributos de cada tabela 
Definição de índice para uma tabela, etc… 
Armazena informações estatísticas 
Exemplo 
Cardinalidade de uma tabela 
Utilizadas na otimização de consultas 
Fragmentos de código 
Stored procedures 
Triggers 
Métodos 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 20 
1. Sistemas de Bancos de Dados 
 - Classificação - 
q Modelo de Dados 
Sistema de Banco de Dados Relacional 
Modelo Relacional 
Tipo primitivo de dados 
Relação (tabela) 
Conjunto de tuplas (linhas) 
Conjunto de Operadores 
Álgebra e Cálculo Relacional 
Restrições de integridade 
Integridade de chave primária, integridade referencial, etc. 
Sistema de Banco de Dados Orientado a Objeto 
Modelo orientado a objeto 
Objeto, herança, composição, métodos 
Tipos primitivos 
Objeto, conjunto, lista, string, integer, real 
Sistema de Banco de Dados Objeto-Relacional 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 11 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 21 
1. Sistemas de Bancos de Dados 
 - Classificação - 
q Arquitetura 
Centralizada 
Sistema de Banco de Dados Centralizados 
Os componentes do SBD residem no mesmo host 
Distribuída 
Critérios 
Função 
Controle 
Dados 
Sistema de Banco de Dados Cliente-Servidor 
Distribuição de funções do SGBD entre clientes e servidor 
Sistema de Banco de Dados Paralelos 
Distribuição do controle de funções do DBMS entre diversos 
sistemas computacionais 
Sistema de Banco de Dados Distribuídos 
Distribuição de dados através de diversos SBDs homogêneos 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 22 
1. Sistemas de Bancos de Dados 
 - Classificação - 
q Arquitetura (cont.) 
Distribuída (cont.) 
Sistema de Banco de Dados Heterogêneos 
Distribuição de dados através de SBDs heterogêneos e 
 autônomos 
Sistema de banco de dados múltiplos (MDBS) 
Sistema de banco de dados federados (FDBS) 
Arquitetura de Mediadores 
Sistema de Banco de Dados Móvel 
Distribuição de funções e dados do SGBD entre clientes e 
servidor em ambientes de computação móvel 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 12 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 23 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Sistema computacional 
Variedade de dispositivos para armazenar instruções e 
dados necessários a sua operação 
Sistema de memória 
q Sistema de memória 
Dispositivos de armazenamentoAlgoritmos 
implementados por software ou por hardware 
Objetivo dos componentes de um sistema de memória 
Controlar e gerencia a informação armazenada 
 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 24 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Tipos de Meios Físicos de Armazenamento 
Memória Interna do Processador 
Compreende pequeno conjunto de registradores de alta 
velocidade 
Utilizada como memória de trabalho para armazenamento 
temporário de instruções e dados 
Memória Cache 
Dispositivo de memória que funciona como dispositivo de 
armazenamento temporário e intermediário entre 
registradores e memória principal 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 13 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 25 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Tipos de Meios Físicos de Armazenamento (cont.) 
Memória Principal (Memória Primária) 
Armazenamento de programas e dados que estão sendo 
operados pelo sistema computacional 
Memória relativamente rápida e cara 
Normalmente apresenta capacidade muito limitada 
+Computadores (64 bits) com 14 GB de memória principal 
Tecnologia de bancos de dados em memória principal 
Endereços facilmente e rapidamente acessados pelo 
conjunto de instruções da CPU 
Denominada de memória RAM (Random Access Memory) 
Memória volátil 
Conteúdo é perdido em caso de queda de energia ou crash do 
sistema 
 - Dados não persistentes (memória volátil) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 26 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Tipos de Meios Físicos de Armazenamento (cont.) 
Memória Secundária 
Dispositivo de memória com maior capacidade de 
armazenamento que a memória principal 
Memória Não-Volátil 
Utilizada para armazenar de forma persistente 
Programas aplicativos 
Grandes arquivos de dados e 
Bancos de dados 
Acesso mais lento 
Pode ser utilizada como memória de overflow quando a 
capacidade da memória principal é excedida 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 14 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 27 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Tipos de Meios Físicos de Armazenamento (cont.) 
Memória Terciária 
Classe composta por dispositivos mais lentos 
Fita magnéticas e discos óticos 
Utilizada para armazenar um grande volume de dados 
back-up 
q Características dos Meios Físicos de Armazenamento 
Custo 
Definido por c=CT/CA dollars/bit, onde 
 CT representa o custo total do sistema de memória 
completo cuja capacidade de armazenamento é dado por 
CA 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 28 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Características dos Meios Físicos de Armazenamento 
Tempo de Acesso (TA) 
Representa o tempo médio necessário para ler uma 
quantidade fixa de informação da memória 
Por exemplo, uma palavra (word) 
Utilizado como medida de performance para dispositivos 
de memória 
Taxa de acesso (bA) de um dispositivo de memória é 
dada por 1/TA 
Representa a quantidade de palavras lidas por segundo 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 15 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 29 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Características dos Meios Físicos de Armazenamento 
Modo de Acesso (cont.) 
(i) Random-access memory (RAM) 
Dispositivos de memória cujas posições podem ser acessadas 
em qualquer ordem 
O tempo de acesso é independente da localização a ser 
acessada 
Existe um mecanismo de acesso para cada posição de memória 
 
Seletor de cabeçote de Leitura/Escrita 
Cabeçote de Leitura/Escrita 
Posições de memória 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 30 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Características dos Meios Físicos de Armazenamento 
Modo de Acesso (cont.) 
(ii) Serial-access memory (memória de acesso seqüencial) 
Dispositivos cujas posições só podem ser acessadas em 
seqüências pré-definidas 
Um único mecanismo de acesso é compartilhado por várias 
posições de memória 
Alterabilidade 
Característica que representa a capacidade de permitir a 
alteração do conteúdo de memória 
(i) Read-only memory (ROM) 
(ii) Read-write memory 
 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 16 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 31 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Características dos Meios Físicos de Armazenamento 
Persistência de Armazenamento 
Os processos físicos envolvidos no armazenamento são 
algumas vezes instáveis 
Pode provocar a perda da informação armazenada após um certo 
período de tempo 
Propriedades de memória de que podem destruir 
informação 
(i) Destructive read-out (leitura destrutiva) 
Em alguns dispositivos de armazenamento, o método de 
leitura destrói a informação armazenada 
Dispositivos DRO 
 - Têm como contrapartida os dispositivos NDRO 
Em dispositivos DRO, cada operação de leitura precisa ser 
seguida de uma operação de escrita 
 - Para restaurar o estado original da memória 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 32 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Características dos Meios Físicos de Armazenamento 
Persistência de Armazenamento (cont.) 
Propriedades de memória de que podem destruir 
informação (cont.) 
(ii) Memória dinâmica 
Certos dispositivos de armazenamento, apresentam a 
seguinte característica: 
 Um “1” armazenado torna-se um “0” devido a algum 
processo de decaímento 
Por exemplo: 
 Muitos dispositivos armazenam um “1” através de uma 
carga elétrica em um capacitor 
 Com o passar do tempo, a carga armazenada tende a se 
 descarregar (decair) 
Tais dispositivos necessitam de um processo de recarga, 
denominado de refreshing 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 17 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 33 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Características dos Meios Físicos de Armazenamento 
Persistência de Armazenamento (cont.) 
Propriedades de memória de que podem destruir 
informação (cont.) 
(iii) Volatilidade 
Fenômeno através do qual certos dispositivos de memória 
têm seu conteúdo destruído por falhas elétricas ou crash de 
sistema 
Memória volátil 
 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 34 
2. Armazenamento de Dados 
- Meios Físicos de Armazenamento - 
q Hierarquia de meios físicos de armazenamento 
Banco de dados relacional 
No nível conceitual 
Conjunto de tabelas 
No nível físico 
Dados armazenados em dispositivo de armazenamento não 
volátil 
Acessar dados 
Acessar diferentes dispositivos (níveis) de armazenamento 
 
Memória 
Secundária 
Memória 
Terciária 
Memória 
Principal 
Cache 
CPU 
 (Registradores) 
Custo 
Tempo de 
acesso 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 18 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 35 
2. Armazenamento de Dados 
- Armazenamento em Disco - 
q Discos Magnéticos 
Em cada superfície de um disco, existem várias trilhas 
que são arranjadasde forma concêntrica 
Existem de 20 a 1500 trilhas por disco 
Cada trilha está subdividida em setores 
Um setor representa a menor unidade de informação 
que pode ser lida ou escrita no disco 
Setores podem variar de 32 bytes até 4096 bytes 
Tipicamente, um setor possui 512 bytes. 
Existem de 4 a 32 setores por trilha 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 36 
2. Armazenamento de Dados 
- Armazenamento em Disco - 
q Discos Magnéticos (cont.) 
Trilha t 
Cilindro c 
Cabeçote de leitura e escrita 
Suporte do braço 
 braço 
Motor de Rotação 
Disco d 
Setor 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 19 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 37 
2. Armazenamento de Dados 
- Armazenamento em Disco - 
q Discos Magnéticos (cont.) 
Acessando uma unidade de disco 
 o motor de rotação faz o disco girar a uma velocidade 
constante (60, 90 ou 120 rps) 
Cada superfície do disco possui um cabeçote de 
leitura/escrita 
O cabeçote está montado em um dispositivo chamado 
braço do disco 
O braço movimenta-se transversalmente pelo disco para 
acessar as diferentes trilhas do disco. 
Uma unidade de disco possui geralmente um conjunto 
de discos 
Os cabeçotes de leitura/escrita de todas as superfícies de 
discos de uma unidade movimentam-se em conjunto 
(simultaneamente) e são acionadas pelo suporte do braço. 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 38 
2. Armazenamento de Dados 
- Armazenamento em Disco - 
q Discos Magnéticos (cont.) 
Acessando uma unidade de disco (cont.) 
Suponha que os discos de uma unidade A apresentem 
1000 trilhas cada um. Em um instante de tempo t: 
Todos os cabeçotes acessam a mesma posição nos diferentes 
discos 
Os cabeçotes acessam trilhas de diferentes discos ou 
superfícies, mas que apresentam mesmo diâmetro 
Cilindro 
o conjunto de trilhas pertencentes a diferentes superfícies e 
discos de uma uma mesma unidade, mas que apresentem a 
mesma posição relativa 
Por exemplo, o conjunto de todas as trilhas 450 dos discos da 
unidade A compõe um cilindro 
Para otimizar o acesso a disco, dados de um mesmo 
arquivo são armazenados em cilindros. 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 20 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 39 
2. Armazenamento de Dados 
- Armazenamento em Disco - 
q Discos Magnéticos (cont.) 
Medidas de Desempenho de Discos 
Tempo de procura (TP) 
Tempo gasto para posicionar o braço sobre a trilha correta 
Tempo médio de latência rotacional (TL) 
Tempo médio necessário para que o setor desejado passe pelo 
cabeçote de leitura/escrita. Definido como 1/2 do tempo de uma 
rotação completa. Se r é a taxa de rotações/segundo, então 
T=(2r)-1 
Taxa de transferência de dados (TTr) 
Taxa na qual os dados são lidos ou armazenados por segundo. 
Se N é a capacidade das trilhas em palavras, então 
 TTr= rN 
Tempo de transferência de dados de um setor 
Tempo (segundos) necessário para transferir dados de um setor. 
Se n é o tamanho (palavras) de um setor, então 
 TT= n(rN)
-1 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 40 
2. Armazenamento de Dados 
- Armazenamento em Disco - 
q Discos Magnéticos (cont.) 
Medidas de Desempenho de Discos 
Tempo de acesso a um setor (TA) 
Tempo gasto desde um pedido de leitura/escrita até o fim da 
transferência de dados 
A fórmula para determinar o tempo de acesso de um disco é 
dada por: 
TA=TP + TL + TT 
TA= TP + (2r)
-1 + n(rN)-1 
Acesso a disco é extremamente lento 
 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 21 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 41 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Redundância de dados para aumentar a confiabilidade 
MTTF (Mean Time to Failure) 
Seja TF o tempo médio de falha de um disco 
O tempo médio de falha em um disco de um conjunto de N 
discos é dado por TF / N. 
Se considerarmos TF =10
5 horas e N=100 
Tempo médio de perda de dados é 1000 horas ou 41,66 dias 
Pode-se aumentar esse tempo médio através da 
redundância de dados 
Armazenar informação redundante 
Informação normalmente não necessária 
Utilizada para reconstruir informação perdida durante 
uma falha de disco 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 42 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Redundância de Dados para aumentar a confiabilidade 
(cont.) 
Espelhamento de discos (replicação) 
Caso um disco falhe 
dados podem ser acessados no disco espelho 
Perda total de dados 
só ocorre se o segundo disco falhar antes que o primeiro disco 
tenha sido recuperado 
Tempo médio de perda de dados depende do: 
Tempo médio de falhas (TF ) e do 
Tempo necessário para substituir o disco que falhou mais o 
tempo para recuperar os dados perdidos (TR) 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 22 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 43 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Redundância de Dados para aumentar a confiabilidade 
(cont.) 
Espelhamento de discos (cont) 
Considerando-se que as falhas em dois discos físicos de 
um mesmo disco lógico sejam independentes e que a 
probabilidade de falha não varie ao longo tempo, o 
tempo médio de perda de dados com espelhamento é 
dado por 
 (TF)
2 / 2TR 
Exemplo 
Se considerarmos TF =10
5 horas e TR =10 horas, então 
 o tempo médio de perda de dados é de 5 x 108 horas ou 57 x 103 
anos. 
Existem sistemas de discos espelhado no mercado que 
garantem um tempo médio de perda de dados da ordem de 
106 horas (110 anos) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 44 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Acesso paralelo a discos para aumentar desempenho 
Em um conjunto de N discos 
Acesso paralelo a diversos discos através da 
distribuição paralela de dados nos múltiplos discos 
Aumentar a taxa de transferência de dados 
Estratégias para distribuição de dados 
Distribuição paralela de bits 
Distribuir os bits de um byte em diferentes discos 
Exemplo 
 (a) Em um conjunto de oito discos, cada bit i é armazenado 
no disco i 
 (b) Em um conjunto de quatro discos, como deverá ser 
realizada a distribuição de bits de um byte ? 
Os bits i e 4+i de um byte são armazenados no disco i Os bits i e 4+i de um byte são armazenados no disco i 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 23 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 45 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Acesso paralelo a discos para aumentar desempenho 
Estratégias para distribuição de dados (cont.) 
Distribuição paralela de blocos 
Distribuir os blocos de um arquivo em diferentes discos 
Política de alocação de blocos de um arquivo 
O bloco i deve ser alocado no disco (i mod n) + 1 
 n representa o número de discos disponíveis 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 46 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Mecanismo de RAID 
Espelhamento 
Garante confiabilidade (+) 
Tecnologia extremamente cara (-) 
Distribuição paralela de dados 
Altas taxas de transferência de dados (+) 
Não garante confiabilidade (-) 
Técnicas RAID 
Combinar diferentes graus de distribuição de dados e de 
redundância 
Redundância a baixo custo 
Níveis de RAID 
Striping 
Concatenar múltiplas unidades de disco em uma únicaunidade de armazenamento lógica 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 24 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 47 
Disco 1 Disco 2 Disco 3 Disco 4 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Níveis de RAID 
RAID nível 0 
Organização de discos com distribuição paralela 
Baseada em blocos 
Blocos de um arquivo são armazenados em diversos discos 
Não apresenta redundância 
Exemplo 
RAID 0 com quatro discos 
Distribuição paralela não-redundante 
Striping 
Arquivo A 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 48 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 1 
Organização de discos com distribuição paralela 
Baseada em blocos 
Redundância implementada através de replicação 
Exemplo 
RAID 1 com quatro discos de dados e quatro discos 
para replicação 
Distribuição paralela com replicação 
D1 D2 D3 D4 R1 R2 R3 R4 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 25 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 49 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 2 
Organização de discos com distribuição paralela 
Baseada em bytes 
Redundância implementada através de bits de correção 
Bits de correção podem ser implementados através de bit 
de paridade 
Mecanismo de bit de paridade 
Para cada byte armazenado existe um bit de paridade 
0 
Se o número de bits no byte com valor 1 é par (paridade 0) 
1 
Se o número de bits no byte com valor 1 é ímpar (paridade 1) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 50 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 2 
Se o bit de paridade de um byte for danificado 
Não coincidirá com a paridade calculada 
Um erro em um byte pode ser detectado e corrigido 
Estratégia do RAID nível 2 é 
Implementar o código de correção de erros 
Dois ou mais bits adicionais 
Implementar distribuição paralela de bytes 
Bits em diferentes discos 
Organização de código de correção de erros 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 26 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 51 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 2 (cont) 
P1 P2 P3 
Para cada 4 discos de dados, 3 discos para armazenar os bits 
de paridade 
a0 b0 c0 d0 a1 b1 c1 d1 a2 b2 c2 d2 a3 b3 c3 d3 
a0 a1 a2 a3 
Unidades de 
Transferência 
b0 b1 b2 b3 c0 c1 c2 c3 d0 d1 d2 d3 
a b c d 
Setor 0 
Disco D1 
Setor 0 
Disco D2 
Setor 0 
Disco D3 
Setor 0 
Disco D4 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 52 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 2 (cont) 
Exemplo 1 
RAID 2 com oito discos de dados 
Distribuição paralela de bytes 
Cada bit i de um byte é armazenado no disco i 
Redundância 
Os bits de correção são armazenados em outros discos 
Caso um disco falhe, como recuperar seus dados ? 
Exemplo 2 
RAID 2 com quatro discos de dados 
Distribuição paralela de bytes 
Os bits i e 4+i de um byte são armazenados no disco i 
Redundância 
Os bits de correção são armazenados em outros discos 
Caso um disco falhe, como recuperar seus dados ? 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 27 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 53 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 2 (cont) 
Exemplo 2 
Byte n 
0 1 1 1 1 1 1 1 Paridade=1 
Disco 1 
Caso disco 1 falhe 
Pela paridade, sabe-se que os bits perdidos do byte n são 0 e 1 
Como determinar a posição correta dos bits no byte??? 
São necessários bits adicionais 
Para recuperar a posição correta dos bits perdidos 
Diferentes estratégias para definir bits adicionais 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 54 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 3 
No RAID nível 2 
Um bit de paridade para cada byte 
Bits adicionais 
Controladoras armazenam bits de paridade por setor de 
disco 
Um único bit de paridade por byte 
poder ser utilizado para correção de erros 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 28 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 55 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 3 (cont) 
RAID nível 3 ou mecanismo de paridade de bits 
entrelaçados 
Organização de discos com distribuição paralela 
Baseada em bytes 
Bits de um mesmo byte em diferentes discos 
Caso mais de um bit de um mesmo byte s armazenados em 
um mesmo disco i 
 Armazenados em diferentes setores de i 
Redundância implementada através de bits de paridade 
 Armazenar um bit de correção (bit de paridade) para cada byte 
Utilizar bits de paridade de setores 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 56 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 3 (cont) 
Redundância implementada através de bits de paridade 
 Armazenar um bit de correção (bit de paridade) para cada byte 
Utilizar bits de paridade de setores 
 
 
Exemplo 2 
RAID 2 com quatro discos de dados 
Distribuição paralela de bytes 
Os bits i e 4+i de um byte são armazenados em setores 
diferentes do disco i 
Redundância 
Os bits de correção são armazenados em outros discos 
Caso um disco falhe, como recuperar seus dados ? 
D1 D2 D3 D4 P1 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 29 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 57 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 3 (cont) 
Exemplo 2 
Byte n 
0 1 1 1 1 1 1 1 Paridade=1 
 
 
 
Caso disco 1 falhe 
Pela paridade, sabe-se que os bits perdidos do byte n são 0 e 1 
Pela paridade dos setores 
Pode-se descobrir a posição correta dos bits no byte n 
Vantagens 
Recuperação eficiente 
Mais barato 
Necessita de apenas um disco adicional para vetores de discos 
não muito grandes 
Setor 1 do 
Disco 1 
Setor 2 do 
Disco 1 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 58 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 4 
Não apresenta distribuição 
Blocos são armazenados da mesma forma que em 
discos comum 
Redundância implementada através de blocos de 
paridade 
Um disco armazena todos os blocos de paridade 
Bloco i do disco redundante armazena bit de paridade dos 
blocos i de todos discos de dados 
D1 D2 D3 D4 P1 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 30 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 59 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 4 
 
RAID nível 4 ou mecanismo de paridade de blocos 
entrelaçados 
Caso um disco falhe 
Bloco de paridade mais os blocos dos discos em 
funcionamento são utilizados para recuperar os blocos do 
disco que falhou 
Recuperação por blocos de um disco 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 60 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 5 
Apresenta distribuição de dados 
Redundância implementada através de blocos de paridade 
 Um bloco de paridade para cada bloco armazenado nos 
discos de dados 
 
 
 
RAID nível 5 ou mecanismo de paridade distribuída de 
blocos entrelaçados 
Distribuição 
Blocos de dados e de paridade são distribuídos nos N+1 discos 
No RAID nível4, os dados são armazenados nos N discos e o 
bloco de paridade é armazenado em um disco separado 
D1+P D2+P D3+P D4+P D5+P 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 31 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 61 
2. Armazenamento de Dados 
- Técnicas RAID - 
RAID nível 5 
Exemplo 
Para cada bloco i em um conjunto de 5 discos 
 Bloco de paridade de i é armazenado no disco (i mod 5) +1 
 Os i-ésimos blocos dos outros quatro discos armazenam os 
dados do bloco I 
O bloco de paridade para um bloco i 
Armazenado em um disco diferente dos discos que armazenam i 
Caso um disco falhe 
Bloco de paridade mais os blocos dos discos em funcionamento 
são utilizados para recuperar os blocos do disco que falhou 
RAID nível 6 
Semelhante ao nível 
Armazena informações adicionais para recuperar dados 
no caso de falha em mais de um disco 
Garante maior grau de confiabilidade que o nível 5 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 62 
2. Armazenamento de Dados 
- Técnicas RAID - 
q Escolha do nível de RAID 
Vários fatores devem ser considerados 
Tempo e complexidade da atividade de reconstrução de 
discos após falhas 
Aplicações que requerem um fornecimento contínuo de dados 
Fator importante para determinar tempo médio de falha 
Tipo de aplicações que acessam discos do mecanismo RAID 
RAID nível 0 
Aplicações de alto desempenho 
Discos bastante confiáveis 
RAID nível 1 
Aplicações que requerem um fornecimento contínuo de dados 
RAID níveis 3 e 5 
Aplicações que requerem um fornecimento contínuo de dados e 
armazenam grandes volumes de dados 
Quantidade de discos 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 32 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 63 
2. Armazenamento de Dados 
- Memória Terciária - 
q Sistemas de banco de dados com grande volume de dados 
Limitação de capacidade de armazenamento de memória 
secundária 
Parte dos dados são armazenados em memória terciária 
Exemplo 
Bancos de dados que armazenam fotos da terra tiradas por 
satélites 
Fotos enviada periodicamente (a cada 2 minutos) 
Mídias para armazenamento terciário 
Discos óticos 
Fita Magnética 
Sistema de memória virtual 
 Hierarquia com três níveis de memória 
Memória Principal Memória secundária Memória 
 terciária 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 64 
2. Armazenamento de Dados 
- Memória Terciária - 
q Fitas Magnéticas 
Meio de armazenamento 
Fita de plástico flexível revestida de material magnético 
Acesso seqüencial 
Utilizada como memória secundária 
Informação armazenada em 9 trilhas longitudinais 
Trilha 1 0 
Trilha 2 1 
Trilha 3 1 
Trilha 4 0 
Trilha 5 1 
Trilha 6 1 
Trilha 7 1 
Trilha 8 0 
Trilha 9 1 
O cabeçote de leitura/escrita de uma unidade de fita magnética acessa as 
9 trilhas simultaneamente 
Palavra de memória (fita magnética) de 9 bits 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 33 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 65 
2. Armazenamento de Dados 
- Memória Terciária - 
q Fitas Magnéticas (cont.) 
O bit da trilha 9 
Bit de paridade 
Cálculo do bit de paridade 
Considere a palavra 
b8,b7,b6,b5,b4,b3,b2,b1,b0 
b8 representa o bit de paridade 
b7 o bit mais significativo do byte 
Tabela Verdade para  
0  0 = 0; 0  1 = 1; 1  0 = 1; 1  1 = 0 
Calcule o bit de paridade para o byte 10101101 
b8=b7b6b5b4b3b2b1b0 b8=b7b6b5b4b3b2b1b0 
:exclusive-or para bits (0-F, 1-V) :exclusive-or para bits (0-F, 1-V) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 66 
2. Armazenamento de Dados 
- Memória Terciária - 
q Fitas Magnéticas (cont.) 
Quando uma unidade de fita está em uso, o acionador 
movimenta a fita em movimento não contínuo 
Lê um bloco e pára 
Os dados armazenados em uma fita estão organizados em 
blocos 
Gaps são inseridos entre os blocos de informação 
Espaços vazios entre os blocos 
Porque são necessários estes gaps??? 
Medidas de desempenho 
Taxa de transferência de dados de uma unidade de fita 
(TTr) 
Velocidade do acionador de fita (V) 
Densidade da fita (d) 
TTr= dV 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 34 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 67 
2. Armazenamento de Dados 
- Memória Terciária - 
q Fitas Magnéticas (cont.) 
Jukeboxes de fitas 
Grande número de fitas 
Alguns acionadores nos quais as fitas podem ser 
montadas 
Montagem feitas por braços mecânicos 
Armazenar volumes de dados da ordem de 12 Terabytes 
(1012 bytes) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 68 
2. Armazenamento de Dados 
- Memória Terciária - 
q Discos Óticos 
Características físicas semelhantes a discos magnéticos 
Informação binária é armazenada em trilhas concêntricas 
Na forma de pontos de sombra ou de reflexão 
Largura de 0.6 m 
Disco em uso 
O motor de rotação faz o disco girar a uma velocidade constante 
Os dados são acessados da seguinte forma 
Cabeçote de leitura/escrita 
Mecanismo de laser 
Movimenta-se transversalmente pelo disco 
Um raio laser percorre a superfície do disco 
O raio é refletido diferentemente por pontos de sombra ou de 
reflexão 
Meio barato e com boa capacidade armazenamento 
Geralmente, são do tipo WORM 
Write Once, Read Many 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 35 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 69 
2. Armazenamento de Dados 
- Memória Terciária - 
q Discos Óticos (cont.) 
Menores velocidades rotacionais e maiores tempos de 
procura do que discos magnéticos 
Maiores tempos de latência 
DVD 
4,7 a 17 giga 
 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 70 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
q Armazenamento eficiente e seguro de dados 
Capacidade de armazenar grandes volumes de dados 
Os dados devem continuar armazenados após o término da 
aplicação que os acessou 
Persistência dos dados 
q Solução para o problema de armazenamento 
Armazenar dados em unidades 
Arquivos 
q Operações sobre arquivos 
Leitura 
Escrita 
q Dados armazenados em arquivos 
Persistentes 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 36 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 71 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
q Gerenciador (Sistema) de arquivo (file system) 
Componente do SGBD (SO) responsável pelo gerenciamento 
de arquivos 
q Arquivos 
Abstração que fornece uma maneira de agrupar dados 
logicamente relacionados 
Armazenar esse conjunto de dados relacionados em 
disco, para depois garantir o acesso a esse mesmo 
conjunto 
Torna transparente para usuários detalhes como: 
Como e onde os dados estão armazenados 
Como acessar discos 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 72 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
q Arquivos (cont.) 
Não estruturado 
Seqüência de bytes 
Qualquer semântica deve ser definida a nível de 
programa 
UNIX 
Estrutura de registro 
Seqüência de registros 
Unidade para operações de leitura e escrita 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementaçãode Sistemas de 
Banco de Dados 37 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 73 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
q Armazenamento de Arquivos 
Identificar em quais blocos um arquivo está armazenado 
Política de alocação de arquivos em disco 
1. Alocação Contínua 
Arquivo armazenado em blocos contíguos em disco 
Exemplo: Considere um disco com blocos de 2K 
Um arquivo de 60K será armazenado em 30 blocos consecutivos 
Vantagens 
Facilidade em localizar todos os dados em disco 
É suficiente guardar apenas o número do primeiro bloco do 
disco que contem o arquivo 
Acessar seqüencialmente esses blocos 
Performance 
Desvantagens 
Como reservar espaço em disco para armazenar um arquivo 
Arquivos crescem dinamicamente 
Fragmentação 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 74 
q Armazenamento de Arquivos (cont.) 
 2. Alocação com Lista Encadeada 
Cada arquivo é alocado como uma lista encadeada de 
blocos de disco 
Cada elemento da lista representa um bloco 
A primeira palavra de um bloco contem um ponteiro para o 
próximo bloco do mesmo arquivo 
 
 
 
 
 
10 7 11 2 5 3 15 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
Bloco do 
Arquivo 
1 
Bloco do 
Arquivo 
2 
Bloco do 
Arquivo 
3 
Bloco do 
Arquivo 
4 
Bloco de 
disco 
Bloco do 
Arquivo 
1 
Bloco do 
Arquivo 
2 
Bloco do 
Arquivo 
3 
Arq1 Arq2 
0 0 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 38 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 75 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
2. Alocação com Lista Encadeada (cont.) 
Vantagens 
Facilidade em localizar todos os dados em disco 
É suficiente guardar apenas o número do primeiro bloco do disco que 
contem o arquivo 
Acessar seqüencialmente esses blocos 
Não ocorre fragmentação 
Desvantagens 
Tamanho do bloco não é mais uma potência de 2 
Ponteiro ocupa alguns bytes 
Acesso randômico 
Lento 
Identificação de blocos vazios (não utilizados) 
3. Alocação com Lista Encadeada Utilizando Índices 
Alocação com lista encadeada 
Ponteiros armazenados no próprio bloco 
Armazenar os ponteiros em uma tabela na memória 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 76 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
3. Alocação com Lista Encadeada Utilizando Índices 
Arq1 ocupa os blocos 10, 7, 11, 2 
Arq2 ocupa os blocos 5, 3, 15 
 
 
 
 
 
 
 
 
 
 
0 
1 
2 0 
3 15 
4 
5 3 
6 
7 11 
8 
9 
10 7 
11 2 
12 
13 
14 
15 0 
Blocos 
de disco 
Ponteiro para 
próximo bloco 
Início Arq1 
Início Arq2 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 39 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 77 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
3. Alocação com Lista Encadeada Utilizando Índices 
Vantagens 
Facilidade em localizar todos os dados em disco 
É suficiente guardar apenas o número do primeiro bloco do disco que 
contem o arquivo 
Acessar seqüencialmente esses blocos 
Não ocorre fragmentação 
Todo o bloco é ocupado só com dados 
Acesso randômico mais eficiente 
Desvantagens 
A tabela precisa ser carregada em memória 
Disco com 2,5x105 blocos de 4K (1G) 
Tabela com 250000 entradas 
Cada entrada ocupa em média 4 bytes 
A tabela ocuparia quase 1M 
Identificação de blocos vazios (não utilizados) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 78 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
4. Alocação utlizando I-nodes 
Cada arquivo está associado a uma tabela denominada 
de index-node (i-node) 
Conteúdo de um i-node 
Atributos do arquivo 
Endereços dos blocos de disco, onde estão armazenados os 
blocos do arquivo 
Tabela i-node deve ser carregada na memória 
Tabela de tamanho fixo 
Como armazenar os blocos de disco ocupados por 
grandes arquivos no i-nodes 
single indirect block 
double indirect block 
triple indirect block 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 40 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 79 
2. Armazenamento de Dados 
- Gerenciamento de Arquivos - 
4. Alocação utlizando I-nodes 
Single indirect 
 block 
double indirect 
 block 
triple indirect 
 block 
Atributos 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 80 
3. Gerenciamento de Buffer 
- Sistema de Memória Virtual - 
q Conceituação 
Sistema de armazenamento hierárquico, com no mínimo 
dois níveis de memória 
A maioria dos sistemas de memória virtual implementam 
uma hierarquia de dois níveis, compreendendo: 
1. Uma memória principal M1 
Capacidade S1 e 
Custo C1 
2. Uma memória secundária M2 
Capacidade S2 e 
Custo C2 
+S2 >> S1 ; C1 > C2 ; TA1 < TA2 
 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 41 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 81 
3. Gerenciamento de Buffer 
- Sistema de Memória Virtual em SGBDs - 
q Conceituação 
SGBDs possuem mecanismo de memória proprietários 
Implementado pelo Gerenciador de Buffer 
Objetivo 
Dar a ilusão ao usuário do SGBD que existe uma única 
memória principal com grande capacidade 
Permitir um compartilhamento eficiente do espaço de 
memória entre diferentes usuários 
Reentrância 
Apresentar altas taxas de acesso a baixo custo de 
armazenamento por bit 
Otimizar acesso ao banco de dados 
Mecanismo de Buffer 
1. Região de buffer M1 (em memória principal) 
2. Região de memória secundária M2 (banco de dados) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 82 
3. Gerenciamento de Buffer 
- Gerenciador de Buffer - 
q Funcionamento 
Funciona com base no seguinte princípio 
Toda informação armazenada em M1, em qualquer 
instante, também está armazenada em M2 
O inverso não é verdade 
O SGBD comunica-se diretamente com M1 e M1 
comunica-se com M2 
Caso a informação desejada pelo SGBD não se encontre 
em M1 
 Gerenciador de buffer realiza uma realocação de 
armazenamento apropriada de M1 
Carregar de M2 para M1 a informação requerida 
Gerenciador de buffer eficiente 
Informação desejada deve ser encontrada em M1 com 
uma taxa de freqüência ótima 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 42 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 83 
3. Gerenciamento de Buffer 
- Gerenciador de Buffer - 
q Performance 
Medida com base na taxa de acerto (H) 
Definida pela probabilidade que os endereços gerados 
pelo SGBD refiram-se a informação já alocada em M1 
A taxa de acerto é determinada experimentalmente como 
descrito a seguir: 
Um conjunto de programas (consultas) é executado 
Os números de referências de endereços satisfeitas 
por M1 e M2 são registrados 
Números denotados por N1 e N2 
A taxa de acerto é calculada aplicando-se a fórmula 
H= N1 / (N1+N2) 
A taxa de acerto ótima deve tender a 1 
Porque? 
A taxa de não acerto é definida por 1-H 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 84 
3. Gerenciamento de Buffer 
- Gerenciador de Buffer - 
q Performance 
Considere TA1 e TA2 o tempo de acesso de M1 e M2 
O tempo médio para o SGBDacessar um dado no 
sistema de memória é dado por: 
TA = H.TA1 + (1-H).TA2 (1) 
Caso um dado não é encontrada em M1 
Uma página do banco de dados (em disco) contendo a 
palavra é transferida para M1 
Tempo de transferência da página (TB) 
TA2 = TB + TA1 (2) 
Substituindo (2) em (1), temos: 
TA = TA1 + (1-H).TB 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 43 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 85 
3. Gerenciamento de Buffer 
- Gerenciador de Buffer - 
q Performance 
A razão do tempo de acesso de um sistema de memória 
virtual com dois níveis é definida como: 
r= TA2 / TA1 
 A eficiência de acesso (e) de um sistema de memória 
virtual é determinada pela equação: 
e= 1 / [r+(1-r).H] 
 
O objetivo é obter valores para e próximos a 1. 
É necessário que H seja próximo a 1 
Porquê ? 
 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 86 
3. Gerenciamento de Buffer 
- Gerenciador de Buffer - 
q Mecanismo de Paginação (Swapping ) 
A operação mais importante em qualquer sistema de 
memória virtual 
Troca de blocos de informação entre os níveis de 
memória 
Paginação 
Essa troca ocorre de acordo com a demanda de 
processamento 
Demanda de Paginação 
Propriedade que indica quando uma operação de 
paginação deve ocorrer 
Política de Alocação 
Método utilizado para determinar o local (endereço) da 
memória principal, onde uma nova página deve ser 
carregada 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 44 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 87 
3. Gerenciamento de Buffer 
- Gerenciador de Buffer - 
q Mecanismo de Paginação (cont.) 
Tipos de Alocação 
Alocação estática 
Cada página de dados está ligado a uma região fixa da 
memória principal 
Alocação dinâmica 
A região de memória principal na qual uma página K é 
carregado é variável 
Alocação dinâmica não preemptiva 
Página a ser carregada só pode ser alocado em um 
espaço vazio da memória principal 
Alocação dinâmica preemptiva 
Página a ser carregada pode ser alocado em um espaço 
ocupado por outra página K 
A página K deve ser re-alocada em um outro endereço ou 
removida totalmente da memória 
 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 88 
3. Gerenciamento de Buffer 
- Gerenciador de Buffer - 
q Mecanismo de Paginação (cont.) 
Políticas de alocação dinâmica preemptiva 
FIFO (First-In First-Out) 
A página a ser carregada é alocada na região de buffer 
ocupada pela página carregada menos recentemente no buffer 
LRU (Least Recently Used) 
A página a ser carregada é alocada na região de buffer 
ocupada pela página acessada mais remotamente (tempo) 
MRU (Most Recently Used) 
 A página a ser carregada é alocada na região de buffer 
ocupada pela página acessada mais recentemente 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 45 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 89 
4. Indexação 
- Conceitos Básicos - 
q Índices 
Cada estrutura de índice está associada a uma chave de 
busca 
Chave de busca representa um atributo de tuplas 
Fornecem um caminho através do qual os dados podem ser 
localizados e acessados de forma mais eficiente 
Reduzem o overhead de busca a um pequeno conjunto de 
tuplas 
q Classificação de índices 
Índice ordenado 
Índice hash 
Índice Primário 
Índice Secundário 
Denso 
Esparso 
+ 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 90 
q Índice Primário (Clustering Indices) 
Definido sobre uma chave de busca que determina 
 a ordem física dos registros 
4. Indexação 
- Tipos de Índices - 
matr nome sal 
1 
2 
3 
4 
7 
9 
10 
 
André 
Bárbara 
Ines 
Lucas 
Sofia 
Caio 
Lara 1 
4 
10 
 
Esparso 
Denso 
1 
2 
3 
4 
7 
9 
10 
 
Uma entrada na estrutura 
 de índice para cada valor 
da chave de busca 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 46 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 91 
4. Indexação 
- Tipos de Índices - 
q Índice Secundário 
Chave de busca não determina a ordem física das tuplas 
Índices determinam uma ordem (lógica) das tuplas 
Exemplo 
Chave de busca definida sobre atributo chave 
matr nome sal 
7 
10 
9 
4 
1 
3 
2 
 
Sofia 
Lara 
Caio 
Lucas 
André 
Inês 
Bárbara 
Denso 
1 
2 
3 
4 
7 
9 
10 
 
Uma entrada na estrutura 
 de índice para cada valor 
da chave de busca 
4Índice secundário é sempre denso 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 92 
4. Indexação 
- Tipos de Índices - 
q Índice Secundário (cont.) 
Chave de busca definida sobre atributo não chave 
Nível extra de indireção 
matr nome sal 
7 
10 
9 
4 
1 
3 
2 
 Sofia 1000 
 Lara 900 
 Caio 500 
 Lucas 900 
 André 3000 
 Inês 5000 
 Bárbara 3000 
500 
900 
1000 
3000 
5000 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 47 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 93 
4. Indexação 
- Tipos de Índices - 
q Índice Hash 
Estrutura de índice organizada como um arquivo hash 
Hashing Estático 
Bucket representa uma unidade armazenamento de 
um conjunto de registros 
Função de Hash 
 h: K B, onde 
K representa o conjunto de todas as chaves de busca e 
B é o conjunto do endereço de todos os buckets 
+Eficiente para consultas do tipo exact match 
+Utilizado para implementar select com igualdade 
sobre atributos chaves 
Select A1,A2,A3, ..., An 
 From s 
where Ak = c 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 94 
4. Indexação 
- Tipos de Índices - 
q Índice Hash (cont.) 
Hashing Estático (cont.) 
h(matr)= matr / 3 
1 
2 
3 
4 
7 
9 
10 
11 
André 
Bárbara 
Ines 
Lucas 
Sofia 
Caio 
Lara 
Yasmim 
matr nome sal 
1 
2 
3 
4 
7 
 
9 
10 
11 
 
Bucket 0 
Bucket 1 
Bucket 2 
Bucket 3 
Bucket overflow 
Estimativa de custo (sem overflow) 
 2 acessos a disco 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 48 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 95 
4. Indexação 
- Tipos de Índices - 
q Índice Hash (cont.) 
Hashing Estático (cont.) 
Fatores geradores de overflow de buckets 
Número insuficiente de buckets 
Altas taxas de colisão 
Número ideal de buckets nB é dado por 
 nB > nR/fR, onde 
 + nR representa o número de tuplas e 
 + fR representa o número de tuplas por bucket 
Desequilíbrio 
Poucos buckets armazenam mais tuplas que os outros buckets 
 + Overflow de buckets, mesmo com buckets com espaço 
Várias tuplas com mesmo valor de chave de busca 
Função hash não garante uma distribuição uniforme 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 96 
4. Indexação 
- Tipos de Índices - 
q Índice Hash (cont.) 
Hashing Estático (cont.) 
Função de hash é escolhida no momento em que a estrutura de índice 
está sendo criado 
Função de hash 
Mapea um valor de chave de busca em um endereço pertencente ao 
conjunto B 
B muito grande 
Desperdício de espaço em disco 
B muito pequeno 
Overflow de bucketsAlteração da função de hash 
Reorganização 
Situação ideal 
A medida que a estrutura de índices cresce, devem ser alterados 
dinamicamente 
Número de buckets 
Função de hash 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 49 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 97 
4. Indexação 
- Tipos de Índices - 
q Índice Hash (cont.) 
Hashing Dinâmico 
Permitir a modificação dinâmica da função de hash e do número de 
buckets 
Adequar a função ao crescimento da quantidade de entradas de índices 
Resultado de funções de hash sobre a chave de busca 
Valores inteiros e não negativos 
Representados através de números binários 
Alocação de registros por buckets 
Construída com base na representação binária do resultado da função de 
hash 
String de bits 
Valor de hash de uma tupla 
Alocação da tupla 
Feita com base nos bits iniciais de seus valores de hash 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 98 
4. Indexação 
- Tipos de Índices - 
q Índice Hash (cont.) 
Hashing Dinâmico (cont) 
Funcionamento 
Inicialmente 
Estrutura de índice com apenas um bucket (tamanho fixo) 
Quando o primeiro bucket estiver cheio e um novo registro é 
inserido 
Um novo bucket é criado 
Registros são distribuídos nos dois buckets com base no valor 
do primeiro bit (mais à esquerda) de seu valor de hash 
Registros com bit inicial igual a 0 são armazenados no bucket 
com endereço 0 
Registros com bit inicial igual a 1 são armazenados no bucket 
com endereço 1 
Uma árvore binária é construída 
Estrutura de diretório 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 50 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 99 
4. Indexação 
- Tipos de Índices - 
q Índice Hash (cont.) 
Hashing Dinâmico (cont) 
0 
1 
overflow overflow 
0 
1 
0 
1 
Bucket 
overflow 
Bucket 
overflow 
Bucket para registros com valor 
de hash começando por 0 
Bucket para registros com valor 
de hash começando por 1 
Bucket para registros com valor 
de hash começando por 10 
Bucket para registros com valor 
de hash começando por 11 
Bucket para registros com valor 
de hash começando por 0 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 100 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (B-trees) 
Árvore balanceada 
Todos os caminhos a partir da raiz até os nós folhas 
apresentam o mesmo comprimento 
Altura da árvore é constante 
Regras de formação de uma B-Tree de ordem n 
Cada nó interno de uma B-tree é da forma 
<P1,<K1,PD1>,P2,<K2,PD2>, ... ,Pm-1,<Km-1,PDm-1>,Pm> 
m  n 
Cada Pi representa um ponteiro para uma subárvore 
(B-tree) 
ponteiro de árvore 
Cada PDi representa um ponteiro para a página que 
contém uma tupla r cuja chave de busca é igual a Ki 
Ponteiro de dados 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 51 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 101 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Regras de formação de uma B-Tree de ordem n (cont.) 
-Dentro de um nó: K1< K2< ... < Km-1 
Para todo valor X de chave de busca na subárvore 
apontada por Pi, temos 
Ki-1< X < Ki para 1<i<m, X < Ki para i=1 e Ki-1< X para i=m 
Cada nó possui no máximo n ponteiros de árvore 
Cada nó possui no mínimo n/2 ponteiros de árvore 
(n-1)/2 valores de chave de busca 
 Todos os nós exceto a raiz 
A raiz possui no mínimo dois ponteiros de árvore 
Um nó com m ponteiros de árvore possui m-1 valores de 
chave de busca e m-1 ponteiros de dados 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 102 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Regras de formação de uma B-Tree de ordem n (cont.) 
Todos os nós folhas possuem a altura e apresentam a 
mesma estrutura que os nós internos 
 Os ponteiros de árvore têm valor null 
 
Quantidade máxima de valores de chave de busca que 
podem ser armazenados na raiz de uma B-tree de ordem p 
 p-1 p-1 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 52 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 103 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Estrutura de uma árvore B 
(Nó) 
Pi P1 
... ..
. 
K1 PD1 
(X<K1) 
X 
P2 Ki-1 PDi-1 Ki PDi 
(Ki-1<Y<Ki) 
Y 
Pm Km-1 PDm-1 
Ponteiro 
de dados 
(V > Km-1) 
V 
K1 PD1 
Ponteiro 
de dados 
... ... Ki-1 PDi-1 Ki PDi Km-1 PDm-1 (Folha) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 104 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Construção uma árvore B de ordem n 
árvore_B ( ) 
Árvore é inicializada com apenas um nó (nó raiz) - altura 0; 
Enquanto existir entradas para serem inseridas 
 inserção_nova_entrada(L, chave-busca, PD); 
Fim; 
Função inserção_nova_entrada(L, chave_busca, PD) 
Se o nó L possui n-1 entradas <chave_busca, PD> /* overflow */ 
 Um nó L´ de mesma altura é criado 
 Se Pai(L)   /* nó L possui um nó pai */ 
 /* Valor médio M da chave de busca é inserido no nó pai de L */ 
 inserção_nova_entrada(Pai(L), M, PD) 
 Caso contrário 
 criar um nó pai R para L e L´ /* L era raiz da árvore */ 
 inserção_nova_entrada(R, M, PD) 
 /* No nó R, P1 aponta para L e PT2 aponta para L’ */ 
 Valores de chave de busca X < M continuam alocados no nó L; 
 Valores de chave de busca Y > M são alocados no nó L´; 
Senão 
 inserir entrada <chave_busca, PD) em L 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 53 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 105 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Construa árvore B de ordem 3 com a seguinte ordem de inserção de 
valores de chave de busca 
1,3,5,6,7,8,9,12 
PD 1 PD 3 
PD 1 
PD 3 
PD 5 6 PD 
PD 1 
PD 3 PD 6 
PD 5 PD 7 
Incluir 5 - overflow 
Incluir 7 - overflow 
PD 8 
Incluir 9 - overflow 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 106 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Construa árvore B de ordem 3 (cont.) 
PD 1 
PD 6 
PD 5 PD 7 PD 9 PD 12 
PD 3 PD 8 
- Pior caso: nós com capacidade mínima. 
- Deve ser considerado para cálculo da altura 
- Pior caso: nós com capacidade mínima. 
- Deve ser considerado para cálculo da altura 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 54 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 107 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Altura 
Quanto maior o número de ponteiros de árvore por nó 
Menor a altura da árvore 
Árvore larga 
Altura deve ser calculada no pior caso para árvores B 
Cada nó apresenta sua capacidade mínima 
Existe uma relação entre altura h e número de nós M (na altura h) em 
uma árvore B de ordem n 
h=0; M=1 
h=1; M=n/2 (quantidade mínima de nós apontados em h) 
h=2; M=(n/2)2 
h=3; M=(n/2)3 . . . 
 h=k; M=(n/2)k  logn/2 M = logn/2 (n/2)
k 
 h= logn/2 M 
 Quanto maior a ordem, menor a altura da árvore B 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 108 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Remoção de entradas em um nó 
 
Função remoção_entrada(L,chave_busca) 
Se L é nó raiz 
 remoção_entrada_raiz(L, chave_busca) 
Senão 
 remoção_entrada_nó(L, chave_busca) 
Fim; 
 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 55 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 109 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
Remoção de entradas em um nó 
Função remoção_entrada_raiz(L, chave_busca) 
Se L possui apenas uma entrada <chave,PD> /* L possui 2 filhos (ponteiros de árvore) */ 
 S=filho(L) /* retorna filho de L que possui no mínimo (n/2) entradas <chave,PD> */ 
 Se S   
 Se S=filho_esquerda(L) 
 /* Inserir na raiz maior valor de chave de busca em S - considerar toda subárvore */ 
 remoção_entrada(S, K) 
 inserção_nova_entrada(L, K, PD) 
 Senão 
 /* Inserir na raiz menor valor de chave de busca em S */ 
 remoção_entrada(S, K) 
 inserção_nova_entrada(L, K, PD) 
 Senão 
 /* fundir os nós filhos de L em um nó R que será a nova raiz da árvore */ 
Senão 
remover entrada <Ki, PDi> de L 
Se Pi  NULL ou Pi+1  NULL 
atualizar_chave busca(L,i) 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 110 
PD V PL' PL 
4. Indexação 
- Estruturas de Índices Ordenados - 
Função remoção_entrada_nó(L, chave_busca) 
remover entrada <Ki, PDi> de L; 
Se nó L possui ((n- 1)/2) entradas <chave de busca, PD> /* underflow */ 
 L’= irmão (L); /* retorna irmão (esq/ dir) de L que possui (n/2) entradas <chave,PD> */ 
 Se L’   
inserção_nova_entrada(L, V, PD); /*inserir V (valor entre L e L’ no pai(L)) em L */ 
Se L’=irmão_esq(L) /* Substituir V no nó pai por maior valor de chave de busca em L’ */ 
 remoção_entrada(L’, K); inserção_nova_entrada(Pai(L), K, PD) 
Senão /* Substituir V’ no nó pai por menor valor de chave de busca em L’ */ 
 remoção_entrada(L’, F); inserção_nova_entrada(Pai(L), F, PD); 
 Senão /* Irmãos de L contêm exatamente n/2 - 1 entradas <chave, PD> */ 
Se L’=irmão_esq(L) 
 inserção_nova_entrada(L’, V, PD); /*inserir V em L’ */ 
 remoção_entrada(Pai(L), V, PD); /*remove V de Pai(L) */ 
 inserção_nova_entrada(Pai(L), K, PD); /*Substituir V em Pai(L) por maior valor K em L*/ 
 Transferir entradas de L para L’; remover nó L; 
Senão 
 inserção_nova_entrada(L, V, PD) /*inserir V em L’ */ 
 remoção_entrada(Pai(L), V, PD); /*remove V de Pai(L) */ 
 inserção_nova_entrada(Pai(L), K, PD) /* Substituir V no nó pai por maior chave 
em L’ */ 
 Transferir entradas de L’ para L; remover nó L’; 
Senão 
Se PTi  NULL ou PTi+1  NULL 
atualizar_chave busca(L,i); 
Pai(L) 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 56 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 111 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Árvores B (cont.) 
 
Função atualiza_chave_busca(L, i) 
S=filho(L, PTI) /*retorna verdade se filho de L apontado por PTI tem (n/2) entradas 
 <chave,PD> */ 
S´= filho(L, PTi+1) 
 Se (S) 
 /* Inserir na raiz maior valor de chave de busca da subárvore apontada PTI*/ 
 remoção_entrada(L´, K) 
 inserção_nova_entrada(L, K, PD) 
 Senão 
 Se (S´) 
 /* Inserir na raiz menor valor de chave da subárvore apontada PTi+1 */ 
 remoção_entrada(L´, K) 
 inserção_nova_entrada(L, K, PD) 
 Senão 
 /* fundir os nós filhos de L em um nó S que será a nova raiz da árvore */ 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 112 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Estrutura de Índices Ordenados (cont.) 
Árvores B+ (B+-trees) 
Árvore balanceada 
Altura da árvore é constante 
Regras de formação de uma B+-Tree de ordem n 
Cada nó interno de uma B+-tree é da forma 
 <PT1, K1, PT2, K2, ... , PTm-1, Km-1, PTm> 
m  n 
Em um nó não folha, 
Cada PTi representa um ponteiro para uma subárvore (B
+-
tree) 
Em um nó folha 
Cada PTi representa um ponteiro para a página que contém 
uma tupla r cuja chave de busca é igual a Ki 
PTm representa um ponteiro para a próxima folha 
 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 57 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 113 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Estrutura de Índices Ordenados (cont.) 
Árvores B+ (cont) 
Regras de formação de uma B+-Tree de ordem n (cont.) 
-Dentro de um nó: K1< K2< ... < Km-1 
Para todo valor X de chave de busca na subárvore 
apontada por PTi, nós temos 
Ki-1< X  Ki para 1<i<m, X  Ki para i=1 e Ki-1< X para i=m 
Cada nó não folha 
Possui no máximo n ponteiros de árvore 
Um nó com m ponteiros de árvore possui m-1 valores de 
chave de busca 
Possui no mínimo n/2 ponteiros de árvore 
 (n-1)/2 valores de chave de busca 
 Todos os nós exceto a raiz 
 A raiz possui no mínimo dois ponteiros de árvore 
 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 114 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Estrutura de Índices Ordenados (cont.) 
Árvores B+ (cont.) 
Regras de formação de uma B+-Tree de ordem n (cont.) 
 Cada nó folha 
Possui no máximo n-1 ponteiros de dados e um ponteiro para 
próxima folha 
Uma folha com m ponteiros de árvore possui m-1 valores de 
chave de busca 
Possui no mínimo n/2 ponteiros de dados 
 (n-1)/2 valores de chave de busca 
 Todos os nós exceto a raiz 
 A raiz possui no mínimo dois ponteiros de árvore 
Todos nós folhas apresentam mesma altura 
 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 58 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 115 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Estrutura de Índices Ordenados (cont.) 
Árvores B+ (cont.) 
Uma entrada <chave de busca, ponteiro para página> só 
é inserida nos nós folhas 
Cada nó não folha contém apenas valores de chave de 
busca e ponteiros de árvore 
Não contém ponteiros de dados 
Podem conter mais ponteiros de árvore que árvores B 
A ordem de árvores B+ é maior que a de árvores B 
Para um mesmo tamanho de página T 
Um nó em uma árvore B+ pode ter mais filhos que um nó em 
uma árvore B 
Qual uma importante conclusão que se pode tirar do fato acima?? 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 116 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Estrutura de Índices Ordenados (cont.) 
Árvores B+ (cont.) 
Estrutura de uma árvore B+ 
Ki Ki-1 Pi P1 K1 ... Km-1 Pm ... (Nó) 
Pi+1 Pi Ki K1 ... P1 Pm ... 
(Folhas) 
Próxima folha 
(XK1) 
X 
(Ki-1<YKi) 
Y 
(V > Km-1) 
V 
Km-1 Pm-1 Km-2 
José de Aguiar Moraes Filho 07.02.2012 
Técnicas de Implementação de Sistemas de 
Banco de Dados 59 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 117 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Estrutura de Índices Ordenados (cont.) 
Árvores B+ (cont.) 
Algoritmo de inserção 
semelhante ao algoritmo para árvores B 
Quando há overflow ou underflow 
Só são transferidos para os nós não folhas valores de chave 
de busca 
Não são transferidos ponteiros de dados 
Cálculo da ordem n de uma árvore B+ 
Parâmetros 
Tamanho de página T bytes 
Tamanho da chave de busca C bytes 
Tamanho do ponteiro de árvore P bytes 
(nP) + ((n-1) C)  T 
 
 José de Aguiar Moraes Filho Técnicas de Implementação de SBDs 118 
4. Indexação 
- Estruturas de Índices Ordenados - 
q Estrutura de Índices Ordenados (cont.) 
Construa uma