Panduan Database Indexing - Algorithm, Implementation, dan Real-World Trade-off

#Pengenalan

Setiap database engineer telah mengalaminya: query yang seharusnya memakan millisecond merayap pada detik. Penyebabnya? Missing atau poorly designed index.

Indexing adalah salah satu tool paling powerful namun misunderstood dalam database optimization. Ini adalah perbedaan antara scanning jutaan row dan pinpointing persis apa yang Anda butuhkan. Namun banyak developer treat index sebagai afterthought, menambahkannya hanya ketika performance menjadi critical.

Dalam production system, index bukan optional—mereka adalah foundational. Database yang well-indexed dapat handle 10x lebih banyak traffic dengan hardware yang sama. Yang poorly indexed akan collapse di bawah load regardless of berapa banyak Anda scale.

Panduan ini berjalan melalui semuanya: apa index, mengapa penting, bagaimana different algorithm bekerja internally, dan cara mengimplementasikannya dengan benar dalam aplikasi Anda.

#Apa Itu Database Indexing?

Index adalah data structure yang enable faster data retrieval. Anggap saja seperti book index—daripada membaca setiap page untuk find mention "concurrency," Anda flip ke index, find page number, dan jump langsung ke sana.

Tanpa index, database perform full table scan. Dengan index, mereka navigate langsung ke relevant data.

#Core Problem yang Index Selesaikan

Pertimbangkan table dengan 10 juta user record. Query seperti:

sql

SELECT * FROM users WHERE email = 'user@example.com'

Tanpa index, database membaca semua 10 juta row secara sequential sampai find match. Dengan index pada email column, itu locate record dalam millisecond.

Trade-off? Index consume disk space dan slow down write (INSERT, UPDATE, DELETE) karena index harus di-update alongside table. Ini adalah mengapa indexing strategy penting—Anda optimize untuk access pattern Anda.

#Di Mana Index Digunakan

Index accelerate:

WHERE clause - Filtering row dengan specific condition
JOIN condition - Matching row di seluruh table
ORDER BY - Sorting result efficiently
GROUP BY - Aggregating data
DISTINCT - Finding unique value
Range query - Finding value antara bound

Mereka tidak membantu dengan:

SELECT * - Jika Anda perlu semua column anyway
Full table scan - Ketika filtering return most row
Unindexed column dalam WHERE - Index harus match query pattern Anda

#Pro dan Kontra Indexing

#Keuntungan

Dramatic query speedup - Sering 100x-1000x lebih cepat untuk selective query
Reduced CPU usage - Lebih sedikit data processing berarti lower CPU load
Better scalability - Handle lebih banyak concurrent query
Predictable performance - Consistent response time

#Kerugian

Disk space overhead - Index duplicate data
Write performance penalty - Setiap INSERT/UPDATE/DELETE update index
Maintenance cost - Index fragment seiring waktu, memerlukan rebuild
Query planner confusion - Poor index dapat mislead optimizer
Memory pressure - Large index compete untuk cache space

Tip

Best index adalah yang Anda tidak create. Sebelum indexing, verify query benar-benar perlu optimization. Gunakan EXPLAIN ANALYZE untuk confirm index membantu.

#Index Type dan Algorithm

Different index type optimize untuk different access pattern. Mari kita explore yang paling common.

#B-Tree Index

B-tree adalah default index type dalam most database (PostgreSQL, MySQL, SQL Server). Mereka adalah balanced, self-organizing tree dioptimalkan untuk disk-based storage.

#Bagaimana B-Tree Bekerja

B-tree maintain sorted data di seluruh multiple level:

plaintext

                    [40, 80]
                   /    |    \
            [10,30]  [50,70]  [90,100]
           /   |   \  /  |  \  /   |   \
          1   15  35 45  60 75 85  95  110

Setiap node (disebut page) hold multiple key dan pointer ke child node. Ketika Anda search untuk value:

Mulai di root
Compare target Anda dengan key dalam node
Follow appropriate pointer ke child node
Repeat sampai Anda find value atau reach leaf

Mengapa B-tree excel:

Balanced - Semua leaf node pada depth yang sama, guarantee O(log n) performance
Disk-friendly - Node align dengan disk page, minimize I/O operation
Range query - Leaf node linked, enable efficient sequential scan
Self-balancing - Insertion dan deletion maintain balance automatically

#B-Tree Contoh dalam SQL

Membuat B-tree index

