1. Index-sequential files: Files are ordered sequentially on some search key, and a primary index is associated with it.

Dense and Sparse Indices

1. There are Two types of ordered indices:

Dense Index:

• An index record appears for every search key value in file.
• This record contains search key value and a pointer to the actual record.

Sparse Index:

• Index records are created only for some of the records.
• To locate a record, we find the index record with the largest search key value less than or equal to the search key value we are looking for.
• We start at that record pointed to by the index record, and proceed along the pointers in the file (that is, sequentially) until we find the desired record.

2. Figures 11.2 and 11.3 show dense and sparse indices for the deposit file.
3. Notice how we would find records for Perryridge branch using both methods. (Do it!)
4. Dense indices are faster in general, but sparse indices require less space and impose less maintenance for insertions and deletions. (Why?)

5. A good compromise: to have a sparse index with one entry per block.

Why is this good?

• Biggest cost is in bringing a block into main memory.
• We are guaranteed to have the correct block with this method, unless record is on an over flow block(actually could be several blocks).
• Index size still small.

Multi-Level Indices

1. Even with a sparse index, index size may still grow too large. For 100,000 records, 10 per block, at one index record per block, that's 10,000 index records! Even if we can fit 100 index records per block, this is 100 blocks.

2. If index is too large to be kept in main memory, a search results in several disk reads.

• If there are no over flow blocks in the index, we can use binary search.
• This will read as many as 1 + log2(b) blocks (as many as 7 for our 100 blocks).
• If index has over flow blocks, then sequential search typically used, reading all b index blocks.

3. Solution: Construct a sparse index on the index (Figure 11.4).
4. Use binary search on outer index. Scan index block found until correct index record found. Use index record as before - scan block pointed to for desired record.
5. For very large files, additional levels of indexing may be required.
6. Indices must be updated at all levels when insertions or deletions require it.
7. Frequently, each level of index corresponds to a unit of physical storage (e.g. indices at the level of track,cylinder and disk).

Index Update

Regardless of what form of index is used, every index must be updated whenever a record is either inserted into or deleted from the flle.

1. Deletion:

• Find (look up) the record
• If the last record with a particular search key value, delete that search key value from index.
• For dense indices, this is like deleting a record in a file.
• For sparse indices, delete a key value by replacing key value's entry in index by next search key value.If that value already has an index entry, delete the entry.

2. Insertion:

• Find place to insert.
• Dense index: insert search key value if not present.
• Sparse index: no change unless new block is created. (In this case, the first search key value appearing in the new block is inserted into the index).