Bloom Filter
ব্লুম ফিল্টার
Probabilistic set membership — 'সম্ভবত আছে' বা 'নিশ্চিত নেই' বলে; false positive আছে, false negative কখনো নেই।
m-bit array + k hash function; add-এ k বিট set, query-তে সব 1 হলে “হয়তো আছে”:
idx = [(h1 + i * h2) % m for i in range(k)] # double hashing
present = all(bits[i] for i in idx)- Memory: ~9.6 bit/key @ 1% FP — hash table-এর key+pointer-এর দশমাংশও না
- FPR formula: p ≈ (1 − e^(−kn/m))^k; k = (m/n)·ln2 optimal
- Delete করা যায় না — bit share হয়; দরকার হলে counting bloom (counter array)
LSM-এ প্রতি SSTable-এ একটা — “নেই” বললেই ওই ফাইল খোলা বাদ, read path-এর সবচেয়ে সস্তা ছাঁকনি।