CREATE INDEX idx_users_email ON users(email);

Ini create B-tree index pada email column. PostgreSQL dan MySQL gunakan B-tree secara default.

#B-Tree dalam ORM

Prisma - B-tree index

model User {
  id    Int     @id @default(autoincrement())
  email String  @unique
  name  String
 
  @@index([email])
}

TypeORM - B-tree index

@Entity()
export class User {
  @PrimaryGeneratedColumn()
  id: number;
 
  @Column()
  @Index()
  email: string;
 
  @Column()
  name: string;
}

#Hash Index

Hash index gunakan hash function untuk map value ke bucket location. Mereka extremely fast untuk equality lookup tetapi tidak support range query.

#Bagaimana Hash Index Bekerja

plaintext

Hash Function: hash(value) → bucket_id
 
email: "alice@example.com" → hash() → bucket 42 → [row_id: 1001]
email: "bob@example.com"   → hash() → bucket 15 → [row_id: 2003]
email: "charlie@example.com" → hash() → bucket 42 → [row_id: 3005]

Ketika multiple value hash ke bucket yang sama (collision), mereka disimpan dalam chain atau overflow area.

Characteristic:

O(1) average case - Direct bucket lookup
Equality only - Tidak dapat do range query seperti WHERE age > 30
Hash collision - Performance degrade dengan poor hash function
Not ordered - Tidak dapat gunakan untuk ORDER BY atau range scan

#Hash Index Contoh

Membuat hash index (PostgreSQL)

CREATE INDEX idx_users_email ON users USING HASH (email);

Warning

Hash index dalam PostgreSQL tidak crash-safe dan rarely recommended. Gunakan B-tree sebagai gantinya kecuali Anda memiliki specific performance requirement.

#Full-Text Search Index

Full-text index optimize searching dalam text content. Mereka tokenize text, remove stop word, dan build inverted index untuk fast keyword matching.

#Bagaimana Full-Text Search Bekerja

plaintext

Document: "The quick brown fox jumps over the lazy dog"
 
Tokenization:
  [quick, brown, fox, jumps, lazy, dog]
 
Inverted Index:
  quick → [doc_id: 1]
  brown → [doc_id: 1]
  fox   → [doc_id: 1]
  jumps → [doc_id: 1]
  lazy  → [doc_id: 1]
  dog   → [doc_id: 1]
 
Query: "quick fox"
  → Find doc containing "quick": [1]
  → Find doc containing "fox": [1]
  → Intersection: [1] ✓

#Full-Text Search dalam SQL

PostgreSQL full-text search

CREATE TABLE articles (
  id SERIAL PRIMARY KEY,
  title TEXT,
  content TEXT,
  search_vector tsvector GENERATED ALWAYS AS (
    to_tsvector('english', title || ' ' || content)
  ) STORED
);
 
CREATE INDEX idx_articles_search ON articles USING GIN (search_vector);
 
SELECT * FROM articles 
WHERE search_vector @@ to_tsquery('english', 'database & indexing');

MySQL full-text search

CREATE TABLE articles (
  id INT PRIMARY KEY AUTO_INCREMENT,
  title VARCHAR(255),
  content LONGTEXT,
  FULLTEXT INDEX idx_search (title, content)
);
 
SELECT * FROM articles 
WHERE MATCH(title, content) AGAINST('database indexing' IN BOOLEAN MODE);

#Full-Text Search dalam ORM

Prisma - Full-text search (PostgreSQL)

model Article {
  id      Int     @id @default(autoincrement())
  title   String
  content String
  
  @@fulltext([title, content])
}
 
// Query
const results = await prisma.article.findMany({
  where: {
    OR: [
      { title: { search: 'database' } },
      { content: { search: 'indexing' } }
    ]
  }
});

#Bitmap Index

Bitmap index efficient untuk column dengan low cardinality (few distinct value). Mereka gunakan bit array di mana setiap bit represent row.

#Bagaimana Bitmap Index Bekerja

plaintext

Column: status (value: active, inactive, pending)
 
Bitmap untuk "active":
  Row 1: 1
  Row 2: 0
  Row 3: 1
  Row 4: 0
  Row 5: 1
  
Bitmap untuk "inactive":
  Row 1: 0
  Row 2: 1
  Row 3: 0
  Row 4: 0
  Row 5: 0
 
Bitmap untuk "pending":
  Row 1: 0
  Row 2: 0
  Row 3: 0
  Row 4: 1
  Row 5: 0

