Databases — Advanced Concepts
Indexing, transactions, replication, and beyond
IT & Tech Reports | Class IM24A | 2026
1. Index Internals
B-Tree Index (default in most RDBMS)
A B-Tree index stores sorted key values in a balanced tree structure. It supports equality (=), range (<,
>, BETWEEN), and ORDER BY efficiently. Read in O(log n); writes must update the tree.
Hash Index
Hash indexes store a hash of the key. O(1) equality lookups but cannot support range queries or
ordering. Used by default in Redis and available in PostgreSQL for equality-only columns.
GIN / GiST (PostgreSQL)
Generalised Inverted Index (GIN) is used for full-text search, JSONB, and array containment queries.
GiST supports geometric and range types.
2. Query Optimisation
• EXPLAIN ANALYZE — shows actual execution plan with timings and row estimates
• Seq Scan vs Index Scan — planner chooses seq scan for small tables or low selectivity
• Covering index — include all columns needed by the query to avoid heap lookups
• Partial index — index a subset of rows: CREATE INDEX ON orders(id) WHERE status='pending'
• Statistics — ANALYZE updates planner statistics; run after large bulk inserts
3. Transactions & Isolation Levels
Isolation Level Dirty Read Non-repeatable Read Phantom Read
Read Uncommitted Possible Possible Possible
Read Committed Prevented Possible Possible
Repeatable Read Prevented Prevented Possible
Serializable Prevented Prevented Prevented
PostgreSQL default is Read Committed. Use Serializable for financial transactions. Higher isolation =
more locking = lower concurrency.
4. Locking & Deadlocks
• Row-level locks — most granular; acquired on UPDATE/DELETE for individual rows
• Table-level locks — acquired for schema changes (ALTER TABLE); blocks all DML
• Advisory locks — application-controlled locks for custom concurrency control
• Deadlock — two transactions each hold a lock the other needs; DB detects and kills one
• Prevention: always acquire locks in the same order; keep transactions short
5. Replication
Type How it works Use case
Streaming replication WAL (write-ahead log) shipped to replicas in
Read
realscaling,
time HA failover
Logical replication Row-level changes replicated (can filter tables)
Cross-version upgrades, selective sync
Synchronous Primary waits for at least one replica to confirm
Zero data loss (RPO=0)
Asynchronous Primary does not wait — some lag possibleHigher write throughput
6. Sharding & Partitioning
Table Partitioning (single DB)
Split a large table into smaller physical partitions by range, list, or hash. PostgreSQL handles routing
transparently. Improves query performance and allows partition pruning.
CREATE TABLE orders (id BIGINT, created_at DATE, ...)
PARTITION BY RANGE (created_at);
CREATE TABLE orders_2025 PARTITION OF orders
FOR VALUES FROM ('2025-01-01') TO ('2026-01-01');
Sharding (multiple DBs)
Horizontal sharding splits data across multiple database servers (shards) by a shard key (e.g. user_id %
4). Dramatically increases write throughput but complicates cross-shard queries and transactions.
7. NewSQL & Distributed Databases
Database Type Key feature
CockroachDB NewSQL Distributed SQL, ACID, PostgreSQL-compatible wire protocol
TiDB NewSQL MySQL-compatible distributed SQL with HTAP capabilities
Cassandra Wide-column Masterless, geo-distributed writes, eventual consistency
Redis Key-value In-memory, sub-millisecond latency, pub/sub, Lua scripting
ClickHouse Columnar OLAP analytics — billions of rows in seconds