Database Index Deep Dive: Từ B+Tree đến LSM-Tree và những bẫy phỏng vấn

Tại sao index là câu hỏi phỏng vấn kinh điển?

Nếu bạn từng đi phỏng vấn backend hoặc database engineer, gần như chắc chắn sẽ gặp câu hỏi dạng: "Index hoạt động thế nào?", "Tại sao truy vấn LIKE '%abc' không dùng được index?", hoặc "Khi nào nên dùng B-Tree, khi nào dùng Hash?". Lý do rất đơn giản — index là nơi mà lý thuyết cấu trúc dữ liệu gặp thực tế phần cứng. Nó kiểm tra cả ba thứ cùng lúc:

1. Bạn có hiểu cây cân bằng, hash table, trade-off giữa cấu trúc dữ liệu?
2. Bạn có biết disk I/O đắt hơn memory hàng nghìn lần và điều đó định hình design ra sao?
3. Bạn có viết được câu query nhanh trong production, hay chỉ biết SELECT *?

Đa số ứng viên trả lời ở mức bề mặt: "Index giống mục lục sách, giúp tìm nhanh hơn." Đúng — nhưng quá đủ để cho ra ngoài. Người phỏng vấn muốn xem bạn có thể đi sâu hơn: cấu trúc cây B+ trông như thế nào trên đĩa, tại sao InnoDB lưu data trong leaf node còn PostgreSQL thì không, tại sao Cassandra dùng LSM-Tree thay vì B-Tree, và làm sao một index sai design có thể khiến database chậm đi 100 lần.

Bài này không phải là cheat sheet. Tôi sẽ đi từ những điều cơ bản về cách database tổ chức dữ liệu trên đĩa, rồi mổ xẻ từng loại index quan trọng — B+Tree, Hash, LSM-Tree, Bitmap, GIN/GiST, BRIN — kèm cách chúng được hiện thực thật sự trong MySQL InnoDB và PostgreSQL. Cuối bài là phần "interview gold": những bẫy thường gặp khi thiết kế index mà câu trả lời chuẩn sẽ làm bạn nổi bật.

Index (chỉ mục database): Là một cấu trúc dữ liệu phụ trợ được duy trì bên cạnh bảng, cho phép database tìm các hàng thỏa mãn điều kiện mà không phải quét toàn bộ bảng. Đánh đổi là chi phí ghi tăng lên (mỗi INSERT/UPDATE/DELETE phải cập nhật cả index) và chi phí lưu trữ thêm, để đổi lấy chi phí đọc giảm mạnh.

Lộ trình của bài:

What we cover:

  [Foundations]
  1. Why indexes exist — disk vs memory
  2. Page-based storage and the cost of random I/O

  [Core data structures]
  3. B-Tree / B+Tree — the universal workhorse
  4. Hash indexes — O(1) but limited
  5. LSM-Tree — write-optimized for modern workloads

  [Specialized]
  6. Bitmap, GIN, GiST, BRIN — when B-Tree is wrong

  [Implementation]
  7. MySQL InnoDB clustered index vs PostgreSQL heap+index
  8. Page splits, fill factor, WAL, and vacuum

  [Interview gold]
  9. Leftmost prefix, selectivity, covering indexes,
     index-only scan, function-based indexes, and pitfalls

Nếu bạn đã biết B-Tree căn bản, hãy bỏ qua section 2-3 và nhảy thẳng vào LSM-Tree hoặc phần implementation — ở đó là chỗ nhiều người ngộ ra "à hóa ra nó hoạt động kiểu này".

Nền tảng: vì sao database không thể giống một mảng trong RAM

Trước khi nói về cấu trúc của index, phải hiểu môi trường mà index sống: ổ đĩa. Database engineer khác application developer ở chỗ này — họ không thể giả định data nằm gọn trong RAM.

Disk I/O đắt như thế nào?

Một con số kinh điển từ "Latency Numbers Every Programmer Should Know":

Đọc một block 4KB từ SSD chậm hơn truy cập RAM khoảng 160 lần. Trên HDD truyền thống thì chậm hơn 100,000 lần. Vì thế, database không thể design giống như một mảng trong memory — mỗi lần "chạm" đĩa là một khoản chi phí khổng lồ. Mục tiêu chính của mọi cấu trúc index là giảm số lần chạm đĩa, chứ không phải giảm số phép so sánh CPU.

Page — đơn vị I/O của database

Database không đọc đĩa theo byte hay theo từng hàng. Nó đọc theo page (trang) — một block có kích thước cố định, thường là 4KB, 8KB hoặc 16KB. Vì sao? Vì hệ điều hành và disk hardware đều làm việc theo block, và đọc 1 byte cũng tốn chi phí gần như đọc nguyên block.

Page (data page, block): Là đơn vị I/O cơ bản của database, thường 4KB-16KB. Mỗi page chứa nhiều hàng (rows) hoặc nhiều entry của index. Khi database cần đọc một hàng, nó đọc nguyên page chứa hàng đó vào buffer pool, kể cả khi chỉ cần một cột nhỏ.

Kích thước page của một số database phổ biến:

+---------------------------- 16 KB page (InnoDB) -----------------------------+
| Page Header (38 B) | Page Directory | ... user records ... | Free Space      |
+------------------------------------------------------------------------------+
                                       ^
                                       |
                          Records grow downward, directory grows upward

Một page 16KB có thể chứa khoảng 100-200 hàng tùy schema. Khi bạn SELECT * FROM users WHERE id = 42, database không tìm "hàng số 42" — nó tìm page nào chứa hàng đó, đọc cả page vào buffer pool, rồi mới trích hàng ra.

Buffer pool — cache giữa đĩa và truy vấn

Page đọc lên được giữ trong buffer pool (bộ nhớ đệm). Đây là RAM mà database quản lý riêng, không thông qua page cache của OS (thường là vậy, vì DB biết rõ hơn page nào nóng). Lần đọc tiếp theo của cùng page sẽ "hit" buffer pool và không phải chạm đĩa.

Buffer Pool: Vùng RAM database dùng để cache các page đã đọc từ đĩa. Khi page bị thay đổi, nó được đánh dấu dirty và sẽ được flush về đĩa sau (thường thông qua background writer + WAL). Buffer pool dùng các thuật toán thay thế như LRU, Clock-sweep, hoặc 2Q.