Query gunakan bitwise operation untuk fast filtering:

Bitmap index query

-- Find active OR pending user
-- Bitwise OR: [1,0,1,0,1] | [0,0,0,1,0] = [1,0,1,1,1]
SELECT * FROM users WHERE status IN ('active', 'pending');

Kapan menggunakan:

Low cardinality column (< 100 distinct value)
Data warehouse query
Column seperti status, gender, country

Limitation: Tidak ideal untuk high-cardinality column (banyak distinct value) karena Anda akan perlu terlalu banyak bitmap.

#Partial Index

Partial index index hanya row matching condition, mengurangi size dan improve performance.

Partial index contoh

-- Hanya index active user
CREATE INDEX idx_active_users ON users(email) 
WHERE status = 'active';
 
-- Query gunakan index
SELECT * FROM users WHERE status = 'active' AND email = 'user@example.com';

Ini lebih cepat daripada indexing semua user karena:

Smaller index = faster search
Fewer update (inactive user tidak affect index)
Better cache locality

#Composite Index

Composite index span multiple column, optimize query yang filter pada multiple field.

Composite index

CREATE INDEX idx_users_country_city ON users(country, city);
 
-- Query ini gunakan index efficiently
SELECT * FROM users WHERE country = 'US' AND city = 'New York';
 
-- Ini juga gunakan index (country adalah first)
SELECT * FROM users WHERE country = 'US';
 
-- Ini TIDAK gunakan index (city adalah first, violate column order)
SELECT * FROM users WHERE city = 'New York';

Key principle: Composite index follow leftmost prefix rule. Query harus gunakan column dari left ke right.

#Index Data Structure Deep Dive

#B+ Tree (Variant dari B-Tree)

B+ tree dioptimalkan untuk range query. Unlike B-tree, semua data disimpan dalam leaf node, dan internal node contain hanya key untuk navigation.

plaintext

Internal node:
                    [40, 80]
                   /    |    \
            [10,30]  [50,70]  [90,100]
 
Leaf node (linked):
[1,15,35] ↔ [45,60,75] ↔ [85,95,110]

Keuntungan:

Leaf node form linked list, enable efficient sequential scan
Internal node lebih kecil, fit lebih banyak key per page
Better untuk range query seperti WHERE age BETWEEN 20 AND 40

Most modern database (PostgreSQL, MySQL, SQLite) gunakan B+ tree internally.

#LSM Tree (Log-Structured Merge Tree)

LSM tree optimize write-heavy workload dengan batch write dalam memory sebelum flush ke disk.

plaintext

Write path:
1. Write ke in-memory buffer (MemTable)
2. Ketika full, flush ke disk sebagai immutable SSTable
3. Periodically merge SSTable
 
Read path:
1. Check MemTable
2. Check recent SSTable
3. Check older SSTable

Digunakan oleh: RocksDB, LevelDB, Cassandra, HBase

Trade-off: Faster write, slower read (harus check multiple level)

#Hash Table

Simple hash table map key langsung ke value. Digunakan untuk in-memory cache dan beberapa database index.

plaintext

Hash function: hash(key) % table_size
 
key: "user:123" → hash() % 1000 → bucket 456 → value

Pro: O(1) average lookup Kontra: Tidak ada range query, collision handling overhead

#Practical Implementation Contoh

#SQL Index Creation

Common index pattern

-- Single column index
CREATE INDEX idx_users_email ON users(email);
 
-- Unique index (enforce uniqueness)
CREATE UNIQUE INDEX idx_users_email_unique ON users(email);
 
-- Composite index
CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);
 
-- Partial index (hanya active user)
CREATE INDEX idx_active_users ON users(email) WHERE status = 'active';
 
-- Descending index (untuk ORDER BY DESC)
CREATE INDEX idx_posts_date_desc ON posts(created_at DESC);
 
-- Expression index (index computed value)
CREATE INDEX idx_users_email_lower ON users(LOWER(email));
 
-- Full-text index (PostgreSQL)
CREATE INDEX idx_articles_search ON articles USING GIN (
  to_tsvector('english', title || ' ' || content)
);

#ORM Index Contoh

Prisma schema index

model User {
  id        Int     @id @default(autoincrement())
  email     String  @unique
  name      String
  status    String
  createdAt DateTime @default(now())
 
  // Single column index
  @@index([email])
  
  // Composite index
  @@index([status, createdAt])
  
  // Full-text search
  @@fulltext([name])
}
 
