Organization of Records into Blocks

1. As data is transferred in blocks, it is convenient to assign records to blocks in such a way that a block contains related records.
   • For fixed-length record representation of variable-length records we may use several records to represent one variable-length record.
   • We'd like to store these records together.
   • However, when a new account is opened the block may be full.
   • We must then either move a record or abandon our goal of grouping.
   • An alternative uses a bit more space, but gives greater efficiency in data access.
   • We assign one bucket to each bname value.
   • This bucket holds the entire variable-length record for the corresponding bname value.
   • A bucket consists of as many blocks as necessary, but buckets never share blocks (figure 7.13)
   • The first record in the bucket holds the bname value for that bucket.
   • Subsequent records are repeating fields in the same bucket. (So no need to chain records together.)
2. In figure 7.13, a bucket occupies one block. In a more realistic example, a bucket may require several blocks.
   • We chain blocks of a bucket together.
   • Block header at beginning of each block and pointers - see figure 7.14.
   • We can have a chain of unused (empty) blocks for insertions.
   • However, we would like all the blocks for a bucket to be stored on the same cylinder of a disk.
   • If we reserve emptied blocks for the buckets that release them, we could get a lot of empty blocks, if deletion is more frequent than insertion.
   • In practice this tends to work well.
   • When buckets become sufficiently disorganized that performance begins to suffer, the database can be re-organized.
     • Database is copied to tape.
     • Database is reloaded with blocks relocated so that buckets are no longer fragmented, and reasonable room for bucket growth exists.