Nguồn: Bytebytego
Tóm tắt
Mỗi database engine đều phải giải quyết một bài toán cơ bản: dữ liệu nằm trên đĩa và truy cập đĩa chậm. Cách tổ chức dữ liệu trên đĩa quyết định toàn bộ hiệu năng của hệ thống. Sau nhiều thập kỷ nghiên cứu, hai cách tiếp cận chính đã nổi lên là B-Trees và LSM Trees (Log-Structured Merge Trees).
B-Trees giữ dữ liệu được sắp xếp trên đĩa để đọc nhanh, nhưng phải trả chi phí cho mỗi lần ghi. Ngược lại, LSM Trees buffer các lần ghi trong bộ nhớ và flush chúng xuống đĩa theo từng khối lớn, làm cho ghi rẻ hơn nhưng đọc tốn kém hơn. Hai cách tiếp cận này đại diện cho hai điểm khác nhau trên đường đánh đổi read-write performance.
Hiểu được sự khác biệt giữa B-Trees và LSM Trees là một trong những mental model hữu ích nhất trong system design. Các database như PostgreSQL và MySQL sử dụng B-Trees cho write-heavy workloads có cân bằng đọc/ghi, trong khi Cassandra, RocksDB và LevelDB sử dụng LSM Trees cho các tình huống ghi cực kỳ nhiều.