DBMS & SQL chapters
  1. 01Database Concepts & Relational Architecture
  2. 02Comprehensive SQL Engine & Joins
  3. 03Functional Dependencies & Normalization
  4. 04Transactions & Concurrency Control
  5. 05Indexing, B+ Trees & NoSQL Systems

Chapter 5 · Database Systems

Indexing, B+ Trees & NoSQL Systems

3 topics in 2 parts

Key ideas

Key: 50 Key: 20 | 35 Key: 70 | 85 [10, 15, 20] ➜ [25, 30, 35] ➜ [55, 60, 70] ➜ [75, 80, 85]
Indexing, B+ Trees & NoSQL Systems
Evaluation ParameterStandard Relational PatternProduction Optimization Impact
Storage Engine LayerDisk page blocks & buffer pool cacheMinimizes random disk I/O via sequential prefetching
Index UtilizationB+ Tree logarithmic search $O(\log N)$Avoids full table scans across millions of rows
Concurrency & LocksRow-level shared (S) and exclusive (X) locksPrevents race conditions while maximizing read throughput
Failure RecoveryWrite-Ahead Logging (WAL) / Undo-RedoGuarantees durability and instant crash recovery
External View 1 (Web User Portal) External View 2 (Finance & Billing) External View 3 (Analytics & BI) ↕ LOGICAL DATA INDEPENDENCE ↕ CONCEPTUAL / LOGICAL SCHEMA LEVEL Entities, Relational Tables, Attributes, Constraints, Foreign Keys & Business Rules ↕ PHYSICAL DATA INDEPENDENCE ↕ INTERNAL / PHYSICAL STORAGE LEVEL B+ Tree Indexes, Hashing, Page Blocks, Compression, Record Offsets & RAID Storage
Indexing, B+ Trees & NoSQL Systems

All 3 topics in Indexing, B+ Trees & NoSQL Systems

  1. Indexing

    • Database Indexing Principles
    • B+ Trees Indexing

  2. NoSQL

    • SQL vs NoSQL & CAP Theorem