Bird
Raised Fist0

Database Indexing - B-Tree, Hash Index, Composite Index Design

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Database Indexing - B-Tree, Hash Index, Composite Index Design
Designing scalable and efficient database indexing strategies for high-throughput OLTP systems
mediumDatabases - SQL and TransactionsFreq: high
Prerequisites:Basic understanding of database indexing conceptsFamiliarity with B-Tree and Hash data structuresKnowledge of OLTP system workloads and scaling challenges
⚙️
Functional Requirements
  • Support efficient point and range queries on primary keys using B-Tree indexes
  • Enable fast equality lookups on non-primary key columns via Hash indexes
  • Support composite indexes for multi-column query predicates
  • Maintain index consistency with transactional writes
  • Allow index updates with minimal write amplification
  • Provide query planner hints to choose optimal indexes
📊
Non-Functional Requirements
  • Handle 2 billion daily active users generating 40 writes/user/day
  • Sustain peak write throughput of approximately 925,000 writes/sec
  • Ensure 99.99% availability for index reads and writes
  • Achieve 100ms P99 latency for index lookups under peak load
  • Support data retention of 30 days with replication factor 3
❓
Clarifying Questions to Ask
  • What types of queries are most common: point lookups, range scans, or multi-column filters?
  • Are indexes maintained synchronously or asynchronously with writes?
  • What is the expected size and cardinality of indexed columns?
  • Is the workload read-heavy, write-heavy, or balanced?
  • Are composite indexes always used in prefix order or arbitrary column combinations?
  • What is the acceptable index maintenance overhead on write latency?
Out of Scope
✗ Design of the underlying storage engine (assumed to be a distributed key-value store)
✗ Query execution engine and optimizer internals
✗ Full-text search or geospatial indexing
✗ Backup and disaster recovery mechanisms
📌
Assumptions
  • 2 billion daily active users
  • 40 writes per user per day
  • 100 bytes average size per write
  • Replication factor of 3 for durability
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor → 1,851,852 writes/sec
read qpsAssuming 5 reads per write → 4,629,630 reads/sec
💾
Storage Estimate
daily storage2B × 40 × 100 bytes = 8 TB/day
retention storage8 TB × 30 days = 240 TB
with replication240 TB × 3 = 720 TB total storage
🖥️
Server Estimate
indexing nodesAssuming 100 MB/sec write throughput per node → 926 nodes for writes
query nodesAssuming 200 MB/sec read throughput per node → 2315 nodes for reads
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |    Client Queries    |
          +----------+-----------+
                     |
                     v
          +----------------------+
          | Query Router / Proxy |
          +----------+-----------+
                     |
         +-----------+------------+
         |                        |
         v                        v
 +---------------+        +---------------+
 |  B-Tree Index |        |  Hash Index   |
 |  Manager      |        |  Manager      |
 +-------+-------+        +-------+-------+
         |                        |
         v                        v
 +----------------------------------------+
 |       Composite Index Manager          |
 +----------------+-----------------------+
                  |
                  v
          +----------------------+
          | Distributed Storage  |
          | (e.g. Cassandra)     |
          +----------------------+
🧩
Components
Query Router / Proxy
Receives client queries and routes them to appropriate index managers
Why thisEnvoy proxy supports dynamic routing and load balancing with low latency
Why notNginx lacks native support for dynamic query routing and gRPC multiplexing
B-Tree Index Manager
Manages B-Tree indexes for primary key and range queries
Why thisB-Trees provide efficient ordered traversal and range scan support with O(log n) complexity
Why notHash indexes do not support range queries efficiently
Hash Index Manager
Manages hash indexes for fast equality lookups on non-primary key columns
Why thisHash indexes provide O(1) average lookup time for equality predicates
Why notB-Tree indexes have higher overhead for equality-only lookups
Composite Index Manager
Coordinates multi-column composite indexes combining B-Tree and Hash strategies
Why thisComposite indexes optimize multi-column queries by maintaining column order and selectivity
Why notSeparate single-column indexes cause inefficient multi-index scans and merges
Distributed Storage (Cassandra)
Stores base data and index entries with replication and partitioning
Why thisCassandra supports high write throughput, tunable consistency, and horizontal scaling
Why notPostgreSQL requires complex manual sharding at 925K writes/sec; B-tree writes don't scale linearly
🔄
Data Flow
1
Client Queries → Query Router / Proxy
Receives query and parses predicates
Router decides which index manager(s) to query based on predicates
2
Query Router / Proxy → B-Tree Index Manager
Routes range and primary key queries
B-Tree manager performs ordered scans or point lookups
3
Query Router / Proxy → Hash Index Manager
Routes equality predicate queries on non-primary columns
Hash manager performs O(1) lookups
4
B-Tree/Hash Index Managers → Composite Index Manager
Coordinates multi-column index lookups
Composite manager merges results or uses combined index
5
Index Managers → Distributed Storage
Reads/writes index entries and base data
Storage layer ensures durability and replication
6
Distributed Storage → Index Managers
Returns data or index pointers
Index managers assemble final result sets
7
Index Managers → Query Router / Proxy
Returns query results
Router aggregates and sends response to client

