Databases
Deep Dive

Database 01

Indexing & B+ Trees

An index is the single most impactful performance tool in a database. Understanding why indexes work the way they do — through B+ trees — gives you the intuition to design them correctly every time.

How B+ Trees Work

Most database indexes use a B+ Tree — a balanced tree where all data lives in leaf nodes, and internal nodes are navigation pointers. Leaf nodes are linked in a doubly-linked list, enabling efficient range scans.

B+ Tree (index on age):
                [30 | 50]
               /    |    \
         [15|25]  [35|45]  [55|65]
          |  |     |  |     |  |
         Data    Data    Data   ← Leaf nodes (sorted, linked)

Query: WHERE age BETWEEN 25 AND 45
→ Find 25 in tree (O log n)
→ Scan linked leaf nodes rightward until > 45
→ Very efficient range scan!

Index Types

• Primary Index (Clustered): Data rows are physically stored in index order. Only one per table. Fast for range queries on primary key. In InnoDB, the primary key IS the clustered index.
• Secondary Index (Non-clustered): Separate structure pointing back to primary key. Multiple per table. Looking up a non-key column requires index lookup + primary key lookup (two hops).
• Composite Index: Index on (col_a, col_b, col_c). Useful for queries filtering/sorting multiple columns. Must follow leftmost prefix rule — index (a,b,c) is used by queries on (a), (a,b), (a,b,c) but NOT (b,c) alone.
• Covering Index: Index contains all columns a query needs — no need to touch the actual row. Extremely fast. Design indexes for your most critical queries.
• Partial Index: Index only rows matching a condition. e.g., WHERE status='active'. Smaller, faster than full index. Supported in PostgreSQL, SQLite.

Database 02

Query Optimisation

How the Query Planner Works

When you run a query, the database doesn't execute it literally. The query planner generates multiple possible execution plans, estimates the cost of each (using table statistics), and picks the cheapest one. EXPLAIN ANALYSE shows you what it chose.

EXPLAIN ANALYSE
SELECT u.name, COUNT(o.id) as order_count
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE u.country = 'UK'
GROUP BY u.id;

-- Output shows:
-- Seq Scan on orders (cost=0.00..4200.00 rows=50000)
-- Hash Join  (cost=120.00..5400.00 rows=800)
-- Index Scan on users_country_idx (cost=0.15..45.00 rows=800)

Common Query Anti-Patterns

• SELECT *: Fetches all columns, defeating covering indexes, saturating network. Always select only what you need.
• Function on indexed column: WHERE YEAR(created_at) = 2024 cannot use an index on created_at. Use WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'.
• Implicit type conversion: WHERE user_id = '123' when user_id is INT forces a cast on every row — index not used.
• N+1 queries: Loop over 100 users and query their orders one by one = 101 queries. Use JOIN or IN clause instead.
• Missing index on JOIN column: Joining on an unindexed foreign key causes a full table scan on every join. Always index foreign keys.

Database 03

Transactions, Locks & Deadlocks

Locking Strategies

Deadlock Example

Transaction A:             Transaction B:
  Lock row 1 ✓             Lock row 2 ✓
  Wait for row 2...        Wait for row 1...
  ← DEADLOCK →

Solution: always acquire locks in the same order.
Or use SELECT ... FOR UPDATE SKIP LOCKED for queue-like patterns.

Database 04

NoSQL Database Types

NoSQL doesn't mean "no structure" — it means "different structure optimised for different access patterns." There are five major categories.

Cassandra table for user events:
PRIMARY KEY (user_id, event_time)
-- Partition key: user_id → same node
-- Clustering key: event_time → sorted on disk

-- Query: get last 100 events for user 123
SELECT * FROM events WHERE user_id = 123
ORDER BY event_time DESC LIMIT 100;
-- Extremely fast: single partition, sorted read

-- Find friends of friends of user 123 in Cypher (Neo4j):
MATCH (u:User {id: 123})-[:FOLLOWS*2]->(fof:User)
WHERE NOT (u)-[:FOLLOWS]->(fof)
RETURN fof.name LIMIT 20;

Database 05

Redis Internals

Redis is an in-memory data structure store. Not just a cache — it's a powerful data structure server with persistence options.

Data Structures

• String: Binary-safe. Max 512MB. Atomic INCR/DECR. Use for: counters, rate limiting, session tokens, feature flags.
• List: Linked list. O(1) push/pop from head or tail. O(n) for middle access. Use for: message queues, activity feeds (LPUSH, LTRIM), task queues.
• Hash: Field-value pairs. O(1) field access. Memory-efficient for small hashes. Use for: user profiles, object storage.
• Set: Unordered unique strings. O(1) add/remove/contains. Set operations (UNION, INTERSECT, DIFF). Use for: tags, social connections, unique visitors.
• Sorted Set (ZSet): Set + floating point score. O(log n) operations. Range queries by score or rank. Use for: leaderboards, priority queues, rate limiting windows, delayed tasks.
• Bitmap: Bit array. Space-efficient. 512MB = 4 billion bits. Use for: daily active users, feature toggles per user ID.
• HyperLogLog: Probabilistic cardinality estimation. ~12KB regardless of set size. 0.81% error rate. Use for: unique visitor counts at massive scale.
• Stream: Append-only log. Consumer groups. Like a lightweight Kafka. Use for: event sourcing, audit logs, chat history.

Persistence Options

Database 06

Cassandra Architecture

Cassandra is a masterless, AP distributed database designed for massive write throughput and linear scalability. Used by Netflix, Instagram, Apple (10+ petabytes).

Key Design Principles

• Masterless ring: All nodes are equal peers. No single point of failure. Any node can accept reads and writes. Coordinator node routes requests.
• Consistent hashing: Data is distributed around a hash ring using virtual nodes (vnodes). Adding nodes is seamless — they take over a portion of the ring.
• Tunable consistency: Per-query consistency level. ONE (fastest, least consistent), QUORUM (balanced), ALL (slowest, strongest). Quorum with RF=3 means W+R > N, guaranteeing at least one node has latest data.
• SSTable writes: Writes go to in-memory MemTable + commit log. MemTable flushes to immutable SSTable on disk. SSTables are compacted periodically. Writes are always sequential I/O — extremely fast.
• No joins, no transactions: By design. If you need them, think again about your data model. Cassandra requires query-first design.

Database 07

Choosing the Right Database