مسئله: Yelp/اسنپفود بساز — «رستورانهای باز در شعاع ۲ کیلومتری من، مرتبشده». چالش: مختصات دوبُعدی است و ایندکسهای معمولی تکبُعدیاند؛ و نزدیکی باید در میلیثانیه محاسبه شود.
۱-۲) نیازمندی و تخمین
- FR: ثبت/بهروزرسانی مکان کسبوکار، جستجوی شعاعی + فیلتر (باز بودن، امتیاز)، مرتبسازی بر فاصله.
- NFR: خواندن سنگین (هر اسکرول نقشه یک کوئری)، p99 <100ms ؛ نوشتن نسبتاً سبک.
- تخمین: ۱M کسبوکار، 50K QPS جستجو در پیک — نیازمند ایندکس مکانی، نه اسکن همه نقاط و محاسبه فاصله.
۳) طراحی — تبدیل دو بُعد به یک
دو راه کلاسیک: (الف) Geohash: نقشه را به شبکه بازگشتی تقسیم و هر خانه را با رشتهای کد میکند که پیشوند مشترک = همسایگی؛ کوئری شعاعی = چند بازه پیشوندی روی ایندکس معمولی B-Tree (درس ۱۲). (ب) Quadtree/شبکه: درخت چهارگانه که فضا را بازگشتی چهار قسمت میکند؛ در حافظه برای موتورهای تخصصی. دیتابیسهای مدرن (PostGIS ،Elasticsearch geo ،Mongo 2dsphere) هر دو را درون خود دارند — تو انتخاب میکنی، نه پیادهسازی.
۴) عمق و گلوگاه
- لبههای Geohash: نقاط نزدیکِ سرِ مرز دو خانه، پیشوند متفاوت دارند — همیشه خانههای همسایه را هم در کوئری بگیر و فاصله دقیق را آخرِ کار فیلتر کن.
- تراکم ناهموار: مرکز شهر هزار نقطه در یک خانه، روستا یکی — سلولها باید تطبیقی ریز/درشت شوند (همان کار S2 گوگل میکند).
- موجودی زنده (رستوران باز است؟) را در فیلتر بیاور ولی «ظرفیت» مثل غذای آماده را از سرویس دیگر بخوان — ترکیب نتایج مکانی با سرویسهای دامنه، مرز میکروسرویسهاست.
- کش: پرسوجوهای محبوب (مرکز شهر در ظهر) را با کلید geohash گِردشده کش کن — دقت یک خانه برای بیشتر کاربران کافی است.
به زبان ساده
جستجوی نزدیکترینها یعنی تبدیل نقشه دوبُعدی به کدهای تکبُعدی (Geohash) که ایندکس معمولی بفهمد، و بعد فیلتر دقیق فاصله در پایان.
مثال واقعی
مثل کدپستی: بهجای گشتن کل شهر برای داروخانه نزدیک، اول محلههای همکد را نگاه میکنی و بعد بین همان چند تا، نزدیکترین را با خطکش دقیق میسنجی.