Hầu hết các cấu trúc dữ liệu ta biết như array, linked list, binary tree, red-black tree đều load dữ liệu lên RAM và xử lý trên đó. Tuy nhiên với các dữ liệu lớn thì ko thể load hết lên RAM để xử lý được. Chi phí của việc đọc từ hard disk thì lại quá lớn do đó nếu có cách nào giảm số lần truy xuất xuống hard disk thì tốt. B-Tree sinh ra để giải quyết chuyên này.

Cấu trúc

B-Tree là cậy tự cân bằng (self-balancing), nghĩa là khi thêm hoặc xoá 1 node thì cây sẽ có những action để đảm bảo chiều cao của cây càng thấp càng tốt.

B-Tree có thể chứa nhiều hơn 1 key ở mỗi node. Tại 1 node ta có n key thì các key này sẽ được sắp xếp và đóng vai trò là các cột mốc chia miền giá trị thành n + 1 khoảng khác nhau. Node cha sẽ dựa vào những khoảng này để phân chia các cây con của mình.

Ví dụ:

Với n = 3, tại node A có 3 key a1, ..., a3. Do đó ta có 3 + 1 khoảng chia s1, ..., s4 với s1 < a1, a1 <= s2 < a2, a2 <= s3 < a3, a3 <= s4, tương ứng với 4 cây con. Cây con phía ngoài cùng bên trái chỉ có thể chứa các key thuộc khoảng s1, cây con thứ hai chỉ chứa các key thuộc khoảng s2, và tương tự cho cây con thứ 3 và ngoài cùng bên phải.

B-Tree example

Nếu theo dõi Grokking thường xuyên, các bạn sẽ thấy ý tưởng này quen quen. Thật ra B-Tree chính là dạng tổng quát của cây 2-3-4

Công dụng:

Với khả năng chứa nhiều key ở 1 node, B-Tree có thể giữ cho chiều cao của nó thấp. Hình tượng mà nói thì có thể thấy B-Tree "mập" hơn những loại cây tự cân bằng khác. Các thao tác truy suất dữ liệu trên cấu trúc cây đều có độ phức tạp O(h) nên bằng việc giảm chiều cao, B-Tree sẽ làm giảm số lượng truy xuất xuống hard drive.

Nếu bạn dùng Postgres hoặc MySQL thì nhiều khả năng là bạn đang index column bằng B-Tree.

Nhược điểm

So sánh với các cây khác, mỗi node của B-Tree chứa rất nhiều key. Do đó chi phí khi xử lý trên các key này cũng có chiếm 1 lượng thời gian đáng kể. Giả sử các key này được quản lý bằng Array thì thêm 1 key vào sẽ tốn O(t) thời gian, với t là 1 số định trước, chỉ số lượng key tối thiểu ở mỗi node.

Ngoài ra còn 1 đặc điểm khác của hard disk là dữ liệu sẽ được lấy theo từng block một. Do đó B-Tree sẽ được implement sao cho mỗi node chỉ chứa số lượng key nằm vừa trong 1 block size. Nếu data trong 1 node vượt quá 1 block size thì mục đích của B-Tree sẽ thất bại: giảm số lượng truy suất cần thiết xuống hard disk.

References

http://r.grokking.org/blog-btree-introduction