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

This guide provides a comprehensive overview of database indexes and performance optimization, covering B-Tree, Hash, Fulltext, and Clustered indexes with practical examples.

In a Nutshell

Database indexes dramatically speed up queries by enabling fast access to data. Different index types are optimized for different use cases.

Technical Overview

Database indexes are specialized data structures that improve the speed of data retrieval operations on 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: In-memory tables, exact lookups

Fulltext Index

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

Clustered Index

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

Key Concepts to Remember

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
Relevance: Critical for database administration and optimization

Core Components

Index Structure: Tree, Hash, Inverted Index
Index Type: B-Tree, Hash, Fulltext, Clustered
Query Type: Equality, Range, Fulltext
Performance Metrics: Read time, write time, storage
Index Strategy: Single-column, multi-column, covering
Optimization: EXPLAIN analysis, index tuning
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 operation

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 queries
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 (default)
CREATE INDEX idx_messwerte_zeitpunkt ON messwerte(zeitpunkt);

-- Cluster table by index
CLUSTER messwerte USING idx_messwerte_zeitpunkt;

-- MySQL InnoDB Clustered index (automatic 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;

-- Check 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 the index)
CREATE INDEX idx_kunden_covering ON kunden(stadt, name, id);

-- Query uses index only (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 using function-based index
SELECT * FROM kunden WHERE LOWER(name) = 'mustermann';

-- Composite index with correct 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;

Index Type Performance Comparison

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

Indexing Strategies

Single-Column Index

-- Simple index on a single 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 only on a subset of rows
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

Maximize 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

-- BAD 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

Benefits of indexes

Performance: Dramatically faster queries
Sorting: ORDER BY without additional sorting
Uniqueness: UNIQUE indexes guarantee data integrity
Joins: Foreign key indexes speed up JOINs

Drawbacks

Storage: Indexes consume additional disk space
Write performance: INSERT/UPDATE/DELETE operations become slower
Maintenance: Indexes require upkeep
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
Columns with low selectivity despite high cardinality
Frequent UPDATE/DELETE operations

Index design

Column order: Descending by selectivity
Index width: As narrow as possible
Covering index: Include all required columns
Partial index: Only for relevant data

Common Exam Questions

What’s the difference between B-Tree and Hash indexes? B-Tree supports equality and range searches; Hash supports equality only.
When do you use a Fulltext index? For text search in large text fields with stemming and relevance scoring.
Explain Clustered vs Non-Clustered indexes! Clustered: Physical data storage order; Non-Clustered: Separate index structure.
How do you check index usage? Use EXPLAIN/EXPLAIN ANALYZE to examine the query plan.

Täglicher Artikel