جستجوی مجاورت در طراحی سیستم

جستجوی مجاورت (Proximity Search) از آن موضوعات عجیب و خاصی است که به‌نوعی به موضوع تکراری مصاحبه‌های طراحی سیستم تبدیل شده. هر وقت بر اساس موقعیت جستجو می‌کنید، نه بر اساس شناسه یا مقدار، ظاهر می‌شود، مثل راننده‌های نزدیک مسافر، رستوران‌های نزدیک کاربر یا آدم‌های نزدیک یک مکان.

در نگاه اول سخت به نظر نمی‌رسد، چون پایگاه‌های داده در مرتب‌سازی عالی‌اند. مثلاً می‌توانیم از پایگاه داده بخواهیم همه‌ی کاربران بین ۲۰ تا ۲۵ سال را پیدا کند و ظرف میلی‌ثانیه‌ها برمی‌گردد. پس چرا پیدا کردن همه‌ی راننده‌های در شعاع ۲ کیلومتری مسافر جواب نمی‌دهد؟ این دو Query روی همان پایگاه داده و همان حجم داده می‌خورند، اما یکی فوراً برمی‌گردد و دیگری به Full Table Scan تبدیل می‌شود.

Query سن سریع است چون B-tree کلیدهای مرتب را کنار هم روی دیسک نگه می‌دارد. ۲۰ کنار ۲۱ است که کنار ۲۲ است، همه روی همان Page، پس درخواست «همه‌ی بین ۲۰ و ۳۰» به یک Seek و بعد خواندن ترتیبی کوتاه تبدیل می‌شود، که تقریباً آسان‌ترین چیزی است که می‌توانید از پایگاه داده‌ی مدرن بخواهید.

موقعیت به همین شکل کار نمی‌کند. دو عدد دارید، عرض جغرافیایی (Latitude) و طول جغرافیایی (Longitude)، و چیزی که واقعاً به آن اهمیت می‌دهید فاصله‌ی خط مستقیم بین نقاط است. یک B-tree فقط می‌داند هر بار بر اساس یکی از آن اعداد مرتب کند. روی عرض جغرافیایی Index بگذارید و نواری افقی از زمین می‌گیرید. روی طول جغرافیایی Index بگذارید و نواری عمودی. حتی Index ترکیبی روی هر دو ستون هم نجاتتان نمی‌دهد، چون B-tree بر اساس ستون اول مرتب می‌کند و فقط برای شکستن تساوی از دومی استفاده می‌کند، پس پایگاه داده عملاً هنوز بر اساس یک بُعد مرتب می‌کند و نواری که برمی‌گرداند هنوز میلیون‌ها ردیف دارد، که هیچ‌کدام بر اساس فاصله از مسافر رتبه‌بندی نشده‌اند. پس به نسخه‌ی Brute-force برمی‌گردد: فاصله‌ی واقعی هر راننده تا مسافر را ردیف‌به‌ردیف محاسبه می‌کند و همه‌ی آن‌هایی که بیش از ۲ کیلومتر دورند را کنار می‌گذارد.

مشکل ریشه‌ای این است که ترتیب مرتب‌سازی یک‌بُعدی نمی‌تواند نزدیکی دوبُعدی را حفظ کند. نقشه را به محور مرتب واحد صاف کنید و نقاطی که روی زمین همسایه‌اند می‌توانند در Index دور از هم بیفتند. بقیه‌ی این مطلب درباره‌ی دو راهی است که سیستم‌های Production به اندازه‌ی کافی از آن نزدیکی را بازیابی می‌کنند تا Index دوباره مفید شود.

تقریباً هر سیستمی که در مصاحبه سراغش می‌روید یکی از دو رویکرد را می‌گیرد و اینکه کدام مناسب است به شکل داده‌تان بستگی دارد. اگر داده‌تان هندسی است، پر از چندضلعی، جاده و منطقه‌ی تحویل که در آن‌ها شمول و تقاطع مهم است، درخت سفارشی می‌خواهید که اشکال را بفهمد، که چیزی است که PostGIS و Elasticsearch می‌دهند. اگر داده‌تان بیشتر نقطه‌هایی است که مدام حرکت می‌کنند، مثل راننده‌ها یا موقعیت‌های زنده‌ی کاربر، می‌خواهید هر موقعیت را به یک کلید مرتب‌پذیر صاف کنید که Index معمولی از قبل مدیریتش می‌کند، که ترفند پشت Redis Geospatial، Geohash، S2 و H3 است. وقتی بدانید سیستمی کدام رویکرد را می‌گیرد، Trade-offهایش خودشان بیرون می‌افتند.

