Hash indexes and physical design
Beyond B+ trees, databases offer hash, bitmap, and specialised indexes. Physical design chooses which to build and how to lay out data for a real workload.
Hash indexes
A hash index applies a hash function to the key to find a bucket, giving very fast equality lookups, typically O(1) page reads. But hashing scrambles order, so hash indexes cannot help with ranges, sorting, or prefix searches. PostgreSQL supports hash indexes, and many in-memory systems and key-value stores rely on hashing internally.
Bitmap indexes
A bitmap index keeps, for each distinct value of a low-cardinality column such as status or region, a bit array with one bit per row. Combining conditions is fast bitwise arithmetic: status = 'open' AND region = 'EU' is an AND of two bitmaps. Bitmaps compress well and suit read-heavy analytical systems, but are costly to update under heavy concurrent writes.
Specialised indexes
Full-text indexes, often inverted indexes mapping words to documents, power keyword search. Spatial indexes such as R-trees organise rectangles and points for map queries like 'restaurants within 2 kilometres'. PostgreSQL's GIN indexes handle arrays and JSON documents, and vector indexes support similarity search over machine-learning embeddings.
Partial and expression indexes
A partial index covers only rows matching a condition, such as CREATE INDEX ON orders (customer_id) WHERE status = 'open', which is small and fast when queries target open orders. An expression index indexes a computed value, such as LOWER(email), so case-insensitive lookups using the same expression can use the index.
Selectivity and cardinality
Selectivity is the fraction of rows a condition matches. Indexes help most for selective conditions, those matching few rows. If a condition matches 40% of a table, reading index entries and then scattered rows can be slower than a sequential full scan, so optimisers often ignore indexes on unselective columns such as a Boolean flag.
Physical design decisions
Physical design weighs the workload: which queries run most often, how fast they must be, and the ratio of reads to writes. Decisions include which indexes to build, the clustering key, partitioning schemes, storage formats (row or column), and sometimes denormalised or materialised summaries. Designs should be validated by measuring real query plans and timings, not guesses.
Tools for tuning
Databases provide EXPLAIN to show how a query will run and EXPLAIN ANALYZE to run it and report actual times and row counts. Statistics views reveal unused indexes and slow queries, such as PostgreSQL's pg_stat_statements. Tuning is iterative: find the slowest, most frequent queries, inspect their plans, adjust indexes or queries, and measure again.
Worked example
An orders table with 50,000,000 rows, where only 1% are 'open', and the support dashboard always queries open orders by customer. A full index on customer_id covers all 50 million rows; a partial index on customer_id WHERE status = 'open' covers only 500,000, about 1% of the size, fits easily in memory, and serves the dashboard's queries just as well.
Key takeaways
Hash indexes give fast equality lookups but no ranges or ordering. Bitmap indexes suit low-cardinality columns in analytics, combining conditions with bitwise operations. Full-text inverted indexes, R-trees for spatial data, GIN for JSON and arrays, and vector indexes handle specialised queries. Partial indexes cover subsets; expression indexes cover computed values. Indexes pay off for selective conditions; unselective ones favour full scans. Physical design matches indexes, clustering, partitioning, and formats to the workload, verified with EXPLAIN and statistics.
Flashcard
Hash-based equality lookups
Check your understanding
Why might the optimiser ignore an index on a column is_active that is true for 95% of rows?