Bài 8: B-Tree Database Index — Nền Tảng Của Mọi Cơ Sở Dữ Liệu

Ở Bài 1 chúng ta học cây AVL tự cân bằng — hoàn hảo khi dữ liệu nằm trong RAM. Nhưng nếu dữ liệu nằm trên ổ đĩa (như trong mọi hệ quản trị cơ sở dữ liệu), AVL lại không phải lựa chọn tốt nhất. B-Tree mới là cấu trúc đứng sau chỉ mục (index) của MySQL, PostgreSQL, và hầu hết hệ thống file.

1. Vì sao AVL không tối ưu cho lưu trữ trên ổ đĩa?

Truy cập RAM mất vài nano-giây, nhưng một lần đọc ổ đĩa (disk seek) — kể cả SSD — có thể chậm hơn hàng nghìn lần. Với cây nhị phân như AVL, mỗi node là một lần đọc đĩa riêng biệt; tra cứu 1 triệu bản ghi cần khoảng $\log_2(10^6) \approx 20$ lần đọc đĩa. B-Tree giải quyết vấn đề bằng cách cho mỗi node chứa hàng trăm khóa (vừa đúng 1 trang đĩa — thường 4KB–16KB), khiến cây THẤP hơn rất nhiều dù chứa cùng số lượng dữ liệu.

2. Cấu trúc B-Tree: Bậc (Order) và ràng buộc số khóa

Một B-Tree bậc $m$ (order $m$) tuân theo các ràng buộc: mỗi node có tối đa $m$ con và tối đa $m{-}1$ khóa; mọi node (trừ gốc) có tối thiểu $\lceil m/2 \rceil$ con. Mọi lá nằm ở cùng một độ sâu — đây là điều kiện cân bằng của B-Tree, khác với AVL cân bằng theo chiều cao từng nhánh:

class BTreeNode {
  constructor(leaf) {
    this.keys = [];     // tối đa m-1 khóa, luôn giữ SẮP XẾP
    this.children = [];  // tối đa m con — children[i] chứa khóa GIỮA keys[i-1] và keys[i]
    this.leaf = leaf;    // true nếu là node lá (không có con)
  }
}

3. Chèn node & Tách trang (Insert & Split)

Khi chèn khiến một node có đủ $m{-}1$ khóa (đầy), node phải tách đôi: khóa ở giữa được đẩy lên node cha, 2 nửa còn lại trở thành 2 node con riêng biệt. Nếu node gốc bị tách, cây tăng thêm 1 tầng — đây là cách DUY NHẤT B-Tree tăng chiều cao, luôn từ gốc lên chứ không từ lá xuống như AVL:

// T = bậc tối thiểu (min degree); bậc tối đa m = 2T
// splitChild tách children[i] của parent (đang đầy 2T-1 khóa) làm 2 node,
// đẩy khóa giữa (vị trí T-1) lên parent
function splitChild(parent, i, T) {
  const fullChild = parent.children[i];
  const newChild = new BTreeNode(fullChild.leaf);
  const midKey = fullChild.keys[T - 1];

  newChild.keys = fullChild.keys.slice(T);        // nửa phải -> node mới
  fullChild.keys = fullChild.keys.slice(0, T - 1); // nửa trái -> node cũ

  if (!fullChild.leaf) {
    newChild.children = fullChild.children.slice(T);
    fullChild.children = fullChild.children.slice(0, T);
  }

  parent.children.splice(i + 1, 0, newChild); // gắn node mới làm con của parent
  parent.keys.splice(i, 0, midKey);           // đẩy khóa giữa lên parent
}

B-Tree tách chủ động (proactive splitting): khi đi từ gốc xuống lá để chèn, hễ gặp node đầy trên đường đi là tách ngay trước khi đi tiếp — đảm bảo node cha luôn còn chỗ trống để nhận khóa đẩy lên.

4. Xoá node & Gộp trang (Delete & Merge)

Xoá phức tạp hơn chèn: sau khi xoá, một node có thể có ít hơn $\lceil m/2 \rceil{-}1$ khóa (vi phạm ràng buộc tối thiểu). Khi đó node phải "mượn" (borrow) một khóa từ node anh em liền kề (nếu anh em đó dư khóa), hoặc gộp (merge) với node anh em nếu cả 2 đều thiếu khóa:

// Sau khi xoá 1 khóa khỏi child[i] khiến nó thiếu khóa (còn < T khóa):
function fill(node, i, T) {
  if (i > 0 && node.children[i - 1].keys.length >= T) {
    borrowFromPrev(node, i);   // mượn khóa từ anh em BÊN TRÁI (nếu dư)
  } else if (i < node.keys.length && node.children[i + 1].keys.length >= T) {
    borrowFromNext(node, i);   // mượn khóa từ anh em BÊN PHẢI (nếu dư)
  } else {
    // Cả 2 bên đều không dư — GỘP với 1 anh em + khóa cha ở giữa
    if (i < node.keys.length) merge(node, i);
    else merge(node, i - 1);
  }
}

5. So sánh B-Tree với AVL/Red-Black cho lưu trữ trên đĩa

Sân chơi tương tác: B-Tree Visualizer

Chèn hoặc xoá giá trị để xem cây B-Tree bậc 4 tự tách/gộp trang — quan sát khóa được đẩy lên node cha khi tách, và node anh em cho mượn/gộp khóa khi xoá.