یک ایده‌ی دیگر کل این حوزه را به هم گره می‌زند. Index فضایی تقریباً هرگز خودش پاسخ نهایی را نمی‌دهد. کاری که می‌کند تبدیل «همه‌ی ردیف‌ها را بررسی کن» به «مجموعه‌ی کوچک کاندیدا را بررسی کن» است، و بعد کار را با محاسبه‌ی فاصله‌ی دقیق یا هندسه روی آن مشت کاندیدا تمام می‌کنید. هر ساختاری که الان نگاه می‌کنیم فقط راه متفاوتی برای تولید ارزان آن مجموعه‌ی کاندیدا است.

درخت‌های فضایی سفارشی

رویکرد اول درخت ساخته‌شده برای داده‌ی فضایی می‌سازد. ترفندی که این‌ها را در پایگاه داده کار می‌کند، نه فقط در حافظه، شکل دادن درخت است تا روی دیسک مثل B-tree رفتار کند، با گره‌های متعادل هم‌اندازه‌ی Page و عمق قابل‌پیش‌بینی. سه تا را مرور می‌کنیم و هرکدام مشکلی را حل می‌کند که طراحی قبلی نتوانست، پس پیشرفت مثل زنجیره‌ی تمیز اصلاح‌ها خوانده می‌شود، نه انبوه ساختارهای نامرتبط.

Quadtree

Quadtree اول آمد و هنوز تمیزترین راه ساختن شهود برای کل مسئله است. ترفند این است که خود نقشه را به درخت تبدیل کنید. کل نقشه گره‌ی ریشه است. آن را به چهار ربع تقسیم می‌کنید و هر ربع یکی از چهار فرزندش می‌شود. هر ربعی که هنوز نقطه‌ی زیاد دارد دوباره به چهار تقسیم می‌شود و سطح دیگری زیرش رشد می‌کند، و بازگشتی ادامه می‌دهید تا هر برگ به‌اندازه‌ی کافی نقطه‌ی کم داشته باشد که مستقیم اسکن شود. آن تقسیم چهارراهه در هر گره اسم Quadtree را می‌دهد و خود نقطه‌ها فقط در برگ‌ها زندگی می‌کنند.

برای جستجو، از ریشه پایین می‌روید و در هر گره نقطه‌ی Query را با نقطه‌ی میانی سلول مقایسه می‌کنید، شمال یا جنوب و شرق یا غرب، و در ربع مطابق فرود می‌آیید تا به برگ برسید. نقاط آن برگ، به‌علاوه‌ی چند نقطه‌ی برگ‌های همسایه تا کسی که درست آن سوی مرز نشسته را از دست ندهید، مجموعه‌ی کاندیدای شما هستند و محاسبه‌ی فاصله‌ی دقیق روی آن مجموعه‌ی کوچک برنده‌ها را برمی‌دارد.

یکی از بهترین چیزهای Quadtree این است که با چگالی داده‌تان سازگار می‌شود. محله‌ای مثل منهتن، پر از پین، به درخت عمیق تبدیل می‌شود، در حالی که دریاچه‌ای در شمال ایالت یک سلول درشت می‌ماند چون چیزی آنجا ارزش Index شدن ندارد، پس هرگز فضا را برای تقسیم آب خالی هدر نمی‌دهید.

دردسر در مقیاس به دو شکل ظاهر می‌شود. اولی عمق است. تقسیم‌ها همیشه در نقطه‌ی میانی هندسی سلول فرود می‌آیند، نه جایی که داده نشسته، پس خوشه‌ی متراکم مثل منهتن مدام نصف می‌شود تا نقاط سرانجام جدا شوند. ممکن است ده سطح یا بیشتر برای رسیدن به برگ در مرکز شهر خرج کنید در حالی که Query در ورمونت روستایی در دو سطح تمام می‌شود. Latency حالا به جایی که نگاه می‌کنید بستگی دارد و شلوغ‌ترین مناطق کندترین‌اند، پس استدلال درباره‌ی بدترین عملکرد آسان نیست.