Đây là lý do thực hành: một index tốt là index mà các page hot vừa đủ nhỏ để fit trong buffer pool. Một index 100GB trên server có 32GB RAM sẽ liên tục bị evict và đọc lại từ đĩa.

Vì sao không dùng binary search trên file sorted?

Nếu data đã sorted theo key, ta có thể binary search trên file. Đúng, và đây từng là cách làm thật sự (ISAM). Vấn đề:

1. Insert/Update đắt khủng khiếp — chèn một hàng vào giữa cần dịch chuyển tất cả phía sau, hoặc giữ "overflow pages" mà cuối cùng degrade về linear scan.
2. Mỗi bước binary search là một random I/O — log₂(10⁹) ≈ 30 lần seek, mỗi seek 10ms trên HDD là 300ms cho một query.

Chúng ta cần một cấu trúc:

• Cân bằng: Truy cập bất kỳ key nào cũng có chi phí gần như nhau.
• Fanout cao: Mỗi page chứa nhiều children → cây thấp → ít lần I/O.
• Update tại chỗ: Insert/Delete không phá vỡ cấu trúc.

Đó chính là lý do B-Tree (và biến thể B+Tree) thống trị thế giới database suốt 50 năm qua. Section sau sẽ mổ xẻ nó.

B-Tree và B+Tree — con ngựa kéo của thế giới database

Khi ai đó nói "tôi đã thêm index" mà không nói thêm gì, gần như 100% họ đang nói về B+Tree index. Đây là index mặc định của MySQL InnoDB, PostgreSQL, SQL Server, Oracle, SQLite — vì một lý do: nó là cấu trúc cân bằng nhất giữa read, write, range scan, và disk-friendly.

B-Tree gốc — ý tưởng cơ bản

B-Tree do Rudolf Bayer và Edward McCreight đề xuất năm 1970 tại Boeing. Ý tưởng: thay vì binary tree (mỗi node 1 key, 2 children), tạo một cây mà mỗi node chứa nhiều key và nhiều children — bằng đúng kích thước một disk page.

B-Tree: Cây tìm kiếm tự cân bằng, mỗi node chứa nhiều key (sorted) và có nhiều children. Tất cả các leaf node ở cùng độ sâu. Một B-Tree bậc m có tối đa m children và m-1 key trên mỗi node. Tên "B" chính thức chưa từng được Bayer xác nhận đứng cho từ gì (Balanced, Bayer, Boeing, Broad — đều có thể).

Vì sao "nhiều key trên mỗi node" lại quan trọng? Vì fanout cao = cây thấp = ít I/O. Hãy tính nhanh:

• Một page 16KB. Giả sử mỗi key + pointer mất 16 byte → mỗi node chứa ~1000 children.
• Cây 3 tầng = 1000³ = 1 tỷ key, chỉ cần 3 lần đọc đĩa để tìm bất kỳ key nào.
• Cây 4 tầng = 1000⁴ = 1 nghìn tỷ key, chỉ cần 4 lần đọc đĩa.

Bốn lần I/O cho một nghìn tỷ hàng. Đó là lý do B-Tree vẫn còn ở khắp mọi nơi.

B+Tree — biến thể được dùng thật sự

Database thực tế không dùng B-Tree nguyên bản, mà dùng B+Tree với hai khác biệt quan trọng:

1. Chỉ leaf node chứa data (hoặc pointer tới data). Internal node chỉ chứa key dùng làm navigation.
2. Leaf node được linked list nối với nhau. Cho phép range scan tuần tự rất nhanh.

B+Tree: Biến thể của B-Tree mà toàn bộ giá trị (hoặc con trỏ tới giá trị) được lưu ở leaf node. Internal node chỉ giữ key để định tuyến. Các leaf được nối thành doubly-linked list, cho phép WHERE id BETWEEN 100 AND 500 chỉ cần xuống cây 1 lần rồi đi ngang.

                    +-----------------+
                    |   [50]   [100]  |   <- Internal (routing only)
                    +-----------------+
                       /      |     \
                      v       v      v
              +--------+ +--------+ +-----------+
              | 10 30  | | 50 70  | | 100 130   |  <- Internal
              +--------+ +--------+ +-----------+
                /    \      / \         / \
               v     v     v   v       v   v
        +-------+ +------+ ...
        | 1->R  | | 12->R |
        | 4->R  | | 25->R |   <-- Leaf: key + row pointer
        | 9->R  | | 30->R |       Leaf nodes linked left-right
        +-------+ +------+
            <-------> linked list <------->

Khác biệt then chốt giữa B-Tree và B+Tree khi range scan:

Cách insert hoạt động — page split

Hãy xem điều gì xảy ra khi node bị đầy. Giả sử mỗi leaf chứa được tối đa 4 key:

Bước 1: Insert 5, 9, 12, 20 -> leaf đầy
   +-----------------+
   | [5][9][12][20]  |
   +-----------------+

Bước 2: Insert 15 -> phải split
   Tìm giữa: 12. Chia thành 2 leaf, push 12 lên parent.

   Parent:    [12]
             /    \
   Leaf:  [5,9]  [12,15,20]

Bước 3: Tiếp tục insert. Khi internal node đầy, nó cũng split,
        có thể đệ quy lên root. Nếu root split, cây tăng 1 tầng
        (đây là cách B+Tree luôn cân bằng - growth từ root xuống).

Page split là chi phí ẩn của B+Tree. Mỗi split là:

1. Đọc page sắp đầy.
2. Allocate page mới.
3. Copy nửa data sang page mới.
4. Update parent (có thể trigger split tiếp).
5. Cập nhật linked list của leaf.

Cấu hình fill factor (PostgreSQL) hoặc MERGE_THRESHOLD (InnoDB) cho phép bạn để chừa khoảng trống trong page để giảm split. Mặc định PostgreSQL fill factor là 90% cho B-Tree index — 10% còn lại dành cho insert sau này.

Fill Factor: Phần trăm không gian được dùng khi tạo/build lại một page index. Fill factor thấp (ví dụ 70%) giảm page split nhưng tăng kích thước index. Workload write-heavy nên dùng fill factor thấp, workload read-only nên đặt 100%.

Cây thấp đến cỡ nào trên thực tế?

Tài liệu MySQL InnoDB nói một B+Tree với page 16KB và row key 8 byte có thể chứa khoảng 2000 entries mỗi node. Tương ứng:

