Database Indexes & Performance Optimization: B-Tree, Hash, Fulltext & Clustered

This guide covers database indexes and performance optimization comprehensively, including B-Tree, Hash, Fulltext, and Clustered indexes with practical examples.

In a Nutshell

Database indexes accelerate queries significantly by enabling fast data access. Different index types are optimized for different use cases.

Core Concept

Database indexes are specialized data structures that speed up data retrieval operations on database tables. They work much like the index in a book.

Index types and their characteristics:

B-Tree Index (Balanced Tree)

• Structure: Balanced tree with sorted values
• Use case: Equality, range searches, sorting
• Performance: O(log n) for search operations
• Examples: Primary keys, foreign keys, standard indexes

Hash Index

• Structure: Hash table with direct addressing
• Use case: Equality searches only (=)
• Performance: O(1) for exact matches
• Examples: Memory tables, exact lookups

Fulltext Index

• Structure: Inverted index for text search
• Use case: Full-text search, keyword search
• Performance: Optimized text search algorithms
• Examples: Document search, content search

Clustered Index

• Structure: Physical table sorting
• Use case: Primary key, frequent range queries
• Performance: Fast for primary key access
• Examples: Time series, log data

Key Takeaways

• B-Tree Index: Balanced tree for equality and range searches
• Hash Index: Direct addressing for exact matches
• Fulltext Index: Text search with stemming and relevance
• Clustered Index: Physical data storage ordered by index
• Performance: Query optimization through indexing
• Trade-offs: Storage space versus speed
• Database administration: Essential for database optimization

Core Components

1. Index structure: Tree, hash, inverted index
2. Index type: B-Tree, Hash, Fulltext, Clustered
3. Query type: Equality, range, fulltext
4. Performance metrics: Read time, write time, storage
5. Indexing strategy: Single-column, multi-column, covering
6. Optimization: EXPLAIN analysis, index tuning
7. Maintenance: Rebuild, fragmentation, statistics

Practical Examples

1. B-Tree Index Examples

-- MySQL B-Tree Index creation
CREATE INDEX idx_kunden_name ON kunden(name);
CREATE INDEX idx_bestellungen_datum ON bestellungen(bestelldatum);

-- Multi-column B-Tree Index
CREATE INDEX idx_kunden_stadt_name ON kunden(stadt, name);

-- Unique B-Tree Index
CREATE UNIQUE INDEX idx_email_unique ON kunden(email);

-- Query using B-Tree Index
EXPLAIN SELECT * FROM kunden WHERE name = 'Mustermann';
EXPLAIN SELECT * FROM bestellungen WHERE bestelldatum BETWEEN '2024-01-01' AND '2024-12-31';

-- Performance comparison
-- Without Index: Full Table Scan
SELECT * FROM grosse_tabelle WHERE spalte_x = 'wert';

-- With B-Tree Index: Index Seek
SELECT * FROM grosse_tabelle WHERE spalte_x = 'wert';

2. Hash Index Examples

-- MySQL Hash Index (Memory Engine only)
CREATE TABLE user_sessions (
    session_id VARCHAR(255) PRIMARY KEY,
    user_id INT,
    created_at TIMESTAMP,
    data TEXT,
    INDEX ((session_id)) USING HASH
) ENGINE=MEMORY;

-- PostgreSQL Hash Index
CREATE INDEX idx_hash_email ON benutzer USING HASH (email);

-- Query using Hash Index (equality only)
SELECT * FROM benutzer WHERE email = 'user@example.com';

-- Hash Index will NOT be used for:
SELECT * FROM benutzer WHERE email LIKE 'user%';  -- Range search
SELECT * FROM benutzer WHERE email > 'a';        -- Comparison operator

3. Fulltext Index Examples

-- MySQL Fulltext Index
CREATE TABLE artikel (
    id INT PRIMARY KEY,
    titel VARCHAR(255),
    inhalt TEXT,
    FULLTEXT KEY ft_inhalt (titel, inhalt)
);

-- Fulltext search
SELECT titel, inhalt 
FROM artikel 
WHERE MATCH(titel, inhalt) AGAINST('datenbank performance' IN NATURAL LANGUAGE MODE);

-- With relevance score
SELECT titel, 
       MATCH(titel, inhalt) AGAINST('datenbank performance' IN NATURAL LANGUAGE MODE) AS score
FROM artikel 
WHERE MATCH(titel, inhalt) AGAINST('datenbank performance' IN NATURAL LANGUAGE MODE)
ORDER BY score DESC;

-- Boolean mode for complex searches
SELECT titel, inhalt
FROM artikel 
WHERE MATCH(titel, inhalt) AGAINST('+datenbank +performance -mysql' IN BOOLEAN MODE);