دومی دیسک است. Quadtree ساختار اشاره‌گر (Pointer) است، پس هر گره در آدرس دلخواهی می‌نشیند که اشاره‌گر به فرزندانش را نگه می‌دارد. وقتی کل درخت در RAM زندگی می‌کند خوب است، جایی که دنبال کردن اشاره‌گر جستجوی ارزان حافظه است، ولی پایگاه داده نمی‌تواند این را فرض کند. از دیسک در Pageهای با اندازه‌ی ثابت می‌خواند و هر اشاره‌گری که دنبال می‌کنید خطر خواندن تصادفی برای Page ای دارد که هنوز بارگذاری نشده، پس چند پرش بعد بیشتر منتظر دیسک هستید تا انجام کار.

Quadtreeها هنوز همه‌جا در حافظه هستند، از کاشی‌های Google Maps تا تشخیص برخورد در موتورهای بازی، ولی برای Indexی که باید روی دیسک زندگی کند و وقتی از RAM سرریز کرد سریع بماند، چیز مقاوم‌تری لازم است.

درخت‌های k-d و BKD

بعد پسرعموی دودویی می‌آید، درخت k-d.

به‌جای تقسیم روی همه‌ی ابعاد هم‌زمان به چهار ربع، درخت k-d بینشان متناوب می‌شود. سطح اول درخت روی مختصات x تقسیم می‌کند، سطح بعدی روی y، سطح بعد از آن دوباره به x برمی‌گردد و همین‌طور، با پایین رفتن هر بار یک بُعد را چرخشی می‌گیرد. چیزی که می‌گیرید درخت دودویی برای داده‌ی چندبُعدی است، متعادل تا وقتی همیشه روی میانه تقسیم کنید، و دهه‌ها اسب کار جستجوی نزدیک‌ترین همسایه بود.

آن تقسیم میانه همه‌ی تفاوت با Quadtree است و ارزش ملموس کردن دارد. ده راننده را در یک خیابان تصور کنید، نه تا در انتهای شرقی جمع‌شده و یک نفر عقب‌مانده در غرب. Quadtree در میانه‌ی هندسی بلوک می‌برد، پس اولین تقسیمش راننده‌ی غربی تنها را یک طرف می‌گذارد و هر نه تا را فشرده در طرف دیگر. حالا نیمه‌ی شلوغ باید دوباره و دوباره تقسیم شود، هر برش از میان فضای عمدتاً خالی می‌گذرد تا خوشه را جدا کند. این همان مشکل منهتن از قبل است. درخت k-d به‌جای آن روی میانه می‌برد، راننده‌ی پنجم از غرب، پس خط جداکننده درست وسط جمعیت فرود می‌آید که جداسازی واقعاً لازم است، و پنج راننده در هر طرف می‌ماند هر چقدر خیابان نامتقارن باشد. هر برش تعداد نقاط را نصف می‌کند، نه مساحت را، که درخت k-d را در عمق ( \log n ) متعادل نگه می‌دارد چه مرکز شلوغ شهر را Index کنید چه امتداد خالی بزرگراه را.

همان مشکل دیسک Quadtree را به ارث می‌برد. همه‌اش اشاره‌گر است، بدون نگاشت تمیز به Page دیسک، که آن را در حافظه سریع و وقتی باید جایی بزرگ‌تر از RAM زندگی کند دردناک می‌کند.

راه‌حل مدرن درخت BKD است، مخفف block k-d tree. به‌جای یک نقطه برای هر گره، نقطه‌ها در بلوک‌هایی هم‌اندازه‌ی Page دیسک بسته‌بندی می‌شوند و کل درخت یک بار از دسته‌ی داده ساخته می‌شود. این BKD را اساساً Write-once می‌کند، ساخته‌شده برای تکه‌ای داده که تغییر نمی‌کند، محدودیتی که هنگام صحبت از راننده‌های متحرک به آن برمی‌گردیم.

این چیزی است که Elasticsearch برای فیلدهای جغرافیایی‌اش استفاده می‌کند. (طبق مستندات Elasticsearch، نوع geo_point از درخت BKD برای Index کردن مختصات استفاده می‌کند.) پس Query جغرافیایی در Elasticsearch واقعاً همان ایده‌ی درخت k-d است که در Index مناسب دیسک و بلوک‌ساخت‌یافته‌ای که پایگاه داده می‌تواند تکیه کند بسته‌بندی شده.

