- Gần đây khi đọc Database Internals của Alex Petrov, tôi đã tìm hiểu về cách triển khai storage engine của DBMS, đặc biệt là phần tối ưu hóa cấu trúc dữ liệu B-Tree
- Khi học B-Tree ở đại học, tôi chỉ hiểu đơn giản nó là một kiểu “BST tốt hơn”, nên chưa thực sự cảm nhận được vì sao nó lại được dùng trong thực tế
- B-Tree phù hợp để lưu trữ dữ liệu quy mô lớn và tìm kiếm nhanh khi phải tính đến disk I/O
- Bài viết này giới thiệu vì sao cần B-Tree, cách nó hoạt động, và những tối ưu hóa nào có thể áp dụng trong triển khai thực tế
- Đặc điểm chính là gom nhiều khóa vào một node để giảm số lần truy cập đĩa
Những ràng buộc phát sinh do đĩa
- Giả định tình huống toàn bộ dữ liệu không thể nằm hết trong bộ nhớ
- Đĩa có đặc tính đọc và ghi theo đơn vị “page” mỗi lần
- Truy cập đĩa chậm hơn rất nhiều so với truy cập bộ nhớ
- Vì vậy, cấu trúc dữ liệu cần bố trí dữ liệu theo hướng lấy page làm trung tâm, đồng thời thực hiện được nhiều phép so sánh khóa nhất có thể với số lần truy cập đĩa tối thiểu
- Nếu lưu BST nguyên trạng trên đĩa, các node sẽ bị phân tán, khiến số lần truy cập đĩa cũng tăng theo số lần tìm kiếm
- B-Tree gom nhiều khóa vào một node để chỉ cần đọc đĩa một lần mà vẫn có thể so sánh được nhiều khóa
Slotted page
- Khi bố trí dữ liệu trên đĩa, việc quản lý được thực hiện theo đơn vị “page”
- Mỗi page có header, các cell chứa dữ liệu độ dài biến thiên, và một mảng offset pointer lưu vị trí của các cell
- Cấu trúc slotted page có ưu điểm là vẫn giữ được thứ tự sắp xếp mà không tốn nhiều chi phí sắp xếp lại, ngay cả khi kích thước khóa là biến thiên
- Khi xóa hoặc chèn khóa, việc chỉ sắp xếp lại pointer hiệu quả hơn rất nhiều so với di chuyển dữ liệu thực tế
- Ví dụ, SQLite dùng free list trong cấu trúc page kiểu này để tái sử dụng không gian của các cell đã bị xóa
Tra cứu B-Tree
- Thuật toán tra cứu B-tree khá đơn giản:
- Bắt đầu từ node gốc
- Xem separator key của node hiện tại để tìm node con được dự đoán là chứa khóa cần tìm
- Duyệt cây một cách đệ quy
- Hoàn tất khi tìm thấy node lá chứa khóa cần tìm; nếu không có thì kết luận khóa không tồn tại
- Ở internal node, chỉ cần có separator key thay vì dữ liệu thực, và thông thường dữ liệu thực chỉ được lưu ở leaf node
- Để tìm khóa trong node một cách hiệu quả bằng tìm kiếm nhị phân, các khóa trong mỗi node luôn được giữ ở trạng thái đã sắp xếp
Rút gọn separator key
- Separator key ở internal node không cần phải là toàn bộ khóa thật, chỉ cần đủ để phân biệt phạm vi là được
- Ví dụ, để phân biệt khoảng giữa 0xAAAAAA và 0xBBBBBB, không nhất thiết phải lưu toàn bộ 0xBBBBBB mà có thể phân biệt bằng một tiền tố ngắn hơn
- Với cơ sở dữ liệu có khóa dài, kiểu rút gọn này giúp tiết kiệm đáng kể dung lượng lưu trữ
- Ngoài việc rút gọn separator key, còn có các chiến lược giảm hiệu quả phần prefix và suffix
- Vì số lượng leaf node nhiều hơn hẳn, cũng có quan điểm cho rằng nén prefix đóng góp nhiều hơn cho hiệu năng
Overflow page
- Khi một node có quá nhiều khóa đến mức không thể chứa hết trong một page, người ta dùng overflow page
- Thay vì chuyển nguyên toàn bộ khóa sang overflow page, node chỉ giữ lại một tiền tố ngắn còn phần còn lại được tách ra để lưu riêng
- Làm như vậy giúp việc kiểm tra sự tồn tại của khóa hoặc tìm kiếm theo phạm vi trước hết chỉ cần xem tiền tố trong node, và chỉ đọc overflow page khi thực sự cần
- Đây là cách giảm tổng chi phí tìm kiếm ngay cả khi phải cấp phát thêm page
Sibling pointer
- Có cách triển khai lưu pointer tới sibling node bên trái và bên phải giữa các node
- Nhờ đó, khi tra cứu theo phạm vi, có thể đi thẳng từ một leaf node sang sibling node để duyệt nhanh các khóa liên tiếp
- Nếu không có sibling pointer, phải lặp lại quá trình đi ngược lên node cha rồi đi xuống, khiến chi phí I/O tăng lên
- Vì phạm vi khóa giữa các sibling node không chồng lấp, di chuyển theo right sibling pointer đảm bảo sẽ tới “phạm vi khóa tiếp theo”
Các biến thể của B-Tree
- Ngoài B⁺-Tree còn tồn tại nhiều cấu trúc biến thể khác
- “Lazy B-Tree” như trong WiredTiger hay Lazy-Adaptive Tree dùng cách đệm các phép ghi để tăng hiệu năng
- FD-Tree là cấu trúc được thiết kế phù hợp với đặc tính của SSD, có tính đến các ràng buộc vật lý như ghi theo block
- Bw-Tree (Buzzword Tree) là cấu trúc dữ liệu được tối ưu cho tính đồng thời cao và truy cập cây trên bộ nhớ
Kết luận
- Giữa khái niệm trừu tượng “B⁺-Tree” và cách triển khai thực tế như “định dạng DB của SQLite” tồn tại rất nhiều tối ưu hóa và khác biệt chi tiết trong cài đặt
- Các tối ưu hóa này không làm thay đổi độ phức tạp Big-O, nhưng ảnh hưởng lớn đến hiệu năng và tính khả dụng của cơ sở dữ liệu trong môi trường thực tế
- Ngoài những nội dung được giới thiệu ở đây, mỗi hệ thống lưu trữ cụ thể còn cần rất nhiều tinh chỉnh nhỏ
- Đằng sau cách nói “chỉ cần thêm một chút thông tin phụ” là độ phức tạp trong triển khai và khó khăn khi debug
- Một ví dụ minh họa B-Tree theo hướng gần với thực tế hơn là sơ đồ B-Tree trong Designing Data-Intensive Applications, vốn để lại nhiều ấn tượng
1 bình luận
Ý kiến Hacker News
Cấu trúc của trang gồm header, cell và con trỏ offset, với ưu điểm là có thể lưu trữ dữ liệu kích thước biến đổi
Đây là một bài viết rất hay có kèm hoạt ảnh về B-tree
Vài năm trước tôi đã triển khai B-link Tree có thể phục hồi đồng thời dựa trên nghiên cứu của Ibrahim Jaluta
Tôi đã tạo một trình khám phá trang đĩa SQLite nên hiểu B-tree tốt hơn
Bài này không đề cập đến B-link tree, tính đồng thời và khóa, nhưng đó có thể là thông tin nhiều hơn mức cần thiết
Bình luận trước đây: Hacker News
Một bài viết tuyệt vời, giải thích rất rõ tầm quan trọng của các chi tiết
Đây là tài liệu tốt về triển khai B-tree bằng Golang
Tôi rất thích bài viết này và trước đây cũng có sự "hiểu mơ hồ" giống tác giả