Database Indexing hard
Z-Order Curves (Geohashing) map 2D data to 1D strings for indexing. What is their primary weakness?
- A They are fundamentally unable to handle floating-point numeric coordinates, requiring them to be converted to less precise integer representations.
- B They are typically significantly larger in terms of physical disk footprint than comparable R-Tree structures due to their reliance on raw string literals.
- C Discontinuity issues mean that points which are physically close in 2D space can end up very far apart in the 1D sort order, leading to inefficient query ranges.
- D They strictly support point-based geodata and are mathematically incapable of representing or indexing complex spatial polygons or multi-dimensional lines.
Answer: C. Discontinuity issues mean that points which are physically close in 2D space can end up very far apart in the 1D sort order, leading to inefficient query ranges.
Z-Order Curves (and Geohashes) work by interleaving the bits of X and Y coordinates to create a 1D string. This allows you to use a standard B-Tree for spatial search. However, the curve has 'jumps'. Two neighbors (e.g., across the Z-shape's diagonal) can have vastly different 1D values. In a query like 'Find all people near me', the database might have to scan several disjoint ranges in the index to cover the whole circle, making it less predictable than a true 2D index like an R-Tree.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- 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')?
- You have a composite index on `(Lastname, Firstname)`. Which query can efficiently use this index?