R-tree

R-tree اولین Index فضایی بود که از پایه برای استفاده‌ی پایگاه داده روی دیسک ساخته شد و دو مشکل را حل کرد که درخت‌های قبلی نتوانستند.

اولی مشکل اشکال بود. هر Indexی که تا حالا دیده بودیم فرض می‌کرد داده‌تان نقطه است، چیزی که در یک عرض و طول زندگی می‌کند، مثل راننده، پین یا موقعیت کاربر. داده‌ی جغرافیایی واقعی همیشه این‌قدر همکار نیست. بزرگراه خط است، شهرستان چندضلعی است و حتی Starbucks، که خودش نقطه است، منطقه‌ی تحویل دارد که چندضلعی است. نمی‌توانید به‌طور معناداری شهرستان را در یک سلول Quadtree بگذارید، چون شهرستان در یک نقطه نمی‌نشیند و روی سلول‌های زیاد پهن می‌شود.

دومی مشکل دیسک بود، همان قیدی که هر ساختار قبلی را شکست داده بود. Index پایگاه داده معادل فضایی B-tree می‌خواهد، چیزی که با تغییر داده متعادل می‌ماند، سریع از دیسک می‌خواند و هر بار راننده حرکت می‌کند ارزان به‌روز می‌شود. ساختارهای اشاره‌گر-سنگین درون‌حافظه‌ای قبلی برای چیزی که باید روی دیسک زندگی کند جواب نمی‌دادند.

جواب R-tree کوچک‌ترین مستطیل محاط (Minimum Bounding Rectangle) بود. ایده این است که هر شیء را در کوچک‌ترین مستطیلی که کاملاً در بر دارد بپیچید، با اضلاع موازی محورهای عرض و طول جغرافیایی. نقطه به مستطیل تباهیده با عرض و ارتفاع صفر تبدیل می‌شود، بزرگراه به تکه‌ی باریک بلند و شهرستان به جعبه‌ی بزرگ پهن‌شده. وقتی همه‌چیز پیچیده شد، مستطیل‌های نزدیک داخل مستطیل محاط بزرگ‌تر گروه می‌شوند، آن گروه‌ها در مستطیل‌های بزرگ‌تر محاط می‌شوند و تودرتویی تا ریشه ادامه می‌یابد.

آنچه این را به Index پایگاه داده تبدیل می‌کند این است که درخت دقیقاً مثل B-tree متعادل می‌ماند. هر برگ در عمق یکسان است، پس هر Query تعداد قابل‌پیش‌بینی یکسانی Page لمس می‌کند، و هر گره طوری اندازه شده که در یک Page دیسک جا شود. Insert و Delete با تقسیم و ادغام آن Pageها کل را متعادل نگه می‌دارند، دقیقاً مثل B-tree معمولی.

برخلاف سلول‌های Quadtree، مستطیل‌های R-tree می‌توانند هم‌پوشانی داشته باشند و آن هم‌پوشانی Trade-off است که باید مراقبش بود. اگر نقطه‌ی Query شما هم‌زمان داخل دو مستطیل محاط فرود بیاید، باید هر دو شاخه را پایین بروید و هر دو زیردرخت را بررسی کنید. استراتژی درج شلخته هم‌پوشانی زیاد می‌سازد، یعنی شاخه‌ی زیاد برای دنبال کردن، که عملکرد را پایین می‌کشد. راه‌حلی که همه واقعاً Ship می‌کنند R*-tree است، اصلاحی که هم‌پوشانی را با ابتکارهای هوشمندانه‌تر درج کم نگه می‌دارد، و آن ابتکارها چیزی هستند که تقریباً هر پیاده‌سازی مدرن R-tree بر آن بنا شده.

R-treeها اسب کار Indexهای فضایی Production هستند. PostGIS Indexهای فضایی‌اش را روی چارچوب GiST در Postgres می‌سازد، که رفتار شبیه R-tree بر پایه‌ی Bounding Box می‌دهد، در حالی که SQLite و Oracle Spatial انواع R-tree خودشان را ارائه می‌دهند. اگر مسئله‌ی شما هندسه‌ی واقعی را شامل می‌شود، مثل «آیا این منطقه‌ی تحویل این آدرس را در بر دارد» یا «آیا این جاده از این شهرستان عبور می‌کند»، این رویکردی است که می‌خواهید.

