Database Indexing Algorithms: B‑Tree vs Hash Indexing

Database indexes are essential for optimizing the performance of any database system. Without effective indexes, queries can become slow and inefficient, harming user experience and productivity. This article explores best practices for creating and using different types of database indexes.

1 B‑Tree Index

B‑Tree indexes are self‑balancing tree structures that keep data sorted and allow logarithmic‑time search, sequential access, insertion, and deletion. They are widely used in relational databases such as MySQL and PostgreSQL. B‑Tree indexes excel at range queries because records are stored in sorted order.

Example table definition:

CREATE TABLE products (
    id INT PRIMARY KEY,
    name VARCHAR(255),
    price DECIMAL(10,2)
);

Creating a B‑Tree index on the price column:

CREATE INDEX products_price_index ON products (price);

2 Hash Index

Hash indexes use a hash function to map keys to index positions, making them ideal for exact‑match queries such as primary‑key lookups. They are commonly used in in‑memory databases like Redis. However, hash indexes do not support efficient range queries or sorting because the hash function discards ordering information.

Steps to use a hash index:

Compute the hash value of the query condition.

Locate the corresponding hash bucket.

Retrieve the pointer to the row with that hash value.

Fetch the actual row from the table using the pointer.

Creating a hash index on the name column:

CREATE INDEX products_name_hash ON products (name);
SELECT * FROM products WHERE name = 'iPhone 13 Pro';

Comparing B‑Tree and hash indexes for a range query (price BETWEEN 100 AND 200) demonstrates why B‑Tree is preferred for such operations.

3 Working Principle

B‑Tree

The database starts at the root of the tree and compares the search key with the key stored at the root.

If the key matches, the record is returned; otherwise, the appropriate subtree is chosen based on the comparison.

Hash

Hash indexes map each record to a unique bucket based on its hash value. Because buckets store records in a random order, range queries require scanning many buckets, effectively turning into a full‑table scan. Hash indexes are fast for exact matches but poor for ordered or range queries.

4 Bitmap Index

Bitmap indexes are suited for columns with a low cardinality (e.g., boolean or gender fields). They store a compact bitmap for each distinct value, enabling fast set operations such as unions and intersections, making them ideal for reporting and data‑warehouse scenarios.

SELECT * FROM employees WHERE gender = 'Female';

5 Full‑Text Index

Full‑text indexes are designed for large text data, breaking documents into words or tokens and allowing efficient search operations. They are commonly used in search engines like Elasticsearch and are valuable for e‑commerce product search, supporting relevance ranking, phrase matching, and fuzzy search.

Creating a full‑text index on products (name, description, tags):

CREATE FULLTEXT INDEX products_ft_index ON products(name, description, tags);

Example query to find products related to "running shoes":

SELECT id, name, description, MATCH(name, description, tags) AGAINST('running shoes') AS relevance
FROM products
WHERE MATCH(name, description, tags) AGAINST('running shoes' IN BOOLEAN MODE)
ORDER BY relevance DESC;

Full‑text indexes excel at text‑based columns but consume significant storage space and may degrade performance on very large datasets.

Overall, choosing the right index type depends on query patterns: use B‑Tree for range and sorted queries, hash for exact matches on in‑memory data, bitmap for low‑cardinality columns, and full‑text for searching large bodies of text.