IndexingIndexing

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Mọi cấu trúc trong roadmap này từ trước tới giờ đều được nghiên cứu trong memory: array là một khối liên tục, B-tree là một tập các node, hash table là một mảng bucket. Indexing là chuyện xảy ra khi bạn lấy đúng những cấu trúc đó và trỏ chúng vào dữ liệu không nằm vừa trong memory — một table trên disk, một file, một column store. Thuật toán không thay đổi. Cái thay đổi là mô hình chi phí: một lần dereference pointer thôi không còn miễn phí mà trở thành một lần đọc page, và chỉ riêng sự thật đó đã định hình lại mọi quyết định thiết kế.

Index là một cấu trúc dữ liệu riêng biệt ánh xạ một giá trị tới vị trí của các record chứa giá trị đó. Không có nó, tìm một row nghĩa là đọc mọi row — một full scan, O(n) theo kích thước table. Có nó, tìm một row nghĩa là vài lần tra cứu trong một cấu trúc nhỏ hơn nhiều — O(log n) với tree index, O(1) với hash index — rồi nhảy thẳng tới record. Trên một table 100 triệu row, đó là khác biệt giữa đọc 10 GB và đọc bốn page 8 KB.

Không có lý thuyết nào mới ở đây. Một B+ tree index chính là multiway tree trong ./11-balanced-and-multiway-trees.md, với kích thước node được chọn khớp với disk page. Một hash index chính là hash table trong ./07-hash-tables.md, với các bucket nằm trên disk. Một index file đã sắp xếp được tìm bằng binary search chính là ./09-search-algorithms.md. Bài này nói về dạng ứng dụng: chọn cấu trúc nào cho access pattern nào, index tốn gì trên đường ghi, và tại sao câu trả lời không bao giờ là “đánh index mọi thứ”.

Đây có chủ ý là góc nhìn cấu trúc dữ liệu về indexing, không phải sổ tay DBA. Về phần vận hành — sáu access method của PostgreSQL, partial index và expression index, output của EXPLAIN, bloat, REINDEX CONCURRENTLY — hãy xem Chiến lược Indexing và Query Planning & Performance Tuning. Về chỗ đứng của index trong thiết kế database ở tầng ứng dụng, xem Relational Databases.

Kiến thức nền tảng

Tại sao index tồn tại: chi phí của một lần full scan

Hãy xét một table được lưu dưới dạng một dãy các page kích thước cố định (8 KB trong PostgreSQL, 16 KB trong InnoDB), mỗi page chứa một số record. Trả lời WHERE id = 30 mà không có index nghĩa là đọc hết page này tới page khác và kiểm tra từng record.

import bisect

PAGE_SIZE = 4
records = [(i, f"row-{i}") for i in range(0, 40, 2)]      # key 0, 2, 4, ..., 38
pages = [records[i:i + PAGE_SIZE] for i in range(0, len(records), PAGE_SIZE)]


def full_scan(pages, key):
    """Không index: đọc từng page cho tới khi thấy key. O(P) lần đọc page."""
    reads = 0
    for page in pages:
        reads += 1                        # một lần đọc page = một đơn vị I/O
        for k, v in page:
            if k == key:
                return v, reads
    return None, reads


print(full_scan(pages, 30))               # ('row-30', 4)
print(full_scan(pages, 99))               # (None, 5) — miss thì đọc toàn bộ

Hai điều cần chú ý. Một lần trúng tốn trung bình một nửa số page; một lần trượt luôn tốn toàn bộ. Và hằng số nhân cực kỳ quan trọng: đọc một page từ SSD mất ~100 μs và từ ổ đĩa quay ~10 ms, so với ~100 ns cho một lần truy cập memory đã được cache. Index không chỉ giảm số phép toán, nó chuyển các phép toán đắt thành các phép toán rẻ.

Index như một cấu trúc thứ hai, nhỏ hơn

Index lưu các cặp (giá trị được index → vị trí), được sắp xếp hoặc hash theo giá trị. Nó nhỏ hơn table vì chỉ chứa cột được index cộng một pointer, nên mỗi page chứa được nhiều entry hơn, nên cấu trúc nông hơn và phần lớn nó nằm trong cache.

TABLE (heap) — thứ tự vật lý là tùy ý            INDEX trên `email` — sắp theo giá trị

page 0: (7, "carol@x", ...)                       "alice@x"  → (page 1, slot 0)
        (2, "erin@x",  ...)                       "bob@x"    → (page 2, slot 1)
page 1: (5, "alice@x", ...)                       "carol@x"  → (page 0, slot 0)
        (9, "dan@x",   ...)                       "dan@x"    → (page 1, slot 1)
page 2: (1, "frank@x", ...)                       "erin@x"   → (page 0, slot 1)
        (4, "bob@x",   ...)                       "frank@x"  → (page 2, slot 0)

Hai lựa chọn cấu trúc định nghĩa cả họ này:

