Database Indexing hard
PostgreSQL's GiST (Generalized Search Tree) allows indexing what kind of data?
- A Only standard integer and numeric data types that have a clearly defined, linear mathematical sort order within the database schema.
- B Large binary blobs (LOBs) that require high-speed cryptographic signatures to ensure data integrity across various disparate partitions.
- C Individual keys within deeply nested JSON structures to enable O(1) retrieval speeds for schema-less document-based data processing.
- D Arbitrary complex types (Geometric shapes, IP Ranges) where the concept of 'ordering' is defined by spatial overlap or logical containment rules.
Answer: D. Arbitrary complex types (Geometric shapes, IP Ranges) where the concept of 'ordering' is defined by spatial overlap or logical containment rules.
B-Trees are strictly limited to data that can be sorted linearly (A < B). Postgres's GiST (Generalized Search Tree) is an indexing framework that acts as a template for other index types. It is used to implement R-Trees (for maps/geometry) and GIN indexes. For example, if you want to find all polygons that contain a specific point, GiST allows you to define how the database should 'split' and 'group' those polygons into a tree structure, even though polygons don't have a simple 'ascending' order.
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')?