Storage & Indexing

Syllabus tag: Paper-II, Section-B, Topic IV.7 — Storage & Indexing, Indexing Structures

Definition

Indexing is an auxiliary data structure that speeds up data retrieval by avoiding a full table scan, at the cost of extra storage and slower writes (every index must also be updated on insert/update/delete).

File Organization (how records are stored)

• Heap (unordered) file: records inserted wherever there is space — fast insert, slow search (full scan)
• Sequential (sorted) file: records physically ordered by a key — fast range queries, costly inserts (may need reorganization)
• Hashed file: a hash function maps key → storage location — very fast exact-match lookup, poor for range queries

Index Classification

• Dense index: an index entry for every search-key value/record.
• Sparse index: an index entry only for some records (e.g., one per block) — requires the file to be sorted on that key.
• Multilevel index: an index on the index itself, reducing the number of disk block accesses for very large indexes — the structural idea behind B-Trees.

B-Tree and B+-Tree

• Both are balanced, multi-way search trees used almost universally for database indexes (not binary trees — high fan-out minimizes tree height and disk I/O).
• B-Tree: data pointers stored at both internal and leaf nodes.
• B+-Tree (preferred in practice): data pointers stored only at leaf nodes; internal nodes hold only key values for navigation. Leaf nodes are additionally linked in a sequential chain.
  • Why B+-Tree is preferred: (1) leaves linked sequentially → efficient range queries (BETWEEN, >) via a simple leaf scan after one root-to-leaf descent; (2) internal nodes store only keys (no data pointers) → higher fan-out per node → shorter tree → fewer disk accesses; (3) uniform leaf-level access time since all data pointers sit at the same depth.

Numerical — B+-Tree Order Calculation

Given: block size = 1024 bytes, search-key size = 12 bytes, block-pointer size = 8 bytes.

• Order p of the B+-tree internal node satisfies: p × 8 + (p−1) × 12 ≤ 1024
• 8p + 12p − 12 ≤ 1024 → 20p ≤ 1036 → p ≤ 51.8 → p = 51
• So each internal node can have up to 51 pointers and 50 keys.
• Height estimate: for N = 1,000,000 records with leaf fan-out ~51, height ≈ ⌈log₅₁(1,000,000)⌉ ≈ 4 levels — meaning any record is found in about 4 disk block accesses instead of scanning up to 1,000,000 blocks sequentially.

Hashing

• Static hashing: fixed number of buckets; a hash function maps key → bucket. Simple and fast, but performance degrades badly as the file grows (bucket overflow) or shrinks.
• Dynamic/Extendible hashing: bucket directory grows and shrinks with the data, avoiding the overflow problem of static hashing at the cost of an extra directory-lookup level.

MCQ Trap

• A table can have only one clustering/primary index (data can be physically sorted only one way) but many secondary indexes.
• B+-Trees are preferred over plain B-Trees specifically because of their superior support for range queries, not because they are asymptotically faster for exact-match lookup (both are O(log n)).

CSS Exam Angle

• FPSC 2025 Q6(b) explicitly asked about "the role of primary keys, foreign keys, and indexes" together — link indexing back to keys, don't treat it as an isolated topic.
• Expect either a conceptual comparison (primary vs secondary vs clustering index) or a small numerical computing B+-tree order/height from given block/key sizes.

Likely Questions

1. What is indexing? Why is it needed, and what is its cost?
2. Differentiate primary, clustering, and secondary indexes.
3. Explain why B+-Trees are preferred over B-Trees for database indexing.
4. Given a block size and key/pointer sizes, compute the order of a B+-tree.
5. Differentiate static and dynamic (extendible) hashing.

---

📘 Enrichment — Storage Basics & Classic Numericals

Storage Hierarchy

