Database Systems: The Complete Book- P8: Database Systems and Database Design and Application courses offered at the junior, senior and graduate levels in Computer Science departments. Written by well-known computer scientists, this introduction to database systems offers a comprehensive approach, focusing on database design, database use, and implementation of database applications and database management systems | 680 CHAPTER 14. MULTIDIMENSIONAL AND BITMAP INDEXES 500K _ Salary 225K----------- ---1------------ i 130K-----------_ _ 9ok-----------_ 0 j j_ o 40 55 100 Age Figure Insertion of the point 52 200 followed by splitting of buckets in Fig. lay along the diagonal. Then no matter where we placed the grid lines the buckets off the diagonal would have to be empty. . However if the data is well distributed and the data file itself is not too large then we can choose grid lines so that 1. There are sufficiently few buckets that we can keep the bucket matrix in main memory thus not incurring disk I O to consult it or to add rows or columns to the matrix when we introduce a new grid line. 2. We can also keep in memory indexes on the values of the grid lines in each dimension as per the box Accessing Buckets of a Grid File or ve can avoid the indexes altogether and use main-memory binary search of the values defining the grid lines in each dimension. 3. The typical bucket does not have more than a few overflow blocks so we do not incur too many disk I O s when we search through a bucket. Under those assumptions here is how the grid file behaves on some important classes of queries. Lookup of Specific Points We are directed to the proper bucket so the only disk I O is what is necessary to read the bucket. If we are inserting or deleting then an additional disk write is needed. Inserts that require the creation of an overflow block cause an additional write. I . HASH-LIKE STRUCTURES FOR MULTIDIMENSIONAL DATA 681 Partial-Match Queries Examples of this query would include find all customers aged 50 or find all customers with a salary of S200K. Now we need to look at all the buckets in a row or column of the bucket matrix. The number of disk I O s can be quite high if there are many buckets in a row or column but only a small fraction of all the buckets will be accessed. Range Queries A range query defines
