Database Management Systems: Chapter 2 - Indexing Structures for Files present about Types of Single-level Ordered Indexes (Primary Indexes, Clustering Indexes, Secondary Indexes); Multilevel Indexes; Dynamic Multilevel Indexes Using B-Trees and B+-Trees; Indexes on Multiple Keys. | Chapter 2 Indexing Structures for Files Adapted from the slides of “Fundamentals of Database Systems” (Elmasri et al., 2003) Chapter outline Types of Single-level Ordered Indexes Primary Indexes Clustering Indexes Secondary Indexes Multilevel Indexes Dynamic Multilevel Indexes Using B-Trees and B+-Trees Indexes on Multiple Keys Indexes as Access Paths A single-level index is an auxiliary file that makes it more efficient to search for a record in the data file. The index is usually specified on one field of the file (although it could be specified on several fields) One form of an index is a file of entries , which is ordered by field value The index is called an access path on the field. Indexes as Access Paths (cont.) The index file usually occupies considerably less disk blocks than the data file because its entries are much smaller A binary search on the index yields a pointer to the file record Indexes can also be characterized as dense . | Chapter 2 Indexing Structures for Files Adapted from the slides of “Fundamentals of Database Systems” (Elmasri et al., 2003) Chapter outline Types of Single-level Ordered Indexes Primary Indexes Clustering Indexes Secondary Indexes Multilevel Indexes Dynamic Multilevel Indexes Using B-Trees and B+-Trees Indexes on Multiple Keys Indexes as Access Paths A single-level index is an auxiliary file that makes it more efficient to search for a record in the data file. The index is usually specified on one field of the file (although it could be specified on several fields) One form of an index is a file of entries , which is ordered by field value The index is called an access path on the field. Indexes as Access Paths (cont.) The index file usually occupies considerably less disk blocks than the data file because its entries are much smaller A binary search on the index yields a pointer to the file record Indexes can also be characterized as dense or sparse. A dense index has an index entry for every search key value (and hence every record) in the data file. A sparse (or nondense ) index, on the other hand, has index entries for only some of the search values Example: Given the following data file: EMPLOYEE(NAME, SSN, ADDRESS, JOB, SAL, . ) Suppose that: record size R=150 bytes block size B=512 bytes r=30000 records Then, we get: blocking factor Bfr= B div R= 512 div 150= 3 records/block number of file blocks b= (r/Bfr)= (30000/3)= 10000 blocks For an index on the SSN field, assume the field size VSSN=9 bytes, assume the record pointer size PR=7 bytes. Then: index entry size RI=(VSSN+ PR)=(9+7)=16 bytes index blocking factor BfrI= B div RI= 512 div 16= 32 entries/block number of index blocks b= (r/ BfrI)= (30000/32)= 938 blocks binary search needs log2b= log2938= 10 block accesses This is compared to an average linear search cost of: (b/2)= 30000/2= 15000 block accesses If the file records are ordered, the binary search .