• Dense index — một entry cho mỗi record. Bắt buộc với mọi cột mà giá trị của nó không phải thứ tự vật lý của table, vì bạn không thể nhảy tới một record mà bạn không có pointer trỏ tới. Mọi secondary index đều là dense.
• Sparse index — một entry cho mỗi page, chứa key nhỏ nhất của page đó. Chỉ khả thi khi data file được sắp xếp vật lý theo key được index, nhưng nhỏ hơn hẳn: với 100 record mỗi page, sparse index chỉ bằng 1% kích thước của dense index.

# SPARSE index: một entry cho mỗi page, chứa key nhỏ nhất của page đó.
sparse_index = [(page[0][0], pno) for pno, page in enumerate(pages)]


def sparse_lookup(pages, index, key):
    """Binary search trên index để chọn đúng một page, rồi quét page đó."""
    keys = [k for k, _ in index]
    pos = bisect.bisect_right(keys, key) - 1   # page cuối cùng có key đầu <= key
    if pos < 0:
        return None, 0
    _, pno = index[pos]
    reads = 1                                  # chạm đúng một data page
    for k, v in pages[pno]:
        if k == key:
            return v, reads
    return None, reads


print(sparse_lookup(pages, sparse_index, 30))   # ('row-30', 1)
print(sparse_lookup(pages, sparse_index, 99))   # (None, 1) — miss cũng rẻ

Bốn lần đọc page giảm còn một, và trường hợp miss cải thiện từ năm lần đọc xuống một. Tỷ lệ đó chỉ càng lớn khi table càng lớn, đó chính là toàn bộ lý lẽ cho việc đánh index.

Một trục thứ hai:

• Clustered / primary index — các record của table được lưu vật lý theo thứ tự của index này (primary key của InnoDB, PostgreSQL sau CLUSTER). Chỉ có thể có một, và range scan trên nó là I/O tuần tự — thứ nhanh nhất mà một ổ đĩa làm được.
• Non-clustered / secondary index — một cấu trúc riêng trỏ ngược về heap. Có bao nhiêu cũng được, nhưng range scan sinh ra các lần đọc ngẫu nhiên vào heap, một lần cho mỗi row khớp.

Sự phân biệt đó giải thích sự thật phản trực giác nhất về index: vượt qua một ngưỡng selectivity nào đó, index chậm hơn full scan. Nếu một truy vấn khớp 30% của một table lớn, đi theo secondary index nghĩa là 30% số row được lấy về bằng các lần đọc page đơn lẻ ngẫu nhiên, đắt hơn nhiều so với việc đọc tuần tự toàn bộ table. Query planner thật sẽ ước lượng điều này và chuyển sang sequential scan — xem Query Planning & Performance Tuning để biết quyết định đó thực sự được đưa ra thế nào và đọc nó trong EXPLAIN ra sao.

Linear / sequential indexing

“Linear indexing” bao hàm hai ý tưởng đơn giản có liên quan, cả hai đều đáng nêu tên vì chúng là mốc cơ sở mà mọi thứ khác cải tiến lên từ đó.

1. Linear indexing cho mảng nhiều chiều. Một mảng 2 chiều trong memory thực chất là một khối 1 chiều; “index” ở đây là phép số học làm phẳng (row, col) thành một offset duy nhất. Theo thứ tự row-major (C, Python, hầu hết các ngôn ngữ):

Góc nhìn 2 chiều (3 hàng x 4 cột)      layout tuyến tính (row-major) trong memory

   c0  c1  c2  c3                  offset:  0  1  2  3  4  5  6  7  8  9 10 11
r0  a   b   c   d                  giá trị: a  b  c  d  e  f  g  h  i  j  k  l
r1  e   f   g   h                           |__ row 0 __|__ row 1 __|__ row 2 __|
r2  i   j   k   l

offset(r, c) = r * cols + c          ví dụ offset(1, 2) = 1*4 + 2 = 6 -> 'g'

def linear_index(r, c, cols):
    """Làm phẳng row-major: O(1), và là lý do duyệt theo hàng nhanh hơn theo cột."""
    return r * cols + c

Đây là phép số học địa chỉ O(1) không cần tra cứu gì cả, và nó chính là mẹo dùng để đưa một grid vào union-find trong ./16-disjoint-set-union-find.md. Ý nghĩa thực tiễn của nó là cache locality: duyệt for r: for c: đi tuần tự trong memory và thường nhanh gấp vài lần for c: for r:, vốn nhảy qua cả mảng ở mỗi bước. Các ngôn ngữ column-major (Fortran, MATLAB, và NumPy khi bạn yêu cầu) đảo ngược công thức, và làm ngược là một bug hiệu năng kinh điển. Xem ./04-arrays.md.

2. Một linear (sequential) index file. Nghĩa ở phía database: giữ index dưới dạng một mảng phẳng đã sắp xếp gồm các cặp (key, vị trí). Tra cứu là binary search — O(log n) lần so sánh, và nếu mảng nằm trên disk thì O(log n) lần đọc page.

