ArvoreB

metodo split, iserção e remoção boolean busca(Tipo k, BTPage raiz)
{
int i = 0; if(raiz == null) return false; else if(raiz.filho[i] == null){ while(raiz.info[i] != null){ if(k == raiz.info[i]) return true; else i++;
}
return false;
}
else { while(raiz.info[i] != null){ if(k == raiz.info[i]) return true; else if(k < raiz.info[i]){ if(i==0 OU (K > raiz.info[i-1] E k < raiz.info[i])) return busca(k, raiz.filho[i]); else cont++;
}
else { if((i==0 E K < raiz.info[1]) OU (k > raiz.info[i] E k < raiz.info[i+1])) return busca(k, raiz.filho[i+1]); else i++;
}
}
}
return false;
}
BTPage buscaPage(Tipo k, BTPage raiz)
{
int i = 0; if(raiz.filho[i] == null){ return raiz;
}
else { while(raiz.info[i] != null){ if(k < raiz.info[i]){ if(i==0 OU (K > raiz.info[i-1] E k < raiz.info[i])) return buscaPage(k, raiz.filho[i]); else i++;

} else { if((i==0 E K < raiz.info[1]) OU (k > raiz.info[i] E k < raiz.info[i+1])) return buscaPage(k, raiz.filho[i+1]); else i++;
}
}
}
return null;
}
public void insere(Tipo k, BTPage raiz)
{
int i = 0; int tamanho = 0;
BTPage page; if(raiz == null){ raiz = new BTPage(); raiz.info[i] == k; raiz.filho[i] = raiz.filho[i+1] = null;
}
else if (busca(k, raiz)){ break; // já existe chave na arvore
}
else{ tamanho = buscaPage(k, raiz).tamanho(); page = buscaPage(k, raiz); if(tamanho < raiz.d*2) inserePosicao(k, page); else{ }
}
} public void inserePosicao(Tipo k, BTPage page){ int i = 0;
Tipo aux; while(raiz.info[i] != null){ if(k > raiz.info[i] E k < raiz.info[i+1]){ aux = raiz.info[i+1]; raiz.info[i+1] == k; raiz.info[i+2] == aux; raiz.filho[i+3] == null;
}
else if(k > raiz.info[i] E raiz.info[i+1] == null){

raiz.info[i+1] == k; raiz.filho[i+2] == null;
}
else i++; }
}

Inserçao(raiz, k, chavePromovida)
{
se(raiz == null)//se raiz nao aponta para nenhuma pagina
{
chavePromovida = k return(flag que indica que houve promoção de chave)
}
senao
{
carregue a página P apontada por raiz em memoria primária busque por k nessa página P posicao = página no qual k