Instituto de Ciências Matemáticas e de Computação
Departamento de Computação e Estatística
SCE183 - Algoritmos e Estruturas de Dados 2
Profs. Resp: Graça Pimentel e Maria Cristina
B-Trees & Cia (III)

1. Algoritmos de Pesquisa e Inserção

Dada a declaração de uma página, em C: 
struct BTPAGE {
	        short KEYCOUNT;
                char  KEY[MAXKEYS];
	        short CHILD[MAXKEYS+1];
               } PAGE;

Um exemplo da parte de uma B-tree com de ordem 4 é dado na figura abaixo. Nessa figura é mostrado um nó interno e 4 nós folha.
É explicitado os RRN de cada página, o RRN 0 é um número válido de página, e os ponteiros das folhas apontam para nil (que pode ser -1).

2. Busca

Abaixo é apresentado o algoritmo da função search, a qual busca por uma chave dada. Essa função pesquisa recursivamente através da árvore. Cada evocação de search busca o nó de número RNN.

Se a chave for encontrada, sua identificação volta em Found_RRN (página) e Found_Pos (qual das posições do array). Se a chave não for encontrada, a busca vai até encontrar um nil das folhas, retornando Not Found. 

FUNTION search(RRN,KEY,FOUND_RRN,FOUND_POS)
  if RRN==NIL then /* condição de parada */
    return NOT FOUND
  else
    read page RRN into PAGE
    look through PAGE for KEY, setting POS equal to the position where KEY occurs or should occur.
    if KEY was found then
      FOUND_RRN := RRN   /* RRN atual contem a chave */
      FOUND_POS := POS
      return FOUND
    else  
      return(search(PAGE_CHIELD(POS),KEY,FOUND_RRN,FOUND_POS)
    endif
  endif
end FUNTION

3. Inserção e Divisão

Os algoritmos Insertion e Splitting começam a pesquisa no nó raiz e vão em direção à raiz depois de encontrar a posição de inserção ao nível das folhas, os processos de inserção, divisão e promoção trabalham de baixo para cima, do nível das folhas até a raiz.

O algoritmo insert insere KEY. A tentativa de inserção tem início na página CURRENT_RRN. Se essa página não é uma folha, a função se chama recursivamente até encontrar KEY ou chegar a uma folha. Se KEY for encontrada a função vai retornar erro e terminar (recursivamente). Senão a inserção vai começar na página folha.

Havendo espaço em PAGE a chave é inserida, caso contrário PAGE é dividida chamando-se a funcao split. Uma divisão faz com que PROMO_KEY seja a chave do meio, e PROMO_R_CHILD identifique a nova página criada: com esses dois valores, a inserção continua, recursivamente, no nível de cima da árvore.
A necessidade de nova inserção, no nível superior, é indicada com o retorno de PROMOTING.

4. A função split

Para tratar o overflow causado pela inserção de I_KEy e I_RRN na página PAGE, a função cria uma nova página NEWPAGE, distribui as chaves igualmente entre as chaves, e determina qual chave a ser promovida ao nível superior na árvore.
A chave a ser promovida é colocada em PROM_KEY, e o RRN da nova chave é retornado em PROMO_R_CHILD.
Construção de Árvores
Definição e Propriedades de B-Trees