Bird
Raised Fist0

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

HLDmediumInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/11
Query Router / Proxy

Receives query and analyzes query type

Determines if query is range, equality, or composite

Protocol:gRPC
BeforeQuery arrives at router unprocessed
AfterRouter identifies query type and selects index manager
B-Tree Index Manager

Processes range query using B-Tree index

Navigates B-Tree nodes to locate data pointers

Protocol:Internal RPC
BeforeQuery routed to B-Tree manager for range processing
AfterB-Tree manager identifies data keys to fetch from storage
Distributed Storage (Cassandra)

Fetches data rows based on keys from B-Tree manager

Reads data partitions matching keys

Protocol:Internal RPC
BeforeStorage awaits data keys from index manager
AfterStorage returns requested data rows to B-Tree manager
B-Tree Index Manager

Aggregates data rows and prepares response

Combines data for final query result

Protocol:Internal RPC
BeforeB-Tree manager has raw data rows from storage
AfterB-Tree manager sends results back to Query Router
Hash Index Manager

Processes equality query using hash index

Computes hash to locate data pointers

Protocol:Internal RPC
BeforeQuery routed to Hash manager for equality processing
AfterHash manager identifies data keys to fetch from storage
Distributed Storage (Cassandra)

Fetches data rows based on keys from Hash manager

Reads data partitions matching keys

Protocol:Internal RPC
BeforeStorage awaits data keys from index manager
AfterStorage returns requested data rows to Hash manager
Hash Index Manager

Aggregates data rows and prepares response

Combines data for final query result

Protocol:Internal RPC
BeforeHash manager has raw data rows from storage
AfterHash manager sends results back to Query Router
Composite Index Manager

Processes multi-column query using composite index

Navigates composite index to locate data pointers

Protocol:Internal RPC
BeforeQuery routed to Composite manager for multi-column processing
AfterComposite manager identifies data keys to fetch from storage
Distributed Storage (Cassandra)

Fetches data rows based on keys from Composite manager

Reads data partitions matching keys

Protocol:Internal RPC
BeforeStorage awaits data keys from index manager
AfterStorage returns requested data rows to Composite manager
Composite Index Manager

Aggregates data rows and prepares response

Combines data for final query result

Protocol:Internal RPC
BeforeComposite manager has raw data rows from storage
AfterComposite manager sends results back to Query Router
Query Router / Proxy

Returns query results to client

Sends final response over gRPC

Protocol:gRPC
BeforeRouter awaits results from index manager
AfterClient receives query results
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────────────┐
│ Query Router / Proxy  │
└─────────────┬─────────┘
              │ gRPC
              ▼
┌───────────────────────┐
│ B-Tree Index Manager  │
└───────┬───────────────┘
        │ Internal RPC
        ▼
┌────────────────────────┐
│ Distributed Storage     │
│ (Cassandra)             │
└────────┬───────────────┘
         │
         │
         │
┌────────▼───────────────┐
│ Hash Index Manager     │
└────────┬───────────────┘
         │ Internal RPC
         ▼
┌────────────────────────┐
│ Distributed Storage     │
│ (Cassandra)             │
└────────┬───────────────┘
         │
         │
         │
┌────────▼───────────────┐
│ Composite Index Manager │
└────────┬───────────────┘
         │ Internal RPC
         ▼
┌────────────────────────┐
│ Distributed Storage     │
│ (Cassandra)             │
└────────────────────────┘
Design Rationale

This architecture shows a query flowing vertically through the Query Router to the appropriate index manager based on query type: B-Tree for range queries, Hash for equality, and Composite for multi-column queries. Each index manager interacts with Distributed Storage (Cassandra) to fetch or update data. The vertical layout emphasizes the sequential processing steps and clear separation of concerns. The Query Router acts as a proxy directing queries, while index managers encapsulate index-specific logic. Distributed Storage serves as the durable data backend. This design supports extensibility by adding new index managers without changing the router or storage. The trace highlights how query type determines the path, ensuring efficient index usage and data retrieval.

Primary Focus

✓

Practice

(1/5)
1. A payment gateway must reliably process millions of payment requests per second and ensure durability despite transient failures. Which component is best suited to decouple the payment request ingestion from downstream processing to achieve this?
easy
A. Use a distributed log system like Kafka to persist and stream payment events
B. Use an in-memory cache like Redis to queue payment requests for fast access
C. Use a relational database with auto-increment IDs to store payment requests synchronously
D. Use a REST API gateway that directly calls payment processors synchronously

