Database Indexing easy
Which data structure is the default standard for general-purpose database indexes (e.g., CREATE INDEX in MySQL/Postgres)?
- A Hash Map, which offers constant-time O(1) lookups but cannot handle range queries or order-by operations.
- B Skip List, a probabilistic data structure that provides logarithmic search time and is commonly used in in-memory databases.
- C B-Tree (Balanced Tree), which maintains sorted order and is optimized for the block-based storage architecture of physical disks.
- D Linked List, a fundamental linear structure that stores data in discrete nodes and requires a full scan for every search operation.
Answer: C. B-Tree (Balanced Tree), which maintains sorted order and is optimized for the block-based storage architecture of physical disks.
B-Trees (and their variants like B+Trees) are the gold standard for disk-based storage. They maintain sorted order, which allows the database to perform efficient equality checks, range queries (e.g., `WHERE age > 21`), and sorting without additional work. Because of their high 'fan-out', a B-Tree can locate any specific record within billions of rows in just 3-4 disk hops, making them exceptionally low-latency compared to linear or memory-only structures.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- Z-Order Curves (Geohashing) map 2D data to 1D strings for indexing. What is their primary weakness?
- In-Memory databases (Hyper, HANA) often favor Adaptive Radix Trees (ART). Why?
- Log-Structured Merge (LSM) Trees (RocksDB, Cassandra) optimize for Write Throughput. How does their disk IO pattern differ from B-Trees?
- In LSM compaction strategies, 'Universal' (Tiered) compaction prioritizes what over 'Leveled' compaction?
- In LSM trees, what is 'Space Amplification'?
- Why is it generally ineffective to index a 'Low Cardinality' column like `Gender` ('Male'/'Female')?