def linear_index_lookup(index, key):
    """Binary search trên index phẳng đã sắp xếp. O(log n) — xem ./09-search-algorithms.md."""
    keys = [k for k, _ in index]
    pos = bisect.bisect_left(keys, key)
    if pos < len(index) and index[pos][0] == key:
        return index[pos][1]
    return None

Điểm yếu chí mạng của nó là việc chèn: đưa một key mới vào giữa một mảng đã sắp xếp tốn O(n) vì mọi thứ phía sau phải dịch đi. Điều đó chấp nhận được với một index chỉ đọc được dựng hàng loạt (data warehouse, search index dựng offline) và vô dụng với bất cứ thứ gì mang tính transactional. Toàn bộ phần còn lại của bài này tồn tại để giữ được việc tìm kiếm O(log n) trong khi làm cho việc chèn cũng rẻ.

Khái niệm chính

Tree-based indexing: B-tree và B+ tree

Cấu trúc index thống trị, với khoảng cách rất xa, là B+ tree. Lý do nằm ở một quyết định thiết kế duy nhất: kích thước node được chọn khớp với disk page, nên một lần lấy node là một lần I/O.

Một balanced binary tree chứa 100 triệu key sâu khoảng 27 tầng, tức 27 lần đọc page. Một B+ tree có node chứa ~400 key mỗi node (một page 8 KB với key và pointer 8 byte) có branching factor 400, nên độ sâu của nó là log₄₀₀(10⁸) ≈ 3. Ba lần đọc page, và root cùng tầng nội bộ đầu tiên gần như chắc chắn đã nằm trong cache, nên trên thực tế một lần tra cứu là một lần đọc vật lý. Fan-out cao chính là toàn bộ ý tưởng — xem ./11-balanced-and-multiway-trees.md để biết B-tree split, merge và giữ cân bằng như thế nào.

Sự phân biệt B-tree so với B+ tree chính là điều khiến B+ tree có hình dạng đúng cho một database index:

	B-tree	B+ tree
Dữ liệu/pointer nằm ở đâu	Ở mọi node, cả nội bộ lẫn leaf	Chỉ ở leaf; node nội bộ chỉ giữ key phân tách
Fan-out của node nội bộ	Thấp hơn (mỗi key kèm payload)	Cao hơn (chỉ key ⇒ nhiều key mỗi page ⇒ tree nông hơn)
Point lookup	Có thể dừng sớm ở node nội bộ	Luôn đi xuống tới leaf (chi phí đồng đều, dự đoán được)
Range scan	Cần in-order traversal đi lên đi xuống	Các leaf được liên kết ⇒ một lần đi xuống, rồi đi ngang
Được dùng bởi	Một số filesystem, map trong memory	Về cơ bản là mọi index của relational database

Dòng cuối cùng là dòng quyết định:

B+ tree, fan-out 4 — node nội bộ chỉ mang key phân tách

                        [ 10 | 20 ]                      <- root
                       /     |     \
              [4 | 7]    [13 | 16]    [24 | 27]          <- nội bộ
             /   |   \    /   |   \    /   |   \
            v    v    v  v    v    v  v    v    v

tầng leaf, mọi record đều có mặt, theo thứ tự key, liên kết trái sang phải:

 [1 2 3] <-> [4 5 6] <-> [7 8 9] <-> [10 11 12] <-> ... <-> [28 29 30] -> None

  WHERE k BETWEEN 5 AND 27:
    một lần đi từ root xuống leaf để tìm 5   (3 lần đọc page)
    rồi đi theo liên kết leaf tới 27         (đọc tuần tự, không đi xuống lại)

Một range scan trên B+ tree tốn O(log n + k) cho k kết quả, và — vì các leaf được liên kết và thường nằm gần nhau — k lần đọc đó gần như tuần tự. Trên B-tree thuần thì cùng phép quét đó phải nhảy lên nhảy xuống trong cây. Đây là lý do ORDER BY, BETWEEN, >, <, LIMIT kèm sort, và MIN/MAX đều rẻ trên B+ tree index, và là lý do “B-tree index” trong database gần như luôn nghĩa là B+ tree.

Độ phức tạp, tính theo số lần đọc page thay vì số phép so sánh:

Phép toán	B+ tree index	Ghi chú
Point lookup	O(log_f n) ≈ 3–4 lần đọc	f = fan-out, thường 100–500
Range scan k row	O(log_f n + k/số_record_mỗi_page)	Tuần tự ở tầng leaf
Insert	O(log_f n)	Cộng thêm việc split node thỉnh thoảng lan lên trên
Delete	O(log_f n)	Cộng thêm merge/rebalance, hoặc tombstone + vacuum sau
Space	O(n)	Thường 1–3% kích thước table mỗi cột được index, với page đầy ~70–90%

Hash index

Hash index áp hàm hash lên key và nhảy thẳng tới bucket chứa vị trí của record — O(1) kỳ vọng, không phụ thuộc kích thước table.

def build_hash_index(pages, buckets=8):
    """Hash index: key -> (page, slot). Tra cứu equality O(1), hoàn toàn không có thứ tự."""
    index = [[] for _ in range(buckets)]
    for pno, page in enumerate(pages):
        for slot, (k, _) in enumerate(page):
            index[hash(k) % buckets].append((k, pno, slot))
    return index


