File Organization: Records, Blocks, Heap, Sorted and Hashed Files

A relation is stored as a file of records, and the file is stored on disk in fixed-size blocks (pages). The disk transfers whole blocks, so the cost of a database operation is measured in block accesses, not in record comparisons. File organization decides how records are packed into blocks and in what order the blocks hold them.

The quantities to compute are the blocking factor, the number of blocks a file needs, and the number of block accesses for a search under a given organization. These numbers are also the inputs to every index calculation in Indexing.

None within the GATE syllabus. Familiarity with logarithms and with the idea of a hash function helps.

Three primary file organizations.

Let $b$ be the number of blocks of the file. Costs count block accesses.

A search on a field other than the ordering or hash field gets no help from the organization: it is a scan of $b$ blocks.

Binary search over blocks. Read the middle block; if the key lies between its first and last record the search ends in that block, otherwise continue in one half. The worst case reads $\lfloor \lg b \rfloor + 1$ blocks. Many texts write this as $\lceil \lg b \rceil$; the two agree unless $b$ is a power of 2, where the exact worst case is one more (for $b = 1024$: 11 against 10). For this specified algorithm, use the exact worst case $\lfloor\lg b\rfloor+1$ for $b\ge1$. Treat $\lceil\lg b\rceil$ only as an approximation or a different model explicitly prescribed by the question, never an exact default.

Unspanned waste. With $\text{bfr} = \lfloor B / R \rfloor$, the unused space per block is $B \bmod R$ when $R \le B$, so the file wastes $b \cdot (B \bmod R)$ bytes, ignoring the partly filled last block.

Spanned size. With a pointer of $p$ bytes per block, the usable space is $B - p$, and the file needs $\lceil rR / (B - p) \rceil$ blocks.

Static hashing and overflow. If $r$ records are spread over $M$ buckets of capacity $c$ records, at least $\lceil r / c \rceil$ buckets are needed; real files allocate more (a fill factor below 1) because a skewed hash sends many records to one bucket and creates overflow chains, which cost extra accesses.

Example 1: blocking factor and file size. $B = 1024$ bytes, $R = 100$ bytes, $r = 30000$ records.

Example 2: search costs on that file. Searching for a key value:

Example 3: a non-key field on a sorted file. If the file is sorted on a non-key field and 25 records match, they sit in consecutive blocks: with $\text{bfr} = 10$ they span 3 or 4 blocks depending on where the run starts, so the cost is a binary search that locates the first block of the run plus up to 3 further blocks.

Example 4: static hashing with overflow (Figure 2). $h(k) = k \bmod 5$, one block of 2 records per bucket, keys 12, 7, 22, 3, 17, 8, 15, 2 in that order. Bucket 0: 15. Bucket 2 receives 12, 7, 22, 17, 2: the home block holds 12, 7, a first overflow block holds 22, 17, and a second holds 2. Bucket 3: 3, 8. Buckets 1 and 4 stay empty. A search for 2 reads 3 blocks; a search for 4 (not present) reads only bucket 4. The heap file of the same keys has 4 blocks and the sorted file holds $[2, 3], [7, 8], [12, 15], [17, 22]$.

Related material. Extendible hashing (Elmasri and Navathe 16.8; Korth 24.5, which spells it "extendable") avoids long overflow chains: a directory of $2^d$ pointers is indexed by $d$ bits of the hash value (the global depth), and each bucket records how many bits it really uses (its local depth). A full bucket with local depth below $d$ splits without touching the directory size; a full bucket with local depth $d$ doubles the directory first. Using the last bits of the key, capacity 2, and inserting 8, 3, 12, 5, 16 into an empty structure: 12 doubles the directory to $d = 1$ (buckets $\{8, 12\}$, $\{3\}$); 5 joins $\{3, 5\}$; 16 finds $\{8, 12\}$ full twice, since $8$, $12$ and $16$ end in 00, so the directory doubles to $d = 2$ and then to $d = 3$. The result has global depth 3, 8 directory entries and 4 buckets: $\{8, 16\}$ (bits 000), $\{12\}$ (100), an empty bucket for 010 and 110 (local depth 2), and $\{3, 5\}$ for all odd keys (local depth 1). Korth indexes the directory by a prefix (the first $i$ bits) of the hash value instead of the last bits; the doubling and splitting rules are the same, but the buckets hold different keys, so use the bit order the question gives.

Common misconceptions.