AVL木の拡張とB木との比較評価

概要

論文の詳細を見る
In this paper, we propose to develop an extended AVL tree with 5-subtrees, for the purpose of increasing search efficiency, and examine various evaluations for the extended AVL tree. The data structure of this extended AVL tree contains 5 partially balanced subtrees that match prefixes character by character by implementing the radix search method. A numerical experiment confirmed that the construction time was about 50% of B-tree. When the height of B-trees is smallest, the amount of memory becomes smaller than that of B-trees, using 10^{14} pieces of data or more. The construction time of the extended AVL trees was about 47% of that of B-trees in a numerical experiment using 10 million random pieces with 100-digit character strings in the decimal number, and the comparison frequency of the extended AVL trees obtained an excellent result of about 11% of that of B-trees. In this case, the amount of memory became about 36% for that of B-trees.
2011-12-30