• 1 tầng (root only): ~2,000 hàng
• 2 tầng: ~4 triệu hàng
• 3 tầng: ~8 tỷ hàng
• 4 tầng: ~16 nghìn tỷ hàng

Trong hầu hết database thực tế, cây sâu 3-4 tầng là tối đa. Nếu root + internal được cache trong buffer pool (thường được vì chúng nhỏ), point lookup chỉ tốn 1 I/O để đọc leaf, đôi khi 0 I/O nếu leaf cũng cached.

Khi B+Tree không phù hợp

B+Tree không phải lời giải cho mọi bài toán. Nó kém ở:

• Workload write-heavy với random key: Mỗi insert là một point write vào random page → write amplification cao → LSM-Tree thắng (xem section 5).
• Equality lookup tinh khôi: Hash index có O(1), B-Tree có O(log n) — nếu không cần range thì hash nhanh hơn (xem section 4).
• Full-text search: B-Tree không hiểu "word inside text". Cần inverted index / GIN (xem section 6).
• Very low cardinality: Một cột chỉ có giá trị Y/N, dùng Bitmap index hiệu quả hơn nhiều.

Nhưng cho 80% use case — primary key, foreign key, point lookup, range scan, ORDER BY, MIN/MAX — B+Tree là lựa chọn đúng. Đó là lý do nó là default ở mọi RDBMS.

Hash index — O(1) nhưng kém vạn năng

Nếu B+Tree là con dao đa năng, hash index là con dao mổ — chỉ một nhiệm vụ, nhưng làm cực kỳ tốt: point lookup theo equality.

Ý tưởng

Hash index dùng đúng hash table mà bạn học ở môn cấu trúc dữ liệu:

1. Tính h = hash(key).
2. slot = h mod n (n là số bucket).
3. Trong bucket có một danh sách (linked list / open addressing) chứa các entry trùng hash.
4. So sánh key thật để loại bỏ collision.

Độ phức tạp: O(1) trung bình cho WHERE key = 'x'. So với O(log n) của B-Tree, với 1 tỷ row, hash nhanh hơn ~30 lần về số phép so sánh.

Hash Index: Cấu trúc index dùng hash function để map key thành bucket. Truy vấn equality cực nhanh nhưng KHÔNG hỗ trợ range scan, sorting, hoặc tìm prefix. Tự sửa lại kích thước khi load factor vượt ngưỡng (linear hashing, extendible hashing).

Vì sao không thay B+Tree?

Hash index có ba điểm yếu chí mạng:

1. Không hỗ trợ range (WHERE id > 100, BETWEEN, ORDER BY). Hash phá vỡ thứ tự — hai key liền kề có hash ngẫu nhiên ở hai góc bucket khác nhau.
2. Không hỗ trợ prefix lookup (WHERE name LIKE 'John%'). Cùng lý do.
3. Memory-friendly nhưng disk-unfriendly. Mỗi point lookup là một random I/O vào một bucket bất kỳ — tệ trên HDD, kém hiệu quả khi index lớn hơn buffer pool.

Hash trong database thực tế

MySQL InnoDB — Adaptive Hash Index

InnoDB có một tính năng đặc biệt gọi là Adaptive Hash Index (AHI). Đây không phải là loại index bạn tạo bằng CREATE INDEX. Nó là cache nằm bên trong buffer pool, InnoDB tự động xây dựng cho các index thường xuyên được dùng equality lookup.

Adaptive Hash Index (AHI): Một hash table chạy ngầm bên trong buffer pool của InnoDB. Khi InnoDB phát hiện một secondary index được truy cập rất nhiều bằng equality, nó tự xây hash entry trỏ trực tiếp tới leaf node của B+Tree, bỏ qua việc đi từ root xuống. Có thể bật/tắt bằng innodb_adaptive_hash_index.

Without AHI:                     With AHI hit:
                                                       
  SQL: WHERE id = 42               SQL: WHERE id = 42
   |                                |
   v                                v
  [Root]      <- I/O #1            [Hash Bucket] - O(1) memory
   |                                |
  [Internal]  <- I/O #2             |
   |                                |
  [Leaf]      <- I/O #3       ----> [Leaf] - direct pointer
   |                                |
  Found row                         Found row

AHI giúp tăng tốc đáng kể workload OLTP với key lookup, nhưng nó không thay thế B+Tree gốc — nó chỉ là một shortcut. Trên các workload random key insert nặng, AHI có thể bị contention cao và team thường tắt nó đi.

MySQL MEMORY engine

MEMORY engine (RAM-only, không persist) mặc định dùng hash index. Phù hợp cho lookup table tạm thời, vì range scan trên MEMORY rất hiếm.

PostgreSQL hash index

PostgreSQL có CREATE INDEX ... USING HASH. Trước phiên bản 10, hash index của PostgreSQL không được WAL log, nghĩa là không crash-safe — gần như không ai dùng. Từ PostgreSQL 10, đã được fix nhưng vẫn hiếm khi dùng vì:

• Chỉ hỗ trợ = operator
• B+Tree đã rất nhanh cho equality
• Tradeoff hiếm khi đủ thuyết phục

-- PostgreSQL hash index syntax
CREATE INDEX idx_users_email_hash ON users USING HASH (email);
 
-- Only supports = operator. Following will NOT use this index:
SELECT * FROM users WHERE email > 'm';        -- range, hash unusable
SELECT * FROM users WHERE email LIKE 'a%';    -- prefix, hash unusable
SELECT * FROM users ORDER BY email;           -- sort, hash unusable

Khi nào hash index có ý nghĩa?

• Key-value store thuần (Redis, Memcached): Bản chất là hash table khổng lồ.
• In-memory database (SAP HANA, Memcached): Random I/O không còn là vấn đề.
• Equality-only workload với cardinality cao: Bảng session lookup theo UUID, bảng cache theo key.
• Khi B+Tree quá sâu: Hiếm gặp ngày nay với buffer pool lớn.

Với hầu hết workload OLTP truyền thống, bạn không cần chủ động tạo hash index. B+Tree đã đủ nhanh, và range scan luôn là tính năng mà sớm hay muộn bạn cũng cần.

LSM-Tree — vì sao Cassandra, RocksDB, LevelDB không dùng B+Tree