کلیدهای رمزگذاری‌شده (Encoded Keys)

هر درخت فضایی که الان دیدیم ساختار سفارشی است و همه کار می‌کنند، ولی ماشین‌آلات زیادی برای حمل هستند. پایگاه داده‌تان به کد Indexing ویژه، کد Query ویژه، ابزار ویژه و معمولاً افزونه‌ی فضایی اختصاصی نصب‌شده نیاز دارد پیش از اینکه هیچ‌کدام اجرا شود.

رویکرد کلید رمزگذاری‌شده درخت سفارشی را کاملاً دور می‌زند. به‌جای آن هر عرض و طول را به شناسه‌ی سلول یا کلید مرتب‌پذیر تبدیل می‌کنید که Index معمولی (مثل B-tree) می‌تواند استفاده کند تا جستجو را به تکه‌ی کوچکی از نقشه تنگ کند.

این رویکرد محبوب است چون زیرساختی را که هر پایگاه داده‌ای از قبل دارد دوباره استفاده می‌کند.

Geohash

Geohash ریاضیات Space-filling Curve چندین‌ساله را به چیزی تبدیل می‌کند که با چند خط کد محاسبه می‌شود. Space-filling Curve فقط یک خط است که در فضای دوبُعدی رشته می‌شود طوری که نقاط نزدیک روی نقشه روی خط هم نزدیک بمانند.

ایده آن‌قدر ساده است که در ذهن جا می‌شود. کل جهان را به شبکه‌ی ۳۲ سلولی تقسیم می‌کنید و هر کدام را با یک کاراکتر برچسب می‌زنید. موقعیت شما در یکی از آن‌ها می‌افتد و آن کاراکتر اول شماست. حالا آن سلول را به ۳۲ سلول کوچک‌تر تقسیم کنید. موقعیت شما در یکی از آن‌ها می‌افتد و آن کاراکتر دوم است. تا هر عمقی می‌خواهید بازگشتی ادامه دهید. هر کاراکتر اضافه بیشتر زوم می‌کند، پس Geohash پنج‌کاراکتری تقریباً پنج کیلومتر عرض دارد و نه کاراکتر شما را به حدود پنج متر می‌رساند.

زیر رشته، Geohash فقط بیت است. هر کاراکتر یکی از ۳۲ گزینه را انتخاب می‌کند، که دقیقاً ۵ بیت است، پس رشته‌ی dr5ru ۲۵ بیت است که در پنج حرف برای خواندن انسان گروه شده. همان ۲۵ بیت را مستقیم به‌عنوان عدد بخوانید و عدد صحیحی با همان بیت‌ها به همان ترتیب دارید. به همین دلیل Redis می‌تواند Geohash را به‌صورت عدد صحیح ۵۲ بیتی ذخیره کند و Postgres می‌تواند آن را به‌صورت متن ذخیره کند و هر دو Index یک‌جور رفتار می‌کنند.

برد این است که کلیدهایی که پیشوند مشترک دارند معمولاً نزدیک هم‌اند. این مستقیم از ساخت بیرون می‌آید. دو نقطه فقط وقتی پیشوند مشترک دارند که در هر سطحی که آن پیشوند پوشش می‌دهد در همان سلول افتاده باشند و هر کاراکتر مشترک اضافه سلول مشترک را کوچک می‌کند. اگر دو نقطه پنج کاراکتر اول را مشترک داشته باشند، در همان جعبه‌ی پنج‌کیلومتری هستند و اگر شش داشته باشند، به حدود یک کیلومتر کوچک می‌شود. آن محلی بودن قابل‌پیش‌بینی چیزی است که اجازه می‌دهد Query مجاورت را روی هر Index مرتبی، در هر پایگاه داده‌ای، اجرا کنید. WHERE geohash LIKE 'dr5ru%' Prefix Scan معمولی روی B-tree است، همان نوع اسکنی که روی هر ستون متنی اجرا می‌کنید.

همین ایده در دستورهای Geo در Redis ظاهر می‌شود. وقتی GEOADD را صدا می‌زنید، Redis عرض و طول را در Geohash به‌صورت عدد صحیح ۵۲ بیتی در هم می‌تند و آن را به‌عنوان Score در Sorted Set ذخیره می‌کند. Query نزدیک ZRANGEBYSCORE روی آن Scoreها می‌شود، که همان ایده‌ی Prefix Scan لحظه‌ای پیش با نحو متفاوت است.

