File Organization & Indexing

A database is stored in blocks on a disk, and a query's cost is essentially the number of blocks it reads.

The organising fact is that an index trades space and write cost for a shorter search path, and every question in this chapter reduces to counting the blocks a search must read.

A heap file reads them all. A sorted file reads a logarithmic number. A B-plus tree reads one per level plus one for the record. A hash file reads one, when it works.

The second organising fact is that the branching factor is set by arithmetic on the block size, and getting that arithmetic right is what most numerical questions actually test. A node holds as many pointers as fit in one block, and everything about tree height follows.

The third is that indexes are not free. Every insertion must update every index on the table, so a table with five indexes pays five times on writes to buy faster reads.

1. Records, Blocks and Blocking Factor

A disk transfers whole blocks, so the unit of cost is the block access, not the byte.

The blocking factor is how many records fit in a block, computed as the floor of block size divided by record size.

Spanned organisation lets a record cross a block boundary, avoiding waste but requiring a pointer to the continuation. Unspanned organisation does not, which is simpler and is what exam questions assume unless stated.

The number of blocks a file occupies is the ceiling of record count divided by blocking factor.

Three basic file organisations exist.

A heap file appends new records at the end. Insertion costs one block access; searching costs a full scan, averaging half the file for a successful search and all of it for an unsuccessful one.

A sorted file keeps records ordered on some field. Binary search finds a record in about ${\log }_{2}b$ block accesses for $b$ blocks, but insertion must maintain the order and is expensive.

A hash file computes the block address from a key, giving one access in the ideal case, but supports no range queries at all.

2. Kinds of Index

An index is an auxiliary structure mapping a search key to a record location, and three orthogonal distinctions matter.

A dense index has one entry per record. A sparse index has one entry per block, pointing at its first record.

A sparse index is smaller and therefore shallower, but it works only if the file is ordered on the index field, since finding a record requires scanning within the block the index points to.

A primary index is built on the ordering key field of an ordered file, and is sparse. There is at most one per file.

A clustering index is built on an ordering field that is not a key, so many records share a value.

A secondary index is built on any non-ordering field and must be dense, because the records with a given value are scattered and none can be found by scanning from a neighbour.

A secondary index on a non-key field needs an extra level of indirection, typically a bucket of record pointers per value, because the number of matching records varies.

A multilevel index treats the index itself as an ordered file and indexes it, repeating until the top level fits in one block. That is exactly what a B-plus tree automates.

3. B-Trees

A B-tree of order $p$ has at most $p$ children and at least the ceiling of $p/2$, except the root, which needs only two.

All leaves are at the same level, which is what keeps the height logarithmic and the worst case equal to the average case.

A B-tree stores data pointers in every node, internal nodes included.

A node with $p$ pointers holds $p-1$ keys, and each key is accompanied by a data pointer.

The order is determined by the block size. With block size $B$, key size $K$, tree pointer size $P$ and data pointer size $P_r$, the constraint is that $pP+(p-1)(K+P_r)$ must not exceed $B$.

A search can terminate at any level, which sounds like an advantage but is a small one, since the great majority of keys live in the leaves regardless.

4. B-Plus Trees

A B-plus tree stores data pointers only in the leaves. Internal nodes hold keys purely for navigation.

This is the decisive difference. Removing the data pointers from internal nodes lets each hold more keys, which raises the branching factor and lowers the height.

Leaves are linked in a list, so a range query finds the first matching key through the tree and then walks the leaf chain sequentially, without revisiting the internal nodes.

Keys may appear twice, once as a separator in an internal node and once in a leaf, which is not redundancy but the price of navigation.

The internal node order $p$ satisfies $pP+(p-1)K\le B$.

The leaf order $p_{leaf}$ is different, because a leaf holds key and data pointer pairs plus one pointer to the next leaf: $p_{leaf}(K+P_r)+P\le B$.

Computing these two separately is the most common source of lost marks, since candidates apply the internal formula to the leaves.

Every search costs exactly the height plus one, one access per level down to a leaf plus one for the record itself, which makes the cost uniform and predictable.

5. Insertion, Deletion and Height

Insertion places the key in the correct leaf. If the leaf overflows, it splits into two, and the middle key is copied up into the parent.

In a B-tree the middle key moves up; in a B-plus tree it is copied up, because the leaf must retain every key.

A split can cascade upward, and if the root splits, the tree grows a level. That is the only way a B-plus tree gains height, which is why growth is at the root rather than the leaves.

