I recently decided to review the B-tree chapter (chapter 18, p 486 in 3ed) in Introduction Algorithms, and found that they call pages what I always referred to as blocks or clusters:

In order to amortize the time spent waiting for mechanical movements, disks access not just one item but several at a time. Information is divided into a number of equal-sized pages of bits that appear consecutively within tracks, and each disk read or write is of one or more entire pages. For a typical disk, a page might be $2^{11}$ to $2^{14}$ bytes in length. Once the read/write head is positioned correctly and the disk has rotated to the beginning of the desired page, reading or writing a magnetic disk is entirely electronic (aside from the rotation of the disk), and the disk can quickly read or write large amounts of data.

I always thought that pages are related to the virtual memory, although including swapping with the disk access. When the talk goes into the discussion of the filesystems in general, then I thought the information is divided into blocks rather than pages. Is he talking about virtual memory here? If I restate the whole paragraph in terms of blocks, would it be still correct, except for the provided sizes of the blocks?

  • 1
    $\begingroup$ The book has four different authors. $\endgroup$ May 28 at 22:21
  • $\begingroup$ I don't think that such distinctions are of interested to the authors of Introduction to Algorithms, who are theoreticians. $\endgroup$ May 28 at 22:23
  • 1
    $\begingroup$ It is common in database-related terminology to call page a contiguous set of disk blocks that is treated as the unit of transfer between main memory and permanent memory (e.g. disk). So the estimates of the access costs of persistent data structures, like trees or relations are usually in number of pages read and written. $\endgroup$
    – Renzo
    May 29 at 12:54
  • $\begingroup$ @Renzo, interesting, just opened Garcia-Molina et al Database Systems and saw that they use disk blocks and pages interchangeably. Makes sense, thank you! $\endgroup$
    – 2xMax
    May 29 at 16:43

I think you're right to be confused by this.

If their "pages" are sectors (= disk blocks), then they're right to say that pages "appear consecutively within tracks, and each disk read or write is of one or more entire pages", but their size range for pages makes no sense. The overwhelmingly most common sector size in 2009, when this textbook was published, was $2^9$ bytes. Also, I've never heard the term "page" used for a disk sector before.

If their pages are VM pages, then the size range makes more sense. But then they're wrong to suggest that the page size is a property of the disk, and it's not true that a swapped-out VM page will generally appear consecutively in a track. Also, disk reads and writes are only in units of VM pages if they come from the paging subsystem, and you shouldn't expect B-tree nodes to be paged in general (though they can be).

If their pages are clusters (filesystem allocation units), then the size range may be reasonable, but the rest is wrong. Clusters aren't generally read or written as a whole, they are just allocated as a whole. Also, I can't think of any reason to match the B-tree node size to the cluster size unless it's a filesystem B-tree (probably a directory index) and equating them simplifies the design or implementation of the file system.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.