SP-GIST Index

شاخص SP-GIST در پایگاه داده SQL

شاخص SP-GIST (اختصار از Space Partitioning GIST) نوعی از شاخص GIST است که برای بهبود عملکرد جستجو در داده های فضایی در پایگاه های داده SQL استفاده می شود. شاخص های GIST به طور کلی برای جستجو در انواع داده های غیرساختاری مانند اشیاء JSON، آرایه ها، ماتریس ها و هندسه فضایی بهینه شده اند.

شاخص SP-GIST با استفاده از تکنیک پارتیشن بندی فضایی، داده های فضایی را به زیرمجموعه های کوچکتر تقسیم می کند. این امر به طور قابل توجهی عملکرد جستجو را برای پرس و جوهایی که به مناطق خاص فضای جستجو محدود می شوند، بهبود می بخشد.

ساختار شاخص SP-GIST

ساختار شاخص SP-GIST شبیه به شاخص GIST معمولی است، با این تفاوت که گره های برگ شامل اطلاعات فضایی اضافی هستند. این اطلاعات شامل حدود (bounds) برای زیرمجموعه فضایی مربوطه و اشاره گرها (pointers) به اشیاء فضایی در آن زیرمجموعه است.

هر گره در شاخص SP-GIST دارای ویژگی های زیر است:

• حداکثر ظرفیت (Order): حداکثر تعداد فرزندانی که یک گره می تواند داشته باشد.
• تابع فاصله (Distance function): تابعی که برای محاسبه فاصله بین اشیاء فضایی استفاده می شود.
• حدود (Bounds): برای زیرمجموعه فضایی مربوط به گره.
• اشاره گرها (Pointers): در گره های داخلی، به فرزندان گره اشاره می کنند. در گره های برگ، به اشیاء فضایی در آن زیرمجموعه اشاره می کنند.

نحوه عملکرد شاخص SP-GIST

برای درک نحوه عملکرد شاخص SP-GIST، به مثال زیر توجه کنید:

فرض کنید یک جدول به نام “Points” با ستون های “id” (کلید اصلی) و “location” (مکان به صورت GeoJSON) داریم. می خواهیم یک شاخص SP-GIST بر روی ستون “location” ایجاد کنیم.

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

2. درج: برای درج یک نقطه جدید، ابتدا باید موقعیت مناسب آن را در درخت پیدا کنیم. این کار به روشی مشابه جستجو انجام می شود. سپس، نقطه جدید را در گره برگ مناسب درج می کنیم. اگر گره برگ پر باشد، باید آن را تقسیم کنیم.

3. حذف: برای حذف یک نقطه، ابتدا باید آن را در درخت پیدا کنیم. سپس، نقطه را از گره برگ مربوطه حذف می کنیم. اگر حذف باعث خالی شدن گره برگ شود، ممکن است نیاز به ادغام گره ها با هم باشد.

مثال عملی

در اینجا مثالی از نحوه استفاده از شاخص SP-GIST برای جستجوی نقاط در یک منطقه خاص ارائه شده است:

فرض کنید درخت SP-GIST با حداکثر ظرفیت ۴ داشته باشیم و مقادیر آن به صورت زیر باشند:

[{"id": ۱, "location": {"type": "Point", "coordinates": [۴۰, ۵۰]}},
 {"id": ۲, "location": {"type": "Point", "coordinates": [۶۰, ۷۰]}},
 {"id": ۳, "location": {"type": "Point", "coordinates": [۸۰, ۹۰]}},
 {"id": ۴, "location": {"type": "Point", "coordinates": [۱۰۰, ۱۱۰]}}]

می خواهیم تمام نقاطی را که در یک مربع با گوشه های (۵۰، ۴۰) و (۷۰، ۶۰) قرار دارند پیدا کنیم.

1. جستجو را از ریشه شروع می کنیم. حدود زیرمجموعه فضایی مربوط به ریشه را با منطقه جستجو مقایسه می کنیم. حدود همپوشانی دارند، بنابراین به سمت فرزندی که زیرمجموعه فضایی آن با منطقه جستجو بیشتر همپوشانی دارد می رویم.
2. در حال حاضر در گره داخلی با مقادیر ۱ و ۲ هستیم. حدود زیرمجموعه های فضایی مربوط به این مقادیر را با منطقه جستجو مقایسه می کنیم. حدود مربوط به مقدار ۱ همپوشانی دارد، بنابراین به سمت فرزند مربوطه می رویم.
3. در حال حاضر در گره برگ با مقدار ۱ هستیم. اشاره گر را دنبال می کنیم تا به نقطه فضایی مربوطه برسیم و تابع فاصله را برای محاسبه فاصله بین آن و منطقه جستجو اعمال می کنیم. نقطه با شناسه ۱ در منطقه جستجو و در فاصله جستجو قرار دارد، بنابراین آن را به عنوان نتیجه جستجو برمی گردانیم.
4. مراحل ۲ و ۳ را برای گره داخلی دیگر (مقدار ۲) تکرار می کنیم. در نهایت، نقطه با شناسه ۲ را نیز به عنوان نتیجه جستجو برمی گردانیم.

نکات اضافی

• در عمل، درخت های SP-GIST می توانند گره هایی با صدها یا حتی هزاران مقدار داشته باشند.
• ارتفاع درخت SP-GIST (تعداد سطوح) با تعداد رکوردها در جدول و حداکثر ظرفیت گره ها تعیین می شود.
• الگوریتم های مختلفی برای درج، حذف و جستجو در درخت های SP-GIST وجود دارد.
• شاخص های SP-GIST به طور گسترده در سیستم های مدیریت پایگاه داده (DBMS) مانند PostgreSQL و PostGIS استفاده می شوند.