B-tree internals — page split, fill factor và height

11:20B+ Tree: Database tìm 1 dòng trong 1 TRIỆU chỉ bằng 4 lần đọc — đo thật từng trang11 phút nắm ý chính · bài viết dưới đây là bản đầy đủ ~13 phút

TL;DR: B-tree của PostgreSQL không phải cây nhị phân: mỗi page 8 KB chứa khoảng 400 entry, nên cây 1 tỷ row chỉ cao 4 cấp và một lookup tốn 4 lần đọc page. Insert khi leaf đầy gây page split: cấp page mới, chuyển nửa entry sang, đẩy key giữa lên parent. Key tuần tự (BIGSERIAL, UUID v7) luôn rơi vào leaf cuối nên split hiếm, khoảng 1 lần ghi mỗi insert; key ngẫu nhiên (UUID v4) rơi khắp cây nên split liên tục, 2–3 lần ghi mỗi insert và index phình 2–3 lần. Fill factor 90 mặc định chừa 10% mỗi leaf cho insert sau; DELETE không thu hồi chỗ ngay vì MVCC, VACUUM mới làm.

B-tree là index mặc định ở mọi database từ PostgreSQL đến MySQL đến SQLite. Tên "B-tree" hay bị nhầm với binary tree (2 nhánh, height log₂N), nhưng thực tế khác hẳn: B-tree multi-way balanced, mỗi node chứa hàng trăm key, và chính con số đó quyết định mọi thứ về hiệu năng. Bài này mở B-tree ra xem từng lớp: page format, page split, fill factor, height, rồi đo write amplification khi insert UUID v4 ngẫu nhiên, lý do bài surrogate key khuyên UUID v7 thay UUID v4 cho primary key.

1. Analogy — mục lục sách nhiều tầng

Một cuốn sách kỹ thuật 10 triệu trang cần mục lục nhiều tầng mới tra nhanh được: mục lục cuối sách có 100 nghìn entry, quá dài để lật, nên người ta làm "mục lục của mục lục", chưa đủ thì thêm một tầng nữa. Mỗi trang mục lục chứa khoảng 400 entry. B-tree hoạt động y hệt: mỗi page là một trang mục lục, leaf page trỏ thẳng tới data row, internal page trỏ tới page con, và cây tự cân bằng để mọi nhánh sâu bằng nhau.

2. Vì sao B-tree 1 tỷ row chỉ cao 4 cấp?

Binary search tree có branching factor 2, height log₂N: 1 triệu row là 20 cấp, 1 tỷ row là 30 cấp, mỗi cấp một lần đọc page. B-tree PostgreSQL có branching factor khoảng 400:

Con số 400 từ đâu ra? Mỗi entry trên leaf gồm một line pointer 4 byte, header IndexTuple 8 byte (trong đó 6 byte là CTID, địa chỉ vật lý (page, offset) của row trong heap) và bản thân key. Với key BIGINT 8 byte: 4 + 8 + 8 = 20 byte, 8192 / 20 ≈ 400. Key TEXT dài hơn thì ít entry hơn, height tăng.

Từ đó height = ceil(log₄₀₀(N)):

Mỗi page read tốn ~1 μs từ buffer cache hoặc ~100 μs từ SSD, nên 4 cấp là 4–400 μs mỗi lookup: sub-millisecond với dataset khổng lồ. Height chỉ tăng thêm 1 khi root bị split, chuyện xảy ra vài lần trong cả đời một bảng.

3. Page format và pageinspect

Mỗi page 8 KB có header 24 byte (LSN cho WAL, checksum, con trỏ sang page trái/phải, cờ leaf/internal), dãy line pointer lớn dần từ đầu page, và các item lớn dần từ cuối page về giữa; phần giữa là free space. Hai loại page: leaf trỏ heap row qua CTID và nối nhau thành linked list để range scan không phải leo lên internal; internal chỉ trỏ page con.

Extension pageinspect cho xem trực tiếp:

CREATE EXTENSION IF NOT EXISTS pageinspect;

-- Meta page: root, height (level)
SELECT root, level FROM bt_metap('tasks_pkey');
-- root | level
--    3 |     2        (level 2 = 3 cap: root, internal, leaf)

