Bài 10: SQLite Internals — B-Tree & File Format

Mọi bài trước dừng ở mức SQL — SELECT, JOIN, EXPLAIN QUERY PLAN. Bài này đi xuống 1 tầng nữa: file .sqlite trên đĩa thực chất là gì, tính từng byte. Không lý thuyết suông — mọi con số trong bài đều đọc thẳng từ db.export() (bytes thật của database TechMart quen thuộc từ Bài 1) bằng 1 Page/Byte Explorer tự viết ngay trong sân chơi bên dưới.

1. Header 100 Byte Đầu File

100 byte đầu tiên của mọi file .sqlite là 1 header cố định, cấu trúc giống hệt nhau bất kể dữ liệu bên trong là gì. Đọc thật từ file TechMart (12 khách hàng, 14 sản phẩm, 28 đơn hàng, 34 dòng chi tiết đơn — 5 trang, 20.480 byte):

Đây chỉ là 6/23 trường thật sự tồn tại — bấm "Phân tích trang" ở trang 1 trong sân chơi bên dưới để xem đầy đủ. Mọi database SQLite trên thế giới, dù nặng vài KB hay vài TB, đều bắt đầu bằng đúng 100 byte theo cấu trúc này — đây là lý do bất kỳ công cụ nào (kể cả 1 trình phân tích tự viết bằng JavaScript như trong bài) đều đọc được file .sqlite mà không cần chính SQLite.

2. Cấu Trúc Trang B-Tree: Interior & Leaf

Ngay sau 100 byte header (với trang 1) hoặc ngay từ byte đầu tiên (mọi trang khác) là b-tree page header — 8 byte cho trang lá (leaf), 12 byte cho trang nội (interior, có thêm 4 byte con trỏ phải cùng). Với dataset nhỏ như TechMart (5 trang), mọi bảng chỉ cần 1 trang lá duy nhất — không có trang nội nào cả. Để thấy trang nội thật, sân chơi tự sinh 1 bảng demo_orders 2.000 dòng (kỹ thuật CTE đệ quy quen thuộc từ Bài 8, 9):

-- TechMart chiếm sẵn Trang 1-5. Sau khi tạo demo_orders (2.000 dòng, bước 3️⃣),
-- bảng này chiếm thêm 20 trang (Trang 6-25):
-- Trang 6 (rootpage của demo_orders) = 0x05 Interior table b-tree, 18 cell
-- Con trỏ phải cùng (right-most pointer) → Trang 25

-- 3 cell đầu tiên (đã giải mã thật):
--   khoá ≤ 108  → trang con trái = Trang 7
--   khoá ≤ 214  → trang con trái = Trang 8
--   khoá ≤ 319  → trang con trái = Trang 9

Đọc đúng theo thứ tự: rowid 1-108 nằm ở Trang 7, rowid 109-214 nằm ở Trang 8, rowid 215-319 nằm ở Trang 9, ... và mọi rowid lớn hơn khoá cuối cùng đi theo con trỏ phải cùng (Trang 25). Số trang cụ thể sẽ khác nếu bạn bấm các nút không đúng thứ tự 1️⃣→5️⃣b — tự kiểm tra lại bằng Page Explorer bên dưới. Đây chính là cơ chế đứng sau SEARCH ... USING INTEGER PRIMARY KEY đã thấy ở Bài 8, 9: tra 1 rowid cụ thể không cần dò tuần tự 2.000 dòng — chỉ cần 1-2 bước rẽ nhánh qua trang nội để nhảy thẳng tới đúng trang lá chứa nó, giống hệt tra mục lục sách nhiều cấp.

3. Record Format & Varint: Giải Mã 1 Dòng Dữ Liệu Thật

Trước khi đọc được 1 dòng dữ liệu, cần hiểu varint — cách SQLite mã hoá số nguyên bằng số byte thay đổi (1-9 byte) thay vì luôn cố định 4/8 byte: mỗi byte dùng 7 bit chứa dữ liệu, bit cao nhất (bit thứ 8) báo hiệu "còn byte tiếp theo hay không". Số càng nhỏ (rowid, độ dài chuỗi ngắn...) càng tốn ít byte — tiết kiệm không gian đáng kể khi số đó lặp lại trong hàng triệu bản ghi. Giải mã thật record đầu tiên của bảng customers (rowid = 1, Nguyễn Minh Anh) từ Trang 2 của TechMart:

Payload dài 65 byte, rowid = 1 (1 byte varint)
Header record dài 7 byte, gồm 6 serial type: [0, 47, 61, 27, 33, 9]

