Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/37 done
  • SQL vs NoSQL
  • Indexes & Storage Engines
  • Replication
  • Sharding
  • Consistent Hashing
  • Object Storage & Uploads
  • Search & Inverted Indexes
Learn/System Design/Data & Storage

Indexes & Storage Engines

8 min Intermediate 8 steps

B-trees for reads, LSM trees for writes, and what each costs.

Query
id = 34
Rows read
1
Cost
O(n)
id 17row 0id 42row 1id 8row 2id 63row 3id 25row 4id 34row 5id 91row 6id 56row 7scan
current visited done
In this lessonStep 1 of 8
  1. The problem
  2. B-tree
  3. Range
  4. Composite
  5. Covering
  6. Write cost
  7. LSM tree
  8. Recap
Step 1 / 8problem

Without an index, read every row

Find the row with id = 34. Rows sit in the table in insert order, so the database has to check them one by one.

The cost grows with the table, not with the answer.

Key idea

A full table scan is O(n). An index is a separate structure that makes lookups fast.

←→ step·R replay·Space pause

You'll learn

  • Why a lookup without an index reads every row
  • How a B-tree answers equality and range queries in a few page reads
  • Apply the leftmost prefix rule to composite indexes
  • Weigh the write cost of every index
  • Contrast the B-tree and LSM tree write paths
Read the full notesHLD Building Blocks, 8