How Does Indexing Reduce Database I/O Cost?

TL;DR

Indexing reduces the example's record-search I/O cost from 12 block accesses without an index to 9 with a dense index or 7 with a sparse index. The calculation uses 1,000-byte blocks, 250-byte records, 20-byte index entries, binary search over index blocks, and one final access to the identified data block.

Transcript

Hello Friends, Welcome to Gate Smashers Lets understand the numerical on indexing Firstly I want to tell you that this video is in continuity here I'm making part 2 part one is already made and video is also uploaded Link I'll share in description with you Actually what we've discussed in part one We find out the total I/O cost to search a record w... Read More

Key Insights

• A 1,000-byte data block holds four 250-byte records. Consequently, storing all 10,000 records requires 2,500 data blocks, because the number of records is divided by the four records that fit in each block.
• An index entry consists of a key value and a pointer. The key represents the value used to search, such as a roll number, registration number, or name, while the pointer identifies the page containing the desired record.
• A 1,000-byte index block holds 50 entries when every index entry occupies 20 bytes. Index blocks can contain more entries than data blocks because they store only keys and pointers rather than complete 250-byte records.
• A sparse index stores one anchor entry for each data block rather than one entry for every record. With 2,500 data blocks, the sparse index contains 2,500 entries and occupies 50 index blocks at 50 entries per block.
• Sparse indexing requires the underlying data to be ordered. When records are sorted, an anchor value can represent the records in each block, allowing the index to contain one entry per block instead of one entry per individual record.
• Searching the 50 blocks of a sparse index requires six index-block accesses using binary search, because the upper value of log base 2 of 50 is six. Accessing the resulting data page adds one more I/O, giving seven total accesses.
• A dense index contains an entry for every one of the 10,000 records. At 50 entries per index block, it occupies 200 blocks, and binary search requires eight index accesses followed by one data-block access, totaling nine.
• Indexing lowers the example's I/O cost compared with searching without an index. The earlier unindexed calculation produced a cost of 12, while the dense index produces 9 and the sparse index produces 7 under the stated assumptions.

Questions & Answers

Q: How is the number of data blocks calculated?

The example uses a block size of 1,000 bytes and a record size of 250 bytes. Dividing 1,000 by 250 shows that four records fit in each block. The database contains 10,000 records, so dividing 10,000 by four gives 2,500 data blocks required to store the complete collection of records.

Q: What information is stored in each index entry?

Each index entry stores two items: a key value and a pointer. The key is the searchable value associated with a record, such as a roll number, registration number, or name. The pointer identifies the page where the relevant data is stored, allowing the search process to move from the index to the desired data block.

Q: How many entries fit in one index block?

One index block holds 50 entries in the example. Every index block has the same 1,000-byte size as a disk block, while each index entry occupies 20 bytes. Dividing 1,000 bytes by 20 bytes gives 50 entries. These entries are compact because they contain keys and pointers instead of complete 250-byte records.

Q: What is the difference between dense and sparse indexing?

A dense index stores one index entry for every record, so the example requires 10,000 entries. A sparse index stores one anchor entry for each data block, so it requires only 2,500 entries for the 2,500 data blocks. The sparse arrangement is possible when the underlying data is ordered, allowing one entry to represent a block.

Q: Why does sparse indexing require ordered data?

Sparse indexing uses an anchor or leader value to represent the records stored within each data block. This works when the data follows an ordered sequence, because the search can use the anchor values to identify the appropriate block. The transcript contrasts this with unordered data, where the same sparse organization cannot be formed in the described manner.

Q: How is the sparse-index I/O cost calculated?

The sparse index has 2,500 entries because there is one entry for each data block. Since 50 entries fit in one index block, the index occupies 50 blocks. Binary search over those blocks requires the upper value of log base 2 of 50, which is six accesses. One final data-block access produces seven total I/Os.

Q: How is the dense-index I/O cost calculated?

The dense index contains one entry for each of the 10,000 records. With 50 entries in each 1,000-byte index block, it occupies 200 blocks. Binary search over 200 index blocks requires eight accesses, using the upper value of log base 2 of 200. One additional access to the identified data block raises the total cost to nine.

Q: How much does indexing reduce the search I/O cost?

The unindexed calculation referenced from the preceding lesson gives an I/O cost of 12. Under the same example values, a dense index reduces the total to nine accesses, while a sparse index reduces it to seven. Both totals include the index search and one additional access to retrieve the desired record from its data block.

Summary & Key Takeaways

• The database contains 10,000 records of 250 bytes each, while every disk block holds 1,000 bytes. Dividing the block size by the record size gives four records per block. Storing all records therefore requires 2,500 data blocks, which provides the basis for calculating dense and sparse index sizes.

• Each 20-byte index entry contains a search key and a pointer identifying a page. A 1,000-byte index block can hold 50 entries. A sparse index stores one entry for each of the 2,500 data blocks, requiring 50 index blocks, while a dense index stores 10,000 entries in 200 blocks.

• Binary search over 50 sparse-index blocks requires the upper value of log base 2 of 50, which is six accesses. One additional access retrieves the desired data block, producing a total cost of seven. The dense index similarly requires eight index accesses plus one data-block access, totaling nine.