Quadtree

در این پست، بیایید ساختار داده دیگری را برای یافتن رستوران‌های نزدیک در اپلیکیشن سفارش غذا یا Google Maps بررسی کنیم.

Quadtree یک ساختار داده است که معمولاً برای تقسیم یک فضای دو بعدی با تقسیم مجدد آن به چهار ربع (grids) تا زمانی که محتویات گریدها معیارهای خاصی را برآورده کنند، استفاده می‌شود (نمودار اول را ببینید).

Quadtree یک ساختار داده درون حافظه (𝐢𝐧-𝐦𝐞𝐦𝐨𝐫𝐲) است و یک راه حل پایگاه داده‌ای نیست. در هر سرور LBS/Location-Based Service (سرویس مبتنی بر مکان) اجرا می‌شود و ساختار داده در زمان راه‌اندازی سرور ساخته می‌شود.

نمودار دوم فرایند ساخت Quadtree را با جزئیات بیشتری توضیح می‌دهد. گره ریشه کل نقشه جهان را نمایش می‌دهد. گره ریشه به طور مجدد به 4 ربع شکسته می‌شود تا زمانی که گره‌ای با بیش از 100 کسب و کار باقی نماند.

چگونه با Quadtree مربوط به کسب و کارهای نزدیک را پیدا کنیم؟

• Quadtree را در حافظه بسازید.
• پس از ساخت Quadtree ، جستجو را از ریشه شروع کنید و درخت را طی کنید، تا گره برگی که مبدأ جستجو در آن قرار دارد را پیدا کنید.
• اگر آن گره، برگی از 100 کسب و کار دارد، گره را برگردانید. در غیر این صورت، کسب و کارها را از همسایگان آن اضافه کنید تا تعداد کافی کسب و کار برگردانده شود

به روزرسانی سرور LBS و بازسازی Quadtree

• ساخت یک Quadtree در حافظه با 200 میلیون کسب و کار در زمان راه اندازی سرور ممکن است چند دقیقه طول بکشد.
• در حالی که Quadtree در حال ساخته شدن است، سرور نمی تواند ترافیک را پردازش کند.
• بنابراین، باید یک نسخه جدید از سرور را به صورت تدریجی در یک زیرمجموعه کوچک از سرورها در هر زمان اجرا کنیم. این از آفلاین شدن بخش بزرگی از خوشه سرور (server cluster) و ایجاد اختلال در سرویس جلوگیری می کند.