Questions: Index Types: B-Trees, Hash Indexes, and Bitmap Indexes

Question 1

A data warehouse table has 50 million rows with a 'region' column containing 8 distinct values (North, South, East, West, etc.). Analysts frequently query WHERE region = 'West' AND status = 'Active'. Which index type is best suited for this column?

• A. B-tree, because it handles equality predicates efficiently
• B. Hash index, because equality lookups are O(1) on a hash
• C. Bitmap index, because the low cardinality makes bitwise AND operations across columns extremely fast
• D. No index — a sequential scan is faster when matching a large fraction of rows

Answer: (C)

With only 8 distinct values in 50M rows, 'region' is a classic low-cardinality column tailor-made for bitmap indexes. A bitmap stores one bit per row for each distinct value; combining filters like WHERE region = 'West' AND status = 'Active' becomes a single bitwise AND operation, which CPUs execute in bulk. B-trees and hash indexes handle point queries but cannot efficiently combine multi-column low-cardinality filters the way bitmaps can. Option D might be competitive, but for analytical queries in a write-infrequent warehouse, bitmap excels.

Question 2

An application needs to look up user records by UUID (a globally unique 128-bit identifier) using only exact-match queries. The table has 100 million rows. Which index would give the best lookup performance?

• A. B-tree, because it is the default and handles all query types
• B. Hash index, because UUIDs are high-cardinality and only equality lookups are needed, giving O(1) average performance
• C. Bitmap index, because UUIDs have high cardinality and low repetition
• D. No index — UUID lookups are always sequential scans

Answer: (B)

Hash indexes achieve O(1) average-case lookup for exact matches, beating B-tree's O(log n) for this specific use case. UUIDs are high-cardinality (nearly every row has a unique value), which is exactly where bitmaps fail (they'd need one bit-array per unique UUID — essentially the entire table size). The key is recognizing that hash indexes trade away range and sort capabilities for maximum equality-lookup speed, which is the right tradeoff when range queries will never be issued.

Question 3

A hash index on a column cannot be used to satisfy an ORDER BY clause on that column.

• T. True
• F. False

Answer: True

Hash indexes map keys to buckets via a hash function that deliberately scatters values — the storage order has no relationship to the key's sort order. Retrieving results in sorted order would require fetching all matching rows and sorting them afterward, defeating any index benefit. B-tree indexes, by contrast, store leaf pages in sorted key order linked in a list, so ORDER BY can be satisfied by a sequential scan of the leaf level without any additional sort step.

Question 4

Bitmap indexes are ideal for high-write OLTP systems because the compact bit-array format reduces storage overhead during frequent updates.

• T. True
• F. False

Answer: False

Bitmap indexes are poorly suited to OLTP workloads with frequent writes. Every INSERT, UPDATE, or DELETE requires modifying the bit arrays — potentially locking many rows simultaneously and causing heavy contention. Their strength is in read-heavy analytical environments (data warehouses) where data is loaded in bulk and queried extensively. The 'compact storage' of bitmaps becomes a liability under frequent writes, not an asset.

Question 5

Why can't a hash index support range queries, and what structural property of B-tree indexes allows them to do so efficiently?

Model answer: A hash index maps each key through a hash function to a bucket — the storage location has no relationship to the key's natural order. To answer WHERE price BETWEEN 10 AND 50, you would need to compute a hash for every possible value in the range, which is impossible for continuous or large-domain values. B-tree indexes store keys in sorted order in their leaf pages, and those leaf pages are linked together in a doubly-linked list. To answer a range query, the database finds the start of the range via the tree structure (O(log n)), then scans forward through the sorted leaf pages — accessing only the relevant rows in order, without touching unrelated data.

The structural difference is order preservation: B-trees preserve sort order at every level, enabling both point lookups (top-down traversal) and range scans (leaf-level sequential scan). Hash functions deliberately destroy order to achieve uniform distribution across buckets — this is why they excel at equality and fail at ranges. Understanding this tradeoff is the core of index selection.