Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Database & ORMSenior27 phút đọc

Index bên trong: B-tree, B+tree, clustered, heap và chọn khoá chính

Ôn 22 thẻ
Trong bài này

Cụm bài Index chuyên sâu: 1. Index bên trong · 2. Các loại index ngoài B-tree

Bài này đi xuống bên dưới câu “thêm index thì nhanh”: B+tree lưu gì, InnoDB và PostgreSQL đặt dòng ở đâu, vì sao UUIDv4 làm khoá chính chậm. Đọc xong, bạn chọn được khoá chính, đọc đúng plan composite index và biết khi nào rebuild. Mọi con số đều chạy thật trên PostgreSQL 16 và MySQL 8.4.

Nên đọc trước Index, EXPLAIN, N+1 và phân trang (leftmost prefix, covering index, sargable). Phần thực hành hash index, LIKE, thứ tự cột composite và INCLUDE đã có ở lab index trên dataset hãng bay, ở đây không lặp lại.

1. Key khác index thế nào

Ý chính: key là ràng buộc (luật dữ liệu phải tuân), index là cấu trúc dữ liệu (để tìm nhanh). Database dùng index để thực thi PK và UNIQUE.

  • Key: primary key = không null và duy nhất; unique key = duy nhất; foreign key = giá trị phải tồn tại ở bảng cha.
  • Index: bản sao đã sắp xếp của vài cột kèm con trỏ về dòng, đổi dung lượng và chi phí ghi lấy tốc độ đọc.

Không có index thì mỗi insert phải quét cả bảng để kiểm tra trùng, nên PK và UNIQUE luôn kèm index. Foreign key thì InnoDB tự tạo index trên cột con, PostgreSQL không.

2. B-tree và B+tree

Ý chính: database dùng B+tree: node trong chỉ chứa khoá phân cách, dữ liệu chỉ ở lá, các lá nối thành danh sách. Nhờ vậy cây rất thấp và range scan chỉ là đi ngang theo lá.

  • B-tree: cây cân bằng nhiều nhánh, mọi lá cùng tầng, node có k con chứa k−1 khoá đã sắp xếp, tìm/thêm/xoá O(log n). Mọi node đều mang dữ liệu.
  • B+tree (InnoDB, PostgreSQL, SQL Server, Oracle): chỉ lá mang dữ liệu hoặc con trỏ tới dòng.
flowchart TB
  R["Node trong: 30 | 90"] --> A["Node trong: 8"]
  R --> B["Node trong: 40"]
  R --> C["Node trong: 99"]
  A --> L1["Lá: 1"]
  A --> L2["Lá: 8, 20"]
  B --> L3["Lá: 30"]
  B --> L4["Lá: 40, 44"]
  C --> L5["Lá: 90"]
  C --> L6["Lá: 99, 150"]
  L1 -.-> L2 -.-> L3 -.-> L4 -.-> L5 -.-> L6
B-tree B+tree
Dữ liệu Ở mọi node Chỉ ở lá
Tra một khoá Có thể dừng sớm Luôn xuống tới lá, chi phí đều
Range, ORDER BY Đi lên xuống trong cây Đi ngang theo lá
Fan-out node trong Nhỏ (node còn chở dữ liệu) Lớn (chỉ có khoá)

Fan-out là số con của một node. Một node là một page (khối đọc ghi của database: InnoDB 16 KB, PostgreSQL 8 KB). Các tầng trên gần như luôn nằm trong RAM, nên một lần tra thường chỉ tốn một lần đọc đĩa.

Làm toán chiều cao cây: InnoDB và PostgreSQL
  • InnoDB, PK BIGINT: entry node trong ≈ 8 byte khoá + 6 byte số page, nên ~1.170 con trỏ mỗi page. Dòng ~1 KB thì lá chứa ~15 dòng. Ba tầng: 1.170 × 1.170 × 15 ≈ 20 triệu dòng.
  • PostgreSQL, đo thật ở mục 5: index PK bigint 1 triệu dòng có 2.733 page lá (~366 entry mỗi lá) và tree_level = 2, tức gốc, một tầng trong và lá.

3. Clustered index và heap