model Order {
  id        Int     @id @default(autoincrement())
  userId    Int
  amount    Float
  createdAt DateTime @default(now())
 
  user User @relation(fields: [userId], references: [id])
 
  // Foreign key index (usually automatic)
  @@index([userId])
  
  // Composite untuk common query
  @@index([userId, createdAt])
}

TypeORM index

import { Entity, PrimaryGeneratedColumn, Column, Index } from 'typeorm';
 
@Entity()
@Index(['email'])
@Index(['status', 'createdAt'])
export class User {
  @PrimaryGeneratedColumn()
  id: number;
 
  @Column()
  email: string;
 
  @Column()
  name: string;
 
  @Column()
  status: string;
 
  @Column()
  createdAt: Date;
}
 
@Entity()
@Index(['userId', 'createdAt'])
export class Order {
  @PrimaryGeneratedColumn()
  id: number;
 
  @Column()
  userId: number;
 
  @Column()
  amount: number;
 
  @Column()
  createdAt: Date;
}

Sequelize index

const User = sequelize.define('User', {
  email: {
    type: DataTypes.STRING,
    allowNull: false,
    index: true
  },
  name: DataTypes.STRING,
  status: DataTypes.STRING
}, {
  indexes: [
    { fields: ['email'] },
    { fields: ['status', 'createdAt'] }
  ]
});

#Query Optimization dengan EXPLAIN

Memahami bagaimana database Anda gunakan index memerlukan EXPLAIN analysis.

PostgreSQL EXPLAIN ANALYZE

EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'user@example.com';
 
-- Output:
-- Seq Scan on users  (cost=0.00..35.50 rows=1 width=100)
--   Filter: (email = 'user@example.com')
--   Planning Time: 0.123 ms
--   Execution Time: 2.456 ms
 
-- Setelah create index:
-- Index Scan using idx_users_email on users  (cost=0.29..8.30 rows=1 width=100)
--   Index Cond: (email = 'user@example.com')
--   Planning Time: 0.089 ms
--   Execution Time: 0.234 ms

MySQL EXPLAIN

EXPLAIN
SELECT * FROM users WHERE email = 'user@example.com';
 
-- Output:
-- id | select_type | table | type  | possible_keys | key | rows | Extra
-- 1  | SIMPLE      | users | const | idx_email     | idx_email | 1 | NULL

Key metric:

Seq Scan - Full table scan (bad)
Index Scan - Menggunakan index (good)
rows - Estimated row examined
cost - Relative query cost

#Kesalahan & Jebakan Umum

#Over-Indexing

Membuat terlalu banyak index slow down write tanpa membantu read.

Buruk: Terlalu banyak index

CREATE INDEX idx_users_email ON users(email);
CREATE INDEX idx_users_name ON users(name);
CREATE INDEX idx_users_phone ON users(phone);
CREATE INDEX idx_users_address ON users(address);
CREATE INDEX idx_users_city ON users(city);
-- Setiap INSERT sekarang update 5 index!

Solusi: Index hanya column yang digunakan dalam WHERE, JOIN, atau ORDER BY clause.

#Indexing High-Cardinality Column Dengan Buruk

Buruk: Index pada low-selectivity column

CREATE INDEX idx_users_status ON users(status);
-- Jika 90% user adalah 'active', index ini tidak berguna

Solusi: Gunakan partial index untuk low-selectivity column:

Baik: Partial index

CREATE INDEX idx_inactive_users ON users(id) WHERE status != 'active';

#Mengabaikan Column Order dalam Composite Index

Buruk: Wrong column order

CREATE INDEX idx_orders ON orders(created_at, user_id);
 
-- Query ini tidak gunakan index efficiently
SELECT * FROM orders WHERE user_id = 123;

Solusi: Put frequently filtered column terlebih dahulu:

Baik: Correct column order

CREATE INDEX idx_orders ON orders(user_id, created_at);

#Tidak Maintain Index

Index fragment seiring waktu, degrade performance.

Rebuild fragmented index (PostgreSQL)

REINDEX INDEX idx_users_email;
 
-- Atau rebuild semua index pada table
REINDEX TABLE users;

Rebuild fragmented index (MySQL)

OPTIMIZE TABLE users;
-- Atau
ANALYZE TABLE users;

#Menggunakan Index untuk Column dalam Function

Buruk: Function prevent index use