Serial type 0   → NULL           → customer_id (KHÔNG lưu — xem callout dưới)
Serial type 47  → TEXT dài 17    → "Nguyễn Minh Anh"
Serial type 61  → TEXT dài 24    → "[email protected]"
Serial type 27  → TEXT dài 7     → "Vietnam"
Serial type 33  → TEXT dài 10    → "2025-11-02"
Serial type 9   → hằng số 1      → is_active (0 byte lưu trữ!)

Công thức serial_type cho TEXT: 13 + 2×độ_dài — vd chuỗi "Vietnam" dài 7 ký tự → 13 + 2×7 = 27, khớp chính xác giá trị đọc được. Với BLOB, công thức tương tự nhưng dùng số chẵn: 12 + 2×độ_dài.

4. Overflow Page & Freelist

Overflow page xử lý giá trị quá lớn để nằm gọn trong 1 trang. Sân chơi tạo 1 bảng demo_overflow rồi chèn 1 chuỗi TEXT dài 6.000 ký tự (lớn hơn hẳn trang 4096 byte) — chèn thật, đọc thật kết quả:

Payload tổng = 6.004 byte — vượt xa 1 trang (4096 byte)
→ Chỉ ~1.912 byte đầu lưu cục bộ trên rootpage của demo_overflow (Trang 26, sau khi
  TechMart + demo_orders đã chiếm Trang 1-25 — số trang cụ thể phụ thuộc bạn đã chạy
  những bước nào trước đó, tự kiểm tra lại bằng Page Explorer)
→ 4 byte cuối cùng của phần cục bộ = con trỏ trang overflow: Trang 27
→ Trang 27 bắt đầu bằng 4 byte "con trỏ overflow TIẾP THEO": 0 (= đây là trang overflow CUỐI, không còn trang nào nữa)
→ Ngay sau 4 byte đó là dữ liệu thô tiếp theo của chuỗi — trang overflow KHÔNG có b-tree
  header nào cả, chỉ có [4 byte con trỏ][dữ liệu thô...]

Nếu giá trị dài hơn nữa (vượt cả 1 trang overflow), trang overflow đầu sẽ trỏ tiếp sang trang overflow thứ 2 — tạo thành 1 danh sách liên kết đơn (linked list) các trang, đọc tuần tự cho tới khi gặp con trỏ 0. Đây là lý do truy vấn lọc theo 1 cột TEXT/BLOB rất dài luôn chậm hơn cột ngắn — engine phải nhảy qua nhiều trang overflow rời rạc trên đĩa thay vì đọc liền mạch trong 1 trang.

Freelist quản lý các trang đã giải phóng (sau DELETE hàng loạt hoặc DROP TABLE) để tái sử dụng cho lần ghi sau, tránh phải phình to file liên tục. Sân chơi xoá hẳn bảng demo_orders (20 trang: 1 root + 19 lá) rồi đọc thật:

DROP TABLE demo_orders; -- giải phóng toàn bộ 20 trang, kể cả rootpage

PRAGMA freelist_count;  -- → 20  (20 trang giờ đã "free", chờ tái sử dụng)
PRAGMA page_count;      -- → 27  (KHÔNG giảm — file KHÔNG tự co lại)

-- Header: trang freelist-trunk đầu tiên = Trang 7, tổng số trang free = 20
-- Trang 7 (trunk): 4 byte đầu = con trỏ trunk tiếp theo (0 = trunk cuối),
--                  4 byte kế = số con trỏ lá (19), theo sau là 19 số hiệu trang free: [8, 9, 10, 11, 12, ...]

Điểm quan trọng hay bị hiểu nhầm: DROP TABLE/DELETE không làm file .sqlite nhỏ lại ngay lập tức — các trang cũ chỉ được đánh dấu "free" trong danh sách liên kết freelist-trunk/leaf, sẵn sàng tái sử dụng cho lần INSERT/CREATE TABLE tiếp theo. Muốn thật sự thu nhỏ file trên đĩa, cần chạy VACUUM — lệnh này viết lại toàn bộ database vào 1 file mới, bỏ hết các trang free, rồi thay thế file cũ.

Sân Chơi Tương Tác: SQL Workbench + Page/Byte Explorer

Bấm lần lượt các nút 1️⃣ → 5️⃣b để tái tạo đúng các số liệu ở trên, rồi dùng ô "Phân tích trang" để tự soi bytes thật của bất kỳ trang nào (thử trang 1, 2, và các trang mới sinh ra sau mỗi bước).