File Organization
• The database is stored as a collection of files.
• These files reside permanently on disks.
• File is a sequence of records.
• A record is a sequence of fields.
• Records are mapped onto disk blocks.
Blocks
• File is logically partitioned into fixed-length
storage units called blocks.
• Used for storage allocation and data transfer.
• Most databases use block sizes of 4 to 8
kilobytes by default, but many databases
allow the block size to be specified when a
database instance is created.
• Larger block sizes can be useful in some
database applications.
Blocks
• A block can contain several records.
• The exact set of records that a block contains
is determined by the form of physical data
organization.
Prerequisite
• no record is larger than a block
• each record is entirely contained in a single
block
Fixed Length records
• It assumes that the record size is fixed
• Here each file has records of only one type
• Different files are used for storing
different relations
• Fixed Length record structure is easiest to
implement.
Fixed Length records
Example
• Let us consider a file for storing instructor
records in an university database. Each record of
this file is defined as:
type instructor=record
ID varchar(5);
Name varchar(20);
Deptname varchar(20);
Salary numeric(8,2);
end
Fixed Length records
• Assume that each character occupies 1 byte and
that numeric (8,2) occupies 8 bytes.
• The instructor record is 53 bytes long. A simple
approach is to use the first 53 bytes for storing
the first record, the next 53 bytes for storing the
second record,
Issues in Fixed Length
Records
• Unless the block size happens to be a multiples
of 53, some records may cross block boundaries.
That is, first part of the record will be stored in
one block and the second part in another block.
It would then require two block accesses to read
or write such a record.
• It is difficult to delete a record from this
structure. The space occupied by the record to
be deleted must be filled with some other record
of the file, or we must have a way of marking
deleted records so that they can be ignored
solution
• To address the first issue, we should allocate only
as many records to a block that would fit entirely
in the block.
• This number can be computed easily by
dividing the block size by the record size,
and discarding the fractional part.
• The remaining bytes of each block is left unused.
Solution
• When a record is deleted, we could move the
record that came after it into the space formerly
occupied by the deleted record, and so on
• Every record following the deleted record is
moved one step ahead .
• Such an approach requires moving a large
number of records
Figure 1-After record 3 is deleted
Fixed Length records
• It might be easier simply to move the final
record of the file into the space occupied by
the deleted record
Free list
• We need to introduce an additional structure to
store the address of the first deleted record in the
file header.
• Use the first deleted record to store the address
of the second deleted record, and so on
• We can think of these stored addresses as
pointers since they “point” to the location of a
record.
• The deleted records forms a linked list, which is
often referred to as a free list
Free list
• The figure shows the free list, after records 1, 4, and 6
have been deleted.
Variable-Length Records
• Different records in the file have different sizes.
• Memory efficient.
• Access of the records is slower
Variable length records arise in database systems in
different ways :
• When multiple record types have to be stored in a
file.
• Storing records which allow variable length for one
or more fields.
• Records which allow repeating fields.
Issues in Variable Length Records
• To represent a single record in such a way
that individual attributes can be extracted
easily.
• To store variable-length records within a
block, such that records in a block can be
extracted easily
Solution
• The representation of a record with variable-length
attributes typically has two parts: an initial part with
fixed length attributes, followed by data for variable-
length attributes.
• Fixed-length attributes, such as numeric values,
dates, or fixed-length character strings are allocated
as many bytes as required to store their value.
• Variable-length attributes, such as varchar types, are
represented in the initial part of the record by a pair
(offset, length), where offset denotes where the data
for that attribute begins within the record, and length
is the length in bytes of the variable-sized attribute
Variable-Length Records
• In instructor record, the first three attributes
ID, name, and deptname are variable-length
strings, and the fourth attribute salary is a
fixed-sized number.
• We assume that the offset and length values
are stored in two bytes each, for a total of 4
bytes per attribute. The salary attribute is
assumed to be stored in 8 Bytes
Variable-Length Records: Slotted Page Structure
• Slotted page header contains:
– number of record entries
– end of free space in the block
– location and size of each record
• Records can be moved around within a page to keep
them contiguous with no empty space between them;
entry in the header must be updated.
• Pointers should not point directly to record — instead
they should point to the entry for the record in
header.
