B-Tree là một cấu trúc index được xây dựng dựa trên cấu trúc dữ liệu B-Tree, nhờ vậy nó kế thừa khả năng lưu trữ các cặp key-value một cách có thứ tự. Điều này giúp B-Tree hỗ trợ hiệu quả cả truy vấn tìm kiếm theo key lẫn truy vấn theo khoảng (range query).
Dù đều có đặc điểm dựa trên cây cân bằng tương tự với SSTable, B-Tree lại phát triển theo một hướng hoàn toàn khác. Được giới thiệu lần đầu vào năm 1970 và nhanh chóng phổ biến chỉ trong vòng chưa đầy một thập kỷ sau đó, B-Tree đã liên tục giữ vững vị thế và cho đến nay vẫn là loại index được sử dụng rộng rãi nhất. B-Tree đã đồng hành và trở thành một nhân chứng lịch sử cho sự phát triển của các hệ thống lưu trữ truyền thống, đặc biệt là cơ sở dữ liệu quan hệ (RDBMS), trải qua nhiều trào lưu cơ sở dữ liệu khác nhau nổi lên rồi lại thoái trào.
Liệu NoSQL với LSM-Tree sẽ tiếp tục phát triển hay dần ổn định như những trào lưu trước? Câu trả lời chỉ có thời gian mới xác định được. Tuy nhiên, có một điều chắc chắn: B-Tree vẫn sẽ khó bị thay thế trong nhiều ngữ cảnh, đặc biệt khi ứng dụng của bạn yêu cầu sự hỗ trợ mạnh mẽ về transaction và truy vấn đọc ngẫu nhiên.
B-Tree chia cơ sở dữ liệu thành các khối (page) có kích thước cố định, thường là 4KB (đôi khi lớn hơn). Mỗi lần đọc, toàn bộ page sẽ được tải lên, và tương tự, khi ghi, cả page cũng được ghi xuống đĩa. So với SSTable, thiết kế này tương thích hơn với phần cứng, vì đĩa cứng cũng được tổ chức thành các khối có kích thước cố định.
Truy vấn tìm kiếm trong B-Tree#
Mỗi page được xác định bằng một địa chỉ duy nhất, cho phép page này tham chiếu đến page khác - tương tự như con trỏ trong bộ nhớ, chỉ khác là chúng nằm trên đĩa.
Một page được chỉ định làm gốc (root) của B-Tree. Mọi truy vấn tìm kiếm đều bắt đầu từ đây. Mỗi page sẽ chứa nhiều key và cũng có thể chứa cả tham chiếu tới các page con. Mỗi page con phụ trách một khoảng key nhất định, được giới hạn bởi hai key liền kề trong page cha.
Ví dụ với hình minh họa trên, khi tìm key 251, ta bắt đầu từ root, tìm tham chiếu nằm giữa key 200 và 300, nhảy đến page con tương ứng, rồi lặp lại quá trình này cho đến khi tới được page lá (leaf page) — page chỉ chứa key và giá trị (hoặc con trỏ đến dữ liệu), không có page con. Tại đây, nếu tìm thấy key 251, ta có thể trả về giá trị của nó.
Số lượng tham chiếu trong một page được gọi là branching factor (hệ số nhánh). Trong hình minh họa, branching factor là 6, nhưng thực tế với page 4KB và key cỡ vài chục byte, branching factor có thể lên tới hàng trăm, giúp giảm đáng kể số lần truy cập đĩa khi tìm kiếm.
Ghi giá trị vào B-Tree#
Update key có sẵn#
Tìm đến page lá chứa key, cập nhật giá trị trong page đó, sau đó ghi page lại vào đĩa (thường tại vị trí cũ).
Insert key mới#
Tìm page phù hợp dựa trên khoảng key, rồi thêm key mới vào.
Nếu page không còn đủ chỗ, page sẽ được tách làm hai page mới, và một key trung gian được đẩy lên page cha. Quá trình này có thể lan truyền đệ quy lên đến root nếu page cha cũng đầy.
Thuật toán này đảm bảo cây luôn cân bằng: một B-Tree với N key luôn có độ cao tối đa O(log N). Hầu hết database chỉ cần 3–4 tầng, nhờ đó việc tìm kiếm một key chỉ cần duyệt qua vài page.
Ví dụ về khả năng lưu trữ: một B-Tree 4 tầng với page 4KB và branching factor 500 có thể tham chiếu đến:
Khoảng 125 triệu page lá (tính từ root đến lá)
Mỗi page lá chứa hàng trăm key → tổng số key lên đến hàng chục tỷ
Tùy vào kích thước dữ liệu thực tế, có thể lưu trữ hoặc quản lý dữ liệu với tổng dung lượng lên đến hàng trăm TB.
Chú ý khi sử dụng B-Tree index#
Như đã đề cập ở trên, những gì chúng ta thảo luận mới chỉ là nguyên lý cơ bản. Để vận hành B-Tree trong môi trường thực tế, cần xử lý nhiều vấn đề phức tạp như sau:
Xử lý khi crash: để tránh mất mát dữ liệu khi hệ thống gặp sự cố giữa chừng, thông thường ta sử dụng Write-Ahead Log (WAL) - một file chỉ ghi thêm (append-only) để ghi lại thao tác trước khi áp dụng vào page. Nhờ WAL, khi khởi động lại, database có thể khôi phục lại trạng thái nhất quán.
Copy-on-write (Shadow paging): một số database tránh ghi đè page tại chỗ bằng cách ghi page đã cập nhật vào vị trí mới, sau đó cập nhật con trỏ từ page cha. Cách này giúp đơn giản hóa recovery và hỗ trợ cơ chế snapshot.
Đồng thời nhiều tiến trình: để đảm bảo tính nhất quán khi nhiều transaction cùng truy cập một page, B-Tree sử dụng cơ chế khóa (latch) ở mức page, kết hợp với kỹ thuật lock coupling để tránh deadlock và tăng khả năng xử lý song song.
Nén key: để tiết kiệm không gian lưu trữ, đặc biệt với key dài, ta có thể lưu dạng rút gọn (prefix compression) bằng cách loại bỏ phần tiền tố trùng lặp giữa các key liền kề trong cùng page. Ví dụ:
(AAAAA, BBBBB) -> (A, B).Liên kết ngang giữa page sibling (thường thấy trong B+Tree): thêm con trỏ nối giữa các page sibling giúp hỗ trợ range scan không cần quay lại parent, từ đó tăng hiệu năng cho scan lớn.
So sánh với LSM-Tree#
Như đã từng đề cập ở bài Database 102: Hash Index, B-Tree thực hiện ghi ngẫu nhiên (random write) do cập nhật dữ liệu tại chỗ (in-place update). Điều này khiến tốc độ ghi thường chậm hơn so với LSM-Tree, cấu trúc tối ưu cho ghi tuần tự (sequential write). Ngược lại, B-Tree lại cho hiệu suất đọc nhất quán và nhanh chóng hơn, vì mỗi key chỉ nằm ở một vị trí duy nhất. Trong khi đó, việc đọc trên LSM-Tree có thể chậm hơn do phải kiểm tra qua nhiều tầng SSTable.
Ưu điểm của LSM-Tree so với B-Tree#
Hiệu suất ghi vượt trội: LSM-Tree ghi dữ liệu theo kiểu nối thêm (append-only) vào file log và memtable, sau đó mới tổ chức lại qua compaction. Cách tiếp cận này tận dụng tối đa băng thông ghi tuần tự của đĩa, đặc biệt có lợi thế lớn trên HDD. Trong khi đó, B-Tree thường phải ghi ít nhất hai lần: một lần vào Write-Ahead Log (WAL) và một lần cập nhật page tại chỗ, chưa kể chi phí ghi thêm khi split page.
Nén dữ liệu hiệu quả hơn: Nhờ cơ chế compaction, LSM-Tree có thể nén và loại bỏ dữ liệu trùng lặp hoặc đã xóa một cách triệt để, thường cho tỷ lệ nén cao và kích thước file trên đĩa nhỏ hơn. B-Tree dễ gặp tình trạng phân mảnh nội (internal fragmentation) do không gian trong page không được sử dụng hết, và việc xóa dữ liệu thường chỉ đánh dấu chứ không thu hồi không gian ngay lập tức.
Giảm chi phí cập nhật cấu trúc: Việc thêm/xóa trong B-Tree có thể kích hoạt các thao tác cân bằng cây (split/merge) ngay lập tức, gây ra chi phí I/O trực tiếp. LSM-Tree trì hoãn việc tổ chức lại dữ liệu (compaction) thành một quá trình nền, giúp các thao tác ghi ban đầu diễn ra rất nhanh.
Nhược điểm của LSM-Tree so với B-Tree#
Ảnh hưởng của Compaction đến hiệu năng: Quá trình compaction (dọn dẹp và hợp nhất SSTable) tiêu tốn nhiều tài nguyên CPU và I/O. Nó có thể gây ra hiện tượng tăng độ trễ (latency spike) bất thường cho các thao tác đọc/ghi đang diễn ra (latency bị tăng vọt lên một cách khó hiểu, sau đó lại trở lại bình thường), khiến việc đảm bảo hiệu năng ổn định trở nên khó khăn.
Nguy cơ Write Stall: Nếu tốc độ ghi vào quá cao và compaction không theo kịp, hệ thống có thể rơi vào trạng thái "write stall", buộc các thao tác ghi mới phải chờ đợi cho đến khi compaction hoàn thành một phần. Điều này đòi hỏi việc điều chỉnh tham số compaction phải rất cẩn thận. Xem thêm ở phần Leveled Compaction trong bài Database 103: SSTable và LSM-Tree.
Hiệu suất đọc phức tạp: Một key có thể tồn tại ở nhiều tầng SSTable khác nhau. Do đó, thao tác đọc điểm (point read) trong trường hợp xấu nhất có thể phải kiểm tra qua nhiều file. Dù Bloom Filter và cache có thể được sử dụng để giảm thiểu vấn đề này, hiệu suất đọc vẫn kém ổn định hơn so với B-Tree, nơi mỗi key chỉ có một vị trí xác định với độ phức tạp O(log N) chặt chẽ.
Hỗ trợ Transaction phức tạp hơn: B-Tree, với cấu trúc ổn định và cơ chế khóa (locking) trên page hoặc dải key, rất phù hợp để triển khai các transaction phức tạp với các mức độ cô lập (isolation level) khác nhau. Việc hỗ trợ transaction đầy đủ (ACID) trong LSM-Tree thường phức tạp hơn, mặc dù không phải là không thể (ví dụ: Google Spanner sử dụng kết hợp nhiều kỹ thuật).