Ý chính: InnoDB lưu cả dòng trong lá của cây PK (clustered index), secondary index trỏ về bằng PK. PostgreSQL lưu dòng trong heap, mọi index trỏ thẳng tới vị trí vật lý (TID).

InnoDB: bảng chính là clustered index. Bảng là một B+tree sắp theo PK, lá chứa toàn bộ dòng. Lá của secondary index chứa giá trị cột + giá trị PK, nên đọc qua secondary index là hai lần đi cây.

flowchart LR
  Q["WHERE email = ?"] --> S["Secondary index email: lá chứa email và PK"]
  S -->|"PK = 4791"| C["Clustered index theo PK: lá chứa cả dòng"]
  C --> R["Dòng đầy đủ"]

PostgreSQL: bảng là heap (dòng nằm theo thứ tự chèn, không sắp xếp). Mọi index, kể cả PK, có lá chứa TID (số page + vị trí trong page): tra một lần đi cây rồi nhảy thẳng vào heap. CLUSTER chỉ sắp lại bảng một lần, không duy trì.

Vì sao InnoDB lưu PK chứ không lưu địa chỉ? Vị trí vật lý của dòng đổi liên tục (page split, merge, rebuild); lưu PK thì dòng dời chỗ không phải sửa secondary index.

PostgreSQL trả giá ở phía ghi: do MVCC (giữ nhiều phiên bản dòng), mỗi UPDATE tạo phiên bản mới ở TID mới, nên mọi index phải thêm entry, kể cả index trên cột không đổi. Cứu cánh là HOT update (heap-only tuple): update không đụng cột có index và page còn chỗ thì bản mới nằm cùng page, không sửa index.

fillfactor là phần trăm page được lấp khi ghi, phần còn lại để dành cho update (PostgreSQL mặc định 100 cho bảng, 90 cho B-tree; bảng update nhiều nên hạ xuống 80–90). Page đầy thì không HOT được; đụng cột có index thì không bao giờ HOT.

Lab HOT update: fillfactor và cột có index

Bảng 100.000 dòng có index trên status, update 50.000 dòng:

Bảng Cột được update fillfactor Update HOT
h100 note (không index) 100 0 / 50.000
h80a note (không index) 80 12.506 / 50.000
h80b status (có index) 80 0 / 50.000

Chừa 20% thì được 25% HOT: update liên tiếp ăn hết chỗ trống; update rải rác có autovacuum dọn thì tỉ lệ cao hơn nhiều.

4. Unique index và NULL

Ý chính: theo chuẩn SQL, NULL không bằng NULL, nên cột UNIQUE thường cho phép nhiều NULL. Muốn chặn thì phải khai báo rõ.

Database Nhiều NULL trong cột UNIQUE
MySQL InnoDB Được (kiểm chứng: hai dòng email = NULL insert bình thường)
PostgreSQL Được, trừ khi khai báo NULLS NOT DISTINCT (15+)
SQL Server Chỉ một NULL; muốn nhiều thì filtered index WHERE col IS NOT NULL
CREATE UNIQUE INDEX acc_email ON acc (email);                     -- nhiều NULL được
CREATE UNIQUE INDEX acc_phone ON acc (phone) NULLS NOT DISTINCT;  -- chỉ một NULL
INSERT INTO acc VALUES (1, NULL, NULL), (2, NULL, '1');           -- OK
INSERT INTO acc VALUES (3, NULL, NULL);
-- ERROR: duplicate key value violates unique constraint "acc_phone"

Slide khuyên cột index nên NOT NULL vì NULL “chiếm chỗ”. Phần chỗ không đáng kể (NULL chỉ là một bit trong null bitmap); lý do thật là ngữ nghĩa: NOT IN với subquery có NULL trả về rỗng, unique cho nhiều NULL.

5. Chọn khoá chính: bigint, UUIDv4 hay UUIDv7

Ý chính: khoá tăng dần chèn vào cuối cây nên page luôn đầy; khoá ngẫu nhiên chèn vào giữa nên page bị tách đôi liên tục. UUIDv7 gần tăng dần nên gọn gần như bigint.

  • Khoá tăng dần luôn chèn vào lá phải nhất: page đầy thì mở page mới, page cũ giữ độ đầy.
  • Khoá ngẫu nhiên chèn vào giữa cây: page đầy bị tách đôi (page split), mỗi nửa còn ~50%, page rải rác khắp RAM và đĩa.

