Fast Retrieval at Scale: Databases, Indexing vs Sharding, Red-Black Trees and Tries

This round asked a set of conceptual questions about storing data and finding it quickly. Answer each one, using concrete examples where you can. ### Clarifying Questions - Is "massive data" a large table on one machine, or a dataset spread across many machines? - What do typical queries look like: exact-key lookups, range queries, prefix or text search, or analytical aggregations? - Should the answers focus on relational databases, or also cover key-value stores, document stores and search engines? ### Part 1 — What a database is, and fast retrieval from massive data What is a database? How would you retrieve data quickly from a very large dataset? ```hint Avoid reading everything Start from the cost of a full scan over a huge dataset, then list the ways to touch only the data a query actually needs. ``` #### What This Part Should Cover - A definition that goes beyond "it stores data": what a database management system is responsible for - Techniques for fast retrieval, and the access pattern each one serves - The cost of each technique in writes, storage or consistency - A rough sense of scale: why a full scan is slow and how much a good access path saves ### Part 2 — Sharding versus indexing What is the difference between sharding and indexing in a database? ```hint Different problems Ask what problem each one solves: one changes how a lookup finds rows, the other changes where rows live. ``` #### What This Part Should Cover - What each mechanism is and the problem it solves - The effect of each on reads, writes and storage - How the two combine in a sharded database - The costs and failure modes of each ### Part 3 — Red-black trees and tries Explain the principles behind red-black trees and tries. What is each one good for, and how do they compare? ```hint Balance versus structure For one structure, think about the rules that keep its height bounded. For the other, think about what the path from the root to a node represents. ``` #### What This Part Should Cover - The red-black tree invariants, the height guarantee they give, and how updates restore them - The structure of a trie, the cost of its operations in terms of key length, and its memory trade-offs - Typical uses of each - A direct comparison: ordering, prefix queries, memory and worst-case guarantees ### What a Strong Answer Covers - Correct definitions with the reasoning behind each mechanism, not just names - Clear separation of concerns: access paths within a node versus distribution across nodes - Asymptotic costs stated correctly, plus practical constants such as disk reads - Trade-offs tied to workload: read-heavy versus write-heavy, point versus range versus prefix queries ### Follow-up Questions - Why do databases usually use B-trees or B+ trees on disk rather than red-black trees? - How would you choose a shard key for a table of user events, and what goes wrong if you shard by timestamp? - How would you support prefix autocomplete over a very large set of names? - When can adding an index make a query slower, or the system as a whole worse?