def hash_lookup(pages, index, key):
    """Một lần đọc bucket, rồi quét ngắn bên trong nó. O(1) kỳ vọng."""
    for k, pno, slot in index[hash(key) % len(index)]:
        if k == key:
            return pages[pno][slot][1]
    return None


hidx = build_hash_index(pages)
print(hash_lookup(pages, hidx, 30))        # 'row-30'
print(hash_lookup(pages, hidx, 31))        # None

Cơ chế ở đây là hash table trong ./07-hash-tables.md, được chuyển lên disk — các biến thể on-disk (extendible hashing, linear hashing) tồn tại chính là để tránh cú khựng “rehash toàn bộ table cùng lúc” mà việc resize trong memory chấp nhận được.

Điều mà hash index không làm được chính là lý do nó hiếm khi là lựa chọn đúng:

• Không hỗ trợ range query. Hashing phá hủy thứ tự theo thiết kế; WHERE x > 5 hoàn toàn không dùng được nó.
• Không hỗ trợ sort. Nó không thỏa mãn được ORDER BY, MIN, hay MAX.
• Không so khớp prefix. LIKE 'abc%' là vô hình với nó.
• Không dùng được leftmost-prefix của composite index. Hash của (a, b) không nói gì về riêng a.

B+ tree làm equality lookup trong 3–4 lần đọc page và làm tất cả những thứ còn lại nữa. Nên quy tắc thực tế là: mặc định dùng tree index, và chỉ dùng hashing trong trường hợp hẹp, đã đo đạc cụ thể — thường là key rất dài mà việc hash làm index nhỏ đi đáng kể, và bạn chắc chắn sẽ không bao giờ cần truy vấn range hay ordering. Hash index của PostgreSQL chỉ trở nên crash-safe từ phiên bản 10; xem Chiến lược Indexing để biết lịch sử đó và khuyến nghị hiện tại.

ISAM và vai trò lịch sử của nó

ISAM (Indexed Sequential Access Method), do IBM giới thiệu vào thập niên 1960, là tổ tiên trực tiếp của mọi thứ ở trên và đáng hiểu vì kiểu thất bại của nó giải thích tại sao B+ tree thắng.

Thiết kế: lưu data file sắp xếp vật lý theo key, và dựng một index tĩnh, sparse, nhiều tầng phía trên nó — một entry cho mỗi data block, rồi một index trên index đó, cho tới một root nhỏ. Một lần tra cứu đi xuống qua các tầng index và đáp xuống đúng một data block. Xử lý tuần tự (bảng lương, báo cáo theo lô — các workload của thời đó) đọc thẳng data file theo thứ tự key, và trên băng từ hay ổ đĩa quay thì đó là tối ưu.

Layout của ISAM

  master index   :        [ 100 | 400 | 700 ]
                          /       |        \
  cylinder index : [100|200|300] [400|...]  [700|...]
                     |
  data block     : [101..150][151..200]...        <- sắp xếp vật lý, không chừa chỗ trống
                        |
  overflow chain :  [ 155 ] -> [ 158 ] -> [ 156 ]  <- insert rơi vào đây, không sắp xếp

Vấn đề nằm ở chữ tĩnh. Index được dựng một lần, lúc tạo file. Một lần insert không vừa vào block gốc của nó sẽ đi vào overflow area, được móc xích từ block đó. Các lần đọc giờ phải kiểm tra cả block gốc lẫn đi hết chuỗi overflow của nó. Khi insert tích tụ, chuỗi dài ra, tra cứu suy giảm từ O(log n) về phía O(n) trên các block nóng, và cách chữa duy nhất là đưa file offline và reorganize nó — dựng lại toàn bộ theo thứ tự, với chỗ trống mới.

Việc reorganize offline định kỳ đó là một phần bình thường, được lên lịch của vận hành thập niên 1960–70 và hoàn toàn không chấp nhận được ngày nay. B-tree (Bayer và McCreight, 1970) giải quyết nó bằng cách làm cho index trở nên động: node split và merge tại chỗ khi dữ liệu tới, tree tự giữ cân bằng, và không có overflow area cũng không có cửa sổ reorganize. Chính IBM đã thay ISAM bằng VSAM, và B+ tree tiếp quản mọi nơi khác.

Di sản của ISAM vẫn còn thấy được trong từ vựng — storage engine gốc của MySQL tên là MyISAM, và “index-sequential” vẫn là cách người ta mô tả một clustered index. Và ý tưởng cốt lõi sống tiếp dưới hình thức hiện đại: LSM-tree, được RocksDB, LevelDB, Cassandra và HBase dùng, chính là thỏa thuận của ISAM được viết lại cho SSD. Chúng giữ các run bất biến đã sắp xếp, hấp thụ ghi vào một buffer trong memory, và compact (reorganize) ở nền — đánh đổi read amplification lấy write throughput rất cao. Xem NoSQL Databases.

Chi phí ghi của một index

