B-tree & B+tree — Disk fanout, vì sao DB không dùng AVL/RB

Lesson 06 đã dạy Red-Black tree với height 2 * log₂(n) — đẹp cho RAM. Với 1 tỷ record, cây RB có height tối đa 60: 60 bước so sánh, hoàn toàn chấp nhận được trong bộ nhớ chính.

Nhưng MySQL InnoDB và Postgres không dùng RB tree cho index. Lý do: disk seek. Một lần đọc từ HDD mất khoảng 10ms — gấp 10 triệu lần so với L1 cache access. Nếu mỗi node của RB tree nằm trên một disk page riêng, 60 node = 60 disk seek = 600ms chỉ để đọc một record. Với 1000 query/giây, database đã bão hoà từ trước khi bắt đầu.

Giải pháp: thay vì cây cao với node nhỏ, dùng cây thấp với node rất lớn — mỗi node chứa hàng trăm key, height giảm xuống 3–4. Đó là B-tree (Bayer và McCreight, 1970) và biến thể phổ biến hơn của nó: B+tree.

Bài này giải thích B-tree fanout, B+tree leaf chain, search/insert mechanism, và vì sao MySQL InnoDB chọn B+tree thay vì bất kỳ cấu trúc nào khác.

1. Analogy — Tủ tài liệu nhiều ngăn

Hình dung bạn cần tìm hồ sơ nhân viên trong một kho lưu trữ vật lý. Có hai kiểu tủ:

Kiểu RB tree: Tủ với mỗi ngăn chứa đúng 2 ngăn con. Để tìm một hồ sơ, bạn phải mở ngăn này, đóng lại, bước sang ngăn khác, mở ra, đóng lại — lặp đi lặp lại 60 lần. Mỗi lần mở tủ tốn thời gian di chuyển vật lý.

Kiểu B-tree: Tủ với mỗi ngăn chứa 100 folder mục lục. Mở một ngăn, đọc nhanh 100 nhãn trong bộ nhớ (không cần di chuyển), chọn folder đúng, đi thẳng đến ngăn tiếp theo. Chỉ 3–4 lần mở tủ thay vì 60.

2. Disk vs RAM — con số thực

Trước khi đi vào cấu trúc B-tree, hiểu tại sao disk seek đắt đến vậy:

Latency thực tế (xấp xỉ):
  L1 cache:   1 ns
  L2 cache:   4 ns
  RAM:      100 ns
  SSD:  100,000 ns  (0.1 ms)
  HDD: 10,000,000 ns  (10 ms)

So sanh:
  1 HDD seek = 100,000 RAM access
  1 HDD seek = 10,000,000 L1 cache access
  1 SSD seek = 1,000 RAM access

Hệ quả trực tiếp: Nếu cần truy cập 60 node riêng lẻ trên HDD, tổng thời gian là khoảng 600ms — dù mỗi node nhỏ đến đâu. Ngược lại, nếu có thể đọc 1 node lớn chứa 500 key trong một seek, bạn chỉ cần 3–4 seek, tổng 30–40ms. Chênh lệch 15–20x chỉ từ thay đổi cấu trúc dữ liệu.

Implication cho thiết kế: Khi dữ liệu trên disk, mục tiêu là giảm số node phải visit (số disk seek), không phải giảm số phép so sánh. So sánh 500 key trong RAM sau một disk read là rẻ hơn nhiều so với một disk seek bổ sung.

Cross-link: Module 1 lesson 04 giải thích Big-O và tại sao constant factor quan trọng trong môi trường thực tế.

3. B-tree — định nghĩa và fanout

B-tree bậc m (order m) là cây cân bằng nhiều nhánh (multi-way balanced tree) với các đặc điểm:

• Mỗi node (trừ root) chứa ít nhất ⌈m/2⌉ key và tối đa m - 1 key.
• Một node với k key có đúng k + 1 children.
• Tất cả leaf nodes cùng depth (cây height-balanced).
• Key trong mỗi node được sắp xếp tăng dần.

Fanout là số children mỗi node có thể có — đây là số quan trọng nhất. Với order m = 500 (fanout 500), height của B-tree chứa 1 tỷ record:

n = 1,000,000,000 = 10^9

height = log_500(10^9) = log(10^9) / log(500) = 9 / 2.699 ≈ 3.33

=> Height 4 is enough for 500^4 = 62.5 billion records.

Disk seeks per query: 4
Total time (HDD): 4 * 10ms = 40ms
Total time (SSD): 4 * 0.1ms = 0.4ms

