Database Indexing hard
In-Memory databases (Hyper, HANA) often favor Adaptive Radix Trees (ART). Why?
- A They utilize significantly fewer disk seeks than standard B-Trees when operating on exceptionally large datasets that exceed the system's RAM capacity.
- B They provide a more robust framework for managing ACID-compliant transactions in a distributed environment with high network latency.
- C They optimize for CPU Cache Locality by utilizing wide nodes and byte-chunked keys to minimize the frequency of expensive L3 cache misses.
- D They are significantly easier to persist to durable storage devices during sudden system failures due to their linear, log-structured memory layout.
Answer: C. They optimize for CPU Cache Locality by utilizing wide nodes and byte-chunked keys to minimize the frequency of expensive L3 cache misses.
In modern in-memory databases, the bottleneck is no longer the disk, but the CPU-to-memory bus. B-Trees waste CPU cycles comparing long keys and chasing multiple pointers. An Adaptive Radix Tree (ART) breaks keys into byte-sized chunks and uses nodes with up to 256 children. This 'wide' structure keeps the tree very shallow, reducing the number of pointer lookups (L3 cache misses) needed to find a value. Furthermore, the nodes automatically 'adapt' their size based on the number of children to save space.
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?
- 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')?
- You have a composite index on `(Lastname, Firstname)`. Which query can efficiently use this index?