Armazenamento e Estruturas de Índice

A página (bloco) é a unidade de I/O do SGBD: o controlador posiciona a cabeça, espera o setor e transfere um bloco inteiro para a memória. Seek, latência rotacional e transferência somam o tempo de cada acesso.

Tempo de acesso, densidade do índice e geometria B/B⁺ deste tópico — e índices em SQL, o modelo de custo em páginas e o I/O do laço aninhado nos tópicos seguintes — partem dessa unidade.

As páginas se agrupam em dois blocos. O primeiro mede o custo de trazer uma página: seek até a trilha, meia volta até o setor, transferência do bloco.

O segundo localiza o registro sem varrer o arquivo: desce uma estrutura compacta até o endereço do bloco, ou calcula o balde da chave.

T = seek + latência + transferência, com latência média ½ × 60/r e r em rpm, está em Discos e Acesso.

Por que a transferência é de uma página inteira está em Discos e Acesso. Quantas páginas a busca lê da raiz até o dado, e se o interno da B pode parar a busca, está em Estruturas de Índice.

Buffer, SSTF/LOOK e falha física versus lógica estão em Discos e Acesso.

A maior entrada ≤ k e a leitura daquele único bloco, com o arquivo ordenado pela chave, estão em Estruturas de Índice.

Percorrer [a, b] na lista de folhas da B⁺, cair no balde h(k) = k mod M, ou operar bit a bit num atributo de poucos valores, está em Estruturas de Índice.