%0 Thesis
%4 sid.inpe.br/mtc-m18@80/2009/03.27.14.57
%2 sid.inpe.br/mtc-m18@80/2009/03.27.14.57.07
%T Z-Árvores virtuais: uma técnica de balanceamento para árvores de caminhos múltiplos
%J x
%D 1983
%8 1983-11-28
%9 Dissertação (Mestrado em Computação Aplicada)
%P 113
%A Petrusanis, Mirna Felícia Ramos de Oliveira,
%E Renna e Souza, Celso de (presidente),
%E Seehusen, Hans Jurgen (orientador),
%E Dias, Luiz Alberto Vieira (orientador),
%E Setzer, Valdemar Waingort,
%E Silva, Orion de Oliveira,
%I Instituto Nacional de Pesquisas Espaciais (INPE)
%C São José dos Campos
%K árvores de caminhos múltiplos, organização de arquivos.
%X Neste trabalho será apresentada a primeira implementação e avaliação com simulações de Z-Árvores que são árvores de caminhos múltiplos com chaves similares às B-Árvores. Para que o baixo custo de recuperação seja garantido, requer-se que a árvore esteja balanceada, introduzindo para isto um método de balanceamento, que é a Técnica da Z-Árvore Virtual (TZAV). Comparada com a Técnica de B-Árvores, a TZAV tem as vantagens de baixo custo nas alterações e algoritmos simples, não sendo requeridas técnicas de "overflow" e "underflow". Uma desvantagem da TZAV é a dependência do conhecimento aproximado da distribuição das chaves. Considerando que um nó da Z-Árvore é armazenado em um bloco, o número médio de transferência de blocos é obtido com inserções e eliminações de chaves aleatórias. Esta taxa de transfere de blocos é baixa e da mesma ordem das B-Árvores. A memória utilizada da TZAV pode ser aumentada através de uma representa adequada das folhas, sendo requeridas para este fim técnicas de divisão e junção de folhas. A taxa mínima de utilização de memória é de 50%. Nas similações feitas, a taxa de utilização de memória é, na média, 90%. ABSTRACT: This work presents the first implementation and numerical valuation of Z-Trees, which are multiway search trees similar to B-Trees. In order to obtain low retrieval costs, the trees have to be kept balanced. This is done by a balancing technique the Virtual Z-Tree Technique (VZTT). Compared to B-Trees, the VZTT has the advantages of low update costs and simple algorithms, which do not require overflow and underflow techniques. A disadvantage of the VZTT is the necessity of an approximate knowledge of the key distribution. Assuming that one node of a Z-Tree occupies one block the mean block transfer rate is obtained by insertions and deletions of random keys. The block transfer rate for VZTT is of the order of B-Trees. The storage usage of VZTT can be increased by an adequate representation of the leaves which requires division and junction techniques. With this leaf representation, the minimum storage usage is 50% and in the simulation done of the order of 90%.
%@language pt
%3 publicacao.pdf