(BQ) Part 2 book "A practical introduction to data structures and algorithm analysis" has contents: File processing and external sorting, searching, indexing, graphs, lists and arrays revisited, advanced tree structures, analysis techniques, lower bounds, lower bounds, limits to computation. | 8 File Processing and External Sorting Earlier chapters presented basic data structures and algorithms that operate on data stored in main memory. Some applications require that large amounts of information be stored and processed — so much information that it cannot all fit into main memory. In that case, the information must reside on disk and be brought into main memory selectively for processing. You probably already realize that main memory access is much faster than access to data stored on disk or other storage devices. The relative difference in access times is so great that efficient disk-based programs require a different approach to algorithm design than most programmers are used to. As a result, many programmers do a poor job when it comes to file processing applications. This chapter presents the fundamental issues relating to the design of algorithms and data structures for disk-based We begin with a description of the significant differences between primary memory and secondary storage. Section discusses the physical aspects of disk drives. Section presents basic methods for managing buffer pools. Section discusses the C++ model for random access to data stored on disk. Section discusses the basic principles for sorting collections of records too large to fit in main memory. 1 Computer technology changes rapidly. I provide examples of disk drive specifications and other hardware performance numbers that are reasonably up to date as of the time when the book was written. When you read it, the numbers might seem out of date. However, the basic principles do not change. The approximate ratios for time, space, and cost between memory and disk have remained surprisingly steady for over 20 years. 287 288 Chap. 8 File Processing and External Sorting Medium RAM Disk Flash .
