B-Tree là 1 kiến trúc index được mô phỏng dựa trên cấu trúc dữ liệu B-Tree, nhờ đó nó cũng được thừa kế tính năng lưu trữ cặp key-value dưới dạng có thứ tự. Điều này giúp cho nó có thể đáp ứng các loại truy vấn tìm kiếm key cũng như range query.

Tuy có những ưu điểm gần giống với SSTable, B-Tree lại đi theo 1 trường phái hoàn toàn khác hẳn. Được giới thiệu lần đầu vào năm 1970, và dần dần phổ cập chỉ trong chưa đầy 10 năm sau đó, B-Tree liên tục giữ vững vị thế của mình và tới giờ vẫn đang là loại index được sử dụng rộng rãi nhất hiện nay. B-Tree cùng gắn bó và là chứng nhân lịch sử cho sự phát triển của các loại cơ sở dữ liệu quan hệ (RDMS), trải qua rất nhiều trào lưu DB khác nhau rộ lên rồi lại thoái trào. Liệu NoSQL với LSM-Tree có thoái trào giống như các trào lưu trước đó không hay sẽ lật đổ RDMS? Câu trả lời này chỉ có thời gian mới trả lời được, nhưng chắc chắn rằng nó sẽ khó có thể thay thế được B-Tree trong nhiều ngữ cảnh, đặc biệt là khi ứng dụng của bạn cần tới sự hỗ trợ của transaction.

B-Tree chia nhỏ DB thành các khối (hay còn gọi là page) với kích thước bằng nhau, thường là 4KB (đôi khi lớn hơn). Khi đọc thì ta sẽ read toàn bộ page, và tương tự lúc ghi thì mình cũng write cả page xuống disk. So với SSTables, thiết kế này tương đồng hơn với phần cứng bên dưới, vì disk cũng được sắp xếp 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ởi địa chỉ của nó, điều này cho phép từ page này tham chiếu tới một page khác (tương tự như con trỏ địa chỉ trong ngôn ngữ lập trình, chỉ khác là nó ở trên disk thay vì nằm trong mem).

1 page sẽ được chỉ định làm gốc của B-Tree; bất kể khi nào bạn cần tìm kiếm 1 key trong index, ta đều cần phải bắt đầu từ page nà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 sẽ chịu trách nhiệm cho 1 dải key nhất định, được bao ngoài bởi key đứng cạnh nó trong page cha.

Ví dụ với hình minh họa trên, ta đang tìm kiếm key 251, vì vậy ta cần tìm tới tham chiếu nằm giữa key 200 và 300. Từ tham chiếu thu được ta tiếp tục nhảy sang page con đó, và thực hiện lặp lại cho tới khi tìm được tới page lá (page chỉ chứa key, không có page con). Cuối cùng ta sẽ kết luận key 251 có tồn tại trong DB hay không, và nếu có thì giá trị của nó là gì.

Số lượng tham chiếu ở trong mỗi page được coi là 1 tham số cần điều chỉnh tùy vào nhu cầu của ứng dụng và kích thước của ổ đĩa, nó được gọi là branching factor. Ở hình bên trên branching factor là 6, còn thực tế thì nó lên tới con số hàng trăm.

Ghi giá trị vào B-Tree

• Update key có sẵn: tìm tới page lá có chứa key, cập nhật giá trị của page rồi ghi page lại vào vị trí cũ trên disk.
• Insert key mới: bạn cần tìm page có dải bao trùm key mới và thêm nó vào page đó.
  • Trong trường hợp page không còn không gian trống để cấp phát thêm key mới: page sẽ bị tách làm 2 page con và ta cập nhật tham chiếu của chúng đệ quy ngược lại lên các page cha.

Thuật toán này đảm bảo cho cây luôn được cân bằng: 1 B-Tree với N key sẽ luôn luôn có độ cao tối đa là O(logN). Hầu hết DB đều chỉ cần sử dụng tới 3-4 tầng, nhờ vậy ta sẽ không cần phải duyệt qua quá nhiều page để tìm kiếm 1 key nào đó.

Thực tế: 1 cây B-Tree 4 tầng với 4KB mỗi page và branching_factor=500 có thể lưu trữ lên tới 256TB.

Chú ý khi sử dụng B-Tree index

Cũng như các bài trước, phía trên mới chỉ dừng lại ở nguyên lý cơ bản. Để chạy được trong môi trường thực tế, ta cần phải lưu ý và trau chuốt rất nhiều chi tiết như sau:

