At this point in the semester, we've seen many of the fundamental kinds of data structures (and will cover more, later in the semester). We've generally explored these data structures from the perspective of how they can be represented and manipulated in memory using C constructs. However, it is often desirable or necessary to store data structures in some other form, such as a file, where the methods of representation available are quite different. The general nature of the techniques is a special case of the general process of serialization (the process of converting a data structure into a sequential or ``serial'' sequence of bytes so that it can be sent over a network, printed, or stored on a ``serial'' device such as a CD-ROM or magnetic tape). This chapter does not focus on how serialized data structures can be efficiently accessed or manipulated in more general ways- for example, how to perform a FIND operation on a binary tree stored as a disk file. The only operations we will focus on are how to store and restore data structures.
Rather than try to give solutions for every possible situation and discuss every tradeoff between different approaches, this chapter attempts to illustrate several key themes in data structure serialization, and show how they can be used, either alone or together.
Currently, computer processing speeds are enormously faster than I/O speeds. A typical PC can perform one million arithmetic operations in less time than it can read a single byte of information from its disk. Much the same situation exists in networking (although the range of network speeds varies widely)- a typical PC can perform a considerable amount of computation in the time it requires to send an inquiry to a remote server and receive its response. This means that for many kinds of problems, if the answer can be computed by purely computational means, it is more efficient to recompute the answer every time it is needed than it would be store the answer in a file and consult the file (or to ask a remote server to compute the answer to the question and return the answer).
Therefore, before asking how a data structure can be represented in a file, it usually makes sense to ask whether it makes any sense to store the data structure at all! For the purpose of this chapter, we will assume that the answer to this question is always yes, but in practice this is an important question to consider.
There are many situations where the data or its structure is truly important, usually because it cannot be recomputed by any known means. There many other cases where the data is relatively easy to recompute, however, and the line between easy and hard to compute is changing constantly. Early computers used tables to compute trigonometric functions, but today the idea of storing such tables on disk rather than recomputing them as necessary seems unthinkable.