In this paper, a novel cache conscious indexing technique based on space partitioning trees is proposed. Many researchers investigated efficient cache conscious indexing techniques which improve retrieval performance of in-memory database management system recently. However, most studies considered data partitioning and targeted fast information retrieval. Existing data partitioning-based index structures significantly degrade performance due to the redundant accesses of overlapped spaces. Specially, R-tree-based index structures suffer from the propagation of MBR (Minimum Bounding Rectangle) information by updating data frequently. In this paper, we propose an in-memory space partitioning index structure for optimal cache utilization. The proposed index structure is compared with the existing index structures in terms of update performance, insertion performance and cache-utilization rate in a variety of environments. The results demonstrate that the proposed index structure offers better performance than existing index structures.

In this paper, we propose a new concurrency control protocol for parallel B-tree structures capable reducing the cost of structure-modification-operation (SMO) compared to the conventional protocols such as ARIES/IM and INC-OPT. We call this protocol the MARK-OPT protocol, since it marks the lowest SMO occurrence point during optimistic latch-coupling operations. The marking reduces middle phases for spreading an X latch and removes needless X latches. In addition, we propose three variations of the MARK-OPT, which focus on tree structure changes from other transactions. Moreover, the proposed protocols are deadlock-free and satisfy the physical consistency requirement for B-trees. These indicate that the proposed protocols are suitable as concurrency control protocols for B-tree structures. To compare the performance of the proposed protocols, the INC-OPT, and the ARIES/IM, we implement these protocols on an autonomous disk system adopting the Fat-Btree structure, a form of parallel B-tree structure. Experimental results in various environments indicate that the proposed protocols always improve system throughput, and 2P-REP-MARK-OPT is the most useful protocol in high update environment. Additionally, to mitigate access skew, data should be migrated between PEs. We also demonstrate that MARK-OPT improves the system throughput under the data migration and reduces the time for data migration to balance load distribution.

The Fat-Btree which is a new parallel B-tree structure has been proposed to improve the access performance of shared-nothing parallel database systems. Since the Fat-Btree has only a part of index nodes on each processing element, it can reduce the synchronization cost in update operations. For these reasons, both retrieval and update operations can be processed at high throughput compared to previously proposed parallel B-tree structures for shared-nothing computers. Though we tried to apply some conventional concurrency control methods to the Fat-Btree, e.g., B-OPT and ARIES/IM, which were designed for shared-everything machines, we found that these methods are not always appropriate for the Fat-Btree. In this paper, it is shown that the conventional methods are not suitable for the Fat-Btree and other parallel B-trees. We propose a new deadlock free concurrency control protocol, named INC-OPT, to improve the performance of the Fat-Btree more effectively than the B-OPT and ARIES/IM. Furthermore, in order to prove that the Fat-Btree provides the impact on the performance of shared-nothing parallel databases, we compare the real performance of three types of parallel B-tree structures, Fat-Btree, Copy-Whole-Btree, and Single-Index-Btree, on an nCUBE3 machine where the INC-OPT is applied.