Toàn bộ câu chuyện index cho tới giờ là về việc đọc. Mọi lợi ích đó đều được trả giá trên đường ghi, và đây là nơi sự nhiệt tình với index đi đến hồi kết.

Mỗi index nhân lên khối lượng công việc ghi. Một table có năm index biến một lệnh INSERT thành sáu lần sửa đổi cấu trúc: một lần ghi heap cộng năm lần chèn index, mỗi lần là một lượt đi xuống O(log n) riêng, một lần làm bẩn page riêng, và một khả năng split node riêng. Một mô hình thô:

INSERT vào một table có k secondary index:
    1 lần ghi heap page
  + k lượt đi xuống index (log_f n lần đọc page mỗi lượt, phần lớn đã cache)
  + k lần ghi leaf page của index
  + thỉnh thoảng có page split, mỗi lần ghi 2-3 page và làm bẩn parent
  + bản ghi write-ahead log cho tất cả những thứ trên

Các hệ quả cụ thể đáng biết ở tầng cấu trúc dữ liệu:

• Chèn theo thứ tự ngẫu nhiên tệ hơn nhiều so với tuần tự. Chèn các key tăng đơn điệu (auto-increment id, timestamp) luôn nối vào leaf ngoài cùng bên phải, vốn luôn nóng trong cache — rẻ. Chèn key ngẫu nhiên (UUIDv4) làm bẩn một leaf page khác nhau mỗi lần, nên working set trở thành toàn bộ index. Đây là lý do UUIDv7 / ULID (UUID có thứ tự thời gian) tồn tại, và đó là một lý lẽ thuần túy về cấu trúc dữ liệu, không có gì đặc thù database cả.
• UPDATE có thể tốn hơn INSERT. Cập nhật một cột không được index vẫn có thể buộc phải cập nhật mọi index nếu storage engine ghi một phiên bản row mới (MVCC của PostgreSQL làm đúng như vậy, được giảm nhẹ nhưng không loại bỏ nhờ HOT update — xem Storage Internals & Vacuum).
• Delete để lại rác. Xóa một entry thường chỉ đánh dấu là chết chứ không nén page ngay lập tức; việc thu hồi không gian là một tác vụ nền. Do đó index bị bloat — phình to hơn mức dữ liệu biện minh — khi có nhiều biến động.
• Bulk load nhanh hơn khi đã drop index. Nạp n row vào một table có index tốn n lần chèn O(log n) riêng lẻ với truy cập page ngẫu nhiên; drop index, nạp dữ liệu, rồi dựng lại index thì chỉ sort một lần và điền page tuần tự. Với các đợt nạp lớn, cách này thường nhanh hơn cả một bậc độ lớn.

Chi phí lưu trữ. Một entry của B+ tree index xấp xỉ bằng key cộng một row pointer cộng phần overhead mỗi entry — cứ tạm tính ~16–24 byte cho một key số nguyên 8 byte, với page đầy 70–90%. Một index trên cột bigint của table 100 triệu row dễ dàng đạt 2–3 GB. Đánh index một cột text rộng và index có thể tiệm cận hoặc vượt cả bản thân table. Index cũng cạnh tranh cùng buffer cache với dữ liệu, nên một index không dùng tới không chỉ là disk lãng phí — nó chủ động đẩy ra những page mà bạn thực sự cần.

Tổng hợp lại: một index là một canh bạc rằng lượt đọc nhiều hơn lượt ghi với access pattern này. Trên một table nặng ghi với một truy vấn hiếm khi chạy, canh bạc đó thua. Index không dùng tới là chi phí thuần túy, và việc tìm ra rồi drop chúng là một trong những tác vụ bảo trì database có giá trị cao nhất và rủi ro thấp nhất.

Composite index và quy tắc leftmost-prefix

Một composite index (nhiều cột) sắp xếp các entry theo cột thứ nhất, rồi cột thứ hai trong các trường hợp bằng nhau, rồi cột thứ ba — hệt như sort tuple. Chính thứ tự đó quyết định truy vấn nào dùng được nó.

composite index trên (tenant_id, created_at, status), sắp theo thứ tự từ điển:

  (1, 2024-01-01, 'new')
  (1, 2024-01-01, 'paid')
  (1, 2024-01-02, 'new')
  (1, 2024-01-05, 'paid')
  (2, 2024-01-01, 'new')
  (2, 2024-01-03, 'shipped')

DÙNG ĐƯỢC (một khoảng liền kề trong index):
  WHERE tenant_id = 1
  WHERE tenant_id = 1 AND created_at >= '2024-01-02'
  WHERE tenant_id = 1 AND created_at = '2024-01-01' AND status = 'paid'
  ORDER BY tenant_id, created_at                       (vốn đã theo thứ tự này)

KHÔNG DÙNG ĐƯỢC như một lần tra cứu có thứ tự:
  WHERE created_at >= '2024-01-02'    -- row của ngày đó rải rác khắp các tenant
  WHERE status = 'paid'               -- riêng cột thứ ba: không liền kề chút nào

