Module 3 Capstone: Picking the Right Algorithm

Concept. Real systems combine several data structures. Each workload gets the algorithm and index type that fits its access pattern, and each component does one specialized job.

Intuition. A music service needs fast writes (LSM), fast geography lookups (H3), fast similarity search (LSH), fast range queries on history (B+Tree), and fast parallel scans (hash partitioning). No single tool covers all of them. The skill is picking the right one for each problem.

This is a wrap-up exercise across all of Module 3 (storage, indexing, query optimization). For each Spotify-style goal below, the answer pulls from a different M3 page: B+Tree from index-fundamentals, LSM from lsm-indexes, H3 and LSH from hash-indexes, and Hash Partitioning from hash-partitioning.

SQL, B+Trees, LSM, H3, LSH, and Hash Partitioning are separate tools, and each one fits a different shape of workload.

Five Spotify workloads matched to their Module 3 tool: date-range queries to a B+Tree, similarity clustering to LSH, hyper-local zones to H3 geo-hashing, a write surge to an LSM tree, and a viral surge to hash partitioning. Each row names the workload, the tool in a green chip, and why it fits.

Figure 1. The five workloads below and the structure each one calls for, from a B+Tree for date ranges to hash partitioning for a viral surge. Every row pairs a Spotify problem with the tool that fits its access pattern and the one reason it fits. Green marks the chosen tool.

Goal 1: Artist-Facing UI for Royalty Stats

Problem: Artists need to track geographical trends and specific date ranges, like post-release impacts. How do you handle fast range queries on trillions of listens?

Show Solution

  • Logic: Deploy a SQL engine for counting and mapping zip codes.

  • Indexing: Implement a B+ Tree Index on Listens <song_id, date>.

  • The "Why": date is ordered, so a B+ Tree seeks to the first key in the range and then scans forward across adjacent leaves.

Goal 2: Fan Preference Clustering

Problem: Clustering similar users or songs for marketing requires searching through high-dimensional feature vectors. What's the strategy?

Show Solution

  • Concept: Use Embeddings with Locality Sensitive Hashing (LSH).

  • Design: Generate embeddings (lyrics, tempo, etc.) and use an LSH Index to group similar vectors.

  • The "Why": High dimensions break the ordering a B+ Tree depends on. LSH maps similar items to the same hash bucket with high probability.

Goal 3: Local Fan Club Meetups

Problem: Identifying hyper-local communities when zip codes fall short. How do you pinpoint zones with over 100 fans for "listen parties"?

Show Solution

  • Concept: Geo-Hashing (H3).

  • Design: Map user addresses to H3 cells. Execute: GROUP BY H3(address) HAVING count(user) > 100.

  • The "Why": H3 maps latitude and longitude onto a hierarchical grid of cells, so the same data aggregates at whatever zoom the question needs.

Goal 4: "Live" Taylor Swift Drops

Problem: When 50,000 users tune into a live song drop, a standard B+ Tree chokes on random write overhead. How do you manage these updates?

Show Solution

  • Concept: LSM Trees.

  • Design: Use an LSM Tree to handle the write surge, keeping partial counts in a MemTable and flushing to SSTables.

  • The "Why": LSM Trees convert random writes into sequential flushes, ideal for high-bandwidth telemetry data.

Goal 5: Handling Viral Surges

Problem: Distributing table traffic across a cluster during a viral song surge. What's the approach?

Show Solution

  • Concept: Hash Partitioning.

  • Design: Partition data across nodes using a Hash function on song_id or user_id.

  • The "Why": A hash spreads keys evenly across partitions, which balances reads and writes, avoids hot spots, and lets every node work in parallel.

Takeaway: A modular design gives each workload the structure its access pattern asks for. B+ Trees for ordered range scans, LSH for similar vectors, H3 for nearby locations, LSM for write bursts, and hash partitioning to spread load across machines.