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)
- Every INSERT/UPDATE/DELETE must also update every index → slower writes, more storage.
- Low-cardinality columns (gender, boolean) — the DB often scans anyway.
- Functions on the column:
WHERE YEAR(created_at) = 2025can't use an index on created_at; writecreated_at >= '2025-01-01' AND created_at < '2026-01-01'. - Small tables — a scan is already fast. Index columns used in WHERE, JOIN, ORDER BY and GROUP BY on big tables — nothing more.
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
- SQL when: data is structured and related, you need joins, strong consistency and transactions (banking, orders, inventory).
- NoSQL when: the schema changes often, you need massive scale or very high write throughput, or the data is naturally a document/graph/key-value (feeds, logs, caching, chat).
- Many real systems use both (polyglot persistence): PostgreSQL for orders, Redis for cache, Elasticsearch for search.
Interview one-liners
- Indexes trade slower writes and extra space for much faster reads.
- B+ trees keep data only in linked leaves → shallow trees and fast range scans.
- One clustered index per table; many non-clustered.
- Composite index (a, b) helps queries on a or a+b, not on b alone.
- SQL scales vertically with strong ACID; NoSQL scales horizontally with flexible schemas.
- Related: Transactions and ACID, MongoDB and Mongoose, Database Sharding and Replication.