-- PostgreSQL Fulltext Index
CREATE TABLE dokumente (
    id SERIAL PRIMARY KEY,
    titel VARCHAR(255),
    inhalt TEXT
);

-- Fulltext Index with tsvector
ALTER TABLE dokumente ADD COLUMN searchable_text tsvector;
UPDATE dokumente SET searchable_text = to_tsvector('german', titel || ' ' || inhalt);
CREATE INDEX idx_fulltext ON dokumente USING GIN(searchable_text);

-- Fulltext search in PostgreSQL
SELECT titel, ts_rank(searchable_text, plainto_tsquery('german', 'datenbank performance')) AS rank
FROM dokumente 
WHERE searchable_text @@ plainto_tsquery('german', 'datenbank performance')
ORDER BY rank DESC;

4. Clustered Index Examples

-- SQL Server Clustered Index
CREATE TABLE log_daten (
    log_id INT IDENTITY(1,1),
    zeitstempel DATETIME NOT NULL,
    nachricht VARCHAR(1000),
    level VARCHAR(10)
);

-- Clustered Index on timestamp (physical sorting)
CREATE CLUSTERED INDEX idx_log_zeitstempel ON log_daten(zeitstempel);

-- PostgreSQL Clustered Index (CLUSTER)
CREATE TABLE messwerte (
    id SERIAL PRIMARY KEY,
    sensor_id INT,
    zeitpunkt TIMESTAMP NOT NULL,
    wert DECIMAL(10,4)
);

-- Clustered Index on primary key (standard)
CREATE INDEX idx_messwerte_zeitpunkt ON messwerte(zeitpunkt);

-- Cluster table by index
CLUSTER messwerte USING idx_messwerte_zeitpunkt;

-- MySQL InnoDB Clustered Index (automatically on primary key)
CREATE TABLE transaktionen (
    id BIGINT PRIMARY KEY,  -- Automatically clustered
    konto_id INT,
    betrag DECIMAL(12,2),
    datum DATETIME,
    INDEX idx_konto_datum (konto_id, datum)  -- Secondary Index
);

5. Performance Analysis with EXPLAIN

-- MySQL EXPLAIN analysis
EXPLAIN FORMAT=JSON
SELECT k.name, b.bestelldatum, b.gesamtbetrag
FROM kunden k
JOIN bestellungen b ON k.id = b.kunden_id
WHERE k.stadt = 'Berlin'
  AND b.bestelldatum >= '2024-01-01'
ORDER BY b.gesamtbetrag DESC;

-- PostgreSQL EXPLAIN ANALYZE
EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON)
SELECT k.name, b.bestelldatum, b.gesamtbetrag
FROM kunden k
JOIN bestellungen b ON k.id = b.kunden_id
WHERE k.stadt = 'Berlin'
  AND b.bestelldatum >= '2024-01-01'
ORDER BY b.gesamtbetrag DESC;

-- Verify index usage
-- MySQL: SHOW INDEX FROM table;
SHOW INDEX FROM kunden;

-- PostgreSQL: \d table
-- or pg_indexes view
SELECT indexname, indexdef 
FROM pg_indexes 
WHERE tablename = 'kunden';

6. Index Optimization and Best Practices

-- Covering Index (all required columns in index)
CREATE INDEX idx_kunden_covering ON kunden(stadt, name, id);

-- Query uses index-only scan
SELECT id, name FROM kunden WHERE stadt = 'Berlin';

-- Partial Index (only for subset of data)
CREATE INDEX idx_aktive_kunden ON kunden(id) WHERE status = 'aktiv';

-- Function-Based Index (PostgreSQL)
CREATE INDEX idx_kunden_name_lower ON kunden(LOWER(name));

-- Query uses function-based index
SELECT * FROM kunden WHERE LOWER(name) = 'mustermann';

-- Composite Index with optimal column order
CREATE INDEX idx_bestellungen_optimal ON bestellungen(kunden_id, bestelldatum, status);

-- Good query (uses index fully)
SELECT * FROM bestellungen 
WHERE kunden_id = 123 
  AND bestelldatum >= '2024-01-01' 
  AND status = 'completed';

-- Poor query (cannot use index effectively)
SELECT * FROM bestellungen 
WHERE status = 'completed' 
  AND bestelldatum >= '2024-01-01';  -- Leading column not in WHERE clause

7. Index Maintenance and Monitoring

-- Update index statistics
-- MySQL
ANALYZE TABLE kunden;

-- PostgreSQL
ANALYZE kunden;

