Abstract

The search tree index framework, a sub-framework of the Know-It-All Project, is used to develop a generalized search tree that provides the basis for common tree access methods used in database systems. The search tree index framework covers one-dimensional tree structures, point access structures, and special multi-dimensional structures. It also covers sequential queries, exact match queries, range queries, approximate queries, and similarity queries. It applies the Standard Template Library modularity concept in the analysis, architecture, design and interface and takes advantage of reuse capabilities in modern programming languages such as generic programming and design pattern. By using modularization design, the system is designed as an integrated set of layers including algorithms layer, proxy layer and physical storage layer. Layering design technique provides a mechanism to decompose functionality. The design separates index, data, and data Reference/Page reference; uses iterators perform general queries on search tree structures, while providing a clean interface for these queries to define both positions within indexes or files, as well as to refer to a collection of information. The framework can be adapted to the needs of any application by simply changing some of the building blocks and is designed for maximum flexibility and the simplest extension.