DÙNG ĐƯỢC MỘT PHẦN:
  WHERE tenant_id = 1 AND status = 'paid'
    -> tenant_id thu hẹp index về một khối liền kề;
       status khi đó chỉ là bộ lọc áp dụng trong lúc quét khối đó

Quy tắc suy ra trực tiếp từ thứ tự sắp xếp và không cần học thuộc: một index chỉ dùng được cho một truy vấn tới mức mà truy vấn đó ràng buộc một prefix dẫn đầu các cột của nó, và chỉ cột bị ràng buộc cuối cùng mới được dùng vị từ range — một khi bạn quét range trên cột i, các cột sau i không còn theo thứ tự sắp xếp trong kết quả nữa. Nên thứ tự cột trong composite index là một quyết định thiết kế thực sự: đặt các vị từ equality trước, vị từ range sau cùng, và cột equality có selectivity cao nhất lên đầu.

Covering index và index-only scan

Một index bình thường trả lời “row nằm ở đâu”, sau đó engine lấy row từ heap — một lần đọc thứ hai, ngẫu nhiên, cho mỗi kết quả. Một covering index loại bỏ bước đó bằng cách chứa mọi cột mà truy vấn cần, để riêng index đã trả lời được:

SELECT status FROM orders WHERE tenant_id = 1 AND created_at > '2024-01-01';

index trên (tenant_id, created_at)          -> tìm entry khớp trong index,
                                               rồi một lần đọc heap ngẫu nhiên mỗi row

index trên (tenant_id, created_at, status)  -> `status` đã có sẵn trong index;
   (hoặc ... INCLUDE (status))                 không đọc heap lần nào: INDEX-ONLY SCAN

Với một truy vấn trả về hàng nghìn row, điều này loại bỏ hàng nghìn lần đọc ngẫu nhiên và thường là cải thiện 10×. Đánh đổi vẫn là cái muôn thuở: index rộng hơn là index lớn hơn, ghi chậm hơn và chiếm chỗ cache nhiều hơn. Mệnh đề INCLUDE của Postgres tồn tại để thêm cột payload vào tầng leaf mà không thêm chúng vào sort key của cây, giữ cho node nội bộ vẫn hẹp — một minh họa đẹp rằng việc B+ tree tách key nội bộ khỏi payload ở leaf không phải là ngẫu nhiên. Chi tiết và cú pháp nằm ở Chiến lược Indexing.

Chọn cấu trúc index

Access pattern	Cấu trúc	Lý do
Equality và range, sorting, MIN/MAX, LIKE prefix	B+ tree	Mặc định; xử lý gần như mọi thứ trong 3–4 lần đọc page
Chỉ equality, key rất dài, đã đo được nhu cầu	Hash index	O(1), nhưng không thứ tự, không range, không prefix
Dữ liệu chỉ đọc, dựng hàng loạt, không bao giờ update	File phẳng đã sắp xếp + binary search	Đơn giản và nhỏ nhất; chèn O(n) khiến nó chỉ đọc
Dữ liệu sắp xếp vật lý, xử lý tuần tự theo lô	Sparse index kiểu ISAM	Index rất nhỏ; suy giảm nặng khi có insert
Nặng ghi, đọc chủ yếu tuần tự	LSM-tree	Buffer việc ghi, compact ở nền
Kiểm tra thành viên trên keyspace khổng lồ, chấp nhận false positive	Bloom filter	Bit chứ không phải entry; dùng phía trước index LSM
”Row nào chứa phần tử/từ này?”	Inverted index (GIN)	Một entry cho mỗi token, trỏ tới mọi row chứa nó
Dữ liệu rất lớn, có cụm tự nhiên (time-series)	Block-range index (BRIN)	Lưu min/max mỗi dải block; rất nhỏ, cần tương quan
Prefix/autocomplete trên chuỗi	Trie / radix trie	Xem ./17-advanced-tree-structures.md
Tìm substring trên một corpus cố định	Suffix array / FM-index	Xem ./17-advanced-tree-structures.md

Dòng đầu tiên bao phủ đại đa số các trường hợp thực tế, và đó chính là điểm mấu chốt: tính đa năng của B+ tree đáng giá hơn lợi thế của bất kỳ cấu trúc chuyên biệt nào ở một chiều duy nhất. Các access method GIN, GiST, SP-GiST và BRIN của PostgreSQL chính là các dòng chuyên biệt được cụ thể hóa — xem Chiến lược Indexing để biết khi nào mỗi loại xứng đáng có chỗ.

Best Practices

