AED_III_Arvore B e Arvore B

Prévia do material em texto

Comparac¸̃ao entre a Arvore B+ tradicional e a Arvore B
Distribuı́da
1Instituto de Ciências Exatas e Informática
Pontificia Universidade Católica de Minas Gerais (PUC-MG)
Belo Horizonte – MG – Brasil
Artigo: A Practical Scalable Distributed B-Tree[1]
1. Descric¸̃ao e comparac¸̃ao
A arvore B distribuı́da é uma arvore que pode ter seus n ós espalhados por vários
servidores de uma rede. Nela cada n ó tem uma flag indicando se o n ó é uma folha, um
campo indicando sua altura na arvore, e o par chave e valor śo existe nas folhas. Diferente
da arvore B+, na implementac¸̃ao da arvore distribúıda temos métodos que interagem com
os servidores, na alocac¸̃ao de um n ó por exemplo temos o m étodo chooseServer() que
retorna um servidor para que o n ó seja alocado. Cada servidor tem um vetor de bits que
indica se um nó está livre, e cada cliente tem uma copia desse vetor, apos obter o retorno
do método chooseServer() é selecionada uma entrada que esteja livre no vetor de bits do
servidor e é adicionado o novo valor e em seguida a flag da posic¸ão ocupada é marcada
para indicar que a posic¸̃ao (no vetor de bits) n ão está mais livre, s ó depois o novo valor
é adicionado no conjunto v álido de valores. Além disso existe também um método para
migrar um nó de um servidor1 para um servidor2, e um para migrar um conjunto de nós
entre servidores.
References
[1] AGUILERA , M. K., GOLAB , W., AND SHAH , M. A. A practical scalable distributed
b-tree. Proc. VLDB Endow. 1, 1 (Aug. 2008), 598–609.
	Página 1
	Página 2