-- Items trong leaf page so 1
SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('tasks_pkey', 1) LIMIT 3;
-- itemoffset | ctid  | itemlen | data
--          1 | (0,1) |      16 | 01 00 ...
--          2 | (0,2) |      16 | 02 00 ...

Thử ngẫmbt_metap trả về level=2 cho một index 50 triệu row. Nếu key là TEXT dài thay vì BIGINT, con số level này còn giữ nguyên không?

4. Vì sao insert UUID v4 chậm hơn BIGSERIAL 2–3 lần?

Insert vào B-tree đi từ root xuống đúng leaf theo key. Leaf còn chỗ thì ghi một page là xong. Leaf đầy thì page split: cấp page mới, chuyển 50% entry sang, nối lại linked list, đẩy key giữa lên parent; parent đầy thì split tiếp lên trên, tới root thì height tăng 1.

Khác biệt nằm ở chỗ key mới rơi vào đâu. BIGSERIAL luôn lớn hơn mọi key hiện có nên chỉ chạm leaf cuối; leaf đó đầy thì split một lần rồi page mới rỗng lại nhận tiếp, amortized ~1 write/insert. UUID v4 rơi ngẫu nhiên khắp cây, xác suất trúng leaf đã lấp 90% cao, split liên tục, trung bình 2–3 write/insert.

Trước khi chạy đoạn dưới: bạn đoán insert 1 triệu row UUID v4 chậm hơn BIGSERIAL bao nhiêu lần, và index lớn hơn bao nhiêu lần? Ghi hai con số ra rồi mới đọc kết quả.

CREATE TABLE bench_serial (id BIGSERIAL PRIMARY KEY, payload TEXT);
CREATE TABLE bench_uuid   (id UUID PRIMARY KEY DEFAULT gen_random_uuid(), payload TEXT);

\timing on
INSERT INTO bench_serial(payload) SELECT repeat('x', 100) FROM generate_series(1, 1000000);
-- ~5 giay
INSERT INTO bench_uuid(payload)   SELECT repeat('x', 100) FROM generate_series(1, 1000000);
-- ~12 giay (2.4x cham hon)

SELECT pg_size_pretty(pg_relation_size('bench_serial_pkey'));  -- ~22 MB
SELECT pg_size_pretty(pg_relation_size('bench_uuid_pkey'));    -- ~50 MB (2.3x)

Chênh lệch thời gian đến từ số page phải ghi; chênh lệch size đến từ những leaf nửa rỗng sau split mà insert ngẫu nhiên không bao giờ lấp lại được.

5. Fill factor — chừa chỗ cho insert tương lai

Fill factor là mức tối đa một leaf được lấp trước khi PG mở page mới. Mặc định B-tree: 90, tức mỗi leaf chừa 10% cho insert rơi vào giữa sau này.

-- Mac dinh fillfactor=90
CREATE INDEX idx_tasks_due ON tasks(due_at);

-- Append-only / read-only: fillfactor=100, tiet kiem storage
CREATE INDEX idx_archive_due ON archive_tasks(due_at) WITH (fillfactor=100);

-- Bang UPDATE tai cho nhieu: fillfactor=80
CREATE INDEX idx_tasks_status ON tasks(status) WITH (fillfactor=80);

Fill factor thấp có ích nhất cho HOT update (Heap-Only Tuple): PG update row mà không đụng index nếu cột được index không đổi và heap page còn chỗ; cơ chế đó được mổ ở MVCC internals.

Thử ngẫmidx_tasks_status đặt fillfactor=80 để hưởng HOT update, nhưng bảng này thực ra chỉ INSERT chứ hiếm khi UPDATE tại chỗ. 20% free space đó đang mua được gì?

6. Bloat — DELETE không trả chỗ ngay

Trước khi xem: bạn vừa DELETE nửa số row của bench_serial. Bạn đoán pg_relation_size của index thay đổi thế nào ngay sau lệnh DELETE?

DELETE FROM bench_serial WHERE id % 2 = 0;
SELECT pg_size_pretty(pg_relation_size('bench_serial_pkey'));  -- van ~22 MB

VACUUM bench_serial;
SELECT pg_size_pretty(pg_relation_size('bench_serial_pkey'));  -- ~11 MB