Có một loại workload mà B+Tree dở tệ: write-heavy với throughput cực cao và key gần như ngẫu nhiên. Tin nhắn, sự kiện IoT, telemetry, time-series — hàng triệu write/giây, mỗi write đụng vào một page khác nhau. B+Tree sẽ:

1. Page split liên tục → write amplification cao.
2. Random write trên đĩa → IOPS bão hòa.
3. Lock contention trên internal node.

Năm 1996, O'Neil, Cheng, Gawlick và O'Neil đề xuất một cấu trúc mới: Log-Structured Merge Tree (LSM-Tree). Ý tưởng: thay vì update tại chỗ, gom write vào memory, định kỳ ghi xuống đĩa theo sequential I/O, rồi merge ngầm.

LSM-Tree (Log-Structured Merge Tree): Cấu trúc lưu trữ write-optimized, gom write vào memory (memtable), flush xuống đĩa thành các file bất biến (SSTable), và định kỳ merge các SSTable theo level để tránh không gian bị đầy. Đánh đổi write tại chỗ → write tuần tự, để có throughput write cực cao.

Anatomy của LSM-Tree

+----------------------- MEMORY -----------------------+
|                                                      |
|  Write -> WAL (append-only log)                      |
|                                                      |
|  Memtable (sorted skiplist or red-black tree)        |
|     [ key1->v, key2->v, key3->v, ... ]               |
|                                                      |
+------------------ flush when full -------------------+
                            |
                            v
+------------------------ DISK ------------------------+
|                                                      |
|  Level 0 (newest, may have overlapping ranges)       |
|     SSTable_001  SSTable_002  SSTable_003            |
|                                                      |
|  Level 1 (sorted, no overlap within level)           |
|     SSTable_L1_a    SSTable_L1_b    ...              |
|                                                      |
|  Level 2  (10x size of L1)                           |
|     ...                                              |
|                                                      |
|  Level 3  (10x size of L2)                           |
|     ...                                              |
|                                                      |
+------------------------------------------------------+

Write path

1. Write vào WAL (write-ahead log) — append-only file để recover khi crash.
2. Insert vào memtable trong RAM — thường là skiplist hoặc red-black tree, sorted by key.
3. Khi memtable đầy (vài MB - vài chục MB), nó chuyển thành immutable và bắt đầu một memtable mới.
4. Một background thread flush memtable đó xuống đĩa thành một SSTable (Sorted String Table) ở Level 0.

SSTable (Sorted String Table): File bất biến trên đĩa chứa các key-value đã sort. Một khi đã ghi, SSTable không bao giờ được sửa, chỉ bị merge với các SSTable khác hoặc bị xóa. Mỗi SSTable kèm theo một Bloom filter và một sparse index để tăng tốc lookup.

Read path

Đọc phải kiểm tra mọi nơi key có thể tồn tại, từ mới nhất đến cũ nhất:

GET key:
  1. memtable        (RAM, instant)
  2. immutable mt    (RAM, instant)
  3. Level 0 SSTables (may overlap, check all)
  4. Level 1 SSTable (binary search, key range known)
  5. Level 2 SSTable
  ...
  Return first match found.

Đọc tệ hơn B+Tree đấy chứ! Vì sao vẫn dùng? Hai cứu cánh:

• Bloom filter: Mỗi SSTable có Bloom filter giúp loại bỏ nhanh "key này chắc chắn không có ở đây", tránh phải đọc đĩa.
• Block cache: Các SSTable nóng được cache trong RAM.

Bloom Filter: Cấu trúc dữ liệu xác suất, dùng nhiều hash function, trả lời "phần tử có trong tập?" bằng YES có thể hoặc NO chắc chắn. Tỉ lệ false positive cấu hình được (thường 1%). Cực kỳ tiết kiệm bộ nhớ — chỉ vài bit/key.

Compaction — bí mật của LSM

Vì SSTable bất biến, khi update hoặc delete xảy ra, các phiên bản cũ vẫn còn. Phải có quá trình compaction: định kỳ merge các SSTable, loại bỏ các bản cũ và tombstone (đánh dấu xóa).

Compaction: Quá trình background gộp nhiều SSTable thành ít hơn, loại bỏ duplicate và tombstone, đẩy data xuống level thấp hơn. Là chi phí ẩn lớn nhất của LSM-Tree — chiếm I/O và CPU, có thể gây spike latency nếu không tune đúng.

Hai chiến lược compaction phổ biến:

So sánh thẳng B+Tree vs LSM-Tree

Database dùng LSM-Tree

• Cassandra, ScyllaDB — distributed NoSQL, time-series.
• HBase — Hadoop-based.
• RocksDB — engine nhúng từ Facebook, dùng trong MySQL MyRocks, CockroachDB, TiKV, YugabyteDB.
• LevelDB — tiền thân RocksDB, từ Google.
• InfluxDB — time-series.

Đáng chú ý là MySQL MyRocks. Facebook viết một storage engine cho MySQL dùng RocksDB thay InnoDB, đạt 2x compression và giảm write amplification đáng kể cho workload của họ. Đây là ví dụ rõ nhất: không có "best index data structure" — chỉ có best for the workload.

Bài học rút ra cho phỏng vấn

Nếu được hỏi "Cassandra khác MySQL ở chỗ nào về storage?", câu trả lời sâu là:

"MySQL InnoDB dùng B+Tree với update tại chỗ — tốt cho OLTP với mix read/write. Cassandra dùng LSM-Tree với sequential write và compaction nền — tối ưu cho write throughput nhưng read phải merge nhiều SSTable, và compaction tạo write amplification cao. Lựa chọn phụ thuộc workload."

Câu trả lời này đánh thắng 90% ứng viên ở mức "MySQL là SQL, Cassandra là NoSQL".

Index chuyên dụng — khi B+Tree là câu trả lời sai

B+Tree đa năng đến mức nhiều người tưởng đó là loại index duy nhất. Sự thật là PostgreSQL hỗ trợ ít nhất 6 loại (btree, hash, gin, gist, brin, spgist), Oracle có bitmap index, MongoDB có geospatial, Elasticsearch có inverted index. Mỗi loại được sinh ra để giải bài toán B+Tree không làm tốt.

Bitmap Index — cardinality thấp, OLAP

Cột "gender" chỉ có 2-3 giá trị. Cột "status" có 10 giá trị. Cột "country" có vài trăm giá trị. Trên cột như vậy, B+Tree gần như vô dụng — một giá trị gender = 'M' match nửa bảng, optimizer sẽ chọn full scan.

