Ho Chi Minh City University of Technology Faculty of Computer Science and Engineering Chapter 3: Indexing Structures for Files Database Management Systems (CO3021) Computer Science Program Dr. Võ Thị Ngọc Châu (chauvtn@hcmut.vn) Semester 1 – 2020-2021 Course outline Chapter 1. Overall Introduction to Database Management Systems Chapter 2. Disk Storage and Basic File Structures Chapter 3.
Indexing Structures for Files Chapter 4. Query Processing and Optimization Chapter 5. Introduction to Transaction Processing Concepts and Theory Chapter 6. Concurrency Control Techniques Chapter 7.
Database Recovery Techniques 2 References [1] R. Navathe, Fundamentals of Database Systems- 6th Edition, Pearson- Addison Wesley, 2011. Navathe, Fundamentals of Database Systems- 7th Edition, Pearson, 2016. Widom, Database System Implementation, Prentice-Hall, 2000.
Widom, Database Systems: The Complete Book, Prentice-Hall, 2002 [4] A. Sudarshan, Database System Concepts –3rd Edition, McGraw-Hill, 1999. Types of Single-level Ordered Indexes 3. Dynamic Multilevel Indexes Using B- Trees and B+-Trees 3.
Indexes on Multiple Keys 3. Other File Indexes 3. Indexes in Today‘s DBMSs 4 Indexing … Determine what data is Determine what ―Active database systems‖ is Determine what ―4, 22‖ are The index section in [1] Have you ever used this section in any book? 5 Indexing … Index … Value Page No. 1 ‗‘, string notation, … 182, 196, 347-348 … … … … Active Action, SQL triggers 227 database systems Active database systems 4, 22 … Active database techniques, SQL 202 4 … … … … Active Ordered indexed values Linking values database systems (addressable) … 22 … Book content 6 Indexing … Assumption: a data file exists with some primary organization such as the unordered, ordered, or hashed organization.
Indexes are additional auxiliary access structures of a data file. Role: secondary access paths, which provide alternative ways to access the records without affecting the physical placement of records in the primary data file on disk Purpose: speed up the retrieval of records in response to certain search conditions Management: additional ordered files on disk 7 3. Types of Single-level Ordered Indexes A single-level ordered index is an access structure defined on a field of a file (or multiple fields of a file). This index is a file including many entries.
Each entry is <Field value, Pointer(s)>. Field values: able to be ordered. Pointer(s): record pointers or block pointers to the data file. The field is called an indexing field.
The index file is ordered with the field values. Binary search is applied on the index file with the conditions =, >, <, ≥, ≤, between on the indexing field. Types of Single-level Ordered Indexes Data file of employee records (bfr = 3 records/block) SSN Name … Dept Single-level ordered index file 2 F … 2 (bfri = 4 records/block) 5 AA … 5 Field Value (Block) Pointer 8 U … 4 2 10 C … 2 10 11 L … 2 18 15 EG … 1 23 18 B … 4 35 19 FL … 5 21 N … 5 23 Y … 5 28 D … 1 34 O … 2 35 NM … 3 SSN: indexing field 9 3. Types of Single-level Ordered Indexes The index file usually occupies considerably less disk blocks than the data file because the number of the entries in the index file is much smaller.
A binary search on the index file yields a pointer to the file record. Indexes are characterized as dense or sparse. A dense index has an index entry for every field value (and hence every record) in the data file. A sparse (or non-dense ) index has index entries for only some field values.
The previous example is a non-dense index. Types of Single-level Ordered Indexes Types of ordered indexes A primary index is specified on the ordering key field of an ordered file of records. A clustering index is specified on the ordering non-key field of an ordered file of records. A secondary index is specified on any non-ordering field of a file of records.
A file can have at most one physical ordering field, so it can have at most one primary index or one clustering index, but not both. A data file can have several secondary indexes in addition to its primary access method. Types of Single-level Ordered Indexes Primary indexes An ordered file whose records are of fixed length with two fields: The first field is of the same data type as the ordering key field—called the primary key—of the data file. The second field is a pointer to a disk block.
There is one index entry (or index record) in the index file for each block in the data file. Each index entry has the value of the primary key field for the first record in a block and a pointer to that block as its two field values: <K(i), P(i)>. The first record in each block of the data file is called the anchor record of the block, or simply the block anchor. 12 Primary Indexes Primary indexes - Non-dense index - Block anchor Figure 17.
Types of Single-level Ordered Indexes Primary indexes A primary index is a nondense (sparse) index. Why? The index file for a primary index occupies a much smaller space than does the data file. Why? Given the value K of its primary key field, a binary search is used on the index file to find the appropriate index entry i, and then retrieve the data file block whose address is P(i). A major problem with a primary index is insertion and deletion of records.
Why and how to solve it? 14 Primary indexes Example 1: given the following data file with the ordering key field SSN EMPLOYEE(NAME, SSN, ADDRESS, JOB, SAL,. ) record size R=150 bytes block size B=512 bytes number of records r=30,000 records blocking factor bfr= B div R= B/R = 512 div 150= 3 records/block number of file blocks b = r/bfr= 30,000/3 = 10,000 blocks For a primary index on the SSN field, assume the field size VSSN=9 bytes, assume the block pointer size PB=6 bytes. index entry size Ri=VSSN+ PB=9+6=15 bytes index blocking factor bfri= B div Ri= 512 div 15= 34 entries/block number of index entries ri = number of file blocks b = 10,000 entries number of index blocks bi= ri/ bfri = 10,000/34 = 295 blocks binary search on the index needs log2bi = log2295 = 9 block accesses one extra block access to retrieve the record from the data file The total search cost via the index is: 9 + 1 = 10 block accesses This is compared to an average linear search cost directly on the data file: b/2 = 10,000/2 = 5,000 block accesses Because the file records are ordered, the binary search cost would be: log2b = log210,000 = 14 block accesses 15 3. Types of Single-level Ordered Indexes Clustering indexes Also defined on an ordered data file with an ordering non-key field.
Each index entry for each distinct value of the field The index entry points to the first data block that contains records with that field value. It is another example of non-dense index. Record insertion and deletion cause problems. Why? To alleviate the problem of insertion, it is common to reserve a whole block (or a cluster of contiguous blocks) for each value of the clustering field.
All records with that value are placed in the block (or block cluster). 16 Clustering indexes - Non-dense - No block anchor A clustering index on the Dept_number ordering nonkey field of an EMPLOYEE file Figure 17. 607, [1] 17 Clustering indexes - Non-dense - Block anchor A clustering index on the Dept_number ordering nonkey field of an EMPLOYEE file: a separate block cluster for each group of records that share the same value for the clustering field Figure 17. 608, [1] 18 Clustering indexes Example 2: given the data file with the ordering non-key field DEPT_NUMBER EMPLOYEE(NAME, SSN, ADDRESS, JOB, SAL, ., DEPT_NUMBER ) record size R=150 bytes; block size B=512 bytes; block pointer size PB=6 bytes number of records r=30,000 records It is assumed that there are 125 distinct values of the DEPT_NUMBER field and even distribution across DEPT_NUMBER values.
blocking factor bfr= (B-PB) div R= (B-PB)/R = (512-6)/150 = 3 records/block number of file blocks b = r/bfr= 30,000/3 = 10,000 blocks For a clustering index on DEPT_NUMBER, the field size VDEPT_NUMBER=4 bytes, assume the block pointer size PB=6 bytes. index entry size Ri=VDEPT_NUMBER+ PB=4+6=10 bytes index blocking factor bfri= B div Ri= 512 div 10= 51 entries/block number of index entries ri = number of distinct values = 125 entries number of index blocks bi= ri/ bfri = 125/51 = 3 blocks binary search on the index needs log2bi = log23 = 2 block accesses one extra block access to retrieve the first record from the data file The total search cost via the index is: 2 + 1 = 3 block accesses This is compared to an average linear search cost directly on the data file: b/2 = 10,000/2 = 5,000 block accesses Because the file records are ordered, the binary search cost would be: log2b = log210,000 = 14 block accesses 19 3. Types of Single-level Ordered Indexes Secondary indexes A secondary index provides a secondary means of accessing a file for which some primary access already exists. a secondary index may be defined on a field which is a candidate key and has a unique value in every record, or a nonkey with duplicate values.
The index is an ordered file with two fields. The first field is of the same data type as some nonordering field of the data file that is an indexing field. The second field is either a block pointer or a record pointer. A secondary index is a dense index.
Why? 20 Secondary indexes A dense secondary index (with block pointers) on a nonordering key field of a file The secondary index provides a logical ordering of the data file. 610, [1] 21 Secondary indexes Example 3: given the following data file with the non-ordering key field SSN EMPLOYEE(NAME, SSN, ADDRESS, JOB, SAL,. ) record size R=150 bytes block size B=512 bytes number of records r=30,000 records blocking factor bfr= B div R= B/R = 512 div 150= 3 records/block number of file blocks b = r/bfr= 30,000/3 = 10,000 blocks For a secondary index on the SSN field, assume the field size VSSN=9 bytes, assume the block pointer size P=6 bytes, the record pointer size PR=7 bytes. index entry size Ri=VSSN+ P=9+6=15 bytes index blocking factor bfri= B div Ri= 512 div 15= 34 entries/block number of index entries ri = number of file records r = 30,000 entries number of index blocks bi= ri/ bfri = 30,000/34 = 883 blocks binary search on the index needs log2bi = log2883 = 10 block accesses one extra block access to retrieve the record from the data file The total search cost via the index is: 10 + 1 = 11 block accesses Because the data file is not ordered according to the values of SSN, an average linear search is done directly on the data file with the cost: b/2 = 10,000/2 = 5,000 block accesses 22 3.
Types of Single-level Ordered Indexes Secondary indexes A secondary index defined on a non-ordering key field has the number of index entries equal to the number of records in the data file. A secondary index defined on a non-ordering non-key field can be implemented in three ways: (1).