Clustering Techniques for Minimizing External Path Length

摘要

There are a variety of main-memory access structures, such as segment trees, and quad trees, whose properties, such as good worstcase behaviour, make them attractive for database applications. Unfortunately, the structures are typically 'long and skinny', whereas disk data structures must be 'short-and-fat' (that is, have a high fanout and low height) in order to minimize I/O.