DBMS Notes
This unit covered how databases physically store data and retrieve it efficiently. The fundamental trade-off throughout this unit is between storage...
Core Concepts Overview
This unit covered how databases physically store data and retrieve it efficiently. The fundamental trade-off throughout this unit is between storage overhead and access speed — indexes consume additional disk space but dramatically reduce query time.
Single-Level Indexing
| Index Type | Description | Records Indexed | Entries |
|---|---|---|---|
| Primary Index | On ordering key of sorted file | One entry per block (sparse) | Fewer entries |
| Clustering Index | On non-key ordering field | One entry per distinct value | Moderate entries |
| Secondary Index | On non-ordering field | One entry per record (dense) | Many entries |
Dense Index: One index entry for every record in the data file — faster search but more space.
Sparse Index: One index entry for each disk block — smaller index but requires block-level search after locating the block.
Multi-Level Indexing and B-Trees
When a single-level index becomes too large to fit in memory, we build an index on the index — creating multiple levels. This naturally leads to tree-structured indexes.
B-Tree Properties
B+ Tree (Most Common in Practice)
Key Differences from B-Tree
- ALL data records (or pointers to records) are in LEAF nodes only
- Internal nodes contain only keys (for navigation)
- Leaf nodes are linked in a linked list (supports range queries)
- More keys fit in internal nodes → shorter tree → fewer disk reads
Why databases prefer B+ Trees
- Range queries follow leaf-level linked list (efficient)
- Higher fanout in internal nodes (more keys per node since no data pointers)
- All searches follow same-length path (predictable I/O cost)
Hashing Techniques
Static Hashing
| Structure | Fixed number of buckets (B) |
| Hash function: h(key) | bucket number (0 to B-1) |
| Problem | Performance degrades as load factor increases |
Dynamic Hashing
| Technique | How It Grows | Directory? | Splitting |
|---|---|---|---|
| Extendible Hashing | Doubles directory | Yes (global/local depth) | Split one bucket at a time |
| Linear Hashing | Adds one bucket at a time | No | Split in round-robin order |
| Global depth (d) | number of bits used from hash value to index directory |
| Local depth | number of bits that actually distinguish a bucket's entries |
| When a bucket overflows | if local depth < global depth, split bucket |
Query Processing Steps
| Step 1 | Parsing and Translation |
| SQL query | parse tree → relational algebra expression |
| Step 2 | Optimization |
| Step 3 | Execution |
Query Optimization Strategies
| Strategy | Description |
|---|---|
| Push selection down | Apply WHERE conditions as early as possible (reduces intermediate result size) |
| Push projection down | Remove unnecessary columns early (reduces tuple width) |
| Reorder joins | Choose join order that minimizes intermediate result sizes |
| Use indexes | If an index exists on the selection attribute, use index scan instead of table scan |
| Pipelining | Pass tuples directly to next operator without materializing intermediate results |
Cost Estimation Fundamentals
Key Metrics
- Number of block transfers (b): reading/writing disk blocks
- Number of seeks (s): moving disk arm to correct track
- Total cost ≈ b × transfer_time + s × seek_time
Typical values
Transfer time: ~0.1 ms per block
Seek time: ~4 ms per seek
→ Seeks dominate cost! Minimizing seeks is critical.
Cost of operations
Linear search (no index): b_r block transfers + 1 seek
Binary search (sorted file): ⌈log₂(b_r)⌉ × (1 transfer + 1 seek)
Primary index search: (h_i + 1) × (1 transfer + 1 seek) [h_i = index height]
B+ tree search: (h + 1) × (1 transfer + 1 seek)
Hash search: 1 seek + 1 transfer (ideal)
Join Algorithms Comparison
| Algorithm | Cost | Best When |
|---|---|---|
| Nested Loop Join | O(n × m) block transfers | Small relations, no indexes |
| Block Nested Loop | O(n × m / B) | More memory buffers available |
| Index Nested Loop | O(n × h) where h is index height | Index exists on join attribute |
| Sort-Merge Join | O(n log n + m log m) | Both relations large, join on sorted attribute |
| Hash Join | O(n + m) | Equality joins, sufficient memory for partitioning |
Key Formulas to Remember
| Concept | Formula |
|---|---|
| B+ Tree height | h = ⌈log_p(n)⌉ where p = order, n = records |
| Hash bucket address | h(K) mod B where B = number of buckets |
| Binary search cost | ⌈log₂(b)⌉ block accesses |
| Extendible hash directory size | 2^d entries (d = global depth) |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Unit 5 Summary — Storage & Indexing.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Database Management Systems (DBMS) topic.
Search Terms
dbms, database management systems (dbms), unit, summary, unit 5 summary — storage & indexing
Related Database Management Systems (DBMS) Topics