Um algoritmo para paginação 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.

Abstract: Binary trees are data structures traditionally used to search efficiently on large amounts of data. If the tree is too large to be completely stored in main memory it must be allocated in pages which are transferred in blocks from secondary to main memory. Analogously, if the tree is stored in a remote computer connected to a network, it is also necessary to allocate the tree in pages which are sent through the network in packets. This work presents a new algorithm for paging binary trees applicable when the information set is static, the access frequencies are not known and the storage is remote or secondary. The algorithm aims at reducing the number of pages visited for searching, and at decreasing the unused space in each page as well as reducing the total number of pages required to store a tree. An alternative version of the algorithm which aims at reducing the distance between nodes stored in a given page is presented. The algorithm builds the best possible paging when it is possible, and presents an efficient strategy for allocating degenerated trees based on onedimensional packing. The complexity of the algorithm is presented, which depends on the complexity of one-dimensional packing. Experimental results are reported and compared with other approaches, including sequential paging and B-trees. The comparison with B-trees shows that while the number of pages accessed in a search is similar in both approaches, the page filling percentage of the proposed algorithm is over 30% larger than that obtained with B-trees.