Bloom Filter
Định nghĩa
Bloom filter là cấu trúc dữ liệu xác suất cho biết một key chắc chắn không tồn tại hoặc có thể tồn tại trong một tập.
Cách hiểu bằng lời của tôi
Bloom filter là bộ lọc rẻ trước khi đọc disk. Nếu nó nói “không có”, ta tin chắc và bỏ qua file. Nếu nó nói “có thể có”, ta vẫn phải kiểm tra thật vì có false positive.
Trong LSM Tree
Mỗi SSTable có thể gắn Bloom filter. Khi đọc một key, storage engine dùng Bloom filter để bỏ qua các SSTable chắc chắn không chứa key, giảm read amplification.