Query Optimization using B+ Trees

Abstract: This is a research-based project and the basic point motivating this project is learning and implementing Data Structures and Algorithms [1] that reduces time and space complexity [2]. In this project, we reduce the time taken to search a given record by using a B/B+ tree [3] rather than indexing and traditional sequential access. It is concluded that disk-access times are much slower than main memory access times. Typical seek times and rotational delays are of the order of 5 to 6 milliseconds and typical data transfer rates are of the range of 5 to 10 million bytes per second and therefore, main memory access times are likely to be at least 4 or 5 orders of magnitude faster than disk access on any given system. Therefore, the objective is to minimize the number of disk accesses and thus, this project is concerned with techniques for achieving that objective i.e. techniques for arranging the data on a disk so that any required piece of data, say some specific record, can be located in as few I/O's as possible.

Keywords: B+ Trees - DBMS - Search Optimizations - File Systems