The R*-tree is an efficient and robust access method for points and rectangles, designed to improve upon the traditional R-tree. It incorporates a combined optimization of area, margin, and overlap of enclosing rectangles in the directory. Through extensive experiments, the R*-tree outperforms existing R-tree variants, including Guttman's linear and quadratic R-tree and Greene's variant, in various types of queries and operations, such as map overlay, for both rectangles and multidimensional points. The R*-tree is attractive due to its ability to efficiently support both point and spatial data, and its implementation cost is only slightly higher than other R-trees. The R-tree is based on a heuristic optimization that minimizes the area of enclosing rectangles in inner nodes. However, this approach may not be optimal for all criteria, such as margin or overlap. The R*-tree addresses these issues by optimizing multiple criteria simultaneously, leading to better performance. The R*-tree uses a standardized testbed for performance comparisons, which allows for a comprehensive evaluation of different access methods. The R*-tree's design includes a more sophisticated split algorithm that considers multiple optimization criteria, such as area, margin, and overlap. This results in better directory rectangle shapes, which improve storage utilization and query performance. The R*-tree also includes a forced reinsert mechanism that reinserts entries into different nodes, reducing overlap and improving storage utilization. The R*-tree was tested against various data distributions and query types, including rectangle intersection, point queries, and rectangle enclosure queries. It consistently outperformed other R-tree variants, particularly the linear R-tree, in terms of performance and storage utilization. Additionally, the R*-tree was tested against a benchmark for point access methods, where it outperformed other methods, including the 2-level grid file. The R*-tree is robust against ugly data distributions and can dynamically reorganize its structure to prevent splits and improve storage utilization. Its average insertion cost is lower than other R-trees, and its implementation cost is only slightly higher. Future work includes investigating ways to increase the fan out of the R*-tree and generalizing it to handle polygons efficiently.The R*-tree is an efficient and robust access method for points and rectangles, designed to improve upon the traditional R-tree. It incorporates a combined optimization of area, margin, and overlap of enclosing rectangles in the directory. Through extensive experiments, the R*-tree outperforms existing R-tree variants, including Guttman's linear and quadratic R-tree and Greene's variant, in various types of queries and operations, such as map overlay, for both rectangles and multidimensional points. The R*-tree is attractive due to its ability to efficiently support both point and spatial data, and its implementation cost is only slightly higher than other R-trees. The R-tree is based on a heuristic optimization that minimizes the area of enclosing rectangles in inner nodes. However, this approach may not be optimal for all criteria, such as margin or overlap. The R*-tree addresses these issues by optimizing multiple criteria simultaneously, leading to better performance. The R*-tree uses a standardized testbed for performance comparisons, which allows for a comprehensive evaluation of different access methods. The R*-tree's design includes a more sophisticated split algorithm that considers multiple optimization criteria, such as area, margin, and overlap. This results in better directory rectangle shapes, which improve storage utilization and query performance. The R*-tree also includes a forced reinsert mechanism that reinserts entries into different nodes, reducing overlap and improving storage utilization. The R*-tree was tested against various data distributions and query types, including rectangle intersection, point queries, and rectangle enclosure queries. It consistently outperformed other R-tree variants, particularly the linear R-tree, in terms of performance and storage utilization. Additionally, the R*-tree was tested against a benchmark for point access methods, where it outperformed other methods, including the 2-level grid file. The R*-tree is robust against ugly data distributions and can dynamically reorganize its structure to prevent splits and improve storage utilization. Its average insertion cost is lower than other R-trees, and its implementation cost is only slightly higher. Future work includes investigating ways to increase the fan out of the R*-tree and generalizing it to handle polygons efficiently.