Practice

(1/5)
1. A microservice calls a downstream service that occasionally fails or responds slowly. To prevent cascading failures and allow quick recovery, which component should be introduced?
easy
A. Implement a circuit breaker to stop calls after failure threshold is reached
B. Use a retry mechanism with exponential backoff on every request
C. Add a load balancer to distribute requests evenly across instances
D. Use a message queue to buffer all requests asynchronously

Solution

  1. Step 1: Identify failure containment mechanism

    Retries alone (A) can worsen cascading failures by increasing load; load balancers (C) distribute load but don't prevent failures; message queues (D) buffer but don't stop calls to failing services.

  2. Step 2: Recognize circuit breaker role

    Circuit breakers (B) detect failure thresholds and open to stop calls, preventing cascading failures and allowing recovery.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Circuit breaker stops calls after failures to prevent cascade [check]
Hint: Circuit breaker stops calls after failures to prevent cascade [OK]
Common Mistakes:
2. In the deployment system request flow, at Step 4 the Canary Controller evaluates metrics from the new version. What happens if error rates exceed the threshold at this step?
easy
A. Canary Controller immediately promotes the new version to 100% traffic
B. Canary Controller triggers automatic rollback to previous stable version
C. Canary Controller ignores errors and continues increasing traffic
D. Canary Controller disables feature flags for the new version

Solution

  1. Step 1: Understand Step 4 role

    At Step 4, Canary Controller monitors metrics to decide if rollout continues or aborts.

  2. Step 2: Analyze error threshold breach

    If error rates exceed threshold, rollback is triggered to prevent faulty version promotion.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Canary Controller triggers rollback on error threshold breach [check]
Hint: Canary aborts rollout and rolls back on high error rates [OK]
Common Mistakes:
3. At 10x scale, which component in a circuit breaker-enabled microservice architecture is most likely to fail first, and why?
hard
A. The downstream service, because it cannot handle increased request volume despite circuit breaker protection
B. The circuit breaker state store, because centralized state tracking causes contention and latency under high concurrency
C. The load balancer, because it cannot distribute 10x more connections evenly
D. The client-side cache, because it grows too large and causes memory pressure

Solution

  1. Step 1: Analyze scaling impact on components

    Downstream service (A) is protected by circuit breaker; load balancer (C) scales horizontally; client cache (D) is local and less critical.

  2. Step 2: Identify circuit breaker state store bottleneck

    Centralized state store for circuit breaker metrics faces contention and latency at 10x concurrency, causing delays and incorrect breaker states.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Centralized circuit breaker state store bottlenecks first at scale [check]
Hint: Centralized circuit breaker state store bottlenecks first at scale [OK]
Common Mistakes:
4. At 10x scale, which component in a real-time chat system is most likely to fail first and why?
hard
A. Database because increased writes cause disk I/O bottlenecks
B. Load balancer because it cannot handle increased TCP connections
C. Chat servers because WebSocket connections are stateful and cannot be resharded easily
D. Message queue because partition count limits throughput

Solution

  1. Step 1: Identify stateful bottleneck at scale

    WebSocket connections are stateful and bound to specific chat servers, limiting horizontal scaling.

  2. Step 2: Compare other components

    Databases and queues can be sharded or scaled horizontally; load balancers can be scaled with proxies.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Stateful WebSocket servers limit scaling more than DB or queues [check]
Hint: Stateful WebSocket servers block scaling before DB or queues [check]
Common Mistakes:
5. At 10x scale, which component in the search ranking system is most likely to fail first and why?
hard
A. Model Serving, because CPU-intensive scoring cannot be parallelized beyond a point
B. Update Stream (Kafka), because partition count limits throughput and causes backpressure
C. A/B Testing Controller, because routing logic becomes too complex to handle high traffic
D. Feature Store, because maintaining consistent, low-latency feature retrieval under massive read load saturates memory bandwidth

Solution

  1. Step 1: Analyze scaling bottlenecks

    Model Serving can be horizontally scaled; A/B controller logic is lightweight; Kafka partitions can be increased.

  2. Step 2: Identify Feature Store bottleneck

    Feature Store must serve millions of low-latency reads with consistency, saturating memory bandwidth and cache, making it the first to fail.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Feature Store memory bandwidth saturates first at 10x scale [check]
Hint: Feature Store memory bandwidth saturates before compute or routing [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard