Um algoritmo para paginaçao de árvores binárias de pesquisa utilizando empacotamento unidimensional

Abstract

Resumo: As árvores binárias são estruturas de dados utilizadas tradicionalmente para a realização de pesquisa de forma eficiente sobre um conjunto de dados. Uma árvore pode atingir grandes dimensões, bem como ser utilizada para armazenar dados em memória secundária ou distribuídos pelos nodos de uma rede de computadores. Nestes casos, é necessário definir uma estratégia eficiente para o acesso aos dados da árvore, que são organizados em páginas. Uma página é utilizada para a transferência de dados em blocos da memória secundária para a primária, além do acesso remoto em redes de computadores, por intermédio de pacotes que possuem tamanho máximo pré-fíxado. Este trabalho apresenta um algoritmo para a paginação de árvores binárias de pesquisa aplicável quando o conjunto de informações é estático, as freqüências de acesso não são conhecidas e o armazenamento é remoto ou secundário. O algoritmo visa reduzir o tempo de pesquisa aos dados armazenados na árvore binária em termos do número de páginas visitadas e do aumento da taxa de preenchimento das páginas utilizadas. Uma versão alternativa do algoritmo que visa reduzir a distância internodal nas páginas é apresentada. Observou-se que o algoritmo proposto constrói a paginação ótima quando possível, isto é, quando a árvore é completa e o número de nodos é múltiplo do tamanho da página. Além disso, propõe-se uma política eficiente para o preenchimento das páginas de uma árvore binária degenerada tendo por base a aplicação de empacotamento unidimensional na franja da árvore. A complexidade computacional do algoritmo, que depende do empacotamento unidimensional a ser utilizado, é discutida e apresentada. O algoritmo foi implementado e resultados experimentais quanto ao número de páginas visitadas e à taxa de preenchimento das páginas utilizadas, comparativos com a paginação seqüencial, valores ótimos teóricos e as árvores B, são descritos e analisados. Comparando o algoritmo proposto com as árvores B, enquanto o número de paginas visitadas por pesquisa é similar em ambas as abordagens, a taxa de preenchimento das páginas produzida pelo algoritmo proposto é mais de 30% superior à taxa obtida pelas árvores B.