Indexing & Query Processing
Indexes speed up data retrieval. B+ trees are the dominant index structure. GATE tests B+ tree operations, dense vs sparse indexes, hashing, and query cost estimation.
Key Points
- ·Primary index: on ordering key of ordered file; one entry per disk block (sparse)
- ·Secondary index: on non-ordering or non-key field; one entry per record (dense)
- ·Clustering index: on non-key, ordering field; sparse — one entry per distinct value block
- ·Dense index: one entry per search-key value; Sparse index: one entry per block
- ·B+ tree: balanced, all data in leaves, leaves linked — supports range queries
- ·B+ tree order n: internal nodes have between n/2 and n pointers; leaves between (n-1)/2 and n-1 values
- ·B+ tree height: O(log_n(N)) where N = number of records
- ·Hashing: good for equality queries, poor for range queries; extendible hashing handles overflow
- ·Query cost unit: number of block I/Os (disk accesses dominate)
Why Indexes?
Analogy: Finding a word in a 1000-page dictionary without the alphabetical index = scan all 1000 pages. With the index = go directly to page 342.
An index is a small data structure that lets you find records fast without scanning the entire table.
Types of Indexes
Primary Index (Ordered file, Key field)
File is sorted on a KEY field.
Index has ONE entry per DISK BLOCK (not per record).
→ SPARSE index (fewer index entries than records)
Example:
Block 1: RollNo 101-110
Block 2: RollNo 111-120
Block 3: RollNo 121-130
Primary Index:
┌──────────┬────────┐
│ RollNo │ Block │
│ 101 │ 1 │ ← first record in block 1
│ 111 │ 2 │
│ 121 │ 3 │
└──────────┴────────┘
Secondary Index (Non-key, Unordered)
File is NOT sorted on this field.
ONE entry per RECORD VALUE → DENSE index
Often uses buckets of pointers for repeated values.
Slower for range queries (records scattered on disk).
Clustering Index (Non-key, Ordered)
File sorted on a NON-KEY field (e.g., Department).
One entry per DISTINCT VALUE → sparse-like.
Multiple records per value (e.g., 50 employees in CS dept).
B+ Tree — The Most Important Index Structure
Analogy: A B+ tree is like a well-organised library catalogue. The top shelves (internal nodes) just have labels to direct you. The bottom shelf (leaf nodes) has the actual book locations, and all bottom shelves are connected in a chain.
[40 | 70] ← Root (internal node, just routing)
/ | \
[10|20] [50|60] [80|90] ← Internal nodes
/ | \ | |
[...][...][...][...][...] ← Leaf nodes (actual data/pointers)
↔ ↔ ↔ ↔ ↔ ← All leaves linked!
Properties (order n)
Internal nodes:
Maximum n pointers (n-1 keys)
Minimum ⌈n/2⌉ pointers (except root: minimum 2)
Leaf nodes:
Maximum (n-1) key-pointer pairs
Minimum ⌈(n-1)/2⌉ pairs
ALL leaves at same depth → perfectly balanced tree
Height ≈ log_{⌈n/2⌉}(N)
Operations
Search: O(log N) — follow path from root to leaf
Insert: Search for leaf → insert → if overflow: SPLIT leaf, push middle key up → split propagates up
Delete: Search → delete → if underflow: MERGE with sibling or REDISTRIBUTE
GATE Calculation Example
1000 records, block = 1024 bytes, key = 4 bytes, pointer = 6 bytes
Internal node capacity: n = ⌊1024 / (6+4)⌋ = 102 pointers
Leaf node capacity: ⌊1024 / (4+6)⌋ = 102 entries per leaf
Minimum fan-out: ⌈102/2⌉ = 51
Height for 1000 records:
Level 1 (root): up to 102 children
Level 2: up to 102 × 102 = 10404 leaves > 1000
→ Height = 2 levels above leaves = 3 total levels → 3 I/Os per search
Hashing
Static Hashing
h(key) mod M → bucket number
Good for EQUALITY queries: "Find student with ID = 105"
Bad for RANGE queries: "Find students with ID between 100 and 200"
Extendible Hashing
Dynamic — grows as data grows
Uses a DIRECTORY of size 2^d (global depth d)
Each bucket has LOCAL depth
On overflow: split bucket, double directory if needed
No long overflow chains
Query Processing Cost
The unit of cost = number of block I/Os (disk is slow!).
| Join Algorithm | When best | Cost |
|---|---|---|
| Simple Nested Loop | Always works | n_r × n_s block I/Os |
| Block Nested Loop | Memory available | ⌈n_r/M⌉ × n_s I/Os |
| Sort-Merge Join | Both relations sortable | Sort + merge = O(n log n) |
| Hash Join | Hash table fits in memory | 3(n_r + n_s) I/Os |
Build hash table on SMALLER relation; probe with larger relation.
Dense vs Sparse Summary
Dense: One index entry per RECORD (every search key has an entry)
→ More index entries, faster exact lookup, larger index size
Sparse: One index entry per BLOCK (only first record of each block)
→ Fewer entries, smaller index, only works for ordered files
→ Must scan block after finding the right block pointer
Quick Check
Q1. A B+ tree of order 4 (max 4 pointers per internal node). How many keys minimum in an internal node (not root)? Answer: Internal node minimum = ⌈4/2⌉ = 2 pointers → 1 key minimum
Q2. Which is better for query "Find all employees with salary between 50K and 80K" — B+ tree or hash index? Answer: B+ tree — leaf nodes are linked in sorted order, enabling efficient range scan. Hash has no ordering.
Q3. Secondary index is dense. Why? Answer: File is not sorted on the indexed field, so records of the same value are scattered. To find any specific value, we need a pointer for every record — hence dense.
Key Formulas
- B+ tree height: h ≤ ⌈log_{⌈n/2⌉}(N)⌉
- Entries per internal node: Between ⌈n/2⌉ and n pointers
- Hash join cost: 3(b_r + b_s) block I/Os (build + probe + output)
GATE Exam Tips
- ★B+ tree all leaves at same depth — always balanced; B-tree stores data in internal nodes too (different!).
- ★GATE asks max/min keys in B+ tree node — always apply the ⌈n/2⌉ formula for minimum.
- ★Dense index: every search key has an entry. Sparse: one per block (only works for ordered files).
- ★Range queries: B+ tree excellent (linked leaves), hashing terrible (no ordering).
Finished reading this topic?
Mark it complete to track your study progress.