ساختار داده جستجو

در علوم کامپیوتر، ساختار داده جستجو هر ساختار داده ای است که امکان بازیابی کارآمد موارد خاص را از مجموعه ای از موارد، مانند یک رکورد خاص از یک پایگاه داده را ایجاد می کند.

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

طبقه بندی

ساده ترین نوع کوئری این است که رکوردی را بیابید که دارای یک فیلد خاص (کلید) برابر با مقدار مشخص v باشد. سایر انواع رایج کوئری ها عبارتند از "یافتن آیتم با کوچکترین (یا بزرگترین) مقدار کلید"، "یافتن آیتم با بزرگترین مقدار کلید که از v بزرگتر نباشد "همه موارد با مقادیر کلیدی بین مرزهای مشخص شده v_min و v_max ".

در بعضی پایگاه‌های داده، مقادیر کلید ممکن است نقاطی در یک فضای چند بعدی باشند. به عنوان مثال، ممکن است کلید یک موقعیت جغرافیایی (عرض جغرافیایی و طول جغرافیایی) روی زمین باشد. در این صورت، انواع متداول کوئری ها عبارتند از "یافتن رکورد با یک کلید در نزدیکترین فاصله از نقطه داده شده  v"، یا "یافتن تمام مواردی که کلید آنها در فاصله‌ای مشخص از v قرار دارد"، یا "یافتن تمام موارد داخل منطقه مشخص R از فضای داده".

یک مورد خاص رایج برای حالت دوم، کوئری های همزمان در محدوده بر روی دو یا تعدادی بیشتر کلید ساده است، مانند "یافتن همه رکوردهای کارمندهایی با حقوق بین50,000 و 100,000 و استخدام شده بین سال های 1995 و 2007".

منابع

• Thomas H, Cormen; Charles E, Leiserson; Ronald L, Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0. LIST-DELETE runs in O(1) time, but if to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH.
• Sherrod, Allen (2007). Data Structures and Algorithms for Game Developers. Cengage Learning. ISBN 978-1-58450-663-8. The insertion of an item into an unordered array does not depend on anything other than placing the new item at the end of the list. This gives the insertion into an unordered array of O(1).
• Thomas H, Cormen; Charles E, Leiserson; Ronald L, Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 978-0-262-53091-0.
• "Algorithm - the time complexity of deletion in a unsorted array". Finding the element with a given value is linear. Since the array isn't sorted anyway, you can do the deletion itself in constant time. First swap the element you want to delete to the end of the array, then reduce the array size by one element