Kết quả lab, 1 triệu dòng mỗi bảng:

bigint UUIDv4 / ngẫu nhiên UUIDv7 / theo thời gian
PostgreSQL: kích thước PK 21 MB 38 MB 30 MB
PostgreSQL: WAL cho 200.000 insert 27 MB 60 MB 30 MB
InnoDB: clustered index 41 MB 80 MB 50 MB

Ở InnoDB, secondary index email cũng to theo PK (62 MB so với 48 MB) vì lá secondary chép PK.

Bảng đo page split trên PostgreSQL 16 và MySQL 8.4, bộ sinh UUIDv7 bằng Java 21

Lab PostgreSQL 16, 1 triệu dòng mỗi bảng. UUIDv7 tự viết bằng PL/pgSQL (48 bit mili giây + 12 bit phần lẻ mili giây + bit ngẫu nhiên, giống uuidv7() của PostgreSQL 18):

Khoá chính Kích thước PK Mật độ lá leaf_fragmentation WAL khi chèn thêm 200.000 dòng
bigint identity 21 MB 90% 0 27 MB
UUIDv4 (gen_random_uuid()) 38 MB 71% 50% 60 MB
UUIDv7 30 MB 90% 0 30 MB

Lab InnoDB trên MySQL 8.4, 1 triệu dòng, thêm secondary index trên email:

Khoá chính Clustered index Secondary email Thời gian insert
BIGINT AUTO_INCREMENT 41 MB 48 MB 2,7 s
BINARY(16) ngẫu nhiên (kiểu v4) 80 MB 62 MB 4,4 s
UUID_TO_BIN(UUID(), 1) (theo thời gian) 50 MB 62 MB 2,7 s

Thời gian insert UUIDv7 bên PostgreSQL bị hàm PL/pgSQL tự viết làm chậm nên không đưa vào bảng.

Bộ sinh UUIDv7 tối thiểu bằng Java 21, bộ đếm 12 bit giữ thứ tự trong cùng mili giây:

import java.security.SecureRandom;
import java.util.UUID;
import java.util.concurrent.locks.ReentrantLock;

public final class UuidV7 {
    private static final SecureRandom RANDOM = new SecureRandom();
    private static final ReentrantLock LOCK = new ReentrantLock();
    private static long lastMillis = -1;
    private static int counter;                       // 12 bit ở vùng rand_a

    public static UUID next() {
        long millis; int seq;
        LOCK.lock();
        try {
            millis = System.currentTimeMillis();
            if (millis <= lastMillis) {               // cùng mili giây hoặc đồng hồ lùi
                millis = lastMillis;
                if (++counter > 0xFFF) { millis = ++lastMillis; counter = 0; }
            } else {
                lastMillis = millis;
                counter = RANDOM.nextInt(0x400);      // bắt đầu ngẫu nhiên, chừa chỗ tăng
            }
            seq = counter;
        } finally {
            LOCK.unlock();
        }
        long msb = (millis << 16) | 0x7000L | seq;    // 48 bit thời gian | version 7 | 12 bit đếm
        long lsb = (RANDOM.nextLong() & 0x3FFFFFFFFFFFFFFFL) | 0x8000000000000000L; // variant
        return new UUID(msb, lsb);
    }
}

Chạy với JDK 21: 1 triệu ID trong ~160 ms, 64 bit đầu tăng ngặt (so sánh không dấu). ReentrantLock để không ghim virtual thread (giữ nó dính vào thread hệ điều hành). Production nên dùng thư viện đã kiểm chứng.

6. Composite index với điều kiện range

Ý chính: thiếu cột đầu thì thường không dùng được composite index, trừ skip scan. Range trên cột đầu làm cột sau chỉ còn định vị điểm bắt đầu, không thu hẹp khoảng quét, dù plan có ghi tên cột đó.