Deletion may cause underflow, repaired by borrowing a key from a sibling or merging with one. Merging can cascade and shrink the tree.

Height bounds follow from the fanout. A tree of height $h$ with minimum fanout $m$ holds at least about $m^h$ keys, and with maximum fanout $p$ holds at most about $p^h$.

Because the fanout is in the hundreds, real B-plus trees are three or four levels deep even for very large tables, which means any record is four block accesses away.

6. Hashing

Static hashing fixes the number of buckets at creation. A good hash function distributes keys evenly, and each bucket is one block.

Overflow chains form when a bucket fills, and performance degrades as chains lengthen, which is unavoidable once the file grows past its design size.

Extendible hashing uses a directory of $2^d$ entries, where $d$ is the global depth, indexed by the first $d$ bits of the hash value.

Each bucket carries a local depth $d^{\prime }$ not exceeding $d$, and $2^{d-d^{\prime }}$ directory entries point at it.

When a bucket overflows, it splits. If its local depth was less than the global depth, only the bucket splits and the directory is untouched. If they were equal, the directory doubles first.

Directory doubling is cheap because it copies pointers, not records, which is the whole point of the indirection.

Linear hashing avoids the directory entirely, splitting buckets in a fixed round-robin order regardless of which one overflowed, which trades some uniformity for the absence of a directory.

7. Worked Examples

Example 1. A file has 30,000 records of 100 bytes each. The block size is 1024 bytes and organisation is unspanned. Compute the blocking factor, the number of blocks, and the average block accesses for a successful linear search and for a binary search on a sorted file.

The blocking factor is the floor of $1024/100$, which is 10 records per block.

The wasted 24 bytes per block are the cost of unspanned organisation, about 2.3 percent here.

The number of blocks is the ceiling of $30000/10$, which is 3000.

A successful linear search reads on average half the file, so 1500 block accesses.

An unsuccessful linear search reads all 3000.

A binary search on a sorted file costs the ceiling of ${\log }_{2}3000$, which is 12 block accesses, since $2^{11}=2048$ and $2^{12}=4096$.

The improvement is from 1500 to 12, which is the argument for ordering, and an index will improve it further.

Example 2. With a block size of 1024 bytes, a key of 9 bytes, a tree pointer of 6 bytes and a data pointer of 7 bytes, compute the order of a B-tree and both orders of a B-plus tree.

For the B-tree, a node with $p$ pointers holds $p-1$ keys, each with a data pointer.

The constraint is $6p+(p-1)(9+7)\le 1024$, that is $6p+16p-16\le 1024$.

So $22p\le 1040$, giving $p\le 47.27$, hence $p=47$.

For the B-plus tree internal node, there is no data pointer.

The constraint is $6p+(p-1)9\le 1024$, that is $15p-9\le 1024$.

So $15p\le 1033$, giving $p\le 68.87$, hence $p=68$.

For the B-plus tree leaf, each entry is a key and a data pointer, plus one pointer to the next leaf.

The constraint is $p_{leaf}(9+7)+6\le 1024$, that is $16p_{leaf}\le 1018$.

So $p_{leaf}\le 63.6$, hence $p_{leaf}=63$.

Note the gain from removing data pointers: 68 against 47, a branching factor about 45 percent higher, which is why B-plus trees are used and B-trees are not.

Example 3. A B-plus tree has internal order 68 and leaf order 63, holding one million records. How many levels does it need, and how many block accesses does a point query cost?

Work from the leaves upward.

Leaves hold at most 63 entries each, so one million records need at least the ceiling of $1000000/63$, which is 15,874 leaves.

The level above holds at most 68 pointers per node, so it needs at least the ceiling of $15874/68$, which is 234 nodes.

The next level up needs the ceiling of $234/68$, which is 4 nodes.

The next needs 1 node, which is the root.

So the tree has 4 levels: root, two internal levels, and the leaf level.

A point query reads one block per level, which is 4, plus one block for the record itself, giving 5 block accesses.

Compare with the sorted file's 12 and the heap file's 1500.

Note also how slowly this grows. Multiplying the record count by 68 adds exactly one level, so a 68-million-record table needs 5 levels, and 6 accesses. That flatness is why B-plus trees dominate.

Example 4. Insert keys 10, 20, 30, 40 into an initially empty B-plus tree with internal order 3 and leaf order 3, showing each split.

Order 3 means an internal node holds at most 3 pointers and 2 keys, and a leaf holds at most 3 keys.

Insert 10, 20, 30. All fit in the single leaf, which is also the root. The tree is one node holding 10, 20, 30.

