Indexação estruturada

Cap. 6 Indexação Estruturada em Árvore
“If I had eight hours to chop down a tree, I’d spent sharpening my ax.” -- Abraham Lincoln

Abel J.P. Gomes

Bibliography: 1. R. Ramakrishnan and J. Gehrke. “Database Management Systems”. Addison-Wesley, 2003 (cap.10).

1

1. Objectivos


 

  

Intuitivamente, o que está por detrás dos índices estruturados em árvore? Porque é que são adequados para selecções (SELECT) por gama de valores? Como é que faz pesquisa (SELECT), inserção (INSERT) e eliminação (DELETE) de registos num índice ISAM? Como é que faz pesquisa (SELECT), inserção (INSERT) e eliminação (DELETE) de registos num índice em árvore B+? Qual é o impacto de valores duplicados da chave na im plementação de índices? O que é a compressão de índices, e porque é que são importantes? O que é que acontece aos idntificadores de registos quando índices dinâmicos são actualizados? Como é que isto afecta os índices conglomerados (clustered indexes)? 2

2. Ficheiros,Páginas e Registos: uma revisão


A abstracção de dados armazenados é a de “ficheiros” de “registos”.
 

Registos (records) residem em páginas (pages) Physical Record ID (RID) =



Dados de tamanho variável requerem estruturas mais sofisticadas para registos e páginas. (porquê?)
 

registos: offset array no header páginas: Slotted pages com internal offsets & área de espaço livre

 

Muitas vezes é melhor ser “permissivo” relativamente a questões como gestão de espaço livre, ordenação exacta, etc. (porquê?) Ficheiros podem ser não-ordenados (heap), ordenados, ou algum tipo de ficheiro ordenado (i.e., “conglomerado”) por uma chave de pesquisa (search key).




Os compromissos são entre o custo de actualização/manutenção e a velocidade dos acessos via chave de pesquisa. Ficheiros podem ser conglomerados (sorted) no máximo de uma maneira.



Índices podem ser usados para tornar mais rápidos muitos tipos de acessos (i.e., “percursos de acesso”)

3

2.