So sánh với RB tree trên disk: 60 seeks × 10ms = 600ms. B-tree với fanout 500: 4 seeks × 10ms = 40ms. 15x faster.

Ví dụ B-tree order 4 (fanout = 4, đơn giản để vẽ):

                    [30 | 70]
                   /    |    \
          [10|20]    [40|50|60]    [80|90]
         / | | \    / | | | \    / | | \
        1 15 25 28 35 45 55 65  75 85 95 99

Trong node [30 | 70]: key 30 và 70 chia thành 3 vùng — children trái chứa key nhỏ hơn 30, giữa chứa key từ 30 đến 70, phải chứa key lớn hơn 70. Đây là multi-way generalization của BST property.

4. B-tree vs B+tree — khác biệt quan trọng

B+tree là variant được dùng phổ biến hơn trong database. Khác biệt cốt lõi:

Tại sao B+tree fanout cao hơn? Internal node của B+tree chỉ chứa key và pointer, không chứa value (row data). Disk page thường là 4KB hay 16KB. Không có value, internal node nhét được nhiều key hơn → fanout lớn hơn → height thấp hơn → ít disk seek hơn.

B-tree internal node (16KB page, key 8 bytes, value 100 bytes, pointer 8 bytes):
  (8 + 100 + 8) * m + 8 <= 16384
  => m <= 141 (fanout ~141)

B+tree internal node (16KB page, key 8 bytes, pointer 8 bytes):
  (8 + 8) * m + 8 <= 16384
  => m <= 1023 (fanout ~1023)

Height difference (10^9 records):
  B-tree:  log_141(10^9) ≈ 3.97 => 4 levels
  B+tree:  log_1023(10^9) ≈ 3.0  => 3 levels

5. B+tree mechanics — cách hoạt động

5.1 Cấu trúc internal node và leaf node

B+tree internal node:
  [ ptr0 | key1 | ptr1 | key2 | ptr2 | ... | key_m | ptr_m ]
  - key1..key_m: navigation keys (chi de tim duong, khong phai data that)
  - ptr0..ptr_m: pointer den node con

B+tree leaf node:
  [ key1 | val1 | key2 | val2 | ... | key_k | val_k | next_leaf_ptr ]
  - key1..key_k: actual keys
  - val1..val_k: actual values (row data hoac row pointer)
  - next_leaf_ptr: pointer den leaf ke tiep (leaf chain)

Tất cả data nằm ở leaf. Internal node chỉ là "bản đồ" để điều hướng xuống đúng leaf.

5.2 Point query: WHERE id = 350

Root: [100 | 300 | 600]
       /    |     |    \
      ...  ...  [300|350|400|500]...  ...
                       |
                   leaf: (350, row_data)

Steps:
  1. Read root: 350 > 300 and 350 < 600 -> go to child[2]
  2. Read internal node [300|350|400|500]: 350 >= 300 -> find 350 -> leaf pointer
  3. Read leaf: found (350, row_data)
  Total: 3 disk reads

5.3 Range query: WHERE id BETWEEN 100 AND 500

Đây là lúc leaf chain tỏa sáng:

Steps:
  1. Walk down tree -> find leaf containing 100  (3 disk reads)
  2. Read row data for id=100
  3. Follow next_leaf_ptr -> next leaf (1 disk read, sequential)
  4. Read rows 150, 200, 250...
  5. Follow next_leaf_ptr -> next leaf (1 disk read, sequential)
  6. Continue until id > 500. Stop.

Sequential read trên leaf chain là nhanh nhất có thể về mặt I/O: OS/disk prefetch có thể đọc trước các page liên tiếp nhau. Ngược lại B-tree không có leaf chain — range query phải backtrack lên internal node, đi xuống lại nhánh khác — nhiều disk seek ngẫu nhiên hơn.

6. Insert vào B+tree — intuition

6.1 Case đơn giản: leaf còn slot

Current leaf: [100 | 200 | 300 | _]   (order 4, can hold 3 keys, 1 slot free)
Insert 250:
Result leaf:  [100 | 200 | 250 | 300]  (sorted insert, done)

6.2 Case leaf đầy: split

Current leaf: [100 | 200 | 300 | 400]  (full -- order 4, max 3 keys exceeded)
Insert 350:
  1. Split leaf into two:
     left:  [100 | 200 | 300]
     right: [350 | 400]
  2. Push median key (300) UP to parent as separator key.
  3. Update leaf chain: left.next -> right.