• Đánh index cho truy vấn, không phải cho cột. Index tồn tại để phục vụ một access pattern cụ thể. Hãy bắt đầu từ những truy vấn bạn thực sự chạy — mệnh đề WHERE, JOIN, ORDER BY của chúng — chứ không phải từ thói quen đánh index mọi foreign key và mọi cột “trông có vẻ tìm kiếm được”.
• Mặc định dùng B+ tree. Nó xử lý equality, range, sorting, MIN/MAX, và so khớp prefix trong 3–4 lần đọc page. Chỉ chọn cấu trúc chuyên biệt khi bạn gọi được tên truy vấn mà nó phục vụ và đã đo được rằng B+ tree không đủ.
• Nhớ rằng index là một canh bạc về tỷ lệ đọc/ghi. Mỗi index làm mọi lần ghi vào table đó đắt hơn, vĩnh viễn. Trên một table nặng ghi phục vụ một truy vấn chạy hai lần mỗi ngày, canh bạc đó thua.
• Đặt cột equality lên trước trong composite index, cột range sau cùng. Quy tắc leftmost-prefix là hệ quả trực tiếp của thứ tự sắp xếp từ điển, và đặt sai thứ tự cột khiến một index vốn đúng trở nên vô dụng với một nửa số truy vấn của bạn.
• Ưu tiên một composite index được sắp xếp tốt hơn là nhiều index một cột. Ba index riêng lẻ nhân ba chi phí ghi và thường vẫn buộc phải lấy dữ liệu từ heap; một composite index trên cùng các cột đó có thể phủ trọn truy vấn.
• Cân nhắc covering index cho các đường đọc nóng. Thêm các cột được chiếu ra sẽ biến một range scan cộng k lần đọc heap ngẫu nhiên thành một index-only scan tuần tự duy nhất. Hãy cân nhắc với kích thước index lớn hơn và chi phí ghi thêm.
• Chèn theo thứ tự key khi có thể. Key đơn điệu nối vào một leaf page nóng duy nhất; key ngẫu nhiên (UUIDv4) làm bẩn một page khác nhau mỗi lần và biến cả index thành working set. Các định danh có thứ tự thời gian (UUIDv7, ULID, Snowflake) tồn tại chính vì lý do này.
• Drop index trước một đợt bulk load rồi dựng lại sau. Một lần dựng hàng loạt có sắp xếp sẽ điền page tuần tự; n lần chèn riêng lẻ thực hiện n lượt đi xuống O(log n) ngẫu nhiên. Khác biệt thường xuyên là cả một bậc độ lớn.
• Tìm và drop các index không dùng tới. Chúng tốn disk, tốn write throughput, và đẩy các page hữu ích ra khỏi buffer cache. Gần như mọi database đều cung cấp thống kê sử dụng theo từng index; kiểm tra định kỳ vừa rẻ vừa hiệu quả cao.
• Đừng ngạc nhiên khi planner bỏ qua index của bạn. Vượt quá khoảng 5–20% selectivity, sequential scan thắng index scan cộng các lần lấy heap ngẫu nhiên, và planner thường đúng. Nếu nó sai, cách sửa là cải thiện statistics hoặc dùng covering index, chứ không phải ép dùng index — xem Query Planning & Performance Tuning.
• Hiểu cấu trúc trước khi tune database. “Tại sao LIKE '%foo' không dùng được index?”, “tại sao composite index cần các cột theo đúng thứ tự đó?”, và “tại sao UUID primary key làm chậm insert?” đều có cùng một câu trả lời: đó là một B+ tree, và B+ tree thì được sắp xếp. Góc nhìn cấu trúc dữ liệu trả lời cho các câu hỏi của DBA.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Database index — Wikipedia
• B-tree — Wikipedia
• B+ tree — Wikipedia
• ISAM — Wikipedia
• Log-structured merge-tree — Wikipedia
• Row- and column-major order — Wikipedia
• Inverted index — Wikipedia
• Use The Index, Luke! — a guide to SQL indexing
• PostgreSQL Documentation — Indexes
• CLRS — Introduction to Algorithms, Chapter 18: B-Trees
• Python Documentation — bisect

import bisect

PAGE_SIZE = 4
records = [(i, f"row-{i}") for i in range(0, 40, 2)]      # keys 0, 2, 4, ..., 38
pages = [records[i:i + PAGE_SIZE] for i in range(0, len(records), PAGE_SIZE)]


def full_scan(pages, key):
    """No index: read pages until the key turns up. O(P) page reads."""
    reads = 0
    for page in pages:
        reads += 1                        # one page read = one unit of I/O
        for k, v in page:
            if k == key:
                return v, reads
    return None, reads


print(full_scan(pages, 30))               # ('row-30', 4)
print(full_scan(pages, 99))               # (None, 5) — a miss reads everything

TABLE (heap) — physical order is arbitrary        INDEX on `email` — sorted by value

page 0: (7, "carol@x", ...)                       "alice@x"  → (page 1, slot 0)
        (2, "erin@x",  ...)                       "bob@x"    → (page 2, slot 1)
page 1: (5, "alice@x", ...)                       "carol@x"  → (page 0, slot 0)
        (9, "dan@x",   ...)                       "dan@x"    → (page 1, slot 1)
page 2: (1, "frank@x", ...)                       "erin@x"   → (page 0, slot 1)
        (4, "bob@x",   ...)                       "frank@x"  → (page 2, slot 0)

# SPARSE index: one entry per page, holding that page's smallest key.
sparse_index = [(page[0][0], pno) for pno, page in enumerate(pages)]


