Multilevel Index If primary index does not fit in memory,access becomes expensive. Solution:treat primary index kept on disk as a sequential file and construct a sparse index on it. outer index-a sparse index of primary index inner index-the primary index file If even outer index is too large to fit in main memory,yet another level of index can be created,and so on. Indices at all levels must be updated on insertion or deletion from the file. Database System Concepts-6th Edition 11.12 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 11.12 ©Silberschatz, Korth and Sudarshan th Edition Multilevel Index If primary index does not fit in memory, access becomes expensive. Solution: treat primary index kept on disk as a sequential file and construct a sparse index on it. outer index – a sparse index of primary index inner index – the primary index file If even outer index is too large to fit in main memory, yet another level of index can be created, and so on. Indices at all levels must be updated on insertion or deletion from the file
Multilevel Index (Cont.) index data block 0 block 0 : index data block 1 block 1 outer index : inner index Database System Concepts-6th Edition 11.13 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 11.13 ©Silberschatz, Korth and Sudarshan th Edition Multilevel Index (Cont.)
Index Update:Deletion 10101 10101 Srinivasan Comp.Sci. 65000 32343 12121 Wu Finance 90000 76766 15151 Mozart Music 40000 22222 Einstein Physics 95000 If deleted record was the 32343 El Said History 60000 33456 Gold Physics 87000 only record in the file with its 45565 Katz Comp.Sci. 75000 particular search-key value, 58583 Califieri History 62000 76543 the search-key is deleted Singh Finance 80000 76766 Crick Biology 72000 from the index also. 83821 Brandt Comp.Sci. 92000 98345 Kim Elec.Eng. 80000 Single-level index entry deletion: Dense indices-deletion of search-key is similar to file record deletion. Sparse indices- if an entry for the search key exists in the index,it is deleted by replacing the entry in the index with the next search-key value in the file (in search-key order). If the next search-key value already has an index entry,the entry is deleted instead of being replaced. Database System Concepts-6th Edition 11.14 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 11.14 ©Silberschatz, Korth and Sudarshan th Edition Index Update: Deletion Single-level index entry deletion: Dense indices – deletion of search-key is similar to file record deletion. Sparse indices – if an entry for the search key exists in the index, it is deleted by replacing the entry in the index with the next search-key value in the file (in search-key order). If the next search-key value already has an index entry, the entry is deleted instead of being replaced. If deleted record was the only record in the file with its particular search-key value, the search-key is deleted from the index also
Index Update:Insertion Single-level index insertion: Perform a lookup using the search-key value appearing in the record to be inserted. Dense indices-if the search-key value does not appear in the index,insert it. Sparse indices-if index stores an entry for each block of the file,no change needs to be made to the index unless a new block is created. If a new block is created,the first search-key value appearing in the new block is inserted into the index. Multilevel insertion and deletion:algorithms are simple extensions of the single-level algorithms Database System Concepts-6th Edition 11.15 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 11.15 ©Silberschatz, Korth and Sudarshan th Edition Index Update: Insertion Single-level index insertion: Perform a lookup using the search-key value appearing in the record to be inserted. Dense indices – if the search-key value does not appear in the index, insert it. Sparse indices – if index stores an entry for each block of the file, no change needs to be made to the index unless a new block is created. If a new block is created, the first search-key value appearing in the new block is inserted into the index. Multilevel insertion and deletion: algorithms are simple extensions of the single-level algorithms
Secondary Indices Frequently,one wants to find all the records whose values in a certain field(which is not the search-key of the primary index)satisfy some condition. Example 1:In the instructorrelation stored sequentially by ID,we may want to find all instructors in a particular department Example 2:as above,but where we want to find all instructors with a specified salary or with salary in a specified range of values We can have a secondary index with an index record for each search-key value Database System Concepts-6th Edition 11.16 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 11.16 ©Silberschatz, Korth and Sudarshan th Edition Secondary Indices Frequently, one wants to find all the records whose values in a certain field (which is not the search-key of the primary index) satisfy some condition. Example 1: In the instructor relation stored sequentially by ID, we may want to find all instructors in a particular department Example 2: as above, but where we want to find all instructors with a specified salary or with salary in a specified range of values We can have a secondary index with an index record for each search-key value