Inserting B will cause the first record to overflow.
The G will have to be shifted into the second record, and so on. Consequently, every record of the index changes as a result of a single insertion. The cost of the index insertion grows linearly with the number of index records. The solution to this problem is to treat this list of records as a linked list in the index file. Therefore, the attempt to insert B will split the record into two records: one with three keys and one with two keys.
Multilevel Indexing
There are two ways to search a multirecord index:
Sequential search: Start at the beginning and look at every index record until we find the key. This approach results in reading half of the index records in the average case.
Binary search: We already know that binary search is too expensive.
The solution to decreasing the cost of searching the index is to build an index for the keys of records, which leads to multiple level of indexes. The figure below shows a two-level index, where the arrows represent the reference fields associated with the keys of the first-level index.
