Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DBMS

Indexing, B+ Trees and SQL vs NoSQL

Why indexes?

Without an index, SELECT * FROM users WHERE email = 'a@x.com' reads every row — a full table scan, O(n). An index is a separate sorted structure (like the index at the back of a book) that finds the row in O(log n).

For 10 million rows: a scan reads 10,000,000 rows; a B+ tree index needs about 3–4 page reads.

CREATE INDEX idx_users_email ON users(email);
CREATE UNIQUE INDEX idx_users_phone ON users(phone);
DROP INDEX idx_users_email ON users;          -- MySQL syntax

B-tree vs B+ tree

Databases store data in pages (blocks, e.g. 16 KB). Trees with a high fan-out (hundreds of children per node) keep the height tiny, so few disk reads are needed.

B-tree B+ tree
Data stored in every node leaf nodes only
Internal nodes keys + data keys only (more fit per page → shorter tree)
Leaves linked? no yes, a linked list
Range queries slower (tree traversal) fast — find the start, walk the leaves
                [ 30 | 60 ]
              /      |      \
      [10|20]     [40|50]     [70|80]      ← internal: keys only
        ↓            ↓           ↓
  [5,10,20] ⇄ [30,40,50] ⇄ [60,70,80,90]   ← leaves: all keys + row pointers, linked

That's why almost every relational database (MySQL InnoDB, PostgreSQL, Oracle) uses B+ trees. Query WHERE age BETWEEN 30 AND 50 → find 30, then follow leaf links.

Hash index: O(1) for exact equality, useless for ranges and sorting (used by MEMORY tables, some key-value stores).

Clustered vs non-clustered

Clustered Non-clustered (secondary)
What the table rows are stored in index order separate structure with key → pointer to the row
How many one per table many
In InnoDB the primary key leaves store the primary key, then a second lookup
Best for range scans on the key lookups on other columns

Composite indexes and the leftmost-prefix rule

CREATE INDEX idx_city_age ON users(city, age);

Sorted by city, then age within a city.

Query Uses index?
WHERE city = 'Delhi' ✅
WHERE city = 'Delhi' AND age > 25 ✅
WHERE age > 25 ❌ (city, the leftmost column, missing)
WHERE city LIKE '%hi' ❌ (leading wildcard)

Put the column used for equality first and the range column last.

Covering index

If the index contains every column the query needs, the DB answers from the index alone without touching the table:

-- index on (city, age) covers this
SELECT age FROM users WHERE city = 'Delhi';

When indexes don't help (or hurt)

Check with EXPLAIN

EXPLAIN SELECT * FROM users WHERE email = 'a@x.com';

Look at type (ALL = full scan ❌, ref/range/const ✅), key (which index) and rows (rows examined). MongoDB: db.users.find({email}).explain("executionStats") — COLLSCAN is bad, IXSCAN is good.

NoSQL

"Not only SQL" — databases without fixed tables, built to scale horizontally and handle flexible data.

Type Data shape Examples Good for
Document JSON-like documents MongoDB, Firestore, CouchDB user profiles, catalogs, content
Key-value key → value Redis, DynamoDB caching, sessions, counters
Wide-column rows with dynamic columns, grouped in families Cassandra, HBase huge write-heavy data, time series, logs
Graph nodes + edges Neo4j social networks, recommendations, fraud

Same data in both worlds:

-- SQL: two tables + a join
SELECT * FROM orders o JOIN order_items i ON i.order_id = o.id WHERE o.id = 7;
// MongoDB: one document with embedded items
{ _id: 7, user: "aman", items: [{ sku: "pen", qty: 2 }, { sku: "book", qty: 1 }] }

SQL vs NoSQL

SQL (relational) NoSQL
Schema fixed, defined upfront flexible / schema-less
Data model tables, rows, joins documents, key-value, columns, graphs
Scaling mostly vertical (bigger machine); sharding is harder horizontal (more machines) built in
Transactions strong ACID often BASE / eventual consistency (many now offer ACID too)
Query language standard SQL database-specific APIs
Joins powerful limited — you embed or denormalize
Examples MySQL, PostgreSQL, Oracle MongoDB, Redis, Cassandra, Neo4j

BASE = Basically Available, Soft state, Eventually consistent — the trade-off many distributed NoSQL stores make (see CAP Theorem and Consistency).

How to choose

Interview one-liners

More DBMS notes