trees and external storage thususing -treeonly six disk accesses are necessary to find any record in file of , records at milliseconds per accessthis takes about millisecondsor / of second this is dramatically faster than the binary search of sequentially ordered file the more records there are in nodethe fewer levels there are in the tree we've seen that there are levels in our -treeeven though the nodes hold only records in contrasta binary tree with , items would have about levelsand tree 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 diskfor 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 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 keylike jones the number of the block where the jones record is located within the file these numbers run from to ,