Bitmap index lưu một bitmap (vector bit) cho mỗi giá trị riêng biệt: bit thứ i là 1 nếu hàng i có giá trị đó, ngược lại 0.

Bitmap Index: Index biểu diễn mỗi giá trị riêng biệt bằng một vector bit có độ dài = số hàng. Truy vấn với điều kiện phức tạp (gender = 'M' AND status = 'active' AND country = 'VN') được giải bằng AND giữa các bitmap — cực kỳ nhanh trên CPU hiện đại.

Table 8 rows, column "status":
  Row:    1 2 3 4 5 6 7 8
  status: A B A C B A B C

Bitmap for "A":    1 0 1 0 0 1 0 0
Bitmap for "B":    0 1 0 0 1 0 1 0
Bitmap for "C":    0 0 0 1 0 0 0 1

Query: status = 'A' OR status = 'B'
  -> Bitmap_A OR Bitmap_B
  -> 1 1 1 0 1 1 1 0
  -> Hàng 1,2,3,5,6,7

Ưu/nhược:

• Cực nhỏ cho cardinality thấp (vài bit/hàng).
• Truy vấn boolean cực nhanh — AND/OR/NOT bitmap bằng SIMD instruction.
• Tệ với write — mỗi update phải sửa N bitmap. Lock toàn bộ index cho ngay cả 1 row update.

→ Phù hợp OLAP / data warehouse (đọc nhiều, write theo batch). Oracle hỗ trợ trực tiếp; PostgreSQL không có bitmap index lưu trữ nhưng có bitmap heap scan, một technique optimizer dùng để kết hợp nhiều B-Tree index tại runtime.

GIN — Generalized Inverted Index, full-text & JSONB

GIN là inverted index: với mỗi element của giá trị (mỗi từ trong text, mỗi key/value trong JSONB, mỗi item trong array), lưu danh sách các hàng có chứa element đó. Đây chính là cấu trúc đằng sau Lucene, Elasticsearch, và full-text search của PostgreSQL.

GIN (Generalized Inverted Index): Index từ "element" tới danh sách các hàng. Tối ưu cho cột có nhiều giá trị bên trong (array, JSONB, tsvector). Nhanh khi query "tài liệu nào chứa từ X", chậm khi update vì một row có thể đụng nhiều entry.

-- PostgreSQL full-text search
CREATE INDEX idx_docs_fts ON documents
  USING GIN (to_tsvector('english', body));
 
SELECT * FROM documents
  WHERE to_tsvector('english', body) @@ to_tsquery('database & index');
-- Dùng GIN để liệt kê doc ID chứa cả "database" và "index"
 
-- JSONB index
CREATE INDEX idx_meta ON events USING GIN (metadata jsonb_path_ops);
 
SELECT * FROM events WHERE metadata @> '{"action": "login"}';

GIN có pending list — một buffer cho các update gần đây, được merge vào index chính định kỳ. Đây là LSM-Tree thu nhỏ bên trong PostgreSQL.

GiST — Generalized Search Tree, geospatial & range

GiST là một framework cho phép tạo index theo loại dữ liệu tùy ý — geometry, range, IP network — bằng cách định nghĩa các operator như "overlaps", "contains", "distance".

GiST (Generalized Search Tree): Cây search có cấu trúc tương tự B-Tree, nhưng các node lưu bounding box (hoặc tương đương) thay vì key. Mỗi loại dữ liệu plug-in cung cấp hàm để tính "có thể chứa kết quả?". Dùng cho PostGIS, range type, IP, ...

PostGIS dùng GiST để answer "tất cả các điểm trong vòng 10km quanh điểm X". Trên một bảng GPS hàng triệu hàng, GiST nhanh hơn full scan vài bậc.

CREATE INDEX idx_locations_geom ON locations USING GIST (geom);
 
-- Tìm điểm gần (10km) một địa điểm
SELECT * FROM locations
  WHERE ST_DWithin(geom, ST_MakePoint(106.7, 10.8), 10000);

BRIN — Block Range Index, dùng cho bảng cực lớn

Một bảng log có 10 tỷ hàng, sort theo created_at. B+Tree index trên created_at cũng có thể vài chục GB. BRIN giải vấn đề này bằng cách chỉ lưu min/max cho mỗi range các page, thay vì chỉ từng hàng.

BRIN (Block Range INdex): Cho mỗi khối liên tục các page (mặc định 128 page = 1 MB), BRIN lưu min/max của các cột được index. Index BRIN nhỏ hơn B-Tree hàng nghìn lần. Chỉ hữu ích khi data có thứ tự physical theo cột index (như timestamp tăng dần).

CREATE INDEX idx_logs_time_brin ON logs USING BRIN (created_at);
 
-- Khi query, BRIN nhanh chóng loại block nào KHÔNG thể chứa kết quả
SELECT * FROM logs WHERE created_at BETWEEN '2026-05-01' AND '2026-05-02';

Một BRIN index cho 1 tỷ hàng có thể chỉ tốn vài MB. Đánh đổi là độ chính xác thấp hơn — sau khi BRIN gợi ý các block khả thi, PostgreSQL vẫn phải scan từng hàng trong các block đó.

So sánh nhanh

Quan trọng nhất là hiểu rằng: chọn loại index = chọn trade-off. Không có "best", chỉ có "best for this workload on this hardware".

Hiện thực thật trong MySQL InnoDB và PostgreSQL

Cùng đều là B+Tree, nhưng MySQL InnoDB và PostgreSQL hiện thực rất khác nhau. Hiểu sự khác biệt này là một trong những câu hỏi phỏng vấn nâng cao mà người hỏi dùng để phân biệt "biết" với "thật sự hiểu".

MySQL InnoDB — Clustered index, mọi thứ là B+Tree

InnoDB lưu toàn bộ bảng bên trong một B+Tree, sort theo primary key. Tức là dữ liệu không nằm trong "heap file" riêng — leaf node của B+Tree primary key chính là data.

Clustered Index (Index-Organized Table): Mô hình mà data của bảng được lưu trực tiếp trong leaf node của một B+Tree theo primary key. Mỗi bảng có đúng một clustered index. InnoDB, SQL Server, Oracle (IOT mode) dùng mô hình này.

