Post #1138

Bloom filter Asosan LSM-tree (Log Structured Merge-tree) ga asoslangan ma'lumotlar bazasida qidirilayotgan key bor yoki yo'qligini O(1) tezlikda aniqlab beradigan kuchli va foydali qurol. Tarkibiy tuzilishi — n uzunlikdagi bitlar massivi — k ta hash-funksiya Qanday ishlaydi? DB ga qo'shilayotgan key k marta heshlanadi va natija bilan mos bo'lgan bitlar massividagi indekslar 1 bilan to'ldiriladi. Keyingi safar key qidirilayotganda key k marta heshlanib, mos indekslardagi qiymat tekshiriladi, agar birortasi 0 bo'lib qolsa, demak bunday key DB ga umuman qo'shilmagan. Nima uchun ishlatiladi? Umuman DB da yo'q bo'lgan key kelganida ortiqcha harakat qilib tekshirib chiqish o'rniga, qo'shilmagan bo'lsa qaytarib yuboradi. Ustunlik tomoni shu yerda. Agar bor bo'lsa, keyin kirib tekshiradi. Bilish muhim Tekshiruv false negative, ya'ni agar yo'q bo'lsa, umuman yo'q. False positive holati ham bor, ya'ni bor desa ham, ehtimol bor, balki qidiruv payti chiqmasligi ham mumkin. @it_suhbat