SQL 73 🛢️ B-Tree, Hash, and Bitmap Indexes
An index is only as good as the data structure underneath it. The previous chapter established why indexes exist and how selectivity drives the optimizer’s decisions. This chapter goes one level deeper and examines the three fundamental index structures that relational databases actually implement: the B-tree, the hash table, and the bitmap. Each structure makes a different trade between the operations it supports, the storage it consumes, and the concurrency it allows. The B-tree is the generalist, capable of almost anything. The hash index is the specialist, unbeatable at exact equality and useless at everything else. The bitmap index is the analyst’s tool, compact and fast for low-cardinality columns in read-heavy warehouses, and unusable in write-heavy transactional systems. Understanding these three structures is what separates a developer who creates indexes by intuition from one who chooses them by design.
Key point: The B-tree, hash, and bitmap indexes are not competing implementations of the same idea. They are three different data structures that support three different sets of operations, and the correct choice depends entirely on which operations your workload actually performs.
Why three index structures exist
The one-size-fits-all problem. A B-tree can answer equality queries, range queries, and sorted queries. That versatility is why it is the default. But versatility has a cost: every B-tree entry stores the full key value plus pointers, and every comparison during a descent walks a multi-level tree. If your workload only ever asks “does this exact value exist,” the B-tree is doing more work than necessary. The hash index exists to strip away everything the B-tree does except equality, and to do that one operation faster.
The low-cardinality problem. A B-tree on a column with only a few distinct values, such as a status column with four possible states, is nearly useless. The optimizer ignores it because a lookup matches too many rows. But analytical queries frequently filter on exactly these low-cardinality columns: WHERE region = 'North', WHERE product_type = 'Electronics', WHERE status = 'shipped'. The bitmap index exists to make these queries efficient by storing, for each distinct value, a compact bit vector marking which rows carry that value. Combining multiple bitmaps with bitwise AND and OR is dramatically cheaper than intersecting sorted lists of row identifiers.
The write-pattern problem. B-trees handle concurrent writes gracefully: a single-row insert touches one leaf, and the structure stays balanced. Hash indexes handle writes similarly but cannot support range operations, so they are only chosen when equality dominates. Bitmap indexes are catastrophic under concurrent writes, because a single update to a row requires modifying the bitmap for the old value and the bitmap for the new value, and those bitmaps are shared across millions of rows. Any concurrent modification to a different row in the same bitmap forces a lock on the entire bitmap. This is why bitmap indexes are essentially read-only structures, confined to data warehouses where bulk loads happen in batch windows.
The storage problem. A B-tree entry on a wide column stores the entire key value at every level of the tree. A bitmap index stores one bit per row per distinct value, plus a mapping from bit position to row identifier. For a column with ten distinct values and one hundred million rows, a bitmap index needs roughly 125 megabytes of raw bit vectors, while a B-tree needs several gigabytes. This compression is why bitmap indexes exist in analytical systems: they make it feasible to index columns that a B-tree would bloat.
The hybrid reality. Real database systems rarely use a single index type in isolation. PostgreSQL offers B-tree, hash, GIN, GiST, SP-GiST, and BRIN. Oracle offers B-tree, bitmap, bitmap join, and function-based indexes. SQL Server has clustered, nonclustered, columnstore, and hash indexes for memory-optimized tables. A production schema typically mixes several types, choosing each one for the specific query pattern it serves. The rest of this chapter examines the three primary structures and the situations that call for each.
a. B-tree indexes in depth
The B-tree is the default index in every major relational database for one reason: it supports the widest range of operations with predictable logarithmic performance. Understanding its internals is what allows a developer to reason about why a particular query uses an index or ignores it.
The node structure
A B-tree node is a page-sized block, typically eight kilobytes in PostgreSQL and InnoDB, containing a sorted array of keys and a parallel array of child pointers. A leaf node stores the indexed key and a pointer to the heap tuple. An internal node stores the indexed key and pointers to child nodes. The keys in an internal node act as separators: everything to the left of a key is less than it, everything to the right is greater.
-- A B-tree node, conceptually, with capacity for four keys:
-- Internal node: [key=20 | key=40 | key=60 | key=80]
-- Child pointers: [p0, p1, p2, p3, p4]
-- p0 → subtree with keys < 20
-- p1 → subtree with 20 <= keys < 40
-- p2 → subtree with 40 <= keys < 60
-- p3 → subtree with 60 <= keys < 80
-- p4 → subtree with keys >= 80A real node holds hundreds of keys, not four, because the keys are small and the page is large. This high branching factor is what keeps the tree shallow.
Descent and the logarithmic bound
A lookup begins at the root and descends one level per comparison step. At each internal node, a binary search over the sorted keys identifies the correct child pointer. The descent continues until a leaf is reached, where the entry is either found or absent. The number of levels is logarithmic in the number of entries, and because the base of the logarithm is the branching factor, which is in the hundreds, the height stays small.
-- B-tree lookup for key = 55
-- Level 0 (root): [20 | 40 | 60 | 80]
-- 55 is between 40 and 60, descend to p2.
-- Level 1: [42 | 48 | 54 | 58]
-- 55 is between 54 and 58, descend to p3.
-- Level 2 (leaf): [54, 55, 56, 57]
-- 55 found. Return heap pointer.
-- Total: three page reads.For a table with one billion rows and a branching factor of 200, the height is log base 200 of one billion, which is approximately four. Four page reads to find any row in a billion-row table. This is the fundamental promise of the B-tree.
Leaf chaining and range scans
Leaf nodes are linked in a doubly linked list sorted by key. This is the defining feature of the B+Tree variant that all production databases use. A range query descends to the first matching leaf, then walks the chain until the range is exhausted, never returning to the internal nodes.
-- Range query: WHERE id BETWEEN 100 AND 150
-- Descend to the leaf containing 100.
-- Walk leaf chain: [100, 101, ... 149, 150] then stop.
-- The internal nodes were visited only once, during the descent.This is why a B-tree can satisfy an ORDER BY clause without an explicit sort. If the query orders by the indexed column, the leaf chain is already in that order.
Write path: insertion and page splits
An insert descends to the correct leaf and adds the entry. If the leaf has room, the insert is cheap: one page read, one page write. If the leaf is full, it splits into two half-full leaves, and the parent node is updated with a new separator key. If the parent is also full, the split cascades upward. In the worst case, a split reaches the root, which then creates a new root and increases the tree height by one.
-- Leaf before insert: [10, 20, 30, 40] (full, capacity four)
-- Insert key = 25.
-- Leaf splits:
-- Left: [10, 20]
-- Right: [25, 30, 40]
-- Parent gains separator key = 25 with pointer to the right leaf.Page splits are the reason random inserts are slower than sequential inserts. A sequential insert always appends to the rightmost leaf, which stays cached in memory, and the leaf fills completely before splitting. A random insert touches a different leaf every time, forcing page reads from disk, and the tree’s nodes stay partially empty because random splits leave them half full. This is why databases recommend using monotonically increasing primary keys, such as sequences or auto-increment columns, rather than random UUIDs.
The deduplication optimization
PostgreSQL 13 introduced B-tree deduplication, which allows a single index entry to reference multiple heap tuples when the indexed key values are identical. This dramatically reduces the size of indexes on columns with many duplicate values, and it speeds up scans because fewer leaf entries need to be visited for the same number of heap tuples.
-- Before deduplication:
-- Leaf entries for a low-cardinality column:
-- ('pending', ptr1), ('pending', ptr2), ('pending', ptr3), ...
-- After deduplication:
-- ('pending', [ptr1, ptr2, ptr3, ...]) -- one entry, many pointersWhen the B-tree is the wrong choice
The B-tree is rarely the wrong choice, but there are situations where it is not the best one. If the workload is pure equality lookups with no range or sort requirement, a hash index may be faster. If the column has very low cardinality and the table is large and read-only, a bitmap index may be far smaller. If the table is enormous and physically ordered by a timestamp column, a BRIN index may be a fraction of the size of a B-tree at comparable query speed. The B-tree remains the safe default, but not always the optimal one.
b. Hash indexes in depth
A hash index answers exactly one question: “which rows have this exact value?” It cannot answer ranges, cannot sort, and cannot enforce uniqueness in some implementations. Within its narrow scope, it is the fastest structure available.
The hash function and the bucket array
A hash index is an array of buckets. When a row is indexed, the database computes a hash of the indexed key, takes that hash modulo the bucket count, and appends the row’s identifier to the linked list of that bucket. A lookup computes the same hash, goes directly to the bucket, and scans the short chain for a matching entry. On average, if the bucket count is well matched to the number of distinct keys, the chain length is one or two entries.
-- Hash index on users(username), 1024 buckets.
-- hash('alice') % 1024 = 137
-- hash('bob') % 1024 = 842
-- hash('carol') % 1024 = 137 -- collision with alice
-- Bucket 137: ['alice' → ptr1, 'carol' → ptr2]
-- Lookup for 'alice': hash, bucket 137, scan chain, find match.The collision problem and chain length
The performance of a hash index depends entirely on the distribution of hash values across buckets. A good hash function distributes keys uniformly, so chain lengths stay short. A poor hash function or an undersized bucket array produces long chains, and lookup degrades toward linear scan of the bucket. The rule of thumb, from Microsoft’s documentation, is to keep the bucket count within ten times the actual number of distinct keys, erring on the side of more buckets rather than fewer.
-- SQL Server memory-optimized hash index
ALTER TABLE MyTable_memop
ADD INDEX ix_hash_Column2 UNIQUE HASH (Column2)
WITH (BUCKET_COUNT = 65536);
-- 65,536 buckets for a column with, say, 20,000 distinct values.
-- Average chain length: 20,000 / 65,536 ≈ 0.3, mostly empty or single.Why hash indexes cannot do ranges
A hash function destroys ordering. Two keys that are numerically adjacent, such as 100 and 101, produce completely unrelated hash values. There is no way to walk the index in key order because the index is not stored in key order. This is not a limitation of a particular implementation; it is a mathematical property of hashing. Any structure that maps keys to buckets by a hash function loses the information needed for range scans.
-- These queries cannot use a hash index on price:
SELECT * FROM products WHERE price > 100; -- range
SELECT * FROM products WHERE price BETWEEN 10 AND 20; -- range
SELECT * FROM products ORDER BY price; -- sort
SELECT MIN(price) FROM products; -- aggregate
-- All of them fall back to a sequential scan or a B-tree.PostgreSQL hash index limitations
PostgreSQL has supported hash indexes since its early versions, but they were not crash-safe until PostgreSQL 10. Even today, PostgreSQL hash indexes have a significant limitation: they do not support unique constraints. Only B-tree indexes can enforce uniqueness. This means that even if a hash index is faster for equality on a given column, a unique B-tree is required alongside it if the column must be unique.
-- PostgreSQL: this is allowed.
CREATE INDEX idx_hash_username ON users USING HASH (username);
-- This is not allowed; hash indexes cannot enforce uniqueness.
CREATE UNIQUE INDEX idx_hash_username ON users USING HASH (username);
-- ERROR: access method "hash" does not support unique indexesWhere hash indexes actually win
The primary use case for hash indexes is memory-optimized tables in SQL Server, where the entire index resides in RAM. In that setting, the hash index avoids the multi-level pointer chasing of a B-tree and provides direct bucket access in a single memory reference. For disk-based tables, the B-tree is usually competitive or better, because the B-tree’s height is already small enough that the extra levels cost little, and the B-tree offers far more functionality.
-- SQL Server memory-optimized table with hash index
CREATE TABLE SessionCache (
SessionId INT NOT NULL PRIMARY KEY NONCLUSTERED HASH
WITH (BUCKET_COUNT = 1048576),
UserId INT NOT NULL,
CreatedAt DATETIME2 NOT NULL
) WITH (MEMORY_OPTIMIZED = ON, DURABILITY = SCHEMA_AND_DATA);c. Bitmap indexes in depth
A bitmap index represents each distinct value of a column as a bit vector with one bit per row in the table. A set bit means the row carries that value; a clear bit means it does not. The structure is designed for low-cardinality columns in read-heavy analytical workloads, where queries filter on multiple such columns and the bitmaps can be combined with fast bitwise operations.
The bit vector representation
For a column with ten distinct values and one hundred million rows, a bitmap index stores ten bit vectors, each one hundred million bits long, totaling about 125 megabytes. A B-tree index on the same column would store one hundred million entries, each carrying the value and a row pointer, requiring on the order of a gigabyte or more. The compression ratio is roughly ten to one or better, which is why bitmap indexes are feasible on columns that a B-tree would make prohibitively large.
-- Table: sales, 100,000,000 rows.
-- Column: region, values: North, South, East, West.
-- Bitmap for 'North': 10000001000000100000010000001000...
-- Bitmap for 'South': 00000000000000000000000000000000... (conceptually)
-- Bitmap for 'East': 00000000100000000000000000000000...
-- Bitmap for 'West': 00000000000000000000000000000000...
-- Query: SELECT COUNT(*) FROM sales WHERE region = 'North';
-- Scan the 'North' bitmap, count set bits.
-- Counting bits is fast; no row access needed.Bitwise combination
The power of bitmap indexes emerges when a query filters on multiple low-cardinality columns. The database fetches the bitmap for each predicate and combines them with bitwise AND for conjunction, OR for disjunction, and NOT for negation. These operations run at memory bandwidth, processing many rows per CPU cycle.
-- Query: WHERE region = 'North' AND product_type = 'Electronics'
-- Bitmap for region = 'North':
-- 10000001000000100000010000001000...
-- Bitmap for product_type = 'Electronics':
-- 10000001000000000000010000001000...
-- Bitwise AND:
-- 10000001000000000000010000001000...
-- Each set bit marks a row satisfying both conditions.
-- Convert set bit positions to row identifiers, fetch those rows.For a query combining three or four such conditions, the intersection is computed in a few passes over the bit vectors, and the resulting set of matching rows is typically small. This is why bitmap indexes are the backbone of star-schema data warehouses, where fact-table queries routinely filter on several dimension keys at once.
The concurrency killer
The property that makes bitmap indexes compact also makes them dangerous under concurrent writes. Every row of the indexed column shares the same bit vector for a given value. A single update to a row changes the value in that column, which requires clearing a bit in the bitmap for the old value and setting a bit in the bitmap for the new value. Those two bitmaps are shared across all rows with the same values, so the update must lock the relevant portions of both bitmaps. If another transaction concurrently updates a different row whose old value maps to the same bitmap, the two transactions contend on the same structure, even though their target rows are unrelated.
-- Transaction A: UPDATE sales SET region = 'South' WHERE id = 100;
-- Clears bit 100 in 'North' bitmap, sets bit 100 in 'South' bitmap.
-- Transaction B: UPDATE sales SET region = 'East' WHERE id = 500;
-- Clears bit 500 in 'North' bitmap, sets bit 500 in 'East' bitmap.
-- Both transactions touch the 'North' bitmap. They serialize.
-- In a B-tree, these updates would target different leaves and proceed in parallel.This is why Oracle, the primary commercial database offering bitmap indexes, documents them as unsuitable for OLTP environments and recommends them only for data warehouses where writes are batched and controlled. PostgreSQL does not have a native bitmap index type for this reason, though it uses a related mechanism, bitmap heap scans, internally at query time.
Bitmap heap scans versus bitmap indexes
The term “bitmap” appears in two different contexts in PostgreSQL, and conflating them causes confusion. A bitmap index is a persistent index structure where each value maps to a bit vector. A bitmap heap scan is a query execution strategy where the database converts the output of an ordinary index scan, such as a B-tree, into a temporary bitmap of matching row locations, sorts the bitmap by physical page address, then reads the heap in physical order. The bitmap heap scan reduces random I/O by grouping heap accesses into page order, but it is a runtime optimization, not an index type.
-- PostgreSQL Bitmap Heap Scan using a B-tree index
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id IN (42, 99, 137);
-- Bitmap Heap Scan on orders
-- Recheck Cond: (customer_id = ANY ('{42,99,137}'))
-- -> Bitmap Index Scan on idx_orders_customer
-- Index Cond: (customer_id = ANY ('{42,99,137}'))
-- The index scan produces three sets of row locations,
-- merges them into one bitmap sorted by page,
-- then reads the heap once in physical order.This is a different mechanism from an Oracle bitmap index, but it serves a similar purpose at query time: reducing the cost of fetching scattered rows.
When bitmap indexes are appropriate
Bitmap indexes belong in read-mostly environments with low-cardinality columns and complex conjunctive filters. A star-schema fact table with foreign keys to a dozen dimension tables, each with a few dozen distinct values, is the canonical use case. The indexes stay small, the bitwise operations are fast, and the batch-loading window keeps concurrency low. In an OLTP system with constant single-row updates and high-cardinality columns, a bitmap index is a performance disaster waiting to happen.
Complete Example Session
-- ============================================
-- PART 1: THE SCENARIO
-- ============================================
-- Two workloads on the same conceptual data.
-- OLTP table: high write rate, point lookups, high cardinality.
CREATE TABLE users (
user_id BIGSERIAL PRIMARY KEY,
username VARCHAR(50) NOT NULL,
email VARCHAR(255) NOT NULL,
created_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);
-- Analytical table: bulk loaded, complex filters, low cardinality.
CREATE TABLE sales (
sale_id BIGSERIAL,
region VARCHAR(20) NOT NULL,
product_type VARCHAR(30) NOT NULL,
channel VARCHAR(20) NOT NULL,
amount DECIMAL(12,2) NOT NULL,
sale_date DATE NOT NULL
);
-- ============================================
-- PART 2: B-TREE FOR THE OLTP TABLE
-- ============================================
-- Username lookups: exact equality, must be unique.
CREATE UNIQUE INDEX idx_users_username
ON users USING BTREE (username);
-- Email lookups: exact equality, must be unique.
CREATE UNIQUE INDEX idx_users_email
ON users USING BTREE (email);
-- Created_at lookups: range queries for reporting.
CREATE INDEX idx_users_created
ON users USING BTREE (created_at);
-- All three are B-trees. Username and email need uniqueness,
-- which only B-tree can enforce. Created_at needs range support,
-- which only B-tree provides.
-- ============================================
-- PART 3: HASH INDEX FOR EQUALITY-ONLY LOOKUP
-- ============================================
-- Suppose the application also does many non-unique lookups
-- on a session token column that is never range-queried.
ALTER TABLE users ADD COLUMN session_token VARCHAR(64);
-- A hash index is smaller and faster for pure equality.
CREATE INDEX idx_users_session_hash
ON users USING HASH (session_token);
-- Query:
EXPLAIN ANALYZE
SELECT * FROM users WHERE session_token = 'abc123def456';
-- Index Scan using idx_users_session_hash on users
-- Index Cond: (session_token = 'abc123def456'::text)
-- The hash index computes the hash, jumps to the bucket,
-- and finds the entry in one page access.
-- ============================================
-- PART 4: THE HASH INDEX LIMITATION
-- ============================================
-- What happens with a range query on the hash-indexed column?
EXPLAIN ANALYZE
SELECT * FROM users WHERE session_token > 'abc';
-- Seq Scan on users
-- Filter: (session_token > 'abc'::text)
-- The optimizer cannot use the hash index.
-- Hash indexes have no ordering, so range queries fall back
-- to a sequential scan. This is expected and unavoidable.
-- ============================================
-- PART 5: BITMAP INDEX FOR THE WAREHOUSE TABLE
-- ============================================
-- The sales table is bulk-loaded nightly and queried with
-- multi-column filters on low-cardinality columns.
-- Oracle syntax (PostgreSQL has no persistent bitmap index):
CREATE BITMAP INDEX idx_sales_region
ON sales(region);
CREATE BITMAP INDEX idx_sales_product
ON sales(product_type);
CREATE BITMAP INDEX idx_sales_channel
ON sales(channel);
-- Each index is a set of bit vectors, one per distinct value.
-- region: 4 values → 4 bit vectors.
-- product_type: 5 values → 5 bit vectors.
-- channel: 3 values → 3 bit vectors.
-- ============================================
-- PART 6: QUERYING WITH BITMAP INDEXES
-- ============================================
-- A conjunctive filter over three low-cardinality columns.
SELECT SUM(amount) FROM sales
WHERE region = 'North'
AND product_type = 'Electronics'
AND channel = 'Online';
-- Oracle execution:
-- 1. Fetch bitmap for region = 'North'.
-- 2. Fetch bitmap for product_type = 'Electronics'.
-- 3. Fetch bitmap for channel = 'Online'.
-- 4. Bitwise AND the three bitmaps.
-- 5. Convert set bits to row identifiers.
-- 6. Fetch only those rows, sum amount.
-- The bitwise AND processes many rows per CPU cycle.
-- Without bitmap indexes, the same query scans the whole table.
-- ============================================
-- PART 7: THE WRITE PROBLEM WITH BITMAPS
-- ============================================
-- Insert a single row into the sales table.
INSERT INTO sales (region, product_type, channel, amount, sale_date)
VALUES ('North', 'Electronics', 'Online', 199.99, '2026-06-15');
-- Oracle must update:
-- 'North' bitmap: set bit for the new row.
-- 'Electronics' bitmap: set bit for the new row.
-- 'Online' bitmap: set bit for the new row.
-- Three bitmaps, each shared across millions of rows.
-- Any concurrent insert touching 'North' serializes with this one.
-- At OLTP write rates, this becomes a bottleneck immediately.
-- ============================================
-- PART 8: B-TREE VERSUS BITMAP FOR THE SAME QUERY
-- ============================================
-- The same conjunctive query on a B-tree-indexed table.
-- With three B-tree indexes on (region), (product_type), (channel):
-- The optimizer picks the most selective one.
-- It scans that index, fetches rows, and filters the rest.
-- If each predicate matches 20% of rows, the chosen index
-- returns 20% of the table, and the other predicates are
-- applied as filters on the heap. 80% of fetched rows are discarded.
-- With three bitmap indexes:
-- All three predicates are applied before any heap access.
-- The AND produces a much smaller set, often 1-2% of the table.
-- Only those rows are fetched.
-- For multi-column low-cardinality filters, bitmaps win decisively.
-- For single-column or high-cardinality filters, B-trees win.
-- ============================================
-- PART 9: POSTGRESQL BITMAP HEAP SCAN
-- ============================================
-- PostgreSQL has no persistent bitmap index, but it uses a
-- bitmap heap scan at query time to reduce random I/O.
CREATE INDEX idx_orders_customer ON orders(customer_id);
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE customer_id IN (42, 99, 137, 256, 789);
-- Bitmap Heap Scan on orders
-- Recheck Cond: (customer_id = ANY (...))
-- Heap Blocks: exact=1240
-- -> Bitmap Index Scan on idx_orders_customer
-- Index Cond: (customer_id = ANY (...))
-- The B-tree index scan produces five sets of row locations.
-- PostgreSQL merges them into one bitmap sorted by page.
-- The heap is then read in physical page order, one pass.
-- This avoids five separate random-access passes.
-- ============================================
-- PART 10: CHOOSING THE RIGHT STRUCTURE
-- ============================================
-- Decision rules:
--
-- 1. Default choice: B-tree.
-- Supports equality, range, sort, uniqueness.
--
-- 2. Equality-only, high cardinality, memory-resident: Hash.
-- Faster than B-tree for exact lookups, useless for ranges.
--
-- 3. Low-cardinality columns, multi-column filters, read-only: Bitmap.
-- Compact, fast bitwise combination, unusable under concurrent writes.
--
-- 4. Time-series or append-only with physical ordering: BRIN.
-- Tiny index, summarizes block ranges, ideal for logs.
--
-- The choice is driven by the query pattern, not by preference.The ten parts moved from schema design through B-tree, hash, and bitmap indexes on realistic workloads, showing where each structure excels and where each breaks down. The OLTP users table and the analytical sales table illustrated why no single index type serves every workload.
Quick Reference
Operation Support by Index Type
| Operation | B-Tree | Hash | Bitmap |
|---|---|---|---|
| Equality | Yes | Yes | Yes |
| Range | Yes | No | No |
| Sort | Yes | No | No |
| Unique constraint | Yes | No | No |
| Multi-column AND | Via composite | No | Yes |
| Multi-column OR | Limited | No | Yes |
| Low-cardinality filter | Poor | Poor | Excellent |
| Concurrent writes | Good | Good | Terrible |
| Storage efficiency | Moderate | Moderate | High |
Storage Comparison
| Structure | Entry Size | 100M Rows, 4 Values | 100M Rows, 1M Values |
|---|---|---|---|
| B-tree | Key + pointer | ~2 GB | ~3 GB |
| Hash | Bucket + pointer | ~2 GB | ~2.5 GB |
| Bitmap | 1 bit per value | ~50 MB | Impractical |
Database Support
| Database | B-Tree | Hash | Bitmap |
|---|---|---|---|
| PostgreSQL | Yes | Yes | No (heap scan only) |
| MySQL InnoDB | Yes | No (adaptive only) | No |
| SQL Server | Yes | Memory-optimized only | No |
| Oracle | Yes | No | Yes |
When Each Structure Is Correct
| Workload | Structure | Reason |
|---|---|---|
| Primary key lookup | B-tree | Unique, equality, default |
| Login by email | B-tree | Unique constraint required |
| Session token lookup | Hash | Equality only, no uniqueness |
| Range report on dates | B-tree | Range and sort support |
| Star-schema dimension filter | Bitmap | Multi-column AND, read-only |
| Time-series append log | BRIN | Physically ordered, tiny index |
Best Practices
✅ Do This:
-- Default to B-tree for general-purpose indexing.
CREATE INDEX idx_users_email ON users USING BTREE (email); -- ✅
-- Use a unique B-tree for columns requiring uniqueness.
CREATE UNIQUE INDEX idx_users_username ON users(username); -- ✅
-- Use hash indexes for equality-only, high-cardinality lookups.
CREATE INDEX idx_session ON sessions USING HASH (token); -- ✅
-- Use bitmap indexes in data warehouses on low-cardinality columns.
CREATE BITMAP INDEX idx_sales_region ON sales(region); -- ✅
-- Use composite B-trees instead of bitmap for OLTP multi-column filters.
CREATE INDEX idx_a_b ON t(col_a, col_b); -- ✅
-- Match index type to the actual query pattern.
-- Verify with EXPLAIN before and after. -- ✅❌ Don’t Do This:
-- Don't use a hash index for range queries.
CREATE INDEX idx_date ON t USING HASH (created_at); -- ❌ Useless for ranges
-- Don't use bitmap indexes on OLTP tables.
CREATE BITMAP INDEX idx_status ON orders(status); -- ❌ Lock contention
-- Don't use bitmap indexes on high-cardinality columns.
CREATE BITMAP INDEX idx_user_id ON orders(user_id); -- ❌ Huge, slow
-- Don't expect a hash index to enforce uniqueness.
CREATE UNIQUE INDEX ... USING HASH (...); -- ❌ Not supported
-- Don't create a bitmap index on a column with thousands of values.
CREATE BITMAP INDEX idx_email ON users(email); -- ❌ Impractical size
-- Don't assume bitmap heap scan equals a bitmap index.
-- They are different mechanisms. -- ❌Common Pitfalls
| Pitfall | Why It Happens | Fix |
|---|---|---|
| Hash index ignored for range | Hash loses ordering | Use B-tree for range queries |
| Bitmap index deadlocks | Shared bitmaps lock on update | Use B-tree in OLTP; bitmap only in warehouse |
| Hash index larger than expected | Undersized bucket array | Size buckets to distinct key count |
| Bitmap index too large | High-cardinality column | Restrict bitmap to low-cardinality columns |
| Composite B-tree on wrong order | Leading column mismatch | Put equality columns first |
| Unique constraint not enforced | Hash does not support unique | Use B-tree for unique columns |
| Bitmap heap scan misunderstood | Runtime strategy, not index | Distinguish from persistent bitmap index |
| Index type not portable | Vendors differ | Verify support on target database |
Real-World Examples
1. Primary Key as B-Tree
CREATE TABLE users (id BIGSERIAL PRIMARY KEY, ...);
-- Primary key creates a unique B-tree automatically.2. Unique Email with B-Tree
CREATE UNIQUE INDEX idx_users_email ON users(email);
-- Uniqueness requires B-tree; hash cannot enforce it.3. Session Token with Hash
CREATE INDEX idx_sessions_token ON sessions USING HASH (token);
-- Equality-only lookups; hash is faster and smaller.4. Date Range with B-Tree
CREATE INDEX idx_orders_date ON orders(order_date);
SELECT * FROM orders WHERE order_date >= '2026-01-01';5. Star Schema with Bitmap Indexes
CREATE BITMAP INDEX idx_sales_region ON sales(region);
CREATE BITMAP INDEX idx_sales_channel ON sales(channel);
-- Oracle warehouse; queries combine filters with bitwise AND.6. Composite B-Tree for OLTP
CREATE INDEX idx_orders_cust_status ON orders(customer_id, status);
-- Multi-column filter in OLTP; composite B-tree instead of bitmap.7. BRIN for Log Tables
CREATE INDEX idx_logs_time ON logs USING BRIN (created_at);
-- Tiny index for naturally ordered append-only data.8. Bitmap Heap Scan in PostgreSQL
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id IN (1,2,3);
-- Bitmap Heap Scan merges multiple index scans into one heap pass.9. Detecting Index Type in PostgreSQL
SELECT indexname, indexdef FROM pg_indexes WHERE tablename = 'users';
-- indexdef shows USING btree or USING hash.10. Oracle Bitmap Index Monitoring
SELECT index_name, index_type FROM user_indexes
WHERE table_name = 'SALES';
-- index_type shows 'BITMAP' or 'NORMAL'.Visual
B-Tree, Hash, and Bitmap Structures
┌────────────────────────────────────────────────────────────┐
│ THREE INDEX STRUCTURES FOR THE SAME DATA │
│ │
│ B-TREE (ordered, hierarchical) │
│ ┌──────────────────────────────────────────────────┐ │
│ │ [20 | 40 | 60] │ │
│ │ / | \ │ │
│ │ [10|15] [30|35] [50|55] │ │
│ │ / \ / \ / \ │ │
│ │ leaves linked left to right │ │
│ └──────────────────────────────────────────────────┘ │
│ Supports: equality, range, sort, unique │
│ │
│ HASH (bucket array, unordered) │
│ ┌──────────────────────────────────────────────────┐ │
│ │ [0] → ptr1 │ │
│ │ [1] → (empty) │ │
│ │ [2] → ptr5 → ptr9 │ │
│ │ [3] → ptr3 │ │
│ │ [4] → (empty) │ │
│ └──────────────────────────────────────────────────┘ │
│ Supports: equality only │
│ │
│ BITMAP (one bit vector per distinct value) │
│ ┌──────────────────────────────────────────────────┐ │
│ │ 'North': 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 │ │
│ │ 'South': 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 │ │
│ │ 'East': 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 │ │
│ │ 'West': 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 │ │
│ └──────────────────────────────────────────────────┘ │
│ Supports: equality, multi-column AND/OR (read-only) │
│ │
└────────────────────────────────────────────────────────────┘B-Tree Descent for Equality and Range
┌────────────────────────────────────────────────────────────┐
│ B-TREE LOOKUP: ROOT TO LEAF IN LOGARITHMIC STEPS │
│ │
│ Root: [ 20 | 40 | 60 | 80 ] │
│ | │
│ Query 55: descend between 40 and 60. │
│ | │
│ v │
│ Internal: [ 42 | 48 | 54 | 58 ] │
│ | │
│ Query 55: descend between 54 and 58. │
│ | │
│ v │
│ Leaf: [ 54 | 55 | 56 | 57 ] --> heap ptr │
│ │
│ Query 55 found in 3 page reads. │
│ For a range 50..60, walk the leaf chain rightward. │
│ │
│ Height for 1B rows with branching factor 200: 4 levels. │
│ 4 page reads to reach any row in a billion-row table. │
│ │
└────────────────────────────────────────────────────────────┘Bitmap AND for Multi-Column Filters
┌────────────────────────────────────────────────────────────┐
│ BITMAP COMBINATION: THREE PREDICATES, ONE AND │
│ │
│ region = 'North' │
│ 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 │
│ │
│ product_type = 'Electronics' │
│ 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 │
│ │
│ channel = 'Online' │
│ 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 │
│ │
│ ─────────────────────────────── AND ──────────────── │
│ result: │
│ 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 │
│ │
│ Set bits: rows 1, 4, 9, 12. Fetch only those rows. │
│ Heap access reduced from 16 rows to 4. │
│ │
│ Each AND processes 64 rows per CPU word on a 64-bit │
│ machine. Thousands of rows filtered per memory cycle. │
│ │
└────────────────────────────────────────────────────────────┘Write Cost Comparison
┌────────────────────────────────────────────────────────────┐
│ WRITE COST: B-TREE vs HASH vs BITMAP │
│ │
│ ONE INSERT into a table with one index of each type: │
│ │
│ B-TREE │
│ Descend to leaf, insert entry, maybe split. │
│ Touches: 1 leaf page, maybe 1 parent page. │
│ Concurrency: other inserts on different leaves proceed. │
│ │
│ HASH │
│ Compute hash, append to bucket chain. │
│ Touches: 1 bucket page. │
│ Concurrency: other inserts on different buckets proceed.│
│ │
│ BITMAP │
│ Set bit in bitmap for new value. │
│ Touches: 1 shared bitmap page. │
│ Concurrency: ALL inserts with the same value serialize. │
│ This is why bitmap indexes cannot survive OLTP writes. │
│ │
└────────────────────────────────────────────────────────────┘Summary
| Item | Value |
|---|---|
| B-tree | Hierarchical, sorted, balanced tree; default index |
| Hash index | Bucket array keyed by hash; equality only |
| Bitmap index | One bit vector per distinct value; read-only analytical |
| B-tree height | Logarithmic in rows; typically 3-4 levels |
| Page split | B-tree leaf overflow; cost of random inserts |
| Bucket count | Hash index sizing parameter; affects chain length |
| Bitmap AND | Bitwise combination of predicates before heap access |
| Bitmap heap scan | PostgreSQL runtime strategy, not an index type |
| Concurrency | B-tree and hash tolerate writes; bitmap does not |
| Uniqueness | Only B-tree can enforce it |
| Low cardinality | Bitmap excels; B-tree struggles |
Key takeaways:
- The B-tree is the default because it does everything. Equality, range, sort, uniqueness, composite filters. When in doubt, use a B-tree. There is rarely a wrong answer in choosing one.
- Hash indexes are narrow specialists. They win on pure equality lookups with high cardinality in memory-resident settings, and they are useless for everything else. They cannot enforce uniqueness in PostgreSQL.
- Bitmap indexes trade write concurrency for read efficiency. They are compact, fast for multi-column low-cardinality filters, and catastrophic under concurrent writes. They belong in data warehouses, not OLTP systems.
- The index type must match the query pattern. A hash index on a range-queried column will never be used. A bitmap index on an OLTP table will cause lock contention. A B-tree on a boolean column will be ignored by the optimizer.
- Composite B-trees often replace bitmaps in OLTP. When a query filters on two or three columns, a composite B-tree with the right column order can be nearly as effective as a bitmap, without the write penalty.
- PostgreSQL’s bitmap heap scan is not a bitmap index. It is a runtime strategy that converts multiple index scans into one physically ordered heap pass. Do not confuse the two.
- The cost of a bad index choice is permanent. Unlike a slow query, which can be rewritten, a badly chosen index type imposes its cost on every write for the life of the schema. Choose with the workload in mind.
Remember: Index structures are not interchangeable. A B-tree, a hash, and a bitmap each support a different set of operations, each consumes a different amount of storage, and each tolerates a different level of write concurrency. The B-tree is the universal default and should be the first choice for almost any column. The hash index is a specialist for equality-only lookups where the B-tree’s ordering and range support are wasted. The bitmap index is a specialist for low-cardinality columns in read-heavy analytical workloads where its compact bit vectors and fast bitwise combination outweigh its inability to handle concurrent writes. Choosing the right structure begins with asking what operations the workload actually performs, and then selecting the structure that supports those operations most efficiently.
Stop using slow, ad-bloated tool sites! 🤮
🔎 Search “KandZ Tools” on Google to use many professional utilities for free.
KandZ.me is the ultimate minimalist hub for:
✅ Finance (Mortgage, Interest, Inflation)
✅ Tech (Base64, JSON, Dev Suite, IP)
✅ Health (BMI, BMR, TDEE)
✅ Productivity (Timer, Workspace, QR)
⚡️ Fast & Private
🔒 No data leaves your device
💎 100% Free
🔗 Use it now: https://tools.kandz.me
🔖 Bookmark it—you’ll need it later!