Entry bị DELETE chỉ được đánh dấu dead, vẫn chiếm chỗ trên leaf. Lý do là MVCC: một transaction đang chạy có thể còn cần nhìn thấy row đó theo snapshot của nó, nên PG chỉ thu hồi khi mọi transaction cần snapshot cũ đã kết thúc, và VACUUM là thứ xác định thời điểm an toàn (VACUUM và dead tuple). Bloat tích luỹ khi autovacuum không đuổi kịp write load: index lớn hơn cần thiết, chiếm buffer cache, range scan chạm nhiều page hơn.

-- Do ty le lap day leaf (can CREATE EXTENSION pgstattuple)
SELECT avg_leaf_density FROM pgstatindex('tasks_pkey');
-- duoi 60-70% -> rebuild khong lock bang (PG 12+)
REINDEX INDEX CONCURRENTLY tasks_pkey;

Thử ngẫmDELETE 1 triệu row xong, autovacuum chưa kịp chạy. Nếu ngay lúc đó có một transaction dài đang mở, VACUUM có thu hồi được các entry đó không?

7. Pitfall — UUID v4 làm primary key trong bảng write-heavy

-- ANTI-PATTERN: UUID v4 PK trong bang write-heavy
CREATE TABLE events (
  id UUID PRIMARY KEY DEFAULT gen_random_uuid(),  -- v4 random
  event_type TEXT NOT NULL,
  payload    JSONB
);
-- Sau 100 trieu INSERT: index ~2.5x lon hon serial PK,
-- insert throughput rot 50-65%, dead entry rai khap tree nen VACUUM gom kho.

-- Fix 1: UUID v7 (co timestamp prefix, tuan tu) -- PG 18 native, PG 13-17 dung extension pg_uuidv7
CREATE TABLE events (id UUID PRIMARY KEY DEFAULT uuidv7(), event_type TEXT NOT NULL, payload JSONB);

-- Fix 2: BIGSERIAL PK + UUID public_id (dual key)
CREATE TABLE events (
  id        BIGSERIAL PRIMARY KEY,
  public_id UUID UNIQUE NOT NULL DEFAULT gen_random_uuid(),
  event_type TEXT NOT NULL,
  payload    JSONB
);

Dual key được cân nhắc kỹ hơn ở Surrogate vs natural key: B-tree tuần tự nhờ BIGSERIAL, URL không đoán được nhờ public_id, đổi lại index public_id vẫn chịu split ngẫu nhiên.

8. Deep Dive — B-tree implementation

9. Liên hệ các bài khác

• Composite index ordering — bài kế: cùng B-tree này nhưng key là bộ nhiều cột, thứ tự cột quyết định query nào navigate được.
• MVCC internals — vì sao DELETE chỉ đánh dấu dead và HOT update né được index; đọc để hiểu fill factor 80 mua gì.
• VACUUM và dead tuple — đo bloat bằng pgstattuple, khi nào REINDEX; tiếp nối mục 6.
• B-tree vs LSM tree — vì sao Postgres chọn B-tree còn Cassandra/RocksDB chọn LSM; bài này là góc PG-specific của bài đó.
• Tuần tự vs ngẫu nhiên — nền tảng I/O giải thích vì sao "rơi vào leaf cuối" rẻ hơn "rơi khắp cây" ngay cả trên SSD.

10. Tóm tắt

• Muốn biết index cao mấy cấp: SELECT level FROM bt_metap('<index>'); level 3 với vài trăm triệu row là bình thường, level 8 là dấu hiệu key quá dài hoặc bloat.
• Chọn PK cho bảng write-heavy: BIGSERIAL hoặc UUID v7; UUID v4 chỉ khi bắt buộc và chấp nhận index phình 2–3 lần.
• Đặt fill factor theo pattern ghi: 100 cho append-only, 90 mặc định, 80 chỉ khi UPDATE tại chỗ nhiều và muốn HOT.
• Index không nhỏ đi sau DELETE là bình thường; avg_leaf_density dưới 60–70% mới cần REINDEX INDEX CONCURRENTLY.
• Benchmark trong bài: 1 triệu insert, 5 s vs 12 s, 22 MB vs 50 MB. Lặp lại trên máy bạn trước khi tin.

Bài tiếp theo xếp nhiều cột vào cùng một B-tree và trả lời vì sao index (a, b, c) không giúp WHERE b = x.

11. Tự kiểm tra

Bài tiếp theo: Composite index ordering — leftmost prefix rule