B-tree và LSM-tree khác nhau thế nào? Vì sao NoSQL ghi-nhiều hay dùng LSM?

Đây là hai kiểu storage engine (cách sắp xếp dữ liệu trên đĩa) đằng sau các DB:

B-tree (PostgreSQL, MySQL InnoDB, hầu hết SQL):
- Cập nhật tại chỗ (in-place) trên các trang có thứ tự; đọc theo khóa/khoảng nhanh và ổn định (O(log n)).
- Ghi thường là ghi ngẫu nhiên tới trang cần sửa → chậm hơn khi ghi rất nhiều; đọc thì tối ưu.

LSM-tree (Log-Structured Merge-tree — Cassandra, RocksDB/LevelDB, HBase, ScyllaDB):
- Ghi vào buffer trong bộ nhớ (memtable) + append vào log, rồi flush thành các file bất biến (SSTable) có thứ tự → ghi là tuần tự (sequential), throughput ghi rất cao.
- Định kỳ compaction trộn các SSTable, loại bản ghi cũ/đã xóa (tombstone).
- Đánh đổi: một khóa có thể nằm ở nhiều SSTable → đọc có thể phải kiểm nhiều tầng (giảm bằng bloom filter + compaction); có write/read/space amplification.

Vì sao ghi-nhiều dùng LSM: ghi tuần tự nhanh hơn ghi ngẫu nhiên của B-tree, tối ưu cho khối lượng insert lớn (log, time-series, telemetry) — đúng như mô tả LSM "hợp file có lượng insert cao". Nói ngắn: B-tree tối ưu đọc & cập nhật tại chỗ; LSM tối ưu ghi tuần tự khối lượng lớn, đổi lại đọc và compaction phức tạp hơn.