Before split:
  parent: [... | 500 | ...]
  leaf:   [100|200|300|400]

After split:
  parent: [... | 300 | 500 | ...]  <- 300 inserted as separator
           /          |          \
  leaf: [100|200|300]  [350|400]  [500+...]
         |
     next_ptr --->  [350|400]

6.3 Recursive split lên parent

Nếu parent cũng đầy sau khi nhận key mới từ split, parent split tương tự: chia đôi, đẩy median lên grandparent. Cây phát triển từ root: root chỉ split khi nó đầy → tạo root mới → height tăng 1.

ASCII split sequence (simplified):

Step 0 - root full:
  Root: [10 | 30 | 50 | 70]  (full)

Step 1 - insert 40, leaf splits, pushes 40 to root:
  Root would become: [10 | 30 | 40 | 50 | 70]  (overflow!)

Step 2 - root splits:
  New root:  [40]
             /  \
           [10|30]  [50|70]

Tần suất split: Mỗi split xảy ra trung bình sau khoảng m/2 insert (m là order). Với m = 500, trung bình 250 insert mới có 1 split — overhead nhỏ.

7. Pitfall tổng hợp

Pitfall 1 — Nhầm B-tree với binary tree

Tên "B-tree" không phải viết tắt của "Binary tree". B-tree là multi-way tree (mỗi node có tới hàng trăm children). "B" có thể là viết tắt của "Balanced", "Bayer" (tên tác giả), hoặc "Boeing" — ngay cả tác giả gốc Bayer và McCreight không giải thích rõ. Nhưng chắc chắn không phải "Binary".

Binary tree:  moi node co toi da 2 children  -> height O(log_2 n) = ~30 cho 10^9
B-tree:       moi node co toi da m children  -> height O(log_m n) = ~4  cho 10^9

Khong lien quan nhau ngoai viec deu la tree.

Pitfall 2 — Index column có cardinality thấp

Index B+tree cực kỳ inefficient khi column có cardinality thấp (ít unique value):

-- BAD: "status" column chi co 3 gia tri: 'pending', 'active', 'closed'
CREATE INDEX idx_orders_status ON orders(status);

-- Query tra ve 1/3 tong so rows -> B+tree lookup + fetch 3 trieu rows
-- TABLE SCAN thong thuong nhanh hon vi tranh duoc random I/O tren row data
SELECT * FROM orders WHERE status = 'pending';  -- 3M rows out of 9M

Rule of thumb: nếu query trả về hơn 5–10% tổng số rows, table scan thường nhanh hơn index lookup. Database query planner (MySQL EXPLAIN, Postgres EXPLAIN ANALYZE) sẽ chọn table scan tự động trong trường hợp này — nhưng việc tạo index vô dụng vẫn tốn write overhead mỗi khi INSERT/UPDATE.

Với low-cardinality column: xem xét bitmap index (Postgres, Oracle) hoặc partition theo giá trị đó.

Pitfall 3 — Composite index column order sai

Index (country, city) và (city, country) là hai index khác nhau hoàn toàn:

-- Index: (country, city)
-- B+tree sap xep theo: concat(country, city)
--   "VN_Hanoi", "VN_HCMC", "US_LA", "US_NY" ...

-- DUNG index (country, city):
SELECT * FROM users WHERE country = 'VN';              -- prefix match -> OK
SELECT * FROM users WHERE country = 'VN' AND city = 'Hanoi'; -- OK

-- KHONG dung index (country, city):
SELECT * FROM users WHERE city = 'Hanoi';  -- skip leftmost column -> full scan

Mental model: B+tree leaf chain sort theo (country, city) concatenated. Query WHERE city = 'Hanoi' cần tìm Hanoi rải rác khắp nơi trong chain (US_Hanoi, VN_Hanoi, JP_Hanoi...) — không thể range scan, phải full scan.

8. Cardinality và selectivity

Hai khái niệm quan trọng khi thiết kế index:

Cardinality: Số unique value của column.

• user_id trong bảng users: cardinality = số users (rất cao).
• status trong bảng orders: cardinality = 3–5 (rất thấp).
• country_code trong bảng users: cardinality = 100–200 (trung bình).

Selectivity: Tỉ lệ rows match / tổng rows. High selectivity = ít row match = index hữu ích.

Selectivity = unique_values / total_rows

user_id (10M unique / 10M rows): selectivity = 1.0  -- perfect for index
country ('VN' matches 3M / 10M rows): selectivity = 0.3  -- borderline
status ('pending' matches 4M / 10M rows): selectivity = 0.4  -- too low for index