“Phải có cột đầu” không còn tuyệt đối. Slide kết luận index (country, province, name) không phục vụ câu chỉ lọc province. Nhưng MySQL 8.0.13+ và PostgreSQL 18 có skip scan: cột đầu ít giá trị (như country) thì database nhảy qua từng giá trị cột đầu và tìm cột thứ hai trong mỗi nhóm. Skip scan của MySQL đòi index phủ (covering) mọi cột cần đọc; PostgreSQL 16 chưa có.

Range trên cột đầu (câu đố trên slide). Với index (a, b): a > 1 AND b = 2, a >= 1 AND b = 2, a BETWEEN 2 AND 8 AND b = 2 dùng mấy cột? Slide đáp (a), (a, b), (a, b). Đo thật: a >= 97 AND b = 2 có key_len = 8 nhưng vẫn quét ~63.000 entry; chỉ a IN (97, 98, 99) AND b = 2 thu hẹp còn 30 entry. Xem khoảng quét trong EXPLAIN FORMAT=TREE.

Đo trên MySQL 8.4: skip scan, câu đố range và bẫy key_len

MySQL 8.4, 1 triệu dòng, index (a, b), a có 100 giá trị:

EXPLAIN ANALYZE SELECT a, b, id FROM t WHERE b = 2;
-> Covering index skip scan on t using idx_ab over b = 2
   (actual time=0.016..0.391 rows=1000 loops=1)

SELECT * ... WHERE b = 2 thì vẫn quét cả bảng. PostgreSQL 16: Parallel Seq Scan, 18 ms; phần PostgreSQL 18 không chạy được trong lab này.

Câu đố range: đổi hằng để range đủ hẹp (với a > 1 trên dữ liệu a từ 0 đến 99, range phủ 98% bảng nên optimizer quét cả bảng):

Điều kiện key_len Khoảng quét (EXPLAIN FORMAT=TREE) Ước tính entry quét
a > 97 AND b = 2 4 (97 < a) 37.722
a >= 97 AND b = 2 8 (97 <= a AND 2 <= b) 62.908
a BETWEEN 97 AND 99 AND b = 2 8 (97 <= a <= 99 AND b = 2) 38.702
a IN (97, 98, 99) AND b = 2 8 ba khoảng (a = 97 AND b = 2), … 30

Slide còn khuyên đặt cột cardinality cao (nhiều giá trị khác nhau) lên đầu vì “cây nhiều nhánh hơn”. Sai: chiều cao B+tree phụ thuộc số entry và độ dài khoá, không phụ thuộc thứ tự cột (quy tắc đúng ở Bước 5 của lab index). Đổi sang (name, province, country) còn làm hỏng câu WHERE country = 'US'.

7. Bảo trì index

Ý chính: index không mất cân bằng mà phình (bloat), nên đo rồi mới rebuild. Tạo index trên bảng đang chạy thì dùng cách online, coi chừng index INVALID và metadata lock.

7.1. B+tree không mất cân bằng, nó phình

Slide nói “B+tree có thể mất cân bằng theo thời gian nên phải rebuild”. B+tree luôn cân bằng nhờ cách split và merge. Thứ xấu đi là mật độ page (bloat: page còn nhiều chỗ trống không thu hồi) và phân mảnh.

Ví dụ: xoá 90% dòng rồi VACUUM, index vẫn 21 MB, mật độ lá 9%; REINDEX INDEX CONCURRENTLY đưa về 2,2 MB. Đo bằng pgstatindex(), rebuild khi mật độ thấp kéo dài (MySQL: OPTIMIZE TABLE), không theo lịch.

Lab bloat: xoá 90% rồi VACUUM và REINDEX, cách đo pgstatindex

PostgreSQL, index PK bigint 1 triệu dòng, xoá 90% rồi VACUUM:

Trạng thái tree_level Page lá Mật độ lá Kích thước
Mới tạo 2 2.733 90% 21 MB
Sau DELETE 90% + VACUUM 2 2.733 9% 21 MB
Sau REINDEX INDEX CONCURRENTLY 1 274 90% 2,2 MB

