Topology B-Trees and Their Applications

. The well-known B-tree data structure provides a mechanism for dynamically maintaining balanced binary trees in external memory. We present an external-memory dynamic data structure for maintaining arbitrary binary trees. Our data structure, which we call the topology B-tree, is an external-memory analogue to the internal-memory topology tree data structure of Frederickson. It allows for dynamic expression evaluation and updates as well as various tree searching and evaluation queries. We show how to apply this data structure to a number of external-memory dynamic problems, including approximate nearestneighbor searching and closest-pair maintenance. 1 Introduction The B-tree [8, 12, 14, 15] data structure is a very efficient and powerful way for maintaining balanced binary trees in external memory [1, 11, 13, 18, 19, 21, 22, 2]. Indeed, in his well-known survey paper [8], Comer calls B-trees "ubiquitous," for they are found in a host of different applications. Nevertheless, there ar..