Indexing Strategies
Index access methods suit different operations. This note compares B-tree, bitmap, hash, and full-text indexes using named engines. For composite index design, covering queries, and maintenance, see Database Indexing.
B-tree Indexing Strategy
B-tree-family indexes are one of the most widely used indexing methods in databases. They maintain sorted data in a tree-like structure, which allows for efficient insertion, deletion, and lookup operations.
Understanding B-tree Indexes
Imagine a library where books are organized alphabetically by title. Finding a book doesn't require scanning every single one; instead, you can quickly navigate to the section with the first letter, then to the specific book. B-tree indexes work similarly by keeping data sorted and balanced, ensuring that operations can be performed in logarithmic time.
Here's a simplified ASCII representation of a B-tree:
Tree:
[M]
/ \
[G] [T]
/ \ / \
[A-F] [H-L] [N-S] [U-Z]In this diagram:
- Each node represents a range of values.
- The tree is balanced, meaning all leaf nodes are at the same level.
- Searching for a value involves traversing from the root to a leaf node, making decisions at each node.
When to Use B-tree Indexes
B-tree indexes are ideal for columns where you frequently perform range queries, sorting, or need fast access to individual records based on a key. They are the default index type in many databases because of their versatility.
Example in PostgreSQL
Suppose you have a customers table with a last_name column, and you often search for customers by their last name or need to list them in alphabetical order.
Creating a B-tree index on the last_name column:
CREATE INDEX idx_customers_last_name ON customers(last_name);Example input (customers):
| customer_id | first_name | last_name |
|---|---|---|
| 1 | Alice | Smith |
| 2 | Bob | Jones |
| 3 | Carol | Smith |
The optimizer can use this index for queries such as the following; it may still choose a scan when many rows match:
SELECT * FROM customers WHERE last_name = 'Smith';Result:
| customer_id | first_name | last_name |
|---|---|---|
| 1 | Alice | Smith |
| 3 | Carol | Smith |
How B-tree Indexes Improve Performance
Without an index, the database would perform a full table scan to find all customers with the last name 'Smith'. With the B-tree index, it can quickly locate the matching entries without scanning unnecessary rows.
Bitmap Indexing Strategy
Bitmap indexes are designed for columns with a limited number of distinct values, known as low cardinality. They use bit arrays (bitmaps) to represent the presence or absence of a value, allowing for fast logical operations.
Understanding Bitmap Indexes
Consider a table that records survey responses, with a gender column that can be 'Male', 'Female', or 'Other'. A bitmap index creates a separate bitmap for each distinct value:
Gender Column:
Row IDs: 1 2 3 4 5 6 7 8 9
'Male' Bitmap: 1 0 1 0 1 0 1 0 1
'Female' Bitmap: 0 1 0 1 0 1 0 1 0
'Other' Bitmap: 0 0 0 0 0 0 0 0 0- Each bitmap is a sequence of bits where each bit represents a row.
- A '1' indicates the presence of the value in that row; a '0' indicates absence.
- Logical operations (AND, OR) can be performed quickly across bitmaps.
When to Use Bitmap Indexes
Bitmap indexes are particularly effective in data warehousing environments where queries often involve multiple conditions on low-cardinality columns. They excel at combining conditions using logical operations.
Example in Oracle Database
Suppose you have a sales table with a region column that has a small set of possible values ('North', 'South', 'East', 'West').
Creating a bitmap index:
CREATE BITMAP INDEX idx_sales_region ON sales(region);This index speeds up queries like:
SELECT COUNT(*) FROM sales WHERE region = 'North' AND product_category = 'Electronics';Example input (sales):
| sale_id | region | product_category |
|---|---|---|
| 1 | North | Electronics |
| 2 | North | Books |
| 3 | South | Electronics |
| 4 | North | Electronics |
Result:
| COUNT(*) |
|---|
| 2 |
Advantages and Considerations
- Advantages: Efficient for complex queries involving multiple low-cardinality columns; reduced storage space due to bitmap compression.
- Considerations: Not suitable for columns with high cardinality; bitmap indexes can cause contention issues in environments with frequent updates.
Hash Indexing Strategy
Hash indexes use a hash function to map values to a location in a hash table, enabling fast retrieval for equality comparisons.
Understanding Hash Indexes
Imagine a library where each book is assigned a unique code generated by a hash function based on the book's title. When you want to find a book, you input the title into the hash function and go directly to the location where it's stored.
Here's a conceptual diagram:
Hash Function: H(value) -> Location
Values:
- 'Apple' -> H('Apple') -> Location 5
- 'Banana' -> H('Banana') -> Location 2
- 'Cherry' -> H('Cherry') -> Location 8- The hash function computes a location for each value.
- Lookup is performed by computing the hash of the search value and accessing the corresponding location.
When to Use Hash Indexes
Hash indexes support equality searches. PostgreSQL hash indexes cannot enforce uniqueness; primary-key and unique constraints normally use B-tree indexes. They are not suitable for range queries or sorting because the hash function does not preserve order.
Example in PostgreSQL
Suppose you have a users table with a username column that you want to index for fast lookup.
Creating a hash index:
CREATE INDEX idx_users_username ON users USING HASH (username);Querying with the index:
SELECT * FROM users WHERE username = 'johndoe';Example input (users):
| user_id | username |
|---|---|
| 1 | johndoe |
| 2 | janedoe |
Result:
| user_id | username |
|---|---|
| 1 | johndoe |
Limitations
- No Range Queries: Cannot efficiently handle queries like
username > 'j'. - Collision Handling: Hash functions can produce the same hash for different inputs, requiring collision resolution.
Full-Text Indexing Strategy
Full-text indexes are designed to handle complex searches within large text fields, such as searching for specific words or phrases in documents.
Understanding Full-Text Indexes
Consider a search engine that indexes the content of web pages to allow users to search for specific terms. Full-text indexing involves creating an inverted index that maps words to the documents they appear in.
Simplified diagram:
Word-to-Document Mapping:
'Database' -> Doc1, Doc3
'Index' -> Doc2, Doc3
'Query' -> Doc1, Doc2- Each word is linked to the documents containing it.
- Searching for documents containing 'Database' and 'Index' involves finding the intersection of their lists.
When to Use Full-Text Indexes
Full-text indexes are ideal for columns containing large amounts of text where you need to perform searches based on words or phrases, such as product descriptions, articles, or comments.
Example in PostgreSQL
Suppose you have an articles table with a content column containing the text of each article.
Creating a full-text index:
CREATE INDEX idx_articles_content ON articles USING GIN (to_tsvector('english', content));Searching using the index:
SELECT title FROM articles WHERE to_tsvector('english', content) @@ to_tsquery('database & indexing');Example input (articles):
| title | content |
|---|---|
| Index Design | Database indexing helps select rows efficiently. |
| Query Basics | Learn database queries and joins. |
| Storage Notes | Index structures organize stored pages. |
Result:
| title |
|---|
| Index Design |
This query finds articles that contain both 'database' and 'indexing'.
Features and Benefits
- Advanced Search Capabilities: Supports stemming, ranking, and phrase searching.
- Performance: Significantly improves the speed of text searches compared to scanning entire text fields.
Best Practices for Indexing
Effective indexing improves query performance while managing resource costs.
Analyze Query Patterns
- Applications performing equality searches benefit from hash indexes, which provide fast lookups for exact matches.
- Queries involving range conditions or sorting operations are well-suited to B-tree indexes, which support ordered data access.
- Columns with low cardinality may perform better with bitmap indexes, especially in cases involving multiple conditions.
- Text fields requiring search functionality can use full-text indexes for optimized searching.
Monitor and Maintain Indexes
- Index maintenance is engine- and workload-specific. Rebuild or reorganize an index only when measured bloat, corruption, page-layout behavior, or vendor guidance justifies it; routine rebuilds can create substantial I/O and locking without improving the workload.
- Keeping database statistics updated is important for the query optimizer to make informed decisions.
- Excessive indexing should be avoided, as it can degrade performance of write-intensive operations such as INSERT, UPDATE, and DELETE.
Balance Performance and Resources
- Indexing should focus on columns that are frequently queried to avoid unnecessary overhead.
- Queries filtering on multiple columns simultaneously can benefit from composite indexes.
- Storage costs should be evaluated, particularly for large datasets, to balance performance benefits against space requirements.
Testing and Iteration
- Developing indexes in a controlled environment allows for testing their impact on query performance without affecting production systems.
- Query execution can be analyzed using EXPLAIN plans to ensure indexes are being utilized effectively.
- Continuous monitoring after deployment helps identify any unexpected impacts, enabling further adjustments as needed.
Performance cost of an index
An index moves work rather than making it disappear.
~~~text faster matching reads vs more storage + more write maintenance ~~~
Every INSERT may need new index entries. Updating an indexed column may require index maintenance, and extra indexes consume cache space. Measure both read savings and write cost.
The repository includes a runnable local demonstration:
~~~bash python scripts/performance/sqlite_index_write_cost_demo.py ~~~
It inserts the same synthetic workload into a minimally indexed SQLite database and one with several secondary indexes, then compares local elapsed time and file size. The exact numbers are machine-specific; the lesson is that each index has ongoing cost.