For the past few decades, an important assumption of database research and development is that most of the data in a database are on disk. With the latest development of technology, it is possible to have main memory databases where all data reside in the main memory. On account of the difference between accessing the main memory and the disk, related techniques should be re-examined in developing main memory database management systems. Indexing technique is one of them. While a number of main memory index structures has been proposed, T-tree has been widely accepted as a promising index tree for main memory databases. However, most of the studies on the T-tree appearing in literature have not taken concurrency control into consideration. Therefore, in this thesis, I have investigated...[ Read more ]

For the past few decades, an important assumption of database research and development is that most of the data in a database are on disk. With the latest development of technology, it is possible to have main memory databases where all data reside in the main memory. On account of the difference between accessing the main memory and the disk, related techniques should be re-examined in developing main memory database management systems. Indexing technique is one of them. While a number of main memory index structures has been proposed, T-tree has been widely accepted as a promising index tree for main memory databases. However, most of the studies on the T-tree appearing in literature have not taken concurrency control into consideration. Therefore, in this thesis, I have investigated the performance of the main memory index structures with concurrency control. Preliminary study has indicated that, the B-link-tree, a variant of the widely used B+-tree index, in fact outperforms the T-tree if concurrency control is required. Among the possible solutions, I have proposed the T-tail-tree, a variant of the T-tree, and a new concurrency control algorithm for the problem. Simulation results showed that the concurrency control algorithm in the T-tail-tree provides better performance than the T-tree. In addition, I have modified the T-tree algorithm to a new index structure: IT-tree. Real execution results revealed that the IT-tree performs equally well as the T-tree but less memory needed.