File Organization and Indexing

Records, blocks and the blocking factor, heap, sorted and hashed file organisations with their access costs, primary, clustering and secondary indexes (dense vs sparse) and their sizes, multilevel indexes, B-trees and B+ trees (order from block size, height, search, insertion with splits, range queries), hash indexes (static and extendible), and how to choose an index.

Records, blocks and the blocking factor

Data on disk is read and written in blocks (pages). Because a block access costs far more than in-memory work, file and index performance is measured in block accesses.

\text{blocking factor } \text{bfr} = \left\lfloor\frac{B}{R}\right\rfloor \text{ (unspanned)}, \qquad \text{blocks } b = \left\lceil\frac{r}{\text{bfr}}\right\rceil

for block size $B$ , record size $R$ and $r$ records. Spanned records may cross block boundaries (no wasted space); unspanned records may not.

File organisations

Organisation	How records are placed	Equality search	Range search	Insert
Heap (unordered)	anywhere, usually at the end	$b/2$ average, $b$ if absent	$b$	$O(1)$
Sorted (sequential)	ordered on a key	$\lceil\log_2 b\rceil$ (binary search)	binary search + scan	expensive (shift or overflow area)
Hashed	block = $h(\text{key})$	~1 (+ overflow chains)	$b$	~1
Clustered	records with equal cluster key stored together	via index	scan	moderate

Indexes

An index is an auxiliary file of (search key, pointer) entries, much smaller than the data file, kept sorted (or hashed) for fast lookup.

Index	Built on	Dense/sparse	Per file
Primary	the ordering key field of a sorted file	sparse (one entry per block, the block's first key — the "anchor")	at most one
Clustering	an ordering non-key field	sparse (one entry per distinct value)	at most one (instead of primary)
Secondary	any non-ordering field	dense (one entry per record or per value with a list of pointers)	many

Multilevel indexes

Index the index: the first level is sorted, so build a sparse index over it, and so on, until one block remains. With index fan-out $f_o$ (entries per block), the number of levels is $\lceil\log_{f_o} r_1\rceil$ where $r_1$ is the number of first-level entries, and a lookup costs (levels + 1) block accesses. B+ trees are dynamic multilevel indexes.

B-trees and B+ trees

Balanced search trees with high fan-out, designed so each node is one disk block.

B-tree of order $p$ (max $p$ children):

every node has at most $p - 1$ keys; every non-root node has at least $\lceil p/2\rceil$ children ( $\lceil p/2\rceil - 1$ keys);
keys and their data pointers can live in any node;
all leaves are at the same depth.

B+ tree:

internal nodes hold only keys and child pointers (routing);
leaves hold every key with its data pointer, plus a pointer to the next leaf (sequential access);
because internal nodes store no data pointers, they fit more keys → larger fan-out → shorter trees.

A B+ tree: routing keys above, all data at the linked leaf level.

Order from block size: internal node with $p$ pointers of $P$ bytes and $p - 1$ keys of $K$ bytes: $pP + (p - 1)K \le B$ . Leaf with $q$ (key, record-pointer) pairs and one next-leaf pointer: $q(K + P_r) + P \le B$ .

Height: with fan-out $F$ and $N$ keys, height $\approx \lceil\log_F N\rceil$ . With $F = 100$ , three levels index a million keys; four levels, a hundred million.

Operations:

Search: one node per level, $O(\log_F N)$ block reads.
Range query: search for the lower bound, then follow leaf links.
Insert: insert into the leaf; if it overflows, split it in two and push the middle (first key of the new right leaf) up to the parent; splits can propagate to the root, which is how the tree grows taller.
Delete: remove from the leaf; on underflow, borrow from a sibling or merge with it.

Hash indexes

Static hashing: $M$ buckets, $h(k) \bmod M$ , overflow chains when buckets fill. Equality search ≈ 1–2 block accesses.
Extendible hashing: a directory of $2^d$ pointers indexed by the first $d$ bits of the hash; a full bucket splits and, if necessary, the directory doubles — no long overflow chains.
Linear hashing: buckets split one at a time in round-robin order.

Hash indexes support only equality predicates; range and ordered queries need a tree.