یک نکته هست که باید بدانید چون مردم را گاز می‌گیرد. Geohash در مرز سلول‌ها حالت‌های لبه دارد. دو نقطه‌ی یک متر از هم می‌توانند در سلول‌های کاملاً متفاوت بیفتند و پیشوند کاملاً متفاوت بگیرند، اگر اتفاقاً دو طرف مرز باشند. مسافری را تصور کنید که درست روی لبه‌ی سلول dr5ru ایستاده. نزدیک‌ترین راننده ممکن است ده متر دورتر در سلول همسایه dr5rg باشد و Prefix Scan ساده روی dr5ru او را کاملاً از دست می‌دهد.

راه‌حل استاندارد ترفند 3x3 است. سلولی را که نقطه‌ی Query در آن فرود می‌آید محاسبه می‌کنید، بعد به هشت سلول همسایه می‌روید و هر نه تا را به‌عنوان واحد Query می‌کنید. حالا نمی‌توانید کسی را در فاصله‌ی یک سلول از خودتان از دست بدهید، هر چقدر به مرز نزدیک باشید. بعد نتایج را با فاصله‌ی دقیق Post-filter می‌کنید تا گوشه‌هایی را که از نظر فنی در پنجره‌ی Query شما هستند ولی واقعاً بیش از حد دورند حذف کنید. تقریباً هر Index کلید-رمزگذاری‌شده در Production نسخه‌ای از این رقص «حلقه را Query کن و Post-filter کن» را انجام می‌دهد.

S2

Geohash برای شهر واحد زیبا کار می‌کند، ولی در سراسر کره‌ی زمین شروع به آسیب زدن می‌کند، چون عرض و طول را مثل مستطیل تخت می‌گیرد و زمین تخت نیست. یک درجه طول جغرافیایی در خط استوا حدود ۱۱۱ کیلومتر است و به سمت قطب‌ها به صفر کوچک می‌شود، پس یک سلول Geohash نزدیک استوا مربع چاق است و در شمال تکه‌ی باریک. در مقیاس سیاره سلول‌هایی با مساحت تقریباً مساوی همه‌جا می‌خواهید و ترتیبی که فاصله روی کره را رعایت کند، نه روی مستطیل.

S2 گوگل پسرعموی کروی Geohash است. کره‌ی زمین را در مکعب می‌پیچد و روی شش وجه تصویر می‌کند، که اجازه می‌دهد سلول‌هایی ببرد که در هر جای زمین تقریباً هم‌اندازه می‌مانند، هرکدام با شناسه‌ی سلسله‌مراتبی ۶۴ بیتی که می‌توانید برای گرفتن سلول والد کوتاه کنید. چون S2 واقعاً کره را می‌فهمد، حالت‌هایی را مدیریت می‌کند که شبکه‌ی تخت خرابشان می‌کند، مثل چندضلعی که از Antimeridian (خط طول جغرافیایی ۱۸۰ درجه که مختصات از ۱۸۰+ به ۱۸۰- می‌پیچد) رد می‌شود. سیستم سلولی است که زیر Index مربوط به 2dsphere در MongoDB است.

H3

Uber، H3 را متن‌باز کرد و برای Dispatch و قیمت‌گذاری Surge اجرایش می‌کند. پیچ‌وتابش شش‌ضلعی به‌جای مربع است. سلول مربعی دو نوع همسایه دارد. چهار تا در دو طرف لبه‌هایش و چهار تا در دو طرف گوشه‌هایش، دورتر. آن نامتقارنی Queryهای «همه‌چیز در N حلقه‌ی من» و نقشه‌های حرارتی را آشفته می‌کند. شش‌ضلعی شش همسایه دارد، همه تقریباً با فاصله‌ی یکسان، که برای تحلیل مبتنی بر حلقه که Uber مدام اجرا می‌کند بسیار تمیزتر است. مثل Geohash و S2 هر سلول شناسه‌ی سلسله‌مراتبی ۶۴ بیتی است.