Insert 40. The leaf would need 4 keys, which overflows.

Split the leaf. With 4 keys, the split puts 10 and 20 in the left leaf and 30 and 40 in the right leaf.

Copy the first key of the right leaf, which is 30, up into a new root.

The result is a root holding the single key 30, with a left child holding 10 and 20, and a right child holding 30 and 40.

Note that 30 appears twice, once as a separator in the root and once as data in the leaf. This is the defining behaviour of a B-plus tree.

Contrast with a B-tree. There, 30 would move up rather than being copied, appearing only in the root, and the right child would hold only 40. The leaves would no longer contain every key.

The two leaves are linked, so a range query for keys above 15 finds the left leaf, reads 20, and follows the link to read 30 and 40 without touching the root again.

Example 5. An extendible hash index has global depth 2 and four buckets, one per directory entry, each with local depth 2. Bucket 00 overflows. Describe what happens, then describe the different outcome if its local depth had been 1.

Case one: local depth equals global depth, both 2.

Only one directory entry points at this bucket, so splitting it would leave nowhere to record the distinction.

The directory must double first, becoming 8 entries indexed by 3 bits, and the global depth becomes 3.

Every existing bucket is now pointed at by two entries, and their local depths stay at 2, unchanged.

Now split bucket 00 into buckets for 000 and 100, both with local depth 3, redistributing its records by their third hash bit.

No records outside that bucket move, which is the property that makes extendible hashing worthwhile.

Case two: local depth 1, global depth 2.

Two directory entries point at this bucket, since $2^{2-1}=2$.

There is already spare directory capacity to distinguish the halves, so no doubling is needed.

Split the bucket into two, each with local depth 2, and repoint one of the two directory entries at the new bucket.

The directory size and global depth are unchanged.

The rule to remember: double the directory only when the splitting bucket's local depth equals the global depth.

Example 6. A table has 500,000 records and five secondary indexes. Compare the cost of a point query and of an insertion, and state the design consequence.

A point query using one index costs the index's height plus one for the record. With a fanout in the hundreds, that is about 4 accesses.

Without any index the same query costs a full scan. At 10 records per block that is 50,000 block accesses.

So each index buys a factor of over ten thousand on the queries it serves.

Now consider an insertion.

Writing the record itself costs one block access, or two counting the read.

But every one of the five indexes must be updated, because each must now contain an entry for the new record.

Each index update costs a traversal plus a write, so about 5 accesses each, giving 25 for the five, and more if any node splits.

The insertion therefore costs roughly 27 accesses instead of 2, a factor of thirteen.

The design consequence is that indexes should be chosen against the actual query mix. An index that serves no query is pure cost, and on a write-heavy table the total index count is a direct throughput constraint.

This is also why bulk loading drops indexes first and rebuilds them afterwards, since building an index once over sorted data is far cheaper than maintaining it through half a million individual insertions.

Summary

An index trades space and write cost for a shorter search path, and every question here counts block accesses.

Blocking factor is the floor of block size over record size, and block count is the ceiling of records over blocking factor. Heap files scan, sorted files binary search in about ${\log }_{2}b$, hash files reach a record in one access but support no ranges.

A dense index has an entry per record and a sparse index one per block. Primary indexes are sparse on the ordering key; clustering indexes sit on a non-key ordering field; secondary indexes must be dense, and on a non-key field need a bucket of pointers.

A B-tree stores data pointers in every node and satisfies $pP+(p-1)(K+P_r)\le B$. A B-plus tree stores them only in leaves, so internal nodes satisfy $pP+(p-1)K\le B$ and leaves satisfy $p_{leaf}(K+P_r)+P\le B$. Computing the two B-plus orders separately is essential.

Removing data pointers from internal nodes raises the branching factor substantially, which is why B-plus trees won. Linked leaves make range queries sequential.

A leaf split copies the middle key up in a B-plus tree and moves it up in a B-tree. The tree gains height only when the root splits.

Real trees are three or four levels deep, so a point query is four or five block accesses regardless of table size, and multiplying the row count by the fanout adds exactly one level.

Extendible hashing indexes a directory of $2^d$ entries by the first $d$ hash bits, and doubles the directory only when the splitting bucket's local depth equals the global depth. Linear hashing avoids the directory by splitting in a fixed order.

Every index must be updated on every insertion, so an index that serves no query is pure cost, and bulk loads drop and rebuild rather than maintain. Choosing indexes is therefore a decision about the query mix, not a decision that can be made from the schema alone.