B-Tree vs B+Tree: Sự khác biệt cốt lõi trong Database Indexing

Khi tạo Index trong MySQL (InnoDB) hay PostgreSQL, cơ sở dữ liệu của bạn không dùng Cây nhị phân (Binary Tree) mà dùng B-Tree hoặc B+ Tree. Lý do là vì dữ liệu được lưu trên đĩa cứng (Disk/SSD), cấu trúc B-Tree giúp tăng số lượng node con (fan-out lớn) nhằm giảm chiều cao của cây, từ đó giảm tối đa số lần đọc đĩa (Disk I/O vốn rất chậm).

Tuy nhiên, hầu hết các hệ quản trị CSDL hiện đại đều chọn B+ Tree. Sự khác biệt cốt lõi nằm ở đâu? Hãy nhìn vào sơ đồ so sánh trực quan dưới đây:

Sơ đồ cấu trúc: B-Tree vs B+ Tree

Hệ thống sơ đồ dưới đây minh họa cách bố trí dữ liệu thực tế (Record Data) giữa hai Tree:

Nhìn vào sơ đồ, chúng ta có thể rút ra 2 khác biệt mang tính quyết định:

2 Khác biệt cốt lõi quyết định chiến thắng

1. Vị trí lưu trữ dữ liệu (Data Pointers)

B-Tree (Bên trái): Khóa (Key) và Dữ liệu thực tế (Data / Record Data) được lưu ở tất cả các tầng (bao gồm cả Root, Node trung gian và Node lá).
B+ Tree (Bên phải): Các Node tầng trên (Root, Intermediaries) chỉ lưu Khóa và Con trỏ điều hướng, tuyệt đối không chứa dữ liệu. Toàn bộ Dữ liệu thực tế (Data7, Data8...) được đẩy hết xuống các Node Lá.

Tại sao điều này quan trọng?
Một Node trong CSDL tương ứng với một Trang dữ liệu (Page - ví dụ 16KB). Vì Node trung gian của B+ Tree không phải gánh dữ liệu, nó có thể chứa được thêm hàng nghìn Khóa điều hướng. Cây bẹp hơn, chiều cao thấp hơn, dẫn đến việc tìm kiếm tốn ít lần đọc đĩa (Disk I/O) hơn.

2. Cách xử lý truy vấn khoảng (Range Queries)

B-Tree: Không có sự liên kết giữa các node lá. Để tìm dữ liệu trong một khoảng (ví dụ: WHERE id BETWEEN 10 AND 20), B-Tree phải thực hiện duyệt cây lên - xuống liên tục qua nhiều tầng (In-order Traversal), gây tốn Disk I/O ngẫu nhiên.
B+ Tree: Tất cả các Node lá được nối với nhau bằng một Danh sách liên kết (Linked List). CSDL chỉ cần tìm đến Node lá chứa phần tử đầu tiên (ID = 10), sau đó chỉ việc đi bộ tuần tự (Sequential Read) theo hàng ngang để lấy tiếp các phần tử cho đến ID = 20.

Tóm tắt nhanh

Đặc điểm	B-Tree	B+ Tree
Vị trí lưu Data	Tất cả các Node	Chỉ lưu ở Node Lá
Duyệt khoảng (`BETWEEN`, `>`, `<`)	Chậm (Phải duyệt lên xuống giữa các tầng)	Cực nhanh (Duyệt tuần tự qua Linked List ở hàng lá)
Số lượng khóa / Node	Ít (Vì phải chia sẻ không gian với Data)	Nhiều hơn (Giúp giảm chiều cao của cây)
Ứng dụng thực tế	MongoDB (chỉ mục mặc định), Hệ thống file	MySQL (InnoDB), PostgreSQL, SQLite

Kết luận: B+ Tree tối ưu hóa hoàn hảo cho việc đọc đĩa và các câu lệnh truy vấn khoảng—những tác vụ chiếm tới 80% hiệu năng của một hệ thống Backend thực tế.

Tài liệu tham khảo: https://medium.com/@akashsdas_dev/b-trees-and-b-trees-682d363df1f7