ساختار داده Bloom Filters

یکی از ساختارهای داده ای که مخصوصا در دیتابیس ها خیلی کاربرد داره Bloom Filters هست.
این مقاله بصورت visualize خیلی توضیحات مفیدی در مورد این موضوع ارائه داده.
https://samwho.dev/bloom-filters

یکی از کاربردهای اصلی ش اینه که دیتابیس خیلی زود متوجه بشه که رکورد مورد نظر با key یا id مورد نظر آیا اصلا وجود داره یا خیر؟
چرا باید زود متوجه بشه؟ چون اگه متوجه نشه کلید مد نظر وجود داره یا نه، مجبور میشه کل disk pageهای جدول دیتابیس رو scan کنه که متوجه بشه کلید وجود نداره...
و این هزینه سنگینی برای دیتابیس محسوب میشه
ولی با استفاده از Bloom Filters دیتابیس با درصد خطای خیلی کم میتونه برای اکثر موارد کلیدهایی که در دیتابیس وجود ندارن رو تشخیص بده و هزینه زیادی برای رکوردهایی که وجود ندارن نپردازه.

@gocasts