Database hay gặpBloom filter là cấu trúc dữ liệu xác suất, tiết kiệm bộ nhớ để kiểm tra một phần tử có thuộc tập hợp hay không. Cấu tạo: một mảng bit và k hàm băm; khi thêm phần tử, băm nó ra k vị trí và bật các bit đó lên. Khi kiểm tra, nếu bất kỳ bit tương ứng bằng 0 → chắc chắn KHÔNG có; nếu tất cả bằng 1 → có thể có (có xác suất dương giả).
Đặc tính then chốt:
- Không có âm giả (false negative): đã nói "không có" thì chắc chắn không có.
- Có dương giả (false positive): đôi khi nói "có thể có" nhưng thực ra không — chấp nhận đánh đổi này để cực kỳ nhỏ gọn.
- Bản chuẩn không xóa được phần tử (có biến thể counting để xóa).
Dùng trong backend để tránh thao tác đắt tiền cho phần tử không tồn tại:
- Chống cache penetration: trước khi truy vấn DB/đĩa, hỏi Bloom filter — nếu "chắc chắn không có" thì bỏ qua luôn, khỏi tốn một lần đọc.
- LSM-tree database (Cassandra, RocksDB, HBase): mỗi SSTable có Bloom filter để bỏ qua file chắc chắn không chứa key, giảm số lần đọc đĩa.
- Chống trùng (đã thấy URL/email chưa), lọc sơ bộ ở CDN/proxy.