• Primary (volatile): CPU cache, RAM — nanoseconds, small, lost on power failure.
• Secondary (non-volatile, online): SSD, HDD — where the database lives; data moves in blocks/pages (typically 4–16 KB).
• Tertiary (archival): tape, cloud cold storage — backups.
• Key insight: a disk block access is ~100,000× slower than a RAM access, so DB performance ≈ number of block accesses — that is why every numerical below counts blocks.
• Buffer manager keeps frequently used blocks in RAM (replacement policies: LRU, MRU, clock).

RAID Levels (short-note favourite)

Record Organisation Terms

• Blocking factor (bfr) = ⌊Block size ÷ Record size⌋ = records per block (unspanned).
• Fixed-length vs variable-length records; spanned (a record may cross block boundary) vs unspanned.

Numerical 1 — Cost of Searching Without an Index (Elmasri-style)

Given: r = 30,000 records, record size R = 100 bytes, block size B = 1,024 bytes.

• bfr = ⌊1024 ÷ 100⌋ = 10 records/block
• Blocks b = ⌈30,000 ÷ 10⌉ = 3,000 blocks
• Linear search (heap file): average b/2 = 1,500 block accesses; worst case 3,000.
• Binary search (file sorted on the key): ⌈log₂ 3000⌉ = 12 block accesses.

Numerical 2 — Primary (Sparse) Index on the Same File

Key field V = 9 bytes, block pointer P = 6 bytes → index entry = 15 bytes.

• Index bfr (fan-out) = ⌊1024 ÷ 15⌋ = 68 entries/block
• Entries = one per data block = 3,000 → index blocks = ⌈3000 ÷ 68⌉ = 45 blocks
• Binary search on index: ⌈log₂ 45⌉ = 6 → +1 to read the data block = 7 block accesses (vs 12 without the index).

Numerical 3 — Secondary (Dense) Index on a Non-Ordering Key

• Entries = one per record = 30,000 → index blocks = ⌈30000 ÷ 68⌉ = 442 blocks
• Binary search: ⌈log₂ 442⌉ = 9 → +1 = 10 block accesses (vs 1,500 average linear search).

Numerical 4 — Converting the Dense Index into a Multilevel Index

Fan-out fo = 68.

• Level 1: 442 blocks → Level 2: ⌈442 ÷ 68⌉ = 7 blocks → Level 3: ⌈7 ÷ 68⌉ = 1 block (top).
• Levels t = 3 → access cost = t + 1 = 4 block accesses (vs 10 with binary search).
• General formula: t = ⌈log_fo (number of first-level entries)⌉.

Numerical 5 — Static Hashing with Collisions

h(k) = k mod 5, bucket capacity = 2 records. Insert keys 12, 7, 22, 15, 33, 40.

• 12 → 2 · 7 → 2 · 22 → 2 (bucket 2 full → overflow chain) · 15 → 0 · 33 → 3 · 40 → 0.
• Final: Bucket 0 = {15, 40}; Bucket 2 = {12, 7} + overflow {22}; Bucket 3 = {33}; Buckets 1, 4 empty.
• Lesson: skewed keys overload one bucket while others stay empty → motivates dynamic (extendible/linear) hashing.

B+-Tree Insertion Walk-through (order: max 3 keys per node)

Insert 10, 20, 30, 40:

1. Insert 10, 20, 30 → single leaf [10 | 20 | 30].
2. Insert 40 → leaf overflows (4 keys) → split into [10 | 20] and [30 | 40]; copy the first key of the right leaf (30) up into a new root.

       [30]
      /    \
[10|20] -> [30|40]      (leaves linked for range scans)

• In a B+-tree the separator is copied up (it stays in the leaf); in a B-tree it is moved up. Growth always happens at the root, so the tree stays perfectly balanced.

Index Selection Guidelines (practical, links to FPSC 2025 "role of indexes")

• Index primary keys (automatic) and foreign keys (speeds joins).
• Index columns used frequently in WHERE, JOIN, ORDER BY, GROUP BY.
• Avoid indexing small tables, low-selectivity columns (Gender), and heavily updated columns.
• Composite index (City, Name) helps queries filtering on City or City+Name, not on Name alone (leftmost-prefix rule).