-- Check index fragmentation
-- SQL Server
SELECT * FROM sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID('kunden'), NULL, NULL, 'DETAILED');

-- PostgreSQL
SELECT schemaname, tablename, attname, n_distinct, correlation 
FROM pg_stats 
WHERE tablename = 'kunden';

-- Rebuild indexes when fragmented
-- SQL Server
ALTER INDEX ALL ON kunden REBUILD;

-- MySQL (InnoDB)
ANALYZE TABLE kunden;  -- Update statistics
OPTIMIZE TABLE kunden;  -- Optimize table

-- PostgreSQL
REINDEX INDEX idx_kunden_name;

Performance Comparison: Index Types

Index Type	Search Type	Performance	Storage	Use Case
B-Tree	Equality, range	O(log n)	Medium	Standard indexes
Hash	Equality only	O(1)	Low	Memory tables
Fulltext	Full text	Variable	High	Text search
Clustered	Primary key	O(log n)	Table	Frequent access

Index Strategies

Single-Column Index

-- Simple index on one column
CREATE INDEX idx_kunden_email ON kunden(email);

Multi-Column Index

-- Composite index with optimal column order
CREATE INDEX idx_kunden_stadt_name ON kunden(stadt, name);

Covering Index

-- Index contains all required columns
CREATE INDEX idx_bestellungen_covering ON bestellungen(kunden_id, bestelldatum, gesamtbetrag);

Partial Index

-- Index for subset of data only
CREATE INDEX idx_aktive_kunden ON kunden(id) WHERE status = 'aktiv';

Function-Based Index

-- Index on computed values
CREATE INDEX idx_kunden_name_lower ON kunden(LOWER(name));

Query Optimization

Maximizing Index Usage

-- GOOD queries (use indexes)
SELECT * FROM kunden WHERE stadt = 'Berlin';                    -- Single-column index
SELECT * FROM bestellungen WHERE kunden_id = 123 AND datum > '2024-01-01'; -- Composite index
SELECT * FROM artikel WHERE MATCH(titel) AGAINST('suchbegriff');    -- Fulltext index

-- POOR queries (don't use indexes)
SELECT * FROM kunden WHERE LOWER(name) = 'mustermann';           -- No function-based index
SELECT * FROM bestellungen WHERE YEAR(datum) = 2024;            -- Function on column
SELECT * FROM kunden WHERE name LIKE '%mustermann%';             -- Leading wildcard

EXPLAIN Analysis

-- MySQL
EXPLAIN SELECT * FROM kunden WHERE stadt = 'Berlin';

-- Key columns:
-- type: ALL (bad), ref, range, index (good)
-- key: Index used
-- rows: Estimated row count
-- Extra: Using index (good), Using filesort (bad)

-- PostgreSQL
EXPLAIN ANALYZE SELECT * FROM kunden WHERE stadt = 'Berlin';

-- Key information:
-- Seq Scan vs Index Scan
-- Index-Only Scan (excellent)
-- Actual execution time

Advantages and Disadvantages

Index Benefits

• Performance: Dramatically faster queries
• Sorting: ORDER BY without additional sorting operations
• Integrity: UNIQUE indexes guarantee data integrity
• Joins: Foreign key indexes accelerate JOINs

Drawbacks

• Storage: Indexes consume additional disk space
• Write Performance: INSERT/UPDATE/DELETE operations slow down
• Maintenance: Indexes require ongoing management
• Overhead: Too many indexes can be counterproductive

Best Practices

When to Create Indexes

• Frequent WHERE clauses
• JOIN conditions
• ORDER BY clauses
• GROUP BY clauses
• UNIQUE constraints

When to Avoid Indexes

• Rarely used columns
• Tables with few rows
• Low-selectivity columns with high cardinality
• Frequent UPDATE/DELETE operations

Index Design

• Column Order: Descending selectivity
• Index Width: As narrow as possible
• Covering Index: Include all required columns
• Partial Index: Only for relevant data

Common Exam Questions

1. What’s the difference between B-Tree and Hash indexes? B-Tree supports equality and range searches, Hash only equality searches.

2. When would you use a Fulltext index? For text search in large text fields with stemming and relevance scoring.

3. Explain Clustered vs Non-Clustered indexes! Clustered: Physical data storage order, Non-Clustered: Separate index structure.

4. How do you check index usage? Use EXPLAIN/EXPLAIN ANALYZE to examine the query plan.

Key Resources

1. https://dev.mysql.com/doc/refman/8.0/en/mysql-indexes.html
2. https://www.postgresql.org/docs/current/indexes.html
3. https://docs.microsoft.com/en-us/sql/relational-databases/indexes/indexes

---

Recommended Reading: Databases