Cấu trúc dữ liệu Cây: Binary Tree, BST, Balanced Tree, B-Tree
Binary Search Tree, vì sao cây cần tự cân bằng (AVL/Red-Black), và B-Tree — cấu trúc dữ liệu đứng sau mọi database index bạn đã dùng.
Đây là module có ứng dụng trực tiếp nhất vào công việc backend hàng ngày: mọi lần bạn tạo INDEX trên 1 cột database, bạn đang dùng B-Tree. Hiểu cách cây hoạt động bên dưới giải thích được rất nhiều hành vi "kỳ lạ" của database mà trước đây chỉ biết dùng theo kinh nghiệm.
🎯 Mục tiêu học tập
- Triển khai và duyệt Binary Search Tree (BST), hiểu các thao tác insert/search/delete
- Giải thích vì sao BST không cân bằng có thể suy biến thành O(n), và cách AVL/Red-Black Tree giải quyết
- Hiểu cấu trúc B-Tree và vì sao nó là lựa chọn tối ưu cho database index (không phải Binary Tree thường)
- Đọc hiểu được EXPLAIN ANALYZE của database dưới góc nhìn cấu trúc cây
Binary Search Tree (BST)
BST duy trì bất biến (invariant): với mỗi node, toàn bộ node ở cây con trái nhỏ hơn nó, toàn bộ node ở cây con phải lớn hơn nó — bất biến này cho phép tìm kiếm, thêm, xoá đều O(log n) (nếu cây cân bằng) bằng cách loại bỏ một nửa không gian tìm kiếm ở mỗi bước, giống hệt tìm kiếm nhị phân trên mảng đã sắp xếp nhưng hỗ trợ insert/delete hiệu quả mà mảng không làm được.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def insert(root, val):
if root is None:
return Node(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
def search(root, val):
if root is None or root.val == val:
return root
return search(root.left, val) if val < root.val else search(root.right, val)
Vấn đề mất cân bằng — vì sao cần AVL/Red-Black Tree
Nếu dữ liệu được insert theo thứ tự đã sắp xếp sẵn (1, 2, 3, 4, 5...), BST "ngây thơ" suy biến thành 1 danh sách liên kết — mọi thao tác trở thành O(n) thay vì O(log n), mất hoàn toàn lợi ích của cấu trúc cây. Self-balancing tree (AVL Tree, Red-Black Tree) tự động thực hiện các phép "xoay" (rotation) sau mỗi insert/delete để đảm bảo cây luôn giữ chiều cao ~O(log n) bất kể thứ tự dữ liệu vào — đây là lý do các cấu trúc dữ liệu có sẵn trong hầu hết ngôn ngữ (TreeMap của Java, std::map của C++) đều dùng Red-Black Tree bên dưới thay vì BST thường.
Hầu như không ai tự viết lại AVL/Red-Black Tree trong công việc thực tế — điều quan trọng là hiểu vì sao chúng cần thiết, để nhận ra khi nào 1 thư viện/database đang dùng cấu trúc cây cân bằng bên dưới và tại sao điều đó quan trọng cho hiệu năng ổn định.
B-Tree — cấu trúc đứng sau mọi Database Index
Binary Tree (mỗi node tối đa 2 con) không tối ưu cho dữ liệu lưu trên đĩa (khác RAM) — đọc đĩa theo block (thường 4KB-16KB) có chi phí cố định lớn bất kể đọc ít hay nhiều trong 1 block, nên muốn giảm thiểu số lần đọc đĩa, không phải giảm số phép so sánh. B-Tree giải quyết đúng vấn đề này: mỗi node chứa nhiều khoá (thường hàng trăm, vừa khít 1 block đĩa), giảm chiều cao cây xuống rất thấp (thường chỉ 3-4 tầng dù có hàng triệu bản ghi) — nghĩa là tìm 1 bản ghi chỉ cần 3-4 lần đọc đĩa, thay vì hàng chục lần nếu dùng Binary Tree thường.
Đây chính xác là cấu trúc bên dưới CREATE INDEX trong PostgreSQL/MySQL (B-Tree index —
loại index mặc định) mà bạn đã dùng ở khoá AI Engineer (Module 2) và Databricks (liên hệ Liquid Clustering,
Module 3). Hiểu B-Tree giải thích trực tiếp: vì sao WHERE indexed_col = x nhanh nhưng
WHERE indexed_col LIKE '%x%' (tìm ở giữa chuỗi) không tận dụng được index — B-Tree được sắp
xếp theo thứ tự, chỉ hỗ trợ tra cứu hiệu quả theo prefix/khoảng giá trị, không hỗ trợ tìm kiếm chuỗi con
tuỳ ý.
Đọc EXPLAIN ANALYZE dưới góc nhìn cấu trúc Cây
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 12345;
-- Index Scan using idx_customer_id on orders
-- (cost=0.42..8.44 rows=1 width=120)
-- -> đang duyệt B-Tree index: đi từ root xuống leaf, ~3-4 lần đọc block
-- thay vì Sequential Scan phải đọc TOÀN BỘ bảng (O(n) block đọc)
Khi thấy Index Scan trong execution plan, đó chính là B-Tree đang hoạt động — hiểu cấu
trúc bên dưới giúp bạn dự đoán được hiệu năng truy vấn sẽ thay đổi thế nào khi dữ liệu tăng trưởng (số
lần đọc đĩa tăng theo O(log n), không phải O(n)), thay vì chỉ "tin tưởng" index mà không hiểu vì sao nó
nhanh.
🏋️ Bài tập thực hành
Triển khai đầy đủ BST (insert/search/delete) bằng ngôn ngữ quen thuộc. Thử nghiệm 2 kịch bản: (1) insert 10.000 số ngẫu nhiên, đo chiều cao cây và thời gian tìm kiếm trung bình; (2) insert 10.000 số theo thứ tự đã sắp xếp, đo lại 2 chỉ số đó — so sánh và giải thích sự khác biệt bằng chính khái niệm mất cân bằng đã học. Sau đó chạy EXPLAIN ANALYZE trên 1 bảng có index ở database quen thuộc, xác định chỗ nào trong output thể hiện việc dùng B-Tree.
📚 Tài nguyên học tập
-
VisuAlgo — Binary Search TreeTrực quan hoá tương tác BST và các thao tácTool
-
PostgreSQL — B-Tree ImplementationTài liệu chính thức chi tiết cách PostgreSQL triển khai B-Tree indexDocs
-
CMU Database Group — B+Tree Indexes (video)Bài giảng chuyên sâu về cấu trúc B-Tree/B+Tree trong databaseVideo
✅ Tự đánh giá hoàn thành
- Triển khai đúng insert/search trên BST
- Giải thích được vì sao BST không cân bằng có thể suy biến thành O(n)
- Giải thích được vì sao B-Tree (không phải Binary Tree) là lựa chọn tối ưu cho database index
- Đọc hiểu được phần Index Scan trong EXPLAIN ANALYZE của 1 database thật