Solution

  1. Step 1: Identify the role of the decoupling component

    The component must provide durability and handle high throughput without blocking the ingestion path.

  2. Step 2: Evaluate Kafka's suitability

    Kafka provides a distributed, durable log with partitioning and replication, enabling asynchronous processing and replay.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka decouples ingestion and processing with durability and scale [check]
Hint: Durable logs decouple ingestion from processing [check]
Common Mistakes:
2. A distributed system needs to enforce a global rate limit of 1000 requests per second across multiple API servers. Which component is best suited to maintain a consistent count of requests in real-time?
easy
A. Use a message queue to buffer requests and count them asynchronously
B. Use a local in-memory counter on each API server and aggregate periodically
C. Use a relational database with row-level locking for counting requests
D. Use a centralized Redis counter with atomic increment operations

Solution

  1. Step 1: Identify the need for a consistent global count

    Local counters aggregated periodically (Use a local in-memory counter on each API server and aggregate periodically) cause stale counts and race conditions, failing real-time enforcement.

  2. Step 2: Evaluate Redis atomic increments

    Redis supports atomic INCR commands ensuring consistent, real-time global counters across distributed servers.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Redis atomic counters ensure global consistency and low latency [check]
Hint: Centralized atomic counters ensure global consistency [check]
Common Mistakes:
3. If the Kafka cluster is unavailable, what exact failure occurs in the notification system's delivery path?
medium
A. Notifications are lost silently because the delivery workers cannot fetch messages
B. Notification producers block synchronously, causing upstream request latency spikes and potential timeouts
C. Delivery workers switch to a backup queue automatically with no message loss
D. The system falls back to synchronous HTTP calls to devices, causing slow delivery

Solution

  1. Step 1: Trace failure impact of Kafka unavailability

    Kafka unavailability blocks producers or causes retries; delivery workers cannot fetch messages from Kafka.

  2. Step 2: Evaluate fallback mechanisms

    In a robust design, a backup queue or dead-letter queue is used to avoid message loss; synchronous HTTP fallback (D) is not automatic; silent loss (A) is unacceptable.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Backup queue prevents message loss during Kafka downtime [check]
Hint: Backup queue prevents loss when Kafka is down [check]
Common Mistakes:
4. If the Kafka cluster responsible for location update ingestion becomes unavailable, what is the immediate failure observed in the system?
medium
A. Location updates queue up in the WebSocket Server memory until Kafka recovers
B. WebSocket Server blocks on sending updates, causing client-side UI to freeze
C. Location updates are lost silently without any retry or backpressure
D. Clients receive stale location data but no error is shown

Solution

  1. Step 1: Understand Kafka's role in ingestion

    Kafka decouples ingestion; if unavailable, producers (WebSocket Server) cannot push messages.

  2. Step 2: Trace failure impact

    WebSocket Server buffers updates temporarily but memory is limited; blocking would cause backpressure but usually async buffers exist.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka outage causes buffering, not silent loss or blocking immediately [check]
Hint: Kafka outage -> WebSocket buffers updates temporarily [check]
Common Mistakes:
5. At 10x scale, which component in the AI Code Assistant system is most likely to fail first due to stateful connection limits, and why?
hard
A. The API gateway, because it cannot handle the increased request routing throughput
B. The code generator service, because GPU resources saturate under concurrent requests
C. The WebSocket servers maintaining user sessions, because stateful connections cannot be sharded easily
D. The vector search engine, because its index size grows linearly and slows queries

Solution

  1. Step 1: Analyze vector search scaling

    Vector search scales with index size but can shard horizontally; query latency grows but not immediate failure (A incorrect).

  2. Step 2: Assess code generator scaling

    GPU saturation is a bottleneck but can be mitigated by batching and autoscaling (B less immediate).

  3. Step 3: Evaluate API gateway

    API gateways are stateless and horizontally scalable (C incorrect).

  4. Step 4: Identify WebSocket server bottleneck

    WebSocket servers hold stateful connections bound to server memory; sharding existing connections is complex, causing first failure at 10x scale (D correct).

  5. Final Answer:

    Option C -> Option C

  6. Quick Check:

    Stateful WebSocket connections limit server scaling [check]
Hint: Stateful WebSocket servers bottleneck scaling first [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