InnoDB primary key B+Tree (also the table itself):

                    Internal nodes (PK only)
                          [50]
                         /    \
              [10,30]              [70,90]
              /  |  \              /  |  \
           leaf  leaf leaf       leaf leaf leaf

   Leaf node:
   +----------------------------------------+
   | PK=10 | name=Alice | age=30 | ...      |
   | PK=11 | name=Bob   | age=25 | ...      |
   | PK=13 | name=Carol | age=40 | ...      |
   +----------------------------------------+
   ^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   PK       Toàn bộ row data nằm tại đây

Hệ quả 1: Primary key lookup cực nhanh. Một I/O xuống leaf là có row đầy đủ. Không cần "trip" thứ hai.

Hệ quả 2: Secondary index trỏ tới PK, không phải vị trí vật lý.

Secondary index on `email`:

   +-------------------+
   | email -> PK       |
   +-------------------+
   | alice@x.com -> 10 |
   | bob@x.com   -> 11 |
   | carol@x.com -> 13 |
   +-------------------+

Query: SELECT * FROM users WHERE email='alice@x.com'
  Step 1: B+Tree lookup email -> PK=10        (3-4 I/O)
  Step 2: B+Tree lookup PK=10 -> row data     (3-4 I/O, "double lookup")

Đây là lý do PK của InnoDB nên ngắn và đơn điệu tăng dần (auto-increment INT, BIGINT, hoặc ULID/sortable UUID). Mỗi secondary index lưu kèm PK ở mỗi entry. Nếu PK là VARCHAR(256), mỗi secondary index sẽ phình ra rất nhiều.

Hệ quả 3: Insert ngẫu nhiên gây page split. Auto-increment PK sẽ luôn append vào leaf cuối cùng — không split. Random PK (UUID v4) sẽ rải khắp B+Tree, gây split liên tục, fragment cao. Đây là lý do thực dụng để team thường tránh UUID v4 làm PK.

PostgreSQL — Heap file + index riêng

PostgreSQL có triết lý khác: data sống trong heap file (file không sort, không cấu trúc), index là cấu trúc riêng trỏ tới physical location (TID — Tuple ID = page + slot).

Heap Table: Mô hình mà data lưu trong file không sort — hàng mới chỉ append vào page có chỗ trống. Index lưu (key -> TID). PostgreSQL, MySQL MyISAM, Oracle (default), SQL Server (nếu không có clustered index) dùng mô hình này.

PostgreSQL:

  Heap file (unordered):
  +---------------------------+
  | Page 0: row, row, row     |
  | Page 1: row, row, row     |
  | Page 2: row, row, row     |
  +---------------------------+

  Index on `email`:
  +--------------------------------+
  | email -> (page_no, slot_no)    |
  +--------------------------------+
  | alice@x.com -> (Page 2, slot 1)|
  | bob@x.com   -> (Page 0, slot 3)|
  +--------------------------------+

  Query: SELECT * FROM users WHERE email='alice@x.com'
    Step 1: B+Tree lookup -> TID (1-3 I/O)
    Step 2: Read heap Page 2 slot 1     (1 I/O)

Hệ quả 1: Index lookup luôn là two-step (trừ index-only scan).

Hệ quả 2: Primary index không đặc biệt — nó là một B-Tree index như mọi index khác.

Hệ quả 3: MVCC tạo "dead tuple". PostgreSQL không update tại chỗ — mỗi UPDATE viết một version mới (mới TID), version cũ vẫn còn. Việc dọn version cũ là nhiệm vụ của VACUUM.

MVCC (Multi-Version Concurrency Control): Cơ chế PostgreSQL dùng để cho phép nhiều transaction đọc đồng thời mà không lock. Mỗi row có metadata xmin/xmax cho biết transaction nào tạo và xóa nó. Hệ quả là sau update/delete, các bản cũ vẫn nằm trong heap cho đến khi VACUUM dọn.

Heap-Only Tuple (HOT) update

Nếu một update không thay đổi cột nào có index, và page còn chỗ trống, PostgreSQL có thể tạo version mới trong cùng page và bỏ qua việc cập nhật index. Đây gọi là HOT update, rất nhanh.

Index-only scan

Nếu tất cả các cột được query đều có trong index, PostgreSQL có thể đọc thẳng từ index mà không cần đi tới heap. Nhưng vì MVCC, nó cần kiểm tra tuple có visible với transaction hiện tại không — thông qua visibility map. Nếu page tương ứng đã "all visible", VACUUM sẽ đánh dấu trong visibility map, và index-only scan thật sự thành công.

CREATE TABLE users (id INT, email TEXT, name TEXT);
CREATE INDEX idx_email ON users (email) INCLUDE (name);
 
-- Có thể index-only scan: chỉ cần email + name
EXPLAIN ANALYZE SELECT name FROM users WHERE email = 'a@x.com';
-- Index Only Scan using idx_email

Side-by-side: InnoDB vs PostgreSQL

WAL — backbone của crash safety ở cả hai

Cả hai đều dùng Write-Ahead Log: ghi vào log file (sequential, fsync) trước khi sửa page trong buffer pool. Khi crash, replay log để recover.

WAL (Write-Ahead Log): Log append-only ghi mọi thay đổi page trước khi page đó được flush xuống đĩa. Đảm bảo durability — nếu crash, replay log từ checkpoint cuối cùng sẽ restore lại state. MySQL gọi là redo log; PostgreSQL gọi là WAL.

WAL hai tác dụng:

1. Sequential I/O nhanh hơn random — gom mọi modification thành sequence ghi tuần tự.
2. fsync 1 lần cho nhiều thay đổi — group commit gộp nhiều transaction vào 1 fsync.

Đây là lý do mà ngay cả với LSM-Tree, vẫn cần WAL — memtable chỉ ở RAM, mất là mất hết nếu không log trước.

Practical takeaway

• InnoDB: Thiết kế schema với PK ngắn, đơn điệu tăng. Tránh quá nhiều secondary index trên bảng lớn.
• PostgreSQL: Để autovacuum tune đúng. Hiểu visibility map nếu muốn index-only scan thật sự work. Watch bloat.
• Cả hai: Đo EXPLAIN ANALYZE thật, đừng đoán.

Interview gold — thiết kế index đúng và những cái bẫy phổ biến

Đây là section mà câu trả lời "chuẩn" sẽ làm bạn nổi bật khi phỏng vấn. Mỗi mục là một câu hỏi thường gặp và bẫy đằng sau nó.