• Xử lý khi bị crash: trong trường hợp crash, dữ liệu rất dễ bị hỏng (kiểu dạng như đang ghi được 1 nửa thì bị đứt).
  • Cách khắc phục đơn giản nhất đó là trước mỗi lần ghi xuống disk, ta cần phải backup trước vào 1 append-only file. File này có tên gọi là Write Ahead Log (WAL), được sử dụng để khôi phục dữ liệu sau khi ta khởi động DB trở lại.
  • Cách thứ 2 được 1 số loại DB sử dụng đó là copy-on-write: kết quả update của page sẽ được ghi vào 1 địa chỉ mới, thay vì ghi đè lên địa chỉ cũ. Sau đó ta cập nhật lại tham chiếu từ page cha nối tới địa chỉ mới.
• Khi có nhiều tiến trình cùng update trên 1 page: ta cần phải có cơ chế lock để đảm bảo dữ liệu page được nhất quán.
• Tối ưu không gian lưu trữ page bằng cách chỉ lưu dạng rút gọn của key đối với những page cha, vừa đủ để đánh dấu bao ngoài của page con. Ví dụ: (AAAAA, BBBBB) -> (A, B).
• Bổ sung thêm con trỏ nối tới các page sibling, giúp tiết kiệm được chi phí truy vấn trên 1 dải key lớn, đỡ được việc phải jump qua jump lại giữa page con và page cha.

So sánh với LSM-Tree

Như đã từng đề cập ở bài Database 102: Hash Index, B-Tree đi theo trường phái random write, nên ta có thể thấy ngay được rằng nó sẽ ghi chậm hơn so với LSM-Tree (sử dụng sequential write). Ngược lại, B-Tree lại tối ưu cho việc truy vấn hơn. Việc đọc trên LSM-Tree chậm hơn là bởi vì ta sẽ phải duyệt qua rất nhiều cấu trúc dữ liệu khác nhau và rất nhiều tầng SSTable.

Ưu điểm của LSM-Tree so với B-Tree

• B-Tree phải ghi 2 lần xuống disk: 1 lần để ghi vào WAL, và 1 lần để cập nhật dữ liệu của cây (chưa kể tới việc page bị chia làm 2 vì không đủ không gian cấp phát). Điều này gây lãng phí vì thông thường ta chỉ thay đổi có một vài byte.
• LSM-Tree sử dụng sequential write nên hiệu suất khi ghi của nó là cao hơn hẳn so với B-Tree, đặc biệt là trên các ổ đĩa từ tính (như HDD).
• LSM-Tree nén dữ liệu tốt hơn, thông thường kích thước dữ liệu trên disk của LSM-Tree là nhỏ hơn so với B-Tree (đặc biệt là khi sử dụng Leveled Compaction). Chưa kể, B-Tree còn hay bị xảy ra hiện tượng phân đoạn trong, khi không sử dụng hết các không gian đã được cấp phát.
• B-Tree Index tận dụng lại cơ chế đọc ghi file theo từng block của ổ đĩa (1 số tài liệu gọi là page), cho nên kích thước mỗi bản ghi sẽ chỉ gói gọn không được phép vượt quá 1 block. Mỗi khi xóa hoặc thêm/cập nhật bản ghi, B-Tree sẽ phải kiểm tra và rebalance lại chiều cao của cây (nếu cần thiết), gây tốn kém hơn LSM-Tree rất nhiều.

Nhược điểm của LSM-Tree so với B-Tree

• Quá trình compaction của LSM-Tree có thể gây ảnh hưởng tới hiệu suất đọc-ghi của DB. Trong trường hợp tài nguyên có hạn, các request sẽ phải chờ đợi nhường cho tiến trình compaction hoàn thành, dẫn tới response time bị nhảy vọt lên 1 cách khó hiểu, sau đó lại trở lại bình thường. Điều này khiến cho dev của ứng dụng khó debug và lý giải được nguyên nhân.
• Quá trình compaction tiêu tốn nhiều Disk I/O, sẽ bóp băng thông của các tiến trình ghi khác quan trọng hơn (ghi memtable xuống SSTable, log vào append-only file để khôi phục memtable nếu crash).
• Nếu cấu hình compact không hợp lý, sẽ dẫn tới tình trạng tốc độ compaction sẽ không theo kịp với tốc độ ghi vào của dữ liệu (Xem thêm ở phần Leveled Compaction trong bài Database 103: SSTable và LSM-Tree).
• Mỗi key của B-Tree chỉ xuất hiện ở 1 nơi trong Disk, không bị phân tán ra khắp các Segment như LSM-Tree. Số lượng tầng page cũng không lớn, nên tốc độ đọc của B-Tree là nhanh hơn.
• B-Tree phù hợp với các loại DB cần tới tính năng transaction cực mạnh: ở rất nhiều RDMS, transaction ở mức độ cô lập được thực thi bằng cách lock trên nhiều dải Key cùng 1 lúc. Điều này có thể dễ dàng làm được với B-Tree bằng cách lock trực tiếp trên page.