ایندکس مکانی ، راهکاری مؤثر برای جستجوی سریع هندسه عوارض

ایندکس مکانی چیست؟

   نقش ایندکس مکانی، پشتیبانی از تسریع جستجوی داده موردنظر در انبوه داده‌های مکانی است، به‌عبارت ساده‌تر هنگامی از ایندکس مکانی استفاده می‌کنیم که می‌خواهیم الگوریتم‌های جستجو عوارض مکانی ما را سریع‌تر پیدا کنند.

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

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

ایندکس مکانی
بدون ایندکس مکانی، جستجوی هر عارضه منجر به اسکن متوالی همه رکوردهای پایگاه داده می‌شود.

   تاکنون الگوریتم‌های مختلفی برای پشتیبانی از ایندکس مکانی تعریف شده‌اند. در ژئودیتابیس Esri، سازوکار بهینه‌کردن دسترسی به داده‌ها بر اساس ستون Spatial جدول Business می‌باشد. در اغلب ژئودیتابیس‌ها، یک سیستم شبکه (Grid Index) برای ایندکس مکانی به کار رفته و برخی دیگر نیز از ایندکس R-tree استفاده می‌کنند که ما نیز در ادامه به توضیح این دو روش خواهیم پرداخت.

ایندکس شبکه  (Grid)

   در برخی از  پایگاه داده‌ها (مانند Oracle و DB2) از ایندکس شبکه برای ایجاد ایندکس مکانی استفاده می‌شود. در این حالت، ایندکس مکانی با اعمال یک شبکه به داده‌های ستون مکانی ایجاد می‌شود. ایندکس شبکه مکانی، دوبعدی بوده و می‌تواند برای یک کلاس از عوارض یا یک لایه مکانی تعریف گردد.

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

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

Spatial_Index_1
شکل1. عارضه 101 در سطح اول شبکه ایندکس شده است. عارضه 102 نیز در سطح دوم شبکه ایندکس شده که فقط دارای 2 سلول است.

مستطیل دربرگیرنده عارضه سطحی 102، در سلول‌های 1 تا 8 مربوط به سطح اول قرار دارد. به دلیل اینکه تعداد سلول‌های دربرگیرنده این عارضه بیش از 4 است، برای عارضه، ایندکس سطح دوم تشکیل می‌شود که در آن سطح به دو سلول محدود می‌شود. عارضه 102 در سطح دوم ایندکس شده و دو سطر به جدول ایندکس مکانی اضافه می‌شود. حذف، اضافه یا بهنگام رسانی عارضه، منجر به بهنگام شدن ایندکس مکانی می‌شود.

ایندکس R-tree

   ایندکس کردن، سرعت جستجو را با سازمان‌دهی داده‌ها به شکل یک درخت جستجو افزایش می‌دهد. بدین ترتیب که درخت جستجو برای یافتن رکورد موردنظر، به‌سرعت قابل پیمایش خواهد بود. این سازوکار می‌تواند در زمان پردازش برای پرسش‌های پیچیده، به مقدار زیادی صرفه‌جویی ایجاد کند.

ساختار R-tree یک ساختار داده‌ی درختی است که برای جستجوی مکانی به کار می‌رود. این ایندکس توسط Antonin Guttman در سال 1984 به‌عنوان بسط B-tree برای داده‌های چندبعدی پیشنهاد شد. این ساختار را می‌توان برای ذخیره نقطه یا داده‌های حجمی به‌منظور انجام پرسش مکانی به کار برد. برای مثال، یک پرسش می‌تواند اشیاء درون یک محدوده یا نزدیک به یک نقطه در فضا را برگرداند. امکان حذف و اضافه شیء نیز وجود دارد.

شکل2 به‌سادگی ساختار ایندکس مکانی R-tree را که یک ساختار درختی بر اساس مستطیل است نشان می‌دهد. هر نود R-tree یک box را که توصیف‌کننده فضای اشغال‌شده به‌وسیله فرزندان آن نود هستند، ذخیره می‌کند. در پایین ساختار، نودهای برگ وجود دارند که اشیاء هندسی را در بر دارند.

ساختار درختی ایندکس R-tree
شکل2. ساختار درختی ایندکس R-tree بر اساس مستطیل

هر عارضه دلخواه را بدون توجه به شکل آن، می‌توان در یک مستطیل محصور کرد که به آنMBR یا کوچک‌ترین مستطیل دربرگیرنده می‌گویند. کلمه MBR مخففMinimum Bounding Rectangle  است که مترادف آن نیز MBB یا Minimum Bounding Box است. دو نمونه MBR عارضه در شکل 3 نشان داده شده است.

نمونه‌هایی از MBR عارضه
شکل3. نمونه‌هایی از MBR عارضه

نحوه کارکرد ایندکس R-tree به شرح زیر است:

  • پرسش مکانی، یک محدوده اختیاری جستجو را که آن نیز مستطیل است، تعریف می‌کند.
  • ایندکس R-tree به‌سرعت اسکن کرده و مستطیل‌های ایندکس که دارای هم‌پوشانی با مستطیل جستجو بوده را تشخیص می‌دهد.
  • و در پایان هر عارضه که درون محدوده جستجو قرار داشته باشد، شناسایی می‌شود.

بدین ترتیب می‌توان گفت ایندکس R-tree می‌تواند همان سوزن گم‌شده در انبار کاه را پیدا کند.

این مطالب را نیز مطالعه کنید :
محصولات ویژه فروشگاه :
اشتراک در
اطلاع از
1 دیدگاه
تازه‌ترین
قدیمی‌ترین بیشترین رأی
بازخورد (Feedback) های اینلاین
مشاهده همه دیدگاه ها
فهرست