Rule of thumb cho phần lớn OLTP workload:

• Selectivity dưới 0.05 (query trả về hơn 5% rows): index thường không có lợi.
• Selectivity trên 0.01 và column thường xuyên filter: index gần như luôn có lợi.
• Không đo = không kết luận: dùng EXPLAIN ANALYZE để xem query planner chọn gì.

9. Ứng dụng trong các hệ thống thực tế

MySQL InnoDB — clustered B+tree primary key: Row data được lưu trực tiếp trong leaf node của primary key index. Đây gọi là "clustered index" — table IS the B+tree. Secondary index (index trên các column khác) có leaf chứa giá trị primary key, không phải row data trực tiếp. Kết quả: secondary index lookup = 2 B+tree traversal (một để tìm primary key, một để fetch row data). Gọi là "double lookup" hay "bookmark lookup".

-- InnoDB secondary index lookup on email column:
--   Step 1: B+tree traverse on idx_email -> find primary key (user_id = 12345)
--   Step 2: B+tree traverse on PRIMARY -> find row data at leaf
-- = 2x disk seeks compared to primary key lookup
SELECT * FROM users WHERE email = '[email protected]';

PostgreSQL B-tree: PostgreSQL dùng B-tree nhưng heap và index là tách biệt nhau. Leaf của index chứa (key, ctid) — ctid là physical location tuple trong heap file. Không clustered theo mặc định. Có thể dùng CLUSTER command để sắp xếp lại heap theo index một lần, nhưng cluster không tự duy trì.

MongoDB WiredTiger: B+tree storage engine mặc định. Collection lưu theo B+tree keyed bởi _id. Secondary index leaf chứa _id (tương tự InnoDB).

Filesystem HFS+ và NTFS: Dùng B-tree (không phải B+tree) cho directory entries. Mỗi directory là một B-tree của filename → inode mapping. Lý do: filesystem không cần range scan trên filename thường xuyên, và cần lưu metadata (inode) ngay trong internal node để giảm seek.

LSM tree — alternative cho write-heavy workload: Cassandra, RocksDB, LevelDB dùng LSM tree (Log-Structured Merge tree) thay vì B+tree. LSM tree tối ưu cho sequential write (write-ahead log + memtable + SSTable), đánh đổi read performance hơn. B+tree tốt hơn cho mixed read/write OLTP. Module 9 (Phân tán) sẽ deep dive LSM tree trong context distributed database.

10. Cross-link DB index thực hành

Bài này tập trung vào CTDL fundamentals của B+tree — cơ chế bên dưới. Để học cách áp dụng vào SQL query optimization thực tế (EXPLAIN ANALYZE, composite index design, covering index, partial index), xem SQL nâng cao — Indexing.

11. Deep Dive

12. Tóm tắt

• RB tree không phù hợp cho disk vì height 60 = 60 disk seek = 600ms trên HDD — quá chậm cho database.
• B-tree giải quyết bằng fat node: mỗi node chứa hàng trăm key (fanout cao), height giảm xuống 3–5 cho hàng tỷ record.
• B+tree khác B-tree ở hai điểm: data chỉ ở leaf (internal node chứa navigation key), và leaf được nối thành doubly linked list.
• Leaf chain của B+tree là lý do range query hiệu quả: tìm leaf đầu, scan tuần tự — sequential I/O, không cần backtrack.
• MySQL InnoDB dùng clustered B+tree: row data trong leaf của primary key index. Secondary index leaf chứa primary key → double lookup.
• Index column cardinality thấp (vài giá trị duy nhất) → index vô dụng hoặc phản tác dụng. Cardinality cao, selectivity cao → index có lợi rõ ràng.
• Composite index column order quan trọng: (country, city) cho phép prefix query WHERE country = ? nhưng không cho WHERE city = ?. B+tree sort theo concat key.
• LSM tree là alternative cho write-heavy workload (Cassandra, RocksDB) — trade-off ngược lại với B+tree.

13. Tự kiểm tra

depth 1 (root):  100 children
depth 2:  100 * 100 = 10,000 leaf nodes
depth 3:  100^3 = 1,000,000 leaf nodes
depth 4:  100^4 = 100,000,000 leaf nodes
depth 5:  100^5 = 10,000,000,000 (10 ty) leaf nodes

Bài tiếp theo: Trie — autocomplete, IP lookup, dictionary