Out to the Disk

This chapter deals with data stored on disk rather than in memory. There are two main reasons for using disk storage. First, information on disk persists even when the electricity goes out or the computer is rebooted. Second, some applications involve so much data that it does not fit in memory. For example, a search engine that examines 10 billion web sites, averaging 10 kilobytes each, would have to handle 100 terabytes of data!

Section 17.1 deals with the basics of interacting with files in Java. The remaining sections address special data structures and algorithms used with data stored on disk. Two algorithms for compressing data, so that it takes up less space on disk, are described in Section 17.2. In Section 17.3, we look at an algorithm for sorting data which does not fit in memory. Finally, in Section 17.4, we discuss B-trees, a binary search tree variant especially suited for data stored on disk.