Abstract

An efficient implementation of search trees is crucial for any database systems. The B+-tree is one of the most widely and studied data structures and provides an efficient index structure for databases. The Index subframework is a component of the Know-It-All database framework. It covers tree-based indexes such as B+-tree, R-tree, X-tree and SS-tree, including sequential queries, exact match queries, range queries, approximate queries, and similarity queries. Our B+-tree implementation is a proof-of-concept for the Index subframework. Our B+-tree index is designed to be a container by following the STL style in C++ and implemented by using design patterns and generic programming techniques. Therefore, the B+-tree index can adapt to different key types, data types, different queries, and different database application domains, and be easy and convenient for developers to reuse.