1. Leftmost prefix rule — vì sao composite index không phải lúc nào cũng dùng được

Index (a, b, c) thực ra là một B+Tree sort lexicographically theo (a, b, c). Tức là dữ liệu trên đĩa được sắp xếp:

(1, 1, 5)
(1, 1, 9)
(1, 2, 3)
(1, 2, 8)
(2, 1, 1)
(2, 3, 4)
...

Index này dùng được cho:

• WHERE a = ?
• WHERE a = ? AND b = ?
• WHERE a = ? AND b = ? AND c = ?
• WHERE a = ? AND b > ? (range cuối cùng)
• WHERE a = ? ORDER BY b, c

Không dùng được hoàn toàn cho:

• WHERE b = ? — không có a ở đầu, index vô dụng (trừ khi index skip scan, hiếm)
• WHERE c = ? — tương tự
• WHERE a = ? AND c = ? — chỉ dùng được phần a, phần c filter sau khi đọc

Bẫy phỏng vấn: Nhiều người tưởng "có index trên a,b,c thì query nào liên quan tới a, b, c đều dùng được". Sai. Quy luật là leftmost prefix — phải dùng tiền tố trái của index.

Leftmost Prefix Rule: Một composite index (a, b, c) chỉ có thể được dùng cho các query có điều kiện trên a, hoặc a và b, hoặc a và b và c — luôn phải bắt đầu từ cột bên trái nhất. Lý do là B+Tree sort theo thứ tự lexicographic.

2. Selectivity — index trên cột cardinality thấp gần như vô dụng

Cột gender chỉ có Y/N. Index trên nó về mặt lý thuyết có thể tìm "tất cả nam giới", nhưng optimizer sẽ làm gì?

• B-Tree tìm gender = 'M'. Match nửa bảng.
• Cho mỗi entry, phải lookup heap (PostgreSQL) hoặc clustered (InnoDB) → random I/O cho nửa bảng.
• Random I/O 50% bảng đắt hơn sequential scan toàn bảng → optimizer bỏ index, full scan.

Selectivity: Tỉ số cardinality / row_count. Selectivity gần 1 = mỗi giá trị gần như unique (email, UUID) → index rất hữu ích. Selectivity gần 0 = ít giá trị riêng biệt (gender, status) → index thường vô dụng cho B+Tree.

Quy tắc thực dụng: B+Tree đáng dùng khi selectivity < 5-10% của bảng. Dưới ngưỡng đó, optimizer chọn full scan.

Ngoại lệ: Cardinality thấp + WHERE rất rare combination (status = 'archived' chiếm 0.1%) → vẫn cần một partial index:

-- PostgreSQL
CREATE INDEX idx_archived ON orders (id) WHERE status = 'archived';
 
-- Chỉ index các hàng archived. Cực nhỏ, cực nhanh cho query rất hiếm.

3. Function-based index — vì sao WHERE LOWER(email) không dùng index

CREATE INDEX idx_email ON users (email);
 
SELECT * FROM users WHERE LOWER(email) = 'alice@x.com';
-- ^ KHÔNG dùng được index. Index sort theo email gốc, không phải LOWER(email).

Fix: tạo expression/function index:

CREATE INDEX idx_email_lower ON users (LOWER(email));
 
SELECT * FROM users WHERE LOWER(email) = 'alice@x.com';
-- Bây giờ dùng được.

Tương tự với WHERE DATE(created_at) = '2026-05-20' — phải tạo index trên DATE(created_at) hoặc viết lại thành created_at >= '2026-05-20' AND created_at < '2026-05-21'.

4. LIKE '%abc' không dùng được index — 'abc%' thì có

B+Tree sort theo prefix. WHERE name LIKE 'John%' có thể skip nhanh tới các key bắt đầu bằng "John", và đọc tuần tự đến khi không còn match. Nhưng WHERE name LIKE '%son'? Không có prefix → phải scan toàn bộ.

Workaround: nếu thật sự cần suffix search:

• Lưu thêm cột reverse(name) và index nó → WHERE reverse_name LIKE 'nos%'
• Dùng trigram index (pg_trgm ở PostgreSQL) — chia text thành các 3-gram và index chúng. Hỗ trợ wildcard cả hai phía:

CREATE EXTENSION pg_trgm;
CREATE INDEX idx_name_trgm ON users USING GIN (name gin_trgm_ops);
 
SELECT * FROM users WHERE name LIKE '%son%';
-- Có thể dùng trigram index

5. Implicit cast — index bỗng dưng không hoạt động

CREATE INDEX idx_phone ON users (phone);  -- phone VARCHAR
 
SELECT * FROM users WHERE phone = 1234567;
-- phone là VARCHAR, 1234567 là INT
-- MySQL sẽ convert phone -> INT cho TỪNG hàng -> full scan

Fix: dùng đúng kiểu — WHERE phone = '1234567'. Hoặc cast tường minh phía ngoài.

6. Covering index — tránh "double lookup"

Trên PostgreSQL hoặc trên InnoDB secondary index, query phải đi 2 trip: tìm index → tìm heap/clustered. Nếu cả query chỉ cần cột trong index, có thể skip trip thứ hai = index-only scan.

Covering Index: Một index chứa đầy đủ các cột mà query cần, cho phép database trả lời query chỉ bằng cách đọc index, không cần fetch row từ heap. Trong PostgreSQL gọi là Index Only Scan. MySQL dùng Using index trong EXPLAIN.

-- Query thường truy vấn
SELECT email, name FROM users WHERE email = ?;
 
-- Index thường: (email)
-- Phải đi 2 trip để lấy "name"
 
-- Covering index:
CREATE INDEX idx_email_name ON users (email, name);
-- Hoặc PostgreSQL với INCLUDE (cleaner):
CREATE INDEX idx_email_inc ON users (email) INCLUDE (name);
-- Bây giờ Index Only Scan

7. Index trên NULL — câu hỏi mẹo

PostgreSQL B-Tree index bao gồm cả NULL. Oracle B-Tree thì không. Câu hỏi phỏng vấn cổ điển: "Tại sao SELECT * FROM t WHERE col IS NULL đôi khi không dùng index trên Oracle?" — câu trả lời là B-Tree của Oracle bỏ qua NULL, phải tạo bitmap index hoặc function index (col, 0).

