Indexing techniques and structured queries for relational databases management systems

Abstract

Indexing has long been used to improve the speed of relational database systems, and choosing an adequate index at design time is critical to the database's efficiency. In this study, it was demonstrated empirically that data access time and data insertion time for moderately large datasets are influenced by the index chosen at design time. However, deletion time is approximately the same. As a result, regardless of the query optimization strategy utilized at runtime, record access/insertion time depends on the type of index employed at design time. This paper presents a comparison of BTree indexes with Hash indexes. It was demonstrated empirically that insertion is substantially faster with the Hash index than with the Btree index, at the expense of a larger Hash index file size. The Btree index is slower due to the rebuild time of Btree indexes during insertion. The empirical results of this study complement that of theoretical results for both Btree and Hash indexes. On the other hand, hash index files are large, restricting their use for applications with rapidly increasing dataset sizes; thus, a tradeoff employing Hash index or Btrees is required. In general, this study proposes Hash indexes for small dataset applications and Btree indexes for large dataset applications on systems with limited memory.