Database Indexing medium
Which index structure is designed for Multi-Dimensional spatial queries (e.g., 'Find all points inside this bounding box')?
- A Standard B+ Tree, which utilizes a strictly linear sort order to manage multi-dimensional spatial points via a recursive partitioning algorithm.
- B R-Tree (Rectangle Tree), which organizes objects into nested, hierarchically organized Minimum Bounding Rectangles (MBRs) for multi-dimensional pruning.
- C LSM Tree (Log-Structured Merge Tree), which is natively optimized for high-throughput spatial write operations and real-time geofencing events.
- D Bloom Filter, a probabilistic data structure that can instantly determine if a specific point is physically present within a geometric boundary box.
Answer: B. R-Tree (Rectangle Tree), which organizes objects into nested, hierarchically organized Minimum Bounding Rectangles (MBRs) for multi-dimensional pruning.
B-Trees are excellent for one-dimensional data (sorting numbers or strings). However, space is two-dimensional. An R-Tree handles this by grouping nearby points into 'bounding boxes'. When you query for all restaurants within 1 mile, the R-Tree allows the database to discard entire 'boxes' of the world that don't overlap with your search area. This 'spatial pruning' makes geosearch O(log N) instead of O(N).
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')?