---

✍️ Model Answers — Likely Questions

Q1. What is indexing? Why is it needed and what is its cost?

Definition: an index is an auxiliary structure of (search-key, pointer) entries that locates records without scanning the whole file — like a book's index.

Need: disk block access dominates query time; Numerical 1–4 show search cost falling from 1,500 to 4 block accesses for 30,000 records.

Costs: extra storage; slower INSERT/UPDATE/DELETE (index maintenance); optimizer complexity; poorly chosen indexes waste space.

Conclusion: index selectively — on keys and frequently searched/joined columns.

Q2. Differentiate primary, clustering and secondary indexes.

Use the classification table in the notes and add: primary and clustering indexes are sparse and require the file to be physically ordered, so only one can exist per file; secondary indexes are dense and many can exist. Numbers: primary index 45 blocks vs secondary index 442 blocks on the same file (Numericals 2 and 3).

Q3. Why are B+-trees preferred over B-trees?

1. Range queries: linked leaves allow a sequential scan after one descent.
2. Higher fan-out: internal nodes store keys only, so more keys per block → shallower tree → fewer disk accesses.
3. Uniform access: every search ends at leaf level — predictable cost.
4. Full scans: the leaf chain gives the whole table in key order without tree traversal.

Trade-off: keys are duplicated in internal nodes, and an exact-match search can never stop early at an internal node. Draw the small tree from the insertion walk-through.

Q4. Given block size and key/pointer sizes, compute the order of a B+-tree.

Internal node: p × P + (p − 1) × V ≤ B. With B = 1024, V = 12, P = 8 → 20p ≤ 1036 → p = 51.

Leaf node (each entry = key + record pointer, plus one next-leaf pointer): p_leaf × (V + Pr) + P ≤ B; with Pr = 8: 20 × p_leaf + 8 ≤ 1024 → p_leaf = 50.

Height for 1,000,000 records ≈ ⌈log₅₁ 1,000,000⌉ = 4 levels.

Q5. Differentiate static and dynamic (extendible) hashing.

• Static: fixed M buckets, h(k) = k mod M; simple, one-access lookups while small; growth causes overflow chains (Numerical 5), shrinkage wastes space; reorganizing needs full rehash.
• Extendible: a directory of 2^d pointers (d = global depth) using the first/last d bits of the hash; an overflowing bucket splits and only the directory doubles — no full rehash, performance stays near one access.
• Linear hashing: buckets split one at a time in round-robin order, no directory.
• Both hashing forms are poor for range queries → B+-tree for ranges, hash for exact matches.

---

⚡ 60-Second Revision

• Cost measured in block accesses; bfr = ⌊B ÷ R⌋.
• Sparse needs sorted file; dense does not. One primary/clustering index, many secondary.
• Multilevel index cost = levels + 1.
• B+-tree: data only in leaves, leaves linked, keys copied up on split.
• Hashing: best for equality; B+-tree: best for ranges.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2025 · Paper-II · Q6(b)(ii) · 5 marks

Q. Discuss the role of primary keys, foreign keys and indexes in a database schema. Explain their significance in ensuring data accuracy, enforcing referential integrity and improving query performance.

Ans.

• Primary key: uniquely identifies each row and cannot be NULL. It ensures accuracy by preventing duplicate records, and the DBMS builds an index on it automatically.
• Foreign key: a column that refers to the primary key of another table. It enforces referential integrity: a child row cannot point to a parent that does not exist, and deleting or updating a parent is controlled by rules (CASCADE, SET NULL, RESTRICT).
• Index: an auxiliary structure (B+ tree or hash) on one or more columns that lets the DBMS find rows without scanning the whole table. It improves query performance for searches, joins and sorting. Cost: extra storage and slower inserts, updates and deletes.
• Together: keys keep the data correct and consistent, and indexes make access fast. Index the primary key, the foreign keys used in joins and frequently filtered columns.