would have if we use blocks with hundreds of recordswe can reduce the number of levels in the tree and further improve access times although searching is faster in -trees than in sequentially ordered disk filesit' for insertion and deletion that -trees show the greatest advantage let' first consider -tree insertion in which no nodes need to be split this is the most likely scenariobecause of the large number of records per node in our phone book exampleas we've seenonly accesses are required to find the insertion point then one more access is required to write the block containing the newly inserted record back to the diska total of accesses next let' see how things look if node must be split the node being split must be readhave half its records removedand be written back to disk the newly created node must be written to the diskand the parent must be read andfollowing the insertion of the promoted recordwritten back to disk this is accesses in addition to the six necessary to find the insertion pointfor total of this is major improvement over the , accesses required for insertion in sequential file in some versions of the -treeonly leaf nodes contain records non-leaf nodes contain only keys and block numbers this may result in faster operation because each block can hold many more block numbers the resulting higher-order tree will have fewer levelsand access speed will be increased howeverprogramming may be complicated because there are two kinds of nodesleaves and non-leaves indexing different approach to speeding up file access is to store records in sequential order but use file index along with the data itself file index is list of key/block pairsarranged with the keys in order recall that in our original phone book example we had , records of bytes eachstored records to blockin , blocks assuming our search key is the last nameevery entry in the index contains two itemsthe keysuch as jones the number of the block where the jones record is located within the file these numbers run from to , let' say we use string bytes long for the key (big enough for most last names)and bytes for the block number ( type int in javaeach entry in our index thus requires bytes this is only / the amount necessary for each record the entries in the index are arranged sequentially by last name the original records on the disk can be arranged in any convenient order this usually means that new records are simply appended to the end of the fileso the records are ordered by time of insertion this arrangement is shown in figure