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
45 min · senior
senior

You are building the indexing layer for a large-scale transactional database used by a 50 million daily active user (DAU) startup. The system must support multiple index types: B-Tree for range queries, Hash indexes for exact lookups, and Composite indexes for multi-column queries. The database stores sensitive user data requiring encryption at rest and in transit. The system must guarantee P99 query latency under 200ms for index lookups and updates. The indexing system should handle high write throughput (millions of writes per second) and support efficient range scans and point lookups. Offline batch reindexing must be possible without impacting online query performance.

Constraints
  • Encryption at rest and in transit is mandatory for all index data.
  • P99 query latency for index lookups and updates must be under 200ms.
  • Support 50M DAU generating ~10M writes/sec and 20M queries/sec.
  • Offline batch reindexing without degrading online performance.
  • Composite indexes must support multi-column queries with selective filtering.
📋
Guided Steps
1/5
Step 1
Choosing Index Data Structures
Which index data structures will you use for range queries, exact lookups, and composite queries? Why?
💡 Hint
Consider B-Tree for ordered data, Hash for exact matches, and how composite indexes combine these.
Key Decision
Use B-Tree (e.g., RocksDB LSM with B-Tree-like SSTables) for range queries, Hash indexes (e.g., Redis Hash or Cassandra secondary indexes) for exact lookups, and Composite indexes implemented as concatenated keys in RocksDB for multi-column queries.
Interviewer Expectation
Mid: Names B-Tree and Hash indexes. Senior: Explains why B-Tree supports efficient range scans and why Hash indexes fail for range queries; details composite index key encoding for multi-column filtering.
⚠️Common Wrong Answer
Using only Hash indexes for all queries - leads to inefficient range scans and high latency for range queries.
Step 2
Handling Encryption Requirements
How will you ensure encryption at rest and in transit for index data without compromising query latency?
💡 Hint
Think about transparent encryption layers and TLS for network communication.
Key Decision
Use RocksDB with built-in encryption-at-rest plugin (e.g., Facebook's RocksDB encryption) and TLS 1.3 for all RPCs between indexing nodes and clients to secure data in transit.
Interviewer Expectation
Mid: Mentions encryption at rest and TLS. Senior: Explains how encryption plugins integrate with RocksDB SSTables without blocking reads/writes and impact on P99 latency; discusses key management.
⚠️Common Wrong Answer
Encrypting data at application layer only - causes high CPU overhead and inconsistent encryption coverage.
Step 3
Scaling Index Writes and Reads
How will you architect the system to handle 10M writes/sec and 20M queries/sec with P99 < 200ms?
💡 Hint
Consider sharding, partitioning, and caching strategies.
Key Decision
Shard indexes by partition key using consistent hashing (e.g., MurmurHash) to distribute load across multiple RocksDB instances; use Redis as a caching layer for hot keys to reduce read latency.
Interviewer Expectation
Mid: Describes sharding and caching. Senior: Explains partition key choice impact on write amplification in RocksDB, cache invalidation strategies, and how sharding avoids hotspots.
⚠️Common Wrong Answer
Single monolithic index instance - leads to write bottlenecks and high tail latency.
Step 4
Supporting Offline Batch Reindexing
How will you enable offline batch reindexing without impacting online query performance?
💡 Hint
Think about separate storage layers or versioned indexes.
Key Decision
Maintain separate RocksDB instances for online and offline indexes; use a versioned index metadata service (e.g., ZooKeeper) to atomically switch read traffic to the new index after batch reindexing completes.
Interviewer Expectation
Mid: Mentions offline reindexing. Senior: Details atomic index swap mechanism, how to keep online queries consistent during reindexing, and rollback strategies.
⚠️Common Wrong Answer
Rebuilding indexes in-place - causes query latency spikes and inconsistent reads.
Step 5
Designing Composite Indexes
How will you design composite indexes to efficiently support multi-column queries with selective filtering?
💡 Hint
Consider key encoding order and prefix scans.
Key Decision
Encode composite index keys by concatenating columns in query filter order using fixed-length encoding; store in RocksDB to leverage prefix bloom filters and range scans for selective filtering.
Interviewer Expectation
Mid: Names composite keys. Senior: Explains column order impact on query efficiency, prefix bloom filters in RocksDB, and trade-offs in index size vs query speed.
⚠️Common Wrong Answer
Storing composite indexes as separate single-column indexes - leads to expensive multi-index intersection at query time.
🔌
API Design Challenge
Sketch 3 core API endpoints for the indexing system that support index creation, query, and update operations.
Hints
  • How does the client specify index type and columns during creation?
  • What parameters are needed to perform efficient range or exact lookups?
  • How does the system handle atomic index updates on data writes?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of RocksDB with encryption plugin for range and composite indexes.
  • Sharding indexes by partition key to handle 10M writes/sec and 20M queries/sec.
  • TLS 1.3 for encryption in transit.
  • Atomic index version switching for offline reindexing.
Good to Have - 30%
  • Redis Hash indexes for exact lookups.
  • Redis caching layer for hot keys.
  • Composite index key encoding with prefix bloom filters.
Bonus - 10%
  • Detailed explanation of encryption key management.
  • Rollback strategies for index version switching.
Anti-patterns to Avoid
Using only Hash indexes for all queries - causes inefficient range scans and high latency.
Encrypting data only at application layer - leads to CPU overhead and inconsistent encryption.
Single monolithic index instance - causes write bottlenecks and high tail latency.
Rebuilding indexes in-place during batch reindexing - causes query latency spikes and inconsistent reads.
Storing composite indexes as separate single-column indexes - leads to expensive multi-index intersection.
✅
Model Answer
▼ Reveal

The system uses RocksDB with encryption plugins for B-Tree and composite indexes, Redis Hash indexes for exact lookups, and consistent hashing-based sharding to scale writes and reads. TLS 1.3 secures all RPCs to ensure encryption in transit with minimal latency impact. Offline batch reindexing is supported by maintaining separate RocksDB instances for online and offline indexes, with ZooKeeper managing atomic index version switches to avoid query disruption.

Key Decisions
  • Use RocksDB LSM with B-Tree-like SSTables for range and composite indexes to enable efficient range scans and prefix bloom filters.
  • Implement composite indexes as concatenated fixed-length encoded keys in RocksDB to optimize multi-column query filtering.
  • Shard indexes by partition key using consistent hashing (e.g., MurmurHash) to distribute 10M writes/sec and 20M queries/sec load evenly across multiple RocksDB instances.
  • Use Redis Hash indexes for exact lookups to achieve low latency for point queries.
  • Apply RocksDB encryption-at-rest plugin and TLS 1.3 for all RPCs to ensure data encryption at rest and in transit without significant latency overhead.
  • Maintain separate RocksDB instances for online and offline indexes and use ZooKeeper to atomically switch index versions after batch reindexing, ensuring no impact on online query performance.
  • Employ Redis caching layer for hot keys to keep P99 read latency under 200ms.
  • Manage encryption keys securely with a dedicated key management service integrated with RocksDB encryption plugin.
  • Implement rollback strategies in ZooKeeper metadata service to revert to previous index versions in case of failures during index switching.
  • RocksDB with encryption plugin for B-Tree style range indexes supporting efficient SSTable scans.
  • Redis Hash indexes for exact match lookups with low latency.
  • Composite indexes implemented as concatenated keys in RocksDB enabling prefix scans.
  • TLS 1.3 for all RPCs ensuring encryption in transit with minimal latency overhead.
  • Consistent hashing-based sharding to distribute 10M writes/sec and 20M queries/sec load evenly.
  • Separate RocksDB instances for online and offline indexes with ZooKeeper for atomic index version switching.
  • Redis caching layer for hot keys to reduce P99 read latency below 200ms.
  • Fixed-length encoding of composite index columns to optimize prefix bloom filters and range scans.

Practice

(1/5)
1. A location-based service must efficiently index millions of businesses worldwide to support fast nearby searches within a 5km radius. Which component is best suited to handle spatial indexing for this use case?
easy
A. Use a relational database with latitude and longitude columns and perform range queries with indexes
B. Use a Geohash-based spatial index to bucket locations into hierarchical grids
C. Use a simple key-value store with business IDs as keys and coordinates as values
D. Use a full-text search engine like Elasticsearch without spatial extensions

Solution

  1. Step 1: Identify spatial indexing needs

    Relational DBs with lat/lon indexes (Use a relational database with latitude and longitude columns and perform range queries with indexes) do not scale well for large radius queries and millions of points due to expensive range scans.

  2. Step 2: Evaluate Geohash suitability

    Geohash (Use a Geohash-based spatial index to bucket locations into hierarchical grids) encodes locations into hierarchical grids enabling efficient prefix queries for nearby searches, making it ideal for large-scale spatial indexing.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Geohash buckets locations into grids for fast proximity queries [check]
Hint: Geohash buckets locations hierarchically for fast spatial queries [OK]
Common Mistakes:
2. For a distributed message queue requiring exactly-once delivery semantics, which architecture choice best balances complexity and correctness?
medium
A. Use at-least-once delivery with idempotent consumers to handle duplicates
B. Implement transactional writes in the broker with two-phase commit across producers and consumers
C. Use at-most-once delivery to avoid duplicates but risk message loss
D. Use a best-effort fire-and-forget model for maximum throughput

Solution

  1. Step 1: Analyze delivery semantics

    Exactly-once requires atomicity across producer and consumer; at-least-once (A) can cause duplicates; at-most-once (C) risks loss; fire-and-forget (D) ignores reliability.

  2. Step 2: Evaluate architecture complexity

    Two-phase commit (B) ensures atomic commit across components, enabling exactly-once semantics despite complexity; idempotent consumers (A) reduce duplicates but don't guarantee exactly-once.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Two-phase commit -> atomic exactly-once delivery despite complexity [check]
Hint: Two-phase commit enables atomic exactly-once delivery [check]
Common Mistakes:
3. For a vector database supporting real-time updates and low-latency ANN queries, which architecture best balances update speed and query performance?
medium
A. Use a single monolithic HNSW index rebuilt entirely on every update
B. Maintain an immutable HNSW index for bulk data plus a small dynamic index for recent inserts
C. Use a brute-force linear scan for all queries to avoid index complexity
D. Store vectors in a relational DB and compute ANN on-demand

Solution

  1. Step 1: Evaluate update and query trade-offs

    Rebuilding entire HNSW on every update (Use a single monolithic HNSW index rebuilt entirely on every update) is too slow for real-time.

  2. Step 2: Consider hybrid index approach

    Maintaining an immutable bulk index plus a small dynamic index (Maintain an immutable HNSW index for bulk data plus a small dynamic index for recent inserts) allows fast queries and incremental updates.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Hybrid immutable + dynamic HNSW balances update speed and query latency [check]
Hint: Hybrid immutable plus dynamic index enables real-time updates [check]
Common Mistakes:
4. For a high-read, low-write system, which caching strategy best balances freshness and performance?
medium
A. Use write-through cache to update cache synchronously on every write
B. Disable caching and rely on database read replicas for freshness
C. Use write-back cache to batch writes and update cache asynchronously
D. Use cache-aside pattern where application loads cache on demand and invalidates on writes

Solution

  1. Step 1: Analyze write frequency and freshness needs

    High-read, low-write favors lazy loading and invalidation to avoid cache update overhead.

  2. Step 2: Evaluate caching strategies

    Write-through adds write latency; write-back risks stale data; cache-aside balances freshness and performance.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Cache-aside suits high-read, low-write with freshness [check]
Hint: Cache-aside balances freshness and performance [check]
Common Mistakes:
5. At 10x traffic scale, which component in the cache warming architecture is most likely to become the bottleneck first, and why?
hard
A. The database, because it cannot handle the increased read load from the warming service
B. The network bandwidth, because warming floods the network with data transfers
C. The cache servers, because they run out of memory storing warmed keys
D. The cache warming coordinator, because it maintains global state and cannot shard effectively

Solution

  1. Step 1: Identify coordinator role and scaling limits

    The warming coordinator manages global warming state and task assignment, which is hard to shard.

  2. Step 2: Compare other components

    Database can be scaled with replicas; cache servers scale horizontally; network scales with capacity upgrades.

  3. Step 3: Conclude bottleneck

    Coordinator's centralized state causes it to fail first at 10x scale.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Centralized coordinator state limits sharding, causing bottleneck [check]
Hint: Central coordinator state limits sharding, causing bottleneck [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