H3 در یک چیز که مهم است فرق دارد. Geohash و S2 سلول‌هایشان را در امتداد Space-filling Curve می‌چینند، پس اسکن بازه‌ای عددی یک همسایگی را یک‌جا جمع می‌کند. H3 نمی‌کند، پس شناسه‌های نزدیک الزاماً روی نقشه نزدیک نیستند. در عوض ریاضیات شبکه‌ی ارزان می‌دهد تا حلقه‌ی سلول‌های اطراف هر سلول را مستقیم محاسبه کنید و همان شناسه‌های دقیق را جستجو کنید.

الگوی Dispatch از آن بیرون می‌آید. هر راننده را به سلول H3، مثلاً ۲۰۰ متری، Snap کنید و وقتی مسافر اپ را باز می‌کند، سلولش را به‌علاوه‌ی حلقه‌ی اطراف بگیرید و اگر تور پهن‌تری لازم داشتید حلقه‌ی دیگری بیرون بگیرید. بعد WHERE h3_cell IN (list of cell IDs) را اجرا می‌کنید، جستجوی ساده روی Index عدد صحیح معمولی، و با فاصله‌ی دقیق Post-filter می‌کنید. همه نوشتن ارزان و تولید کاندیدای ارزان بدون هیچ افزونه‌ی فضایی است، که شکلی است که می‌خواهید وقتی به‌روزرسانی موقعیت مدام می‌رسد.

در مصاحبه، به‌ندرت لازم است H3 را در برابر S2 در برابر Geohash نام ببرید تا امتیاز بگیرید. چیزی که اثر می‌گذارد توضیح این است که چرا Index ساده روی عرض/طول جغرافیایی شکست می‌خورد، بعد سراغ گزینه‌ی خسته‌کننده‌ی Production رفتن و بلند توضیح دادن Trade-off. اگر کتابخانه‌ی مشخصی را می‌شناسید نامش را ببرید، ولی استدلال است که به مصاحبه‌کننده می‌گوید واقعاً مسئله را می‌فهمید.

کدام را استفاده کنیم؟

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

وقتی داده‌تان هندسی است درخت فضایی سفارشی: پر از چندضلعی، جاده، منطقه‌ی تحویل و سؤال‌های شمول یا تقاطع. نیاز دارید پایگاه داده اشکال را بفهمد و حاضرید برای گرفتن آن هزینه‌ی افزونه‌ی فضایی و نوشتن گران‌تر بپردازید. PostGIS با Index مربوط به GiST به سبک R-tree پیش‌فرض معمول است و R-tree نقطه، خط و چندضلعی را یکسان مدیریت می‌کند. نکته نوشتن است. متعادل کردن مستطیل‌ها کار واقعی است و واریانت BKD که Elasticsearch استفاده می‌کند اساساً Write-once است، پس هیچ‌کدام داده‌ی دائماً در حال تغییر را دوست ندارند.

وقتی داده‌تان بیشتر نقاطی است که مدام حرکت می‌کنند سلول‌های رمزگذاری‌شده: مثل راننده‌ها، کاربران، دستگاه‌ها یا موقعیت‌های زنده. اینجا بسیار بیشتر از ریاضیات چندضلعی به نوشتن ارزان و تولید سریع کاندیدا اهمیت می‌دهید و مقدار Geohash، S2 یا H3 روی Index معمولی دقیقاً همین را می‌دهد. راننده‌ی متحرک به‌روزرسانی یک عدد صحیح است، که به همین دلیل این رویکرد تا میلیون‌ها نوشتن در ثانیه مقیاس می‌گیرد. بهایی که می‌پردازید این است که بیشتر به نقاط محدودید و مرزهای سلول یعنی همیشه حلقه‌ی همسایه‌ها را Query می‌کنید، نه یک سلول دقیق.

باز هم، هر کدام را انتخاب کنید، Index فقط کاندیدا به شما می‌دهد. «همه‌ی ردیف‌ها را بررسی کن» را به تکه‌ی کوچکی از نقشه محدود می‌کند و شما هنوز Query را با فاصله‌ی دقیق یا محاسبه‌ی هندسی روی آن مشت تمام می‌کنید. وقتی این جا افتاد، کتابخانه‌ی مشخص به‌ندرت مهم است.

درخت فضایی برای اشکال. سلول‌های رمزگذاری‌شده برای نقاط متحرک. و همیشه، همیشه Post-filter کنید.