def sparse_lookup(pages, index, key):
    """Binary search the index to pick exactly one page, then scan that page."""
    keys = [k for k, _ in index]
    pos = bisect.bisect_right(keys, key) - 1   # last page whose first key <= key
    if pos < 0:
        return None, 0
    _, pno = index[pos]
    reads = 1                                  # exactly one data page is touched
    for k, v in pages[pno]:
        if k == key:
            return v, reads
    return None, reads


print(sparse_lookup(pages, sparse_index, 30))   # ('row-30', 1)
print(sparse_lookup(pages, sparse_index, 99))   # (None, 1) — a miss is cheap too

2-D view (3 rows x 4 cols)        linear (row-major) layout in memory

   c0  c1  c2  c3                  offset:  0  1  2  3  4  5  6  7  8  9 10 11
r0  a   b   c   d                  value:   a  b  c  d  e  f  g  h  i  j  k  l
r1  e   f   g   h                           |__ row 0 __|__ row 1 __|__ row 2 __|
r2  i   j   k   l

offset(r, c) = r * cols + c          e.g. offset(1, 2) = 1*4 + 2 = 6 -> 'g'

def linear_index(r, c, cols):
    """Row-major flattening: O(1), and the reason iterating rows beats columns."""
    return r * cols + c

def linear_index_lookup(index, key):
    """Binary search a flat sorted index. O(log n) — see ./09-search-algorithms.md."""
    keys = [k for k, _ in index]
    pos = bisect.bisect_left(keys, key)
    if pos < len(index) and index[pos][0] == key:
        return index[pos][1]
    return None

B+ tree, fan-out 4 — internal nodes carry separator keys only

                        [ 10 | 20 ]                      <- root
                       /     |     \
              [4 | 7]    [13 | 16]    [24 | 27]          <- internal
             /   |   \    /   |   \    /   |   \
            v    v    v  v    v    v  v    v    v

leaf level, every record present, in key order, linked left to right:

 [1 2 3] <-> [4 5 6] <-> [7 8 9] <-> [10 11 12] <-> ... <-> [28 29 30] -> None

  WHERE k BETWEEN 5 AND 27:
    one root-to-leaf descent to find 5      (3 page reads)
    then follow leaf links until 27         (sequential reads, no re-descent)

def build_hash_index(pages, buckets=8):
    """Hash index: key -> (page, slot). O(1) equality lookup, no ordering at all."""
    index = [[] for _ in range(buckets)]
    for pno, page in enumerate(pages):
        for slot, (k, _) in enumerate(page):
            index[hash(k) % buckets].append((k, pno, slot))
    return index


def hash_lookup(pages, index, key):
    """One bucket read, then a short scan within it. Expected O(1)."""
    for k, pno, slot in index[hash(key) % len(index)]:
        if k == key:
            return pages[pno][slot][1]
    return None


hidx = build_hash_index(pages)
print(hash_lookup(pages, hidx, 30))        # 'row-30'
print(hash_lookup(pages, hidx, 31))        # None

ISAM layout

  master index   :        [ 100 | 400 | 700 ]
                          /       |        \
  cylinder index : [100|200|300] [400|...]  [700|...]
                     |
  data blocks    : [101..150][151..200]...        <- physically sorted, no free space
                        |
  overflow chain :  [ 155 ] -> [ 158 ] -> [ 156 ]  <- inserts land here, unsorted

INSERT into a table with k secondary indexes:
    1 heap page write
  + k index descents (log_f n page reads each, mostly cached)
  + k index leaf page writes
  + occasional page splits, each writing 2-3 pages and dirtying the parent
  + write-ahead log records for all of the above

composite index on (tenant_id, created_at, status), sorted lexicographically:

  (1, 2024-01-01, 'new')
  (1, 2024-01-01, 'paid')
  (1, 2024-01-02, 'new')
  (1, 2024-01-05, 'paid')
  (2, 2024-01-01, 'new')
  (2, 2024-01-03, 'shipped')

USABLE (contiguous range in the index):
  WHERE tenant_id = 1
  WHERE tenant_id = 1 AND created_at >= '2024-01-02'
  WHERE tenant_id = 1 AND created_at = '2024-01-01' AND status = 'paid'
  ORDER BY tenant_id, created_at                       (already in this order)

NOT USABLE as an ordered lookup:
  WHERE created_at >= '2024-01-02'    -- rows for that date are scattered across tenants
  WHERE status = 'paid'               -- third column alone: no contiguity at all

PARTIALLY usable:
  WHERE tenant_id = 1 AND status = 'paid'
    -> tenant_id narrows the index to a contiguous block;
       status is then just a filter applied while scanning that block

SELECT status FROM orders WHERE tenant_id = 1 AND created_at > '2024-01-01';

index on (tenant_id, created_at)          -> find matching entries in the index,
                                             then one random heap read per row

index on (tenant_id, created_at, status)  -> `status` is already in the index;
   (or ... INCLUDE (status))                 zero heap reads: an INDEX-ONLY SCAN