CREATE INDEX idx_users_email ON users(email);
 
-- Query ini tidak gunakan index
SELECT * FROM users WHERE LOWER(email) = 'user@example.com';

Solusi: Create expression index:

Baik: Expression index

CREATE INDEX idx_users_email_lower ON users(LOWER(email));
 
SELECT * FROM users WHERE LOWER(email) = 'user@example.com';

#Best Practice untuk Produksi

#1. Index Berdasarkan Query Pattern

Analyze actual query Anda sebelum indexing:

Find slow query (PostgreSQL)

-- Enable query logging
ALTER SYSTEM SET log_min_duration_statement = 1000; -- Log query > 1s
SELECT pg_reload_conf();
 
-- Check log
SELECT query, mean_exec_time FROM pg_stat_statements 
ORDER BY mean_exec_time DESC LIMIT 10;

#2. Gunakan Composite Index Strategically

Composite index strategy

-- Common query pattern
SELECT * FROM orders 
WHERE user_id = ? AND status = ? AND created_at > ?;
 
-- Create composite index matching query pattern
CREATE INDEX idx_orders_lookup ON orders(user_id, status, created_at);

#3. Monitor Index Usage

Find unused index (PostgreSQL)

SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0
ORDER BY pg_relation_size(indexrelid) DESC;

Find unused index (MySQL)

SELECT object_schema, object_name, count_read, count_write
FROM performance_schema.table_io_waits_summary_by_index_usage
WHERE count_read = 0
ORDER BY count_write DESC;

#4. Plan untuk Growth

Estimate index size

-- PostgreSQL
SELECT pg_size_pretty(pg_relation_size('idx_users_email'));
 
-- MySQL
SELECT 
  ROUND(stat_value * @@innodb_page_size / 1024 / 1024, 2) AS size_mb
FROM mysql.innodb_index_stats
WHERE stat_name = 'size' AND index_name = 'idx_users_email';

#5. Test Index Change

Selalu test index dalam staging sebelum production:

Create index dengan minimal locking (PostgreSQL)

-- Non-blocking index creation
CREATE INDEX CONCURRENTLY idx_users_email ON users(email);

Create index dengan minimal locking (MySQL)

-- Gunakan ALGORITHM=INPLACE untuk avoid table lock
ALTER TABLE users ADD INDEX idx_email (email), ALGORITHM=INPLACE, LOCK=NONE;

#Kapan TIDAK Menggunakan Index

#Small Table

Skip index untuk small table

-- Table dengan < 1000 row
-- Full scan sering lebih cepat daripada index lookup
SELECT * FROM countries WHERE name = 'United States';

#High Write-to-Read Ratio

Skip index untuk write-heavy workload

-- Jika Anda INSERT/UPDATE/DELETE lebih banyak daripada SELECT
-- Index maintenance overhead outweigh benefit
-- Pertimbangkan denormalization atau caching sebagai gantinya

#Column dengan NULL Value

NULL handling dalam index

-- Most database tidak index NULL value efficiently
-- Hindari indexing column dengan banyak NULL
CREATE INDEX idx_users_phone ON users(phone) 
WHERE phone IS NOT NULL;

#Temporary atau Staging Table

Skip index untuk temporary data

-- Temporary table digunakan untuk intermediate processing
-- Index overhead tidak worth short lifespan
CREATE TEMPORARY TABLE staging_users AS
SELECT * FROM users WHERE status = 'pending';

#Kesimpulan

Database indexing adalah both art dan science. Fundamental straightforward—index accelerate lookup dengan organize data—tetapi mastering mereka memerlukan understanding access pattern Anda, trade-off, dan algorithm powering different index type.

Key takeaway:

B-tree adalah default untuk reason: balanced, disk-friendly, dan versatile
Hash index cepat untuk equality tetapi useless untuk range
Full-text index unlock text search capability
Composite index harus match query pattern Anda
Over-indexing hurt write lebih banyak daripada help read
Gunakan EXPLAIN untuk verify index benar-benar membantu
Monitor dan maintain index dalam production

Mulai dengan identify slowest query Anda dengan EXPLAIN ANALYZE. Create targeted index untuk query itu. Measure impact. Remove index yang tidak membantu. Iterative approach ini beat guessing.

Best index adalah yang solve real problem. Build dengan intention, measure result, dan iterate.

Panduan Database Indexing - Algorithm, Implementation, dan Real-World Trade-off

Related Posts