7.2. Tạo index trên bảng đang chạy

  • PostgreSQL: CREATE INDEX thường chặn mọi lệnh ghi suốt lúc build. Production dùng CREATE INDEX CONCURRENTLY: không chặn ghi, đổi lại quét bảng hai lần, không chạy trong transaction, chờ transaction đang mở.
  • MySQL 5.6+: ALTER TABLE t ADD INDEX idx (col), ALGORITHM=INPLACE, LOCK=NONE. Trước 5.6 dùng pt-online-schema-change (bảng bóng + trigger) hoặc gh-ost (đọc binlog). Các thuật toán ALTER và expand/contract ở bài Database cơ bản.

7.3. Index thừa, prefix index và khi nào không index

Không nên index: bảng nhỏ; cột ít giá trị phân bố đều (trừ khi tìm giá trị hiếm, dùng partial index); bảng chủ yếu ghi như log thô; cột không bao giờ xuất hiện trong WHERE, JOIN, ORDER BY, GROUP BY. Index thừa: đo rồi mới xoá.

Tìm index thừa, prefix index và index merge cho OR
  • Index thừa: tìm bằng pg_stat_user_indexes (idx_scan = 0) hoặc sys.schema_unused_indexes (MySQL 8). Trước khi xoá, kiểm tra thống kê đủ lâu, index không phục vụ unique/foreign key hay replica. MySQL 8 có invisible index để tắt thử.
  • Prefix index của MySQL (INDEX (email(12))): nhỏ hơn nhưng không covering được, không phục vụ ORDER BY cả cột, và UNIQUE trên prefix coi hai chuỗi chung 12 ký tự đầu là trùng. PostgreSQL không có prefix index; dùng expression index (left(email, 12)).

Bài tập

Bài 1: Kiểm chứng ba nhận định của bài

Đề (diễn đạt lại): chọn ba nhận định về index, với mỗi nhận định ghi phát biểu, SQL kiểm chứng, kết quả chạy thật và giải thích.

Lời giải Bài 1: covering index, skip scan, ép kiểu ngầm

Nhận định 1: đọc qua secondary index cần thêm bước lấy dòng, covering index bỏ được bước đó. PostgreSQL 16, bảng t(id, a, b, c) 1 triệu dòng, index (a, b):

EXPLAIN (ANALYZE, BUFFERS) SELECT c FROM t WHERE a = 5 AND b BETWEEN 1 AND 50;
-- Bitmap Heap Scan, rows=500, Heap Blocks: exact=275, Buffers: 279
EXPLAIN (ANALYZE, BUFFERS) SELECT a, b FROM t WHERE a = 5 AND b BETWEEN 1 AND 50;
-- Index Only Scan using idx_ab, Heap Fetches: 0, Buffers: 5
CREATE INDEX idx_ab_inc ON t (a, b) INCLUDE (c);
-- câu đầu chạy lại: Index Only Scan using idx_ab_inc, Buffers: 6

Cần cột c thì phải vào 275 page heap (500 dòng nằm rải rác); đủ cột trong index thì chỉ 5–6 page.

Nhận định 2: thiếu cột đầu thì không dùng được composite index, trừ skip scan. MySQL 8.4: SELECT a, b, id ... WHERE b = 2 chạy covering index skip scan 0,4 ms; SELECT * ... WHERE b = 2 là type: ALL trên 998.360 dòng vì skip scan đòi index phủ đủ cột. PostgreSQL 16: Seq Scan cho cả hai.

Nhận định 3: ép kiểu ngầm và hàm trên cột làm mất index. MySQL 8.4, bảng u 1 triệu dòng, code VARCHAR(20) có index, id INT là PK:

Truy vấn Plan Thời gian
WHERE id = '500' (cột số, hằng chuỗi) tra PK ~0,04 ms
WHERE code = '00000500' Index lookup ... idx_code ~0,006 ms
WHERE code = 500 (cột chuỗi, hằng số) Table scan ~114 ms
WHERE LENGTH(name) = 6 Table scan ~102 ms
WHERE id + 1 = 501 Table scan ~106 ms

So chuỗi với số thì MySQL đổi từng giá trị của cột sang số, nên index sắp theo chuỗi vô dụng; cột số so với hằng chuỗi thì chỉ đổi hằng một lần. code = 500 còn sai ngữ nghĩa: '500', '0500', '500abc' đều bằng số 500. Hàm và phép tính trên cột cũng vậy, vì index lưu giá trị gốc.

