@MastersThesis{Petrusanis:1983:TéBaÁr,
author = "Petrusanis, Mirna Fel{\'{\i}}cia Ramos de Oliveira",
title = "Z-{\'A}rvores virtuais: uma t{\'e}cnica de balanceamento para
{\'a}rvores de caminhos m{\'u}ltiplos",
school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
year = "1983",
address = "S{\~a}o Jos{\'e} dos Campos",
month = "1983-11-28",
keywords = "{\'a}rvores de caminhos m{\'u}ltiplos, organiza{\c{c}}{\~a}o
de arquivos.",
abstract = "Neste trabalho ser{\'a} apresentada a primeira
implementa{\c{c}}{\~a}o e avalia{\c{c}}{\~a}o com
simula{\c{c}}{\~o}es de Z-{\'A}rvores que s{\~a}o {\'a}rvores
de caminhos m{\'u}ltiplos com chaves similares {\`a}s
B-{\'A}rvores. Para que o baixo custo de recupera{\c{c}}{\~a}o
seja garantido, requer-se que a {\'a}rvore esteja balanceada,
introduzindo para isto um m{\'e}todo de balanceamento, que {\'e}
a T{\'e}cnica da Z-{\'A}rvore Virtual (TZAV). Comparada com a
T{\'e}cnica de B-{\'A}rvores, a TZAV tem as vantagens de baixo
custo nas altera{\c{c}}{\~o}es e algoritmos simples, n{\~a}o
sendo requeridas t{\'e}cnicas de {"}overflow{"} e
{"}underflow{"}. Uma desvantagem da TZAV {\'e} a depend{\^e}ncia
do conhecimento aproximado da distribui{\c{c}}{\~a}o das chaves.
Considerando que um n{\'o} da Z-{\'A}rvore {\'e} armazenado em
um bloco, o n{\'u}mero m{\'e}dio de transfer{\^e}ncia de blocos
{\'e} obtido com inser{\c{c}}{\~o}es e elimina{\c{c}}{\~o}es
de chaves aleat{\'o}rias. Esta taxa de transfere de blocos {\'e}
baixa e da mesma ordem das B-{\'A}rvores. A mem{\'o}ria
utilizada da TZAV pode ser aumentada atrav{\'e}s de uma
representa adequada das folhas, sendo requeridas para este fim
t{\'e}cnicas de divis{\~a}o e jun{\c{c}}{\~a}o de folhas. A
taxa m{\'{\i}}nima de utiliza{\c{c}}{\~a}o de mem{\'o}ria
{\'e} de 50%. Nas simila{\c{c}}{\~o}es feitas, a taxa de
utiliza{\c{c}}{\~a}o de mem{\'o}ria {\'e}, na m{\'e}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%.",
committee = "Renna e Souza, Celso de (presidente) and Seehusen, Hans Jurgen
(orientador) and Dias, Luiz Alberto Vieira (orientador) and
Setzer, Valdemar Waingort and Silva, Orion de Oliveira",
copyholder = "SID/SCD",
englishtitle = "x",
language = "pt",
pages = "113",
ibi = "8JMKD3MGP8W/352RGLB",
url = "http://urlib.net/ibi/8JMKD3MGP8W/352RGLB",
targetfile = "publicacao.pdf",
urlaccessdate = "02 maio 2024"
}