8. Đừng tạo quá nhiều index

Mỗi index là chi phí write. Insert vào bảng 5 index = 1 lần ghi data + 5 lần update index. Bảng OLTP với 20 index gần như chắc chắn là design sai.

Quy tắc thực dụng:

• Mỗi bảng nên có 5-7 index là max (trừ data warehouse).
• Luôn drop index không được dùng (PostgreSQL: pg_stat_user_indexes, MySQL: sys.schema_unused_indexes).
• Nếu hai index có cùng prefix ((a) và (a, b)), thường drop được (a) — (a, b) đã cover.

9. UUID v4 làm Primary Key — chuyện cũ nói lại

UUID v4 là ngẫu nhiên. Trên InnoDB (clustered index), insert UUID v4 PK gây:

• Random page split khắp B+Tree.
• Fragment cao → đọc tệ hơn.
• Mỗi secondary index lưu UUID 16 byte (so với 4 byte INT).

Giải pháp:

• UUID v7 (timestamp + random): Vẫn unique toàn cầu, nhưng sortable theo thời gian. Insert ở cuối B+Tree, không split.
• ULID (26-char Base32): Tương tự, monotonic.
• Hoặc dùng INT auto-increment + thêm UUID làm secondary index cho external API.

10. Đọc EXPLAIN đúng cách

Không có cuộc phỏng vấn database nào không có câu này. Một số manh mối quan trọng:

Luôn đo bằng EXPLAIN ANALYZE (PostgreSQL) hoặc EXPLAIN ANALYZE FORMAT=JSON (MySQL 8) trên dữ liệu thật, không phải production stage data.

Một câu trả lời mẫu cho phỏng vấn

"Tôi sẽ tiếp cận theo ba bước: đầu tiên dùng EXPLAIN ANALYZE để xem optimizer thực sự làm gì; thứ hai kiểm tra selectivity của các điều kiện WHERE — nếu thấp, có thể partial index hoặc xem xét cấu trúc khác; thứ ba xem xét leftmost prefix và covering — sắp xếp cột trong composite index theo selectivity giảm dần và include các cột thường được select. Tôi sẽ tránh thêm index nếu chưa đo, vì mỗi index là chi phí write."

Câu trả lời đó cho thấy bạn không "thuộc lòng" mà suy nghĩ về trade-off.

Kết luận

Index không phải là "mục lục của sách". Nó là một cấu trúc dữ liệu cẩn thận được thiết kế quanh giới hạn của phần cứng — page-oriented I/O, sequential vs random, cache locality, write amplification. Mỗi loại index tồn tại để giải quyết một bộ trade-off cụ thể:

• B+Tree thống trị OLTP vì cân bằng read/write/range tốt nhất. Cây thấp, fanout cao, leaf liên kết — đúng môi trường của database trên đĩa.
• Hash thắng ở point lookup nhưng mất hoàn toàn range — vì thế chỉ dùng trong workload đặc biệt (in-memory, key-value, AHI ngầm).
• LSM-Tree hy sinh read latency để đạt write throughput cực cao — backbone của Cassandra, RocksDB, ScyllaDB và mọi NoSQL write-heavy ngày nay.
• Bitmap, GIN, GiST, BRIN giải các bài toán đặc biệt — cardinality thấp, full-text, geospatial, bảng cực lớn — mà B+Tree làm tệ.

Hiện thực thật còn nhiều tầng nữa: clustered vs heap, WAL group commit, MVCC + VACUUM, page split + fill factor, bloom filter, compaction strategy. Mỗi tầng là một câu hỏi phỏng vấn tiềm năng — và cũng là một quyết định kỹ thuật bạn sẽ phải làm trên hệ thống thật.

Bài học cuối cùng

Khi ai đó hỏi "tôi nên tạo index thế nào?", câu trả lời đúng không bao giờ là một quy tắc cứng. Nó là một loạt câu hỏi ngược:

• Workload ra sao? Đọc nhiều hay ghi nhiều?
• Query pattern điển hình là gì? Point lookup, range, sort, aggregate?
• Cardinality và selectivity của các cột thế nào?
• Hardware: SSD hay HDD? RAM bao nhiêu so với data size?
• Đo đạc: EXPLAIN ANALYZE nói gì? Có dead tuple, có bloat, có page split không?

Hiểu sâu index là hiểu sâu mối liên hệ giữa cấu trúc dữ liệu, phần cứng, và workload. Đó cũng là lý do nó vẫn là một trong những câu hỏi phỏng vấn yêu thích — nó tách những người thật sự hiểu khỏi những người chỉ học vẹt.

Tiếp theo nên đọc gì?

• "Designing Data-Intensive Applications" của Martin Kleppmann — chapter 3 về Storage và Retrieval là nền tảng vàng.
• "Database Internals" của Alex Petrov — đi vào từng cấu trúc lưu trữ (B-Tree, LSM, Bw-Tree) đến mức implementation.
• PostgreSQL Internals ở postgrespro.com/community/books — chi tiết về MVCC, VACUUM, index types.
• MySQL Reference Manual — phần "InnoDB Storage Engine" là tài liệu chính thức tốt nhất.
• The RocksDB Wiki — học LSM-Tree từ một implementation production-grade.

Khi đọc xong, hãy mở EXPLAIN ANALYZE trên một query thật ở dự án của bạn. Đó là khoảnh khắc lý thuyết và thực tế gặp nhau — và là lúc bạn thật sự học chứ không chỉ biết.

References

• Designing Data-Intensive Applications — Martin Kleppmann, Chapter 3
• Database Internals — Alex Petrov
• PostgreSQL Documentation: Indexes
• PostgreSQL Internals — postgrespro.com
• MySQL Reference Manual: InnoDB Storage Engine
• MySQL Reference Manual: B-Tree and Hash Indexes
• The Log-Structured Merge-Tree (O'Neil et al., 1996)
• RocksDB Wiki — LSM-Tree implementation reference
• Use The Index, Luke! — SQL indexing tutorial by Markus Winand
• Latency Numbers Every Programmer Should Know — Jeff Dean

Related posts

• Clean Architecture in Go - Thiết kế ứng dụng sạch, tách biệt với hạ tầng (bao gồm tầng database)
• Golang Goroutines Deep Dive - Một deep dive cùng style về concurrency runtime
• eBPF Deep Dive - Deep dive về một công nghệ kernel khác