Bài 2: Chọn khoá chính cho bảng đơn hàng

Đề (của mình): service đơn hàng trên PostgreSQL, 5 triệu đơn mỗi tháng, app mobile tạo đơn khi offline rồi đồng bộ (ID sinh ở client), ID xuất hiện trên URL công khai.

Lời giải Bài 2: UUIDv7 làm PK
  • Loại bigint làm ID duy nhất: client không sinh trước được, lộ số lượng đơn.
  • Loại UUIDv4: bảng sẽ tới hàng trăm triệu dòng; lab cho index to hơn ~80%, WAL gấp đôi.
  • Chọn UUIDv7 làm PK: client sinh được, index gọn (30 MB, mật độ lá 90%), không đoán được ID kế tiếp. Chấp nhận lộ thời điểm tạo (đơn vốn có created_at). Lưu kiểu uuid.

Khi bảng lớn và cần dọn dữ liệu cũ, xem partition và xoá dữ liệu cũ an toàn.

Câu đố range trên composite index của slide đã được giải ở mục 6.

Ghi nhớ

  • Giải thích được vì sao database dùng B+tree, và vì sao cây chỉ 3 tầng.
  • Vẽ được đường đọc qua secondary index ở InnoDB và PostgreSQL, và nói được cái giá phía ghi của mỗi bên.
  • Biết vì sao UUIDv4 làm PK chậm, khi nào chọn bigint, UUIDv7 hay Snowflake.
  • Đọc được plan của (a, b) với range trên a: b có thật sự thu hẹp khoảng quét không.
  • Biết đo bloat trước khi rebuild, và hai bẫy khi tạo index online.

Câu hỏi phỏng vấn

Junior

Key khác index thế nào?

Key là ràng buộc dữ liệu (PK, unique, foreign key); index là cấu trúc dữ liệu để tìm nhanh.

Database dùng index để thực thi PK và UNIQUE. Với foreign key, InnoDB tự tạo index trên cột con, PostgreSQL thì không.

Vì sao database dùng B+tree thay vì cây nhị phân hay B-tree?

Vì B+tree rất thấp (fan-out hàng nghìn) và range scan chỉ là đi ngang theo lá.

Mỗi node là một page đĩa. Node trong của B+tree chỉ chứa khoá nên 20 triệu dòng chỉ cao 3 tầng; lá nối nhau nên range và ORDER BY là đi ngang. Cây nhị phân quá cao; B-tree chở dữ liệu ở node trong nên fan-out nhỏ hơn.

Unique index có cho phép nhiều NULL không?

MySQL và PostgreSQL: có, vì NULL không bằng NULL. SQL Server chỉ cho một NULL.

PostgreSQL 15+ có NULLS NOT DISTINCT để coi các NULL là trùng.

Mid

Clustered index là gì? InnoDB có cho chọn cột clustered khác khoá chính không?

Clustered index có lá chứa cả dòng và quyết định thứ tự vật lý, mỗi bảng một cái. InnoDB không cho chọn tuỳ ý.

InnoDB dùng PK; không có thì unique index đầu tiên toàn cột NOT NULL; không có nữa thì row id ẩn. SQL Server mới cho chọn cột khác PK. PostgreSQL là heap.

Vì sao secondary index của InnoDB lưu khoá chính mà không lưu địa chỉ dòng?

Vì vị trí vật lý của dòng đổi khi page split, merge, rebuild; lưu PK thì không phải sửa secondary index mỗi lần dòng dời chỗ.

Cái giá là đọc qua secondary phải tra tiếp clustered index, và PK to làm mọi secondary index to theo.

HOT update trong PostgreSQL là gì và làm sao tăng tỉ lệ HOT?

Update không đổi cột có index và page còn chỗ thì phiên bản mới nằm cùng page, không thêm entry vào index nào.

Tăng tỉ lệ: hạ fillfactor bảng, không index cột hay đổi, autovacuum đủ nhanh. Theo dõi n_tup_hot_upd trong pg_stat_user_tables.

