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(as well as deletion)algorithms are simple extensions of the single-level algorithms Database System Concepts-5th Edition,Oct 4,2006 12.12 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 12.12 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 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 (as well as 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 account relation stored sequentially by account number,we may want to find all accounts in a particular branch Example 2:as above,but where we want to find all accounts with a specified balance or range of balances We can have a secondary index with an index record for each search-key value Database System Concepts-5th Edition,Oct 4,2006 12.13 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 12.13 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 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 account relation stored sequentially by account number, we may want to find all accounts in a particular branch Example 2: as above, but where we want to find all accounts with a specified balance or range of balances We can have a secondary index with an index record for each search-key value
Secondary Indices Example A-217 Brighton 750 350 日日日 A-101 Downtown 500 400 A-110 Downtown 600 500 A-215 Mianus 700 600 A-102 Perryridge 400 700 A-201 Perryridge 900 750 A-218 Perryridge 700 900 A-222 Redwood 700 A-305 Round Hill 350 Secondary index on balance field of account Index record points to a bucket that contains pointers to all the actual records with that particular search-key value. Secondary indices have to be dense Database System Concepts-5th Edition,Oct 4,2006 12.14 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 12.14 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 Secondary Indices Example Index record points to a bucket that contains pointers to all the actual records with that particular search-key value. Secondary indices have to be dense Secondary index on balance field of account
Primary and Secondary Indices Indices offer substantial benefits when searching for records. BUT:Updating indices imposes overhead on database modification-- when a file is modified,every index on the file must be updated, Sequential scan using primary index is efficient,but a sequential scan using a secondary index is expensive Each record access may fetch a new block from disk Block fetch requires about 5 to 10 milliseconds versus about 100 nanoseconds for memory access Database System Concepts-5th Edition,Oct 4,2006 12.15 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 12.15 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 Primary and Secondary Indices Indices offer substantial benefits when searching for records. BUT: Updating indices imposes overhead on database modification -- when a file is modified, every index on the file must be updated, Sequential scan using primary index is efficient, but a sequential scan using a secondary index is expensive Each record access may fetch a new block from disk Block fetch requires about 5 to 10 milliseconds versus about 100 nanoseconds for memory access
B*-Tree Index Files B+-tree indices are an alternative to indexed-sequential files. Disadvantage of indexed-sequential files performance degrades as file grows,since many overflow blocks get created. Periodic reorganization of entire file is required. Advantage of B+-tree index files: automatically reorganizes itself with small,local,changes,in the face of insertions and deletions. Reorganization of entire file is not required to maintain performance. (Minor)disadvantage of B+-trees: extra insertion and deletion overhead,space overhead. Advantages of B+-trees outweigh disadvantages B+-trees are used extensively Database System Concepts-5th Edition,Oct 4,2006 12.16 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 12.16 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 B+ -Tree Index Files Disadvantage of indexed-sequential files performance degrades as file grows, since many overflow blocks get created. Periodic reorganization of entire file is required. Advantage of B+-tree index files: automatically reorganizes itself with small, local, changes, in the face of insertions and deletions. Reorganization of entire file is not required to maintain performance. (Minor) disadvantage of B+-trees: extra insertion and deletion overhead, space overhead. Advantages of B+-trees outweigh disadvantages B+-trees are used extensively B+ -tree indices are an alternative to indexed-sequential files