Real-life analogy: The textbook index

Finding 'normalization' in a 900-page textbook: (1) No index = read every page = 900 reads. (2) With index: look up N, find normalization → page 423. Two steps. A database index works identically: small, sorted structure mapping search key values to disk block addresses.

B+ Tree structure and height

\text{Height} = \lceil \log_{\lceil m/2 \rceil}(N) \rceil \quad \text{where } m = \text{order (max pointers per node)}

import math

def bplus_height(n_records: int, order: int) -> int:
    """Max height of B+ tree for n records with given order."""
    min_fanout = math.ceil(order / 2)
    if n_records <= order - 1:
        return 1
    return math.ceil(math.log(n_records, min_fanout))

# B+ tree examples
print(f"1M records, order 100:  height = {bplus_height(1_000_000, 100)}")    # 4
print(f"1B records, order 100:  height = {bplus_height(1_000_000_000, 100)}") # 5
print(f"10K records, order 10:  height = {bplus_height(10_000, 10)}")         # 5

# B+ tree vs sequential scan comparison
n = 1_000_000
order = 100
height = bplus_height(n, order)
print(f"
For {n:,} records with B+ tree order {order}:")
print(f"  Sequential scan: up to {n:,} block reads")
print(f"  B+ tree lookup:  {height} disk reads (height = {height})")
print(f"  Speedup: {n//height:,}x")

Index types

GATE: Clustered vs non-clustered index: Clustered index physically orders table data — only ONE per table. Non-clustered index is a separate structure with pointers — multiple allowed. Primary key is automatically clustered in MySQL InnoDB. PostgreSQL: use CLUSTER command. B+ trees support both; hash indexes are always non-clustered.

Inside a B+ tree: internal nodes vs leaf nodes

A B+ tree separates routing from storage. Internal nodes contain only keys and child pointers — they exist purely to direct the search downward. Leaf nodes contain every key along with record pointers (or the records themselves), and are chained into a sorted linked list. Because all data lives at the leaf level, every lookup travels root → leaf, so every search costs exactly the height of the tree — uniform, predictable I/O.

The order comes directly from the disk block size, and this is why B+ trees dominate disk-based databases. Example: with a 4 KB block, an 8-byte key, and an 8-byte pointer, an internal node fits roughly 4096 / 16 ≈ 256 pointers. A fan-out of 256 means 3 levels address 256³ ≈ 16.7 million records and 4 levels address over 4 billion. Height — and therefore disk reads per lookup — stays at 3–4 even for enormous tables.

Insertion, node splits, and deletion

Insertion: descend to the correct leaf and insert the key in sorted position. If the leaf overflows, it splits into two half-full leaves, and the smallest key of the new right leaf is copied up into the parent as a separator. If the parent overflows in turn, it also splits — but an internal-node split moves its middle key up instead of copying it. Splits can cascade to the root; when the root splits, the tree grows one level taller. Deletion is the mirror image: an underfull node first tries to borrow a key from a sibling, and merges with the sibling if borrowing is impossible — a root merge shrinks the height by one.

Classic GATE trap: copy up vs move up: A leaf split copies the separator key upward — the key exists in both the leaf and the parent afterward (it must, because leaves hold all the data). An internal split moves the middle key upward — it appears only in the parent. Exams regularly test exactly this distinction with "how many keys does the parent contain after insertion?" questions.

• B+ tree invariant: every node except the root is at least half full (⌈p/2⌉ pointers) — this is what guarantees the logarithmic height bound.
• All leaves are always at the same depth — a B+ tree is perfectly height-balanced by construction, unlike a binary search tree.
• Sequential inserts (e.g., auto-increment keys) always hit the rightmost leaf; databases optimize this with a rightmost-split heuristic that keeps pages ~100% full instead of 50%.

Hashing: static, extendible, and linear

Hash-based file organization trades range-query ability for O(1) equality lookups. The GATE syllabus covers three schemes, distinguished by how they handle growth:

GATE: extendible hashing mechanics: Global depth d = number of hash bits the directory uses (directory size 2^d). Local depth ℓ of a bucket = bits actually distinguishing its contents. When a bucket with ℓ < d overflows, it splits and only pointers update. When a bucket with ℓ = d overflows, the directory must double first (d becomes d+1). Questions almost always hinge on whether the directory doubles.

When indexes hurt: the write penalty

Indexes are not free. Every INSERT, UPDATE, and DELETE must also maintain every index on the table — a table with six indexes performs seven writes per inserted row. Over-indexing is one of the most common real-world performance mistakes: it silently taxes every write, bloats storage, and slows down backups and replication.

• Index what you filter, join, and sort on. Columns in WHERE, JOIN ... ON, and ORDER BY clauses are candidates; everything else usually is not.
• Composite index column order matters. Put equality-tested columns first, the range-tested column last: an index on (city, age) serves WHERE city = 'Pune' AND age > 30, but an index on (age, city) cannot use the city condition efficiently.
• Covering indexes skip the table entirely. If the index contains every column a query needs, the database answers from the index alone (an index-only scan) — often a 10× win on hot queries.
• Low-cardinality columns make poor single-column indexes. An index on is_active with two distinct values barely narrows the search; the optimizer will usually ignore it.
• Audit unused indexes. PostgreSQL's pg_stat_user_indexes and MySQL's sys.schema_unused_indexes reveal indexes that cost writes but never serve reads.

Practice questions (GATE-style)

1. B+ tree of order 5 with 500 records. What is the maximum height? (Answer: min fanout = ceil(5/2) = 3. ceil(log₃(500)) = ceil(5.66) = 6.)
2. Why does B+ tree support range queries better than a B-tree? (Answer: B+ tree leaf nodes form a linked list — traverse leaves sequentially after finding start key. B-tree stores data in internal nodes too, requiring full tree traversal for range queries.)
3. Hash index on Salary supports which query efficiently? (Answer: Only equality: WHERE Salary = 50000. Cannot support WHERE Salary > 50000 — hash scatters nearby values to different buckets.)
4. Difference between dense and sparse index? (Answer: Dense: one entry per record — fast lookup, more space. Sparse: one entry per disk block — less space, only works on ordered data.)
5. Relation has 10,000 records, B+ tree order = 50. What is the height? (Answer: min fanout = 25. ceil(log₂₅(10000)) = ceil(2.86) = 3. Just 3 disk accesses!)
6. A B+ tree leaf of order 4 (max 3 keys) contains 10, 20, 30. Insert 25 — what happens? (Answer: Overflow → the leaf splits into [10, 20] and [25, 30], and 25 — the smallest key of the right leaf — is COPIED up to the parent as a separator. 25 now appears in both the parent and the leaf, because leaf splits copy the separator rather than moving it.)
7. Block size 4096 B, search key 12 B, block pointer 8 B. Maximum order of an internal B+ tree node? (Answer: p pointers + (p−1) keys must fit in one block: 8p + 12(p−1) ≤ 4096 → 20p ≤ 4108 → p = 205.)
8. In extendible hashing, when does the directory double? (Answer: Only when a bucket whose local depth equals the global depth overflows. The split needs one more distinguishing bit than the directory has, so global depth increments and directory size doubles from 2^d to 2^(d+1). If local depth < global depth, the bucket splits and only directory pointers are updated.)