Index (a, b), câu WHERE b = ? có dùng được index không?

Thường là không vì thiếu cột đầu; ngoại lệ là skip scan khi a ít giá trị.

Skip scan có ở MySQL 8.0.13+ và PostgreSQL 18; MySQL còn đòi index phủ đủ cột. Nếu WHERE b = ? là truy vấn chính thì tạo index bắt đầu bằng b, đừng dựa vào skip scan.

Senior

Vì sao UUIDv4 làm khoá chính chậm, và bạn chọn gì thay thế?

Khoá ngẫu nhiên chèn vào giữa cây, gây page split, index to và phân mảnh. Thay bằng bigint nếu database cấp ID, UUIDv7/ULID/Snowflake nếu sinh phân tán.

Khi index vượt RAM, mỗi insert thêm một lần đọc ngẫu nhiên. Đo 1 triệu dòng: clustered index InnoDB 80 MB so với 41 MB của bigint; PostgreSQL sinh WAL gấp đôi so với UUIDv7.

Mô hình lưu trữ của InnoDB và PostgreSQL ảnh hưởng thế nào đến thiết kế index?

InnoDB cần PK ngắn và tăng dần; PostgreSQL cần ít index trên bảng update nhiều.

  • InnoDB: secondary chứa PK, đọc tốn hai lần đi cây; update cột không index không đụng index.
  • PostgreSQL: index trỏ TID, đọc một lần đi cây, nhưng update không HOT thêm entry vào mọi index. Bảng update nhiều cần ít index, fillfactor thấp hơn, autovacuum tốt.
Có nên rebuild index định kỳ vì B+tree bị mất cân bằng?

Không. B+tree luôn cân bằng; thứ xấu đi là bloat sau xoá hoặc update hàng loạt.

Đo bằng pgstatindex, rebuild có mục tiêu bằng REINDEX CONCURRENTLY hoặc OPTIMIZE TABLE. Bloat lặp lại do xoá theo thời gian thì dùng partition.

Bạn thêm unique index lên bảng 200 triệu dòng đang chạy production như thế nào?

Dọn trùng trước, rồi tạo index online (CONCURRENTLY hoặc LOCK=NONE/gh-ost), kiểm tra kết quả, chạy giờ thấp điểm.

  • Dọn trùng lặp: GROUP BY ... HAVING count(*) > 1.
  • PostgreSQL: CREATE UNIQUE INDEX CONCURRENTLY, theo dõi pg_stat_progress_create_index, kiểm tra indisvalid, rồi ADD CONSTRAINT ... UNIQUE USING INDEX.
  • MySQL: ALGORITHM=INPLACE, LOCK=NONE với lock_wait_timeout nhỏ hoặc gh-ost; kiểm tra transaction dài trước.
  • Theo dõi replication lag.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
fan-out /ˈfæn aʊt/ số con của một node “Internal nodes hold only keys, so the fan-out is over a thousand.”
clustered index /ˈklʌstəd ˈɪndeks/ index mà lá chứa cả dòng “In InnoDB the table itself is the clustered index.”
heap /hiːp/ vùng lưu dòng không theo thứ tự “Postgres stores rows in a heap and indexes point to tuple IDs.”
page split /peɪdʒ splɪt/ tách page khi đầy “Random UUIDs cause page splits all over the tree.”
write amplification /raɪt ˌæmplɪfɪˈkeɪʃn/ một lần ghi kéo theo nhiều lần ghi “Every extra index adds write amplification.”
HOT update /hɒt ˈʌpdeɪt/ update chỉ ở heap, không sửa index “A lower fillfactor leaves room for HOT updates.”
bloat /bləʊt/ phình do chỗ trống không thu hồi “The tree wasn’t unbalanced, it was bloated.”
skip scan /skɪp skæn/ quét nhảy qua từng giá trị cột đầu “MySQL used a skip scan on the low-cardinality leading column.”
metadata lock /ˈmetədeɪtə lɒk/ khoá cấu trúc bảng (MySQL) “A long transaction held a metadata lock, so the online ALTER blocked every query.”

Ghi chép dựa trên khoá Advanced Backend (Ronin Engineer), viết lại theo cách hiểu của mình.