proto.lib

B-tree vs LSM-tree - Storage Engine

So sánh B-tree (cập nhật tại chỗ, tối ưu đọc) và LSM-tree (ghi vào memtable rồi flush SSTable, tối ưu ghi) cùng đánh đổi read/write amplification.

DatabasesNâng cao2026-07-10
B-tree vs LSM-tree - Storage Engine

Tags

#b-tree#lsm-tree#storage-engine#sstable#compaction

Tài liệu tham khảo

Mở rộng

Animation gốc là một file HTML tự chứa, có thể nhúng lại ở bất kỳ trang nào khác. Mở file gốc

Liên quan

DatabasesNâng cao

LSM Compaction: Leveled vs Tiered

Leveled compaction gộp SSTable thành các tầng không chồng lấn để đọc nhanh, còn tiered compaction gộp các SSTable cùng kích thước để ghi nhanh hơn với write amplification thấp hơn.

#lsm-tree#compaction#leveled#tiered
DatabasesTrung bình

LSM-Tree - Bloom Filter cho SSTable

Mỗi SSTable trong LSM-tree có một bloom filter riêng để nhanh chóng loại bỏ các file chắc chắn không chứa key, giảm số lần đọc đĩa không cần thiết.

#lsm-tree#bloom-filter#sstable#read-amplification
DatabasesNâng cao

B-tree Page Split và Merge

Insert vào leaf B-tree đầy gây page split, đẩy separator key lên node cha; delete có thể gộp các trang thưa để giữ cây cân bằng.

#b-tree#page-split#index-structure#tree-balance