Database Indexing medium
Hash Indexes are O(1). Why are they rarely the default compared to B-Trees?
- A They consume significantly more system memory (RAM) than B-Trees due to the need for a massive, pre-allocated hash buckets array.
- B They cannot support range-based query predicates (e.g., `> 100`) or sort operations because the hash function randomizes the data's order.
- C They are strictly non-durable and are automatically wiped from the disk whenever the database engine performs a standard restart or shutdown.
- D The excessive number of hash collisions for large datasets makes them fundamentally slower than O(log N) tree traversals for most workloads.
Answer: B. They cannot support range-based query predicates (e.g., `> 100`) or sort operations because the hash function randomizes the data's order.
Hash indexes are incredibly fast for exact equality lookups (O(1)). However, the hash function inherently randomizes where data is stored. Because the values aren't stored in sorted order, the database cannot use a hash index for range queries (`WHERE age > 18`) or for ordering results (`ORDER BY name`). Since these are extremely common query patterns, B-Trees (which maintain sorting) are almost always preferred as the default indexing structure.
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')?