Multilevel Indexing (Cont.)

The records are sorted, so the largest key in each index record can be used to represent the entire index record. The key for the records will be C for the first record, G for the second record, and so on. The process can be taken one step further by adding a third level, resulting in the tree below.


The root node is an index record whose references are to nodes at the second level. These second-level nodes are index records whose references are to nodes at the third level. Finally, the third-level nodes are index records whose references are to records in the data file. Cost associated with a multilevel index file includes:

• Space overhead: For example, the space overhead is just 1% more for 80000 index records. Certainly this is not a burden.


• Search time: For example, an 80-megabyte file can be read with just four disk accesses. This is what we need to produce efficient indexed access!


• Insertion and deletion: For example, it may require 80000 reads and writes to insert a new